题目描述本题要求实现一个支持无限列表的惰性求值系统。列表可以通过两种方式定义常量列表name x0 x1 ... xi nextName表示列表的前i1个元素为给定的非负整数x0, x1, ..., xi后续元素由列表nextName继续提供。压缩列表name zip name1 name2表示将两个列表交替合并结果为[name1[0], name2[0], name1[1], name2[1], name1[2], name2[2], ...]。每个列表都是无限的且定义保证合法。名称由单个大写字母表示。输入包含多个数据集每个数据集有n个定义和m个查询。每个查询要求输出列表name中第s到第e个元素包含两端其中e - s 250但s和e可以非常大高达数亿。问题分析核心难点无限性无法预先生成整个列表。大索引直接递归计算list[k]会导致O(k)O(k)O(k)的时间复杂度无法承受。自引用定义可以形成循环如A 1 A或Z zip Z S需要特殊处理避免无限递归。混合依赖常量列表可能依赖zip\texttt{zip}zip列表反之亦然。解题思路1. 惰性求值与记忆化最直接的方法是使用递归函数get(name, pos)计算第pos个元素并用哈希表缓存已计算的结果。但如果不加优化对于A 1 A这样的定义计算A[1000000]仍然需要递归10610^6106层虽然缓存可以避免重复计算但首次计算依然耗时巨大。2. 周期性检测与优化观察发现某些列表具有周期性自引用常量列表A 1 2 A产生无限重复的[1, 2, 1, 2, ...]周期为2。相互递归常量列表A 1 B, B 2 A等价于A 1 2 A同样具有周期性。纯常量链如果从某个列表出发沿着常量依赖链最终形成一个环则该列表具有周期性周期长度为环上所有前缀长度之和。对于具有周期性的列表查询时可以直接取模pos % period从而将问题规模缩小到O(period)O(period)O(period)。3.zip\texttt{zip}zip列表的自引用处理对于Z zip Z S这样的定义需要推导其数学形式Z[0] Z[0]会产生无限递归但实际上下标0应取S[0]边界条件。对于k 1有Z[2k] Z[k]Z[2k1] S[k]这意味着计算Z[pos]时可以通过不断除以2将索引缩小直到pos变为0或奇数然后从S获取值。这个过程的时间复杂度为O(logpos)O(\log pos)O(logpos)。算法设计数据结构mapstring,vectorintp;// 常量列表的前缀数字mapstring,vectorstringnxt;// 后续关系常量存[next]zip存[zip1, zip2]mapstring,intmix;// 标记列表是否包含zip依赖即非常量链mapstring,intid;// 列表名到编号的映射intlen[N][N];// len[i][j]表示从列表i到j的累计前缀长度mappairstring,int,intmem;// 记忆化缓存步骤111标记mix\texttt{mix}mix状态通过DFS\texttt{DFS}DFS遍历依赖图标记每个列表是否包含zip\texttt{zip}zip依赖如果一个列表本身是zip\texttt{zip}zip类型则mix[name] true。如果列表的依赖项中存在mix为true的列表则当前列表也为true。这个标记用于区分“纯常量链”mix false和“混合链”mix true。只有纯常量链才具有周期性。步骤222计算纯常量链的周期长度对于每个mix为false的列表沿着常量依赖链nxt[name].back()行走累加经过的每个列表的前缀长度sum p[cur].size() len[i][j] sum其中i是起始列表的编号j是当前到达的列表编号。当遇到已经计算过的len[i][j]时停止此时len[i][i]就是列表i的周期长度。这个巧妙的设计同时处理了两种情况自引用A 1 A行走一步后cur变为Alen[i][i]被赋值为1。相互递归A 1 B, B 2 A行走两步后回到Alen[i][i]被赋值为123。步骤333查询计算solve(name, pos)函数检查记忆化缓存若已计算则直接返回。获取列表的周期长度len[x][x]如果大于0则pos % len缩小索引。根据列表类型计算若pos在前缀范围内直接返回前缀值。若列表是常量列表p[name]非空递归到nxt[name].back()索引减去前缀长度。若列表是zip\texttt{zip}zip列表p[name]为空根据pos的奇偶性递归到两个源列表索引除以2。时间复杂度预处理O(n⋅L)O(n \cdot L)O(n⋅L)其中LLL是常量链的长度nnn为列表数量。单次查询O(logmax(pos))O(\log \max(pos))O(logmax(pos))由于取模优化和二分递归实际常数很小。总体对于e−s250e-s 250e−s250且pospospos高达10810^8108的数据可以在毫秒级完成。代码实现// Keeps Going and Going// UVa ID: 606// Verdict: Accepted// Submission Date: 2026-05-23// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintN210;mapstring,vectorintp;// 前缀数字mapstring,vectorstringnxt;// 后续列表mapstring,intmix,id;// mix标记是否含zip依赖id为编号intlen[N][N];// 周期长度矩阵mappairstring,int,intmem;// 记忆化缓存// DFS标记是否包含zip依赖intdfs(conststrings){if(mix.count(s))returnmix[s];mix[s](nxt[s].size()2);// zip列表有2个后续for(conststringt:nxt[s])mix[s]|dfs(t);returnmix[s];}// 求解第pos个元素intsolve(conststrings,intpos){autokeymake_pair(s,pos);if(mem.count(key))returnmem[key];intxid[s],llen[x][x];if(l0)pos%l;// 周期优化intres;if(pos(int)p[s].size()){resp[s][pos];// 命中前缀}elseif(p[s].empty()){// zip列表ressolve(nxt[s][pos1],pos/2);}else{// 常量列表ressolve(nxt[s].back(),pos-p[s].size());}mem[key]res;returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0);intT;cinT;while(T--){intn,q;cinnq;p.clear();nxt.clear();mix.clear();id.clear();mem.clear();memset(len,0,sizeoflen);vectorstringnames;// 读取定义for(inti0;in;i){string name,eq;cinnameeq;names.push_back(name);id[name]i;string line;getline(cin,line);stringstreamss(line);string token;vectorstringtok;while(sstoken)tok.push_back(token);if(tok[0]zip){nxt[name]{tok[1],tok[2]};}else{nxt[name].push_back(tok.back());tok.pop_back();for(conststringt:tok)p[name].push_back(stoi(t));}}// 标记混合状态for(conststringname:names)dfs(name);// 计算周期长度for(inti0;i(int)names.size();i){string curnames[i];if(mix[cur])continue;intsum0;while(1){string nxtNamenxt[cur].back();intjid[nxtName];sump[cur].size();if(len[i][j])break;len[i][j]sum;curnxtName;}}// 处理查询while(q--){string name;intl,r;cinnamelr;for(intil;ir;i)coutsolve(name,i) \n[ir];}if(T)cout\n;}return0;}总结本题的核心在于周期性检测与数学归纳通过DFS\texttt{DFS}DFS标记mix\texttt{mix}mix状态区分纯常量链与混合链。对于纯常量链沿依赖链行走并累加前缀长度得到周期长度。查询时先取模缩小索引再递归计算。对于自引用zip\texttt{zip}zip利用奇偶性将索引对数级缩小。这种设计既保证了正确性又能在O(logindex)O(\log \text{index})O(logindex)时间内处理任意大的索引。
UVa 606 Keeps Going and Going
发布时间：2026/5/24 13:43:30
题目描述本题要求实现一个支持无限列表的惰性求值系统。列表可以通过两种方式定义常量列表name x0 x1 ... xi nextName表示列表的前i1个元素为给定的非负整数x0, x1, ..., xi后续元素由列表nextName继续提供。压缩列表name zip name1 name2表示将两个列表交替合并结果为[name1[0], name2[0], name1[1], name2[1], name1[2], name2[2], ...]。每个列表都是无限的且定义保证合法。名称由单个大写字母表示。输入包含多个数据集每个数据集有n个定义和m个查询。每个查询要求输出列表name中第s到第e个元素包含两端其中e - s 250但s和e可以非常大高达数亿。问题分析核心难点无限性无法预先生成整个列表。大索引直接递归计算list[k]会导致O(k)O(k)O(k)的时间复杂度无法承受。自引用定义可以形成循环如A 1 A或Z zip Z S需要特殊处理避免无限递归。混合依赖常量列表可能依赖zip\texttt{zip}zip列表反之亦然。解题思路1. 惰性求值与记忆化最直接的方法是使用递归函数get(name, pos)计算第pos个元素并用哈希表缓存已计算的结果。但如果不加优化对于A 1 A这样的定义计算A[1000000]仍然需要递归10610^6106层虽然缓存可以避免重复计算但首次计算依然耗时巨大。2. 周期性检测与优化观察发现某些列表具有周期性自引用常量列表A 1 2 A产生无限重复的[1, 2, 1, 2, ...]周期为2。相互递归常量列表A 1 B, B 2 A等价于A 1 2 A同样具有周期性。纯常量链如果从某个列表出发沿着常量依赖链最终形成一个环则该列表具有周期性周期长度为环上所有前缀长度之和。对于具有周期性的列表查询时可以直接取模pos % period从而将问题规模缩小到O(period)O(period)O(period)。3.zip\texttt{zip}zip列表的自引用处理对于Z zip Z S这样的定义需要推导其数学形式Z[0] Z[0]会产生无限递归但实际上下标0应取S[0]边界条件。对于k 1有Z[2k] Z[k]Z[2k1] S[k]这意味着计算Z[pos]时可以通过不断除以2将索引缩小直到pos变为0或奇数然后从S获取值。这个过程的时间复杂度为O(logpos)O(\log pos)O(logpos)。算法设计数据结构mapstring,vectorintp;// 常量列表的前缀数字mapstring,vectorstringnxt;// 后续关系常量存[next]zip存[zip1, zip2]mapstring,intmix;// 标记列表是否包含zip依赖即非常量链mapstring,intid;// 列表名到编号的映射intlen[N][N];// len[i][j]表示从列表i到j的累计前缀长度mappairstring,int,intmem;// 记忆化缓存步骤111标记mix\texttt{mix}mix状态通过DFS\texttt{DFS}DFS遍历依赖图标记每个列表是否包含zip\texttt{zip}zip依赖如果一个列表本身是zip\texttt{zip}zip类型则mix[name] true。如果列表的依赖项中存在mix为true的列表则当前列表也为true。这个标记用于区分“纯常量链”mix false和“混合链”mix true。只有纯常量链才具有周期性。步骤222计算纯常量链的周期长度对于每个mix为false的列表沿着常量依赖链nxt[name].back()行走累加经过的每个列表的前缀长度sum p[cur].size() len[i][j] sum其中i是起始列表的编号j是当前到达的列表编号。当遇到已经计算过的len[i][j]时停止此时len[i][i]就是列表i的周期长度。这个巧妙的设计同时处理了两种情况自引用A 1 A行走一步后cur变为Alen[i][i]被赋值为1。相互递归A 1 B, B 2 A行走两步后回到Alen[i][i]被赋值为123。步骤333查询计算solve(name, pos)函数检查记忆化缓存若已计算则直接返回。获取列表的周期长度len[x][x]如果大于0则pos % len缩小索引。根据列表类型计算若pos在前缀范围内直接返回前缀值。若列表是常量列表p[name]非空递归到nxt[name].back()索引减去前缀长度。若列表是zip\texttt{zip}zip列表p[name]为空根据pos的奇偶性递归到两个源列表索引除以2。时间复杂度预处理O(n⋅L)O(n \cdot L)O(n⋅L)其中LLL是常量链的长度nnn为列表数量。单次查询O(logmax(pos))O(\log \max(pos))O(logmax(pos))由于取模优化和二分递归实际常数很小。总体对于e−s250e-s 250e−s250且pospospos高达10810^8108的数据可以在毫秒级完成。代码实现// Keeps Going and Going// UVa ID: 606// Verdict: Accepted// Submission Date: 2026-05-23// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintN210;mapstring,vectorintp;// 前缀数字mapstring,vectorstringnxt;// 后续列表mapstring,intmix,id;// mix标记是否含zip依赖id为编号intlen[N][N];// 周期长度矩阵mappairstring,int,intmem;// 记忆化缓存// DFS标记是否包含zip依赖intdfs(conststrings){if(mix.count(s))returnmix[s];mix[s](nxt[s].size()2);// zip列表有2个后续for(conststringt:nxt[s])mix[s]|dfs(t);returnmix[s];}// 求解第pos个元素intsolve(conststrings,intpos){autokeymake_pair(s,pos);if(mem.count(key))returnmem[key];intxid[s],llen[x][x];if(l0)pos%l;// 周期优化intres;if(pos(int)p[s].size()){resp[s][pos];// 命中前缀}elseif(p[s].empty()){// zip列表ressolve(nxt[s][pos1],pos/2);}else{// 常量列表ressolve(nxt[s].back(),pos-p[s].size());}mem[key]res;returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0);intT;cinT;while(T--){intn,q;cinnq;p.clear();nxt.clear();mix.clear();id.clear();mem.clear();memset(len,0,sizeoflen);vectorstringnames;// 读取定义for(inti0;in;i){string name,eq;cinnameeq;names.push_back(name);id[name]i;string line;getline(cin,line);stringstreamss(line);string token;vectorstringtok;while(sstoken)tok.push_back(token);if(tok[0]zip){nxt[name]{tok[1],tok[2]};}else{nxt[name].push_back(tok.back());tok.pop_back();for(conststringt:tok)p[name].push_back(stoi(t));}}// 标记混合状态for(conststringname:names)dfs(name);// 计算周期长度for(inti0;i(int)names.size();i){string curnames[i];if(mix[cur])continue;intsum0;while(1){string nxtNamenxt[cur].back();intjid[nxtName];sump[cur].size();if(len[i][j])break;len[i][j]sum;curnxtName;}}// 处理查询while(q--){string name;intl,r;cinnamelr;for(intil;ir;i)coutsolve(name,i) \n[ir];}if(T)cout\n;}return0;}总结本题的核心在于周期性检测与数学归纳通过DFS\texttt{DFS}DFS标记mix\texttt{mix}mix状态区分纯常量链与混合链。对于纯常量链沿依赖链行走并累加前缀长度得到周期长度。查询时先取模缩小索引再递归计算。对于自引用zip\texttt{zip}zip利用奇偶性将索引对数级缩小。这种设计既保证了正确性又能在O(logindex)O(\log \text{index})O(logindex)时间内处理任意大的索引。
