UVa 773 The JustaPox Language

题目描述JustaPox\texttt{JustaPox}JustaPox语言只处理整数数组声明数组有两种方式显式指定大小A is [1]表示A是长度为111的数组其值可以是任意一个长度为111的整数序列。通过包含已声明的数组C is A B表示C由数组A和B依次拼接而成其总长度为两者长度之和。若同一个数组在声明中出现多次如D is A A则对应位置的两个子序列必须完全相等。赋值语句形如S i1 i2 ... in.其中S必须是一个已声明的数组右侧整数序列的长度必须等于S的总长度并且所有由同一引用数组产生的子段必须对应位置相等。给定一组数组声明和一组赋值语句要求输出所有不一致的赋值语句按输入原样。输入格式输入由数组声明和赋值语句组成两者交替出现无明确结束标记输入文件读到末尾为止。每个声明或赋值以句点.结束。数组声明格式id is d1 d2 ... dm.其中id是标识符d_i可以是[k]kkk为正整数或之前声明的数组标识符。赋值格式id i1 i2 ... in.其中id是已声明的数组i_j为正整数。任意位置可包含空格和空行。输出格式输出所有不一致的赋值语句每条语句原样输出顺序与输入中出现顺序相同。样例输入A is [1]. B is [3]. C is A B. SEQ is [1] A [4] B A. A 10. B 1 2 3. C 1 1 2 3 4. SEQ 1 10 1 1 1 1 2 2 2 10. SEQ 1 10 1 1 1 1 1 2 3 9.输出C 1 1 2 3 4. SEQ 1 10 1 1 1 1 1 2 3 9.题目分析本题的核心是验证赋值语句是否满足数组声明中隐含的结构约束。每个数组声明定义了一棵展开树基本元素是固定长度的基本块复合元素是对已声明数组的引用。赋值右侧提供了一串整数需要将其按照声明定义的方式划分成若干子段并检查所有同名引用对应的子段是否完全一致。直接思路是对每个数组记录其展开后的基本块序列每个基本块标记为长度或引用数组编号然后对每个赋值递归检查每个引用子段是否满足对应数组的约束并收集所有引用的起始位置和长度最后两两比较同名引用段的值。本题的难点在于解析输入需要保留原始语句用于输出以及递归检查时的段比较。由于数组声明可能嵌套但每个数组只定义一次因此可以构建一个有向无环图引用不形成环因为引用必须指向已声明的数组。每个数组的总长度可以在声明时通过累加其子项的长度得到。解题思路数据结构设计为每个数组存储以下信息name数组名称字符串。items一个向量每个元素表示一个组成部分类型为BASIC固定长度存储长度值。REF引用另一个数组存储被引用数组的索引在全局数组列表中的编号。totalLen该数组展开后的总长度。同时维护一个哈希映射nameToIdx将数组名称映射到其索引。解析输入将整个输入文件读入一个字符串inputStr并记录当前扫描位置pos。顺序扫描跳过空白字符。读取一个标识符id。跳过空白读取下一个令牌若为is则开始解析数组声明。循环读取令牌若为.则结束声明。若为[则读取括号内的正整数k然后读取]构造一个BASIC项。否则该令牌应是一个已有数组名在nameToIdx中查找其索引构造一个REF项。声明结束后计算总长度并存入数组列表。若为则开始解析赋值语句。循环读取整数令牌直到遇到.将整数存入vals向量。然后查找数组索引调用一致性检查函数若不一致则记录该赋值语句的原始字符串从本次赋值开始位置startPos到当前句点后的位置。一致性检查定义递归函数checkArray(idx, vals, start)其中idx是当前数组的索引vals是整数序列start是该数组在vals中的起始位置。该函数需要遍历当前数组的items若为BASIC则直接跳过value个整数。若为REF递归调用checkArray(refIdx, vals, cur)检查该引用子段同时记录一个三元组(refIdx, cur, len)到列表refs中len为被引用数组的总长度。遍历结束后对refs中所有具有相同refIdx的项检查其对应的子段是否完全相等按位置比较整数。若存在不等则返回false。最后在主函数中先比较总长度是否一致再调用checkArray即可。时间复杂度设数组总数为NNN每个数组的items总数之和为MMM所有赋值语句的整数总数之和为VVV。解析和构建O(M输入字符数)O(M \text{输入字符数})O(M输入字符数)。检查每条赋值对每个数组的items递归一次且每个元素最多遍历一次因此检查单个赋值的复杂度为O(O(O(该数组展开后的基本块数)))而基本块数等于items中BASIC个数加上被引用数组的总基本块数分摊后每个数组的基本块总数即其展开长度。但由于每次检查是独立的总复杂度为O(VO(VO(V所有赋值涉及的数组总复杂度)))。若最坏情况下每个赋值都涉及同一个大数组则总复杂度为O(O(O(赋值条数×\times×数组大小)))。但题目未给出明确上限实际输入规模较小此递归方法可行。代码实现// The JustaPox Language// UVa ID: 773// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.070s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structItem{enumType{BASIC,REF}type;intvalue;// BASIC: 长度; REF: 数组索引};structArrayInfo{string name;vectorItemitems;inttotalLen;};vectorArrayInfoarrays;unordered_mapstring,intnameToIdx;string inputStr;size_t pos0;voidskipSpaces(){while(posinputStr.size()isspace(inputStr[pos]))pos;}stringreadToken(){skipSpaces();if(posinputStr.size())return;charcinputStr[pos];if(isalpha(c)||c_){size_t startpos;while(posinputStr.size()(isalnum(inputStr[pos])||inputStr[pos]_))pos;returninputStr.substr(start,pos-start);}elseif(isdigit(c)){size_t startpos;while(posinputStr.size()isdigit(inputStr[pos]))pos;returninputStr.substr(start,pos-start);}else{returnstring(1,inputStr[pos]);}}boolcheckArray(intidx,constvectorintvals,intstart){intcurstart;vectortupleint,int,intrefs;// (refIdx, startPos, len)for(constautoitem:arrays[idx].items){if(item.typeItem::BASIC){curitem.value;}else{intrefIdxitem.value;intlenarrays[refIdx].totalLen;if(!checkArray(refIdx,vals,cur))returnfalse;refs.push_back(make_tuple(refIdx,cur,len));curlen;}}for(size_t i0;irefs.size();i)for(size_t ji1;jrefs.size();j)if(get0(refs[i])get0(refs[j])){intlenget2(refs[i]);ints1get1(refs[i]);ints2get1(refs[j]);for(intk0;klen;k)if(vals[s1k]!vals[s2k])returnfalse;}returntrue;}boolisConsistent(intidx,constvectorintvals){if((int)vals.size()!arrays[idx].totalLen)returnfalse;returncheckArray(idx,vals,0);}intmain(){string line;while(getline(cin,line)){inputStrline;inputStr\n;}vectorstringinconsistent;while(posinputStr.size()){skipSpaces();if(posinputStr.size())break;intstartPospos;string idreadToken();if(id.empty())break;skipSpaces();string nextreadToken();if(nextis){ArrayInfo info;info.nameid;while(true){skipSpaces();if(posinputStr.size())break;string tokreadToken();if(tok.)break;elseif(tok[){skipSpaces();string numStrreadToken();intkstoi(numStr);skipSpaces();string closereadToken();// ]Item it;it.typeItem::BASIC;it.valuek;info.items.push_back(it);}else{autoitMapnameToIdx.find(tok);if(itMap!nameToIdx.end()){Item it;it.typeItem::REF;it.valueitMap-second;info.items.push_back(it);}}}inttotal0;for(constautoitem:info.items)if(item.typeItem::BASIC)totalitem.value;elsetotalarrays[item.value].totalLen;info.totalLentotal;intidxarrays.size();arrays.push_back(info);nameToIdx[id]idx;}elseif(next){vectorintvals;while(true){skipSpaces();if(posinputStr.size())break;string tokreadToken();if(tok.)break;elsevals.push_back(stoi(tok));}autoitMapnameToIdx.find(id);if(itMap!nameToIdx.end()){intidxitMap-second;if(!isConsistent(idx,vals)){string originalinputStr.substr(startPos,pos-startPos);inconsistent.push_back(original);}}}elsebreak;}for(conststrings:inconsistent)couts\n;return0;}总结本题的难点在于对数组声明的递归解析和赋值时对重复引用的值比较。通过将数组声明建模为items列表其中基本元素和引用元素分开存储我们可以方便地递归验证赋值。关键技巧是使用递归函数同时完成子段约束检查和收集引用段信息避免两次遍历。利用全局数组列表和哈希映射快速查找被引用数组。原始语句的保留通过记录起始位置和结束位置实现保证了输出格式与输入一致。该解法结构清晰易于扩展适合处理嵌套声明和多种赋值场景。