UVa 394 Mapmaker

题目描述Cybersoft\texttt{Cybersoft}Cybersoft计算机公司编程语言领域的领导者雇佣你来为一门名为A--的新编程语言工作。你的任务是处理该语言的数组映射任务。你需要接收数组引用如x[5,6]并将其映射到实际的物理地址。物理地址的计算公式为addressC0C1i1C2i2⋯CDiD \text{address} C_0 C_1 i_1 C_2 i_2 \dots C_D i_DaddressC0​C1​i1​C2​i2​⋯CD​iD​其中常数C0…CDC_0 \dots C_DC0​…CD​按以下规则计算BBB数组的基地址DDD数组的维数LdL_dLd​第ddd维的下界UdU_dUd​第ddd维的上界CDC_DCD​数组元素大小字节CdCd1×(Ud1−Ld11)C_d C_{d1} \times (U_{d1} - L_{d1} 1)Cd​Cd1​×(Ud1​−Ld1​1)对于1≤dD1 \leq d D1≤dDC0B−C1L1−C2L2−⋯−CDLDC_0 B - C_1 L_1 - C_2 L_2 - \dots - C_D L_DC0​B−C1​L1​−C2​L2​−⋯−CD​LD​输入格式第一行包含两个正整数NNN数组定义的数量和RRR数组引用数量。接下来NNN行每行定义一个数组数组名最多101010个字符基地址元素大小字节维数DDD1≤D≤101 \leq D \leq 101≤D≤10随后DDD对整数每维的下界和上界接下来RRR行每行指定一个数组引用数组名各维度的索引值i1,i2,…,iDi_1, i_2, \dots, i_Di1​,i2​,…,iD​输出格式对于每个数组引用输出一行名称[索引1, 索引2, ...] 物理地址样例输入3 4 ONE 1500 2 2 0 3 1 5 TWO 2000 4 3 1 4 0 5 5 10 THREE 3000 1 1 1 9 ONE 2 4 THREE 7 TWO 2 0 6 TWO 3 3 9样例输出ONE[2, 4] 1526 THREE[7] 3006 TWO[2, 0, 6] 2148 TWO[3, 3, 9] 2376题目分析问题的本质这是一个数组地址计算问题。根据公式计算多维数组元素在内存中的物理地址。公式推导对于DDD维数组地址公式为addressB∑d1D((id−Ld)×∏kd1D(Uk−Lk1))×bytes \text{address} B \sum_{d1}^{D} \left( (i_d - L_d) \times \prod_{kd1}^{D} (U_k - L_k 1) \right) \times \text{bytes}addressBd1∑D​((id​−Ld​)×kd1∏D​(Uk​−Lk​1))×bytes等价地计算从最低维到最高维的累积跨度偏移量 ∑(id−Ld)×strided\sum (i_d - L_d) \times \textit{stride}_d∑(id​−Ld​)×strided​最终地址 基地址 偏移量 × 元素大小算法步骤存储每个数组的基地址、元素大小、各维边界对于每个引用从最高维到最低维计算累积跨度计算偏移量计算最终地址参考代码// Mapmaker// UVa ID: 394// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structarrayInfo{intbase,bytes,dimensions;vectorpairint,intbounds;// 各维的下界和上界};intmain(intargc,char*argv[]){intN,R;while(cinNR){vectorarrayInfoarrays;mapstring,intindexer;// 数组名到索引的映射// 读取数组定义for(inti1;iN;i){string name;intbase,bytes,dim;cinnamebasebytesdim;arrayInfo info;info.basebase;info.bytesbytes;info.dimensionsdim;for(intj1;jdim;j){intlow,up;cinlowup;info.bounds.push_back({low,up});}indexer[name]arrays.size();arrays.push_back(info);}// 处理数组引用for(inti1;iR;i){string name;cinname;intidxindexer[name];intdimarrays[idx].dimensions;vectorintindices(dim);// 输出数组引用coutname[;for(intj0;jdim;j){if(j0)cout, ;cinindices[j];coutindices[j];}cout] ;// 计算物理地址intaddress0,length1;for(intjdim-1;j0;j--){address(indices[j]-arrays[idx].bounds[j].first)*length;length*(arrays[idx].bounds[j].second-arrays[idx].bounds[j].first1);}addressarrays[idx].baseaddress*arrays[idx].bytes;coutaddressendl;}}return0;}