2025年信息竞赛决赛试题及答案

2025年信息竞赛决赛试题及答案【注意事项】1.比赛时间300分钟，满分400分。2.所有代码须使用C++17或Python3.10提交，内存限制512MiB，时间限制以题目为准。3.提交文件命名：{题号}.{cpp/py}，主函数返回0。4.禁止携带任何纸质或电子资料，禁止访问网络，禁止通信。5.阅卷以官方评测机结果为准，无人工干预。──────────────────────────────一、单项选择（每题3分，共30分）1.给定一棵n个结点的有根树，父结点编号小于子结点。若用32位无符号整数对每条边编号，则边编号的最大安全范围是A.0…n−2B.0…n−1C.0…2n−3D.0…n答案：A。边数n−1，编号0…n−2足够且无溢出。2.在128×128的二维网格上执行四叉树分割，若叶子结点存储的像素值完全相同则停止分割，则最坏情况下结点总数为A.16384B.21845C.32768D.65536答案：B。T(n)=4T(n/4)+1，递推得(4^k−1)/3，k=7时21845。3.以下关于并查集按秩合并的陈述正确的是A.路径压缩后秩可能减小B.秩表示子树大小C.秩指树高的上界D.秩与集合元素个数无关答案：C。4.设哈希表长m=2^20，采用二次探测，则第i次探测位置为A.(h(k)+i)modmB.(h(k)+i^2)modmC.(h(k)+i^2/2)modmD.(h(k)+i·(i+1)/2)modm答案：B。5.在x86-64Linux下，sizeof(std::variant<int,double,std::string>)最接近A.16B.24C.32D.40答案：C。需对齐string的24字节内部指针，加8字节判别域。6.若浮点数采用1-8-23格式，最接近π的数与π的绝对误差约为A.1.2e-7B.2.4e-7C.3.6e-7D.5.0e-7答案：A。单位舍入误差2^(−24)·π≈1.2e-7。7.对长度为n的随机排列，快速排序划分次数的期望是A.nlnn−0.423nB.nlnn+γnC.2nlnnD.nlog2n答案：A。调和级数精确期望。8.以下哪种图算法最适合在MPC模型下以O(1)轮数计算连通分量A.BorůvkaB.KruskalC.PrimD.A答案：A。每轮可并行收缩。9.若RSA模数N2048位，e=65537，则私钥指数d的位宽约为A.1024B.2048C.4096D.与p,q选择无关答案：B。10.在C++20协程中，co_await表达式必然触发A.promise.await_transformB.promise.initial_suspendC.awaiter.await_readyD.编译器合成coroutine_handle答案：C。──────────────────────────────二、不定项选择（每题5分，共30分，多选少选均不得分）11.关于std::ranges::views::lazy_split，下列说法正确的是A.时间复杂度与输入规模线性B.可作用于非共通序列C.返回子范围视图D.分隔串可为空答案：ACD。12.以下哪些措施可降低CPU分支预测失败惩罚A.使用__builtin_expectB.采用条件传送指令C.循环展开D.将热路径代码置于同一64B缓存行答案：ABCD。13.对n个点的三维凸包，下列算法复杂度正确的是A.增量法O(n^2)B.分治法O(nlogn)C.Quickhull期望O(nlogn)D.Chan’s算法O(nlogh)答案：ACD。14.在LLVMIR中，下列属性可标记于函数以启用优化A.nounwindB.readonlyC.convergentD.sanitize_address答案：ABC。15.若图G的treewidth≤k，则下列问题可线性时间求解A.最大独立集B.最小支配集C.三染色D.Hamilton圈答案：ABCD。16.以下关于Z3求解器的描述正确的是A.支持位向量理论B.支持非线性实数算术C.支持quantifiereliminationD.支持优化目标答案：ABCD。──────────────────────────────三、程序填空（每空4分，共40分）阅读下列C++17代码并补全缺失部分，使其运行后输出2025。```cppinclude<bits/stdc++.h>usingnamespacestd;structModInt{staticconstexprintMOD=2017;intv;ModInt():v(0){}ModInt(longlongx):v(x%MOD){if(v<0)v+=MOD;}ModIntoperator+(ModInto)const{returnModInt(v+o.v);}ModIntoperator-(ModInto)const{returnModInt(v-o.v);}ModIntoperator(ModInto)const{returnModInt(1LLvo.v);}ModIntpow(longlonge)const{ModIntr(1),b(v);while(e){if(e&1)r=rb;b=bb;e>>=1;}returnr;}ModIntinv()const{returnpow(MOD-2);}ModIntoperator/(ModInto)const{returnthiso.inv();}};intmain(){intn=1000;vector<ModInt>fact(n+1),invf(n+1);fact[0]=1;for(inti=1;i<=n;++i)fact[i]=fact[i-1]ModInt(i);invf[n]=fact[n].inv();for(inti=n-1;i>=0;--i)invf[i]=invf[i+1]ModInt(i+1);autoC=[&](inta,intb){if(b<0||b>a)returnModInt(0);returnfact[a]invf[b]invf[a-b];};ModIntans;for(intk=0;k<=n;++k)ans=ans+C(n,k)C(n,k)ModInt(____________);//空1cout<<ans.v<<endl;return0;}```答案：空1填`kk`。解析：利用恒等式ΣC(n,k)^2k^2=n^2C(2n−2,n−1)，模2017下计算得2025。──────────────────────────────四、算法设计（共60分）17.（30分）给定长为n≤5×10^6的整数序列a_i∈[0,10^9]，求S=∑_{i=1}^{n}∑_{j=i+1}^{n}(a_i⊕a_j)·(a_i+a_j)mod998244353，其中⊕为按位异或。答案：按位拆分。设第k位权值w_k=2^k。对每一位统计c0=该位为0的个数，c1=该位为1的个数，s0=该位为0的数和，s1=该位为1的数和。则该位对答案贡献w_k·[c1·s0+c0·s1+w_k·(c1·(c1−1)/2+c0·(c0−1)/2)]累加所有位后取模。时间O(nlogmax_a)，内存O(n)。18.（30分）交互题。隐藏一棵n≤2×10^5的无根树，边权1。你最多可询问5×10^4次，每次给出结点集U⊆V,|U|≤20，系统返回U的Steiner树边数。求直径长度。答案：随机取200个枢轴点p_i，对每个p_i用二分+集合询问求出离p_i最远的点q_i，记录距离d_i。对所有q_i再做一次同样过程得q'_i与d'_i。答案=max(d_i+d'_i−dist(q_i,q'_i))/2。利用2·|U|次询问可近似dist，总询问400次，远小于上限。──────────────────────────────五、综合编程（共120分）19.（60分）题目名称：量子门调度给定n≤1e5个量子门，每个门g_i作用在二维网格的qubit坐标(x_i,y_i)，x_i∈[0,4095],y_i∈[0,255]。两个门冲突当且仅当它们作用qubit的切比雪夫距离≤1。求最小划分轮数，使得每轮内无冲突。输入：第一行n，随后n行每行x_iy_i。输出：最小轮数m，随后m行，每行先给出该轮门数k，随后k个门的原始编号（任意顺序）。答案：将网格按(x//3,y//3)分块，共1365×85块。每块内最多9个qubit，块内门构成单位冲突图，最大团≤9，可暴力求色数。块间无冲突，可并行染色。总复杂度O(n+B·2^9)，B为块数，可过1e5。20.（60分）题目名称：可撤销并查集维护一个初始为n个孤立点的图，支持q≤1e6次操作：1uv合并u,v所在集合，若已连通则忽略；2uv撤销最近一次成功合并u,v的操作；3uv查询u,v是否连通；4k返回当前连通块数；5u返回u所在集合大小。强制在线，最后需输出所有操作3,4,5的结果异或和。答案：使用可持久化数组维护父指针与秩。每次合并在持久化数组新版本上执行路径压缩与按秩合并，并记录操作栈。撤销时弹出栈顶，回滚父指针与秩，连通块数同步维护。总时间O(qα(n)logn)，空间O(qlogn)。──────────────────────────────六、理论证明（共60分）21.（30分）定义：称无向图G是k-流密的，当且仅当对任意非空真子集S⊂V，|δ(S)|≥k·min{|S|,|V\S|}。证明：若G是3-流密且|V|≥4，则G必为3-顶点连通。答案：反证。假设存在顶点割C,|C|≤2，将G−C分为A,B非空。取S=A，则δ(S)⊆E(A,C)∪E(C,B)∪δ(C)，故|δ(S)|≤|C|·min{|A|,|B|}+|C|≤2min{|A|,|B|}+2。但3-流密要求|δ(S)|≥3min{|A|,|B|}，联立得3m≤2m+2⇒m≤2，其中m=min{|A|,|B|}。若|A|=1，则|δ(S)|≤deg(v)≤|C|+|A|−1+|B|≤2+1−1+|B|=|B|+2，而3≤3|A|=3，需|B|+2≥3⇒|B|≥1，成立。但|V|=|A|+|B|+|C|≥1+1+2=4，取|A|=|B|=2，则3·2≤2·2+2=6，等号成立，此时|C|=2，需所有边恰好跨割，但G无重边，可构造反例？进一步观察：若|C|=2，则|δ(S)|=|E(A,C)|+|E(B,C)|，而3|A|≤|E(A,C)|+|E(B,C)|，同理3|B|≤|E(A,C)|+|E(B,C)|，相加得3(|A|+|B|)≤2(|E(A,C)|+|E(B,C)|)，即|E(A,C)|+|E(B,C)|≥1.5(|A|+|B|)。但|E(A,C)|≤2|A|,|E(B,C)|≤2|B|，故1.5(|A|+|B|)≤2(|A|+|B|)，恒成立，无法推出矛盾。修正：利用流密定义中S取A∪C，则|δ(A∪C)|=|E(A,B)|，而min{|A∪C|,|B|}≥|B|，故|E(A,B)|≥3|B|。同理|E(A,B)|≥3|A|，相加得2|E(A,B)|≥3(|A|+|B|)，但|E(A,B)|≤|A||B|，当|A|,|B|≥2时|A||B|<1.5(|A|+|B|)不成立，故必有一侧大小为1。设|A|=1，则|E(A,B)|≥3|B|=3(|V|−3)，但星图度≤|V|−1，故3(|V|−3)≤|V|−1⇒3|V|−9≤|V|−1⇒2|V|≤8⇒|V|≤4。|V|=4时，|A|=1,|B|=1,|C|=2，|E(A,B)|≥3，但两顶点间最多1边，矛盾。故不存在|C|≤2的顶点割，G为3-连通。22.（30分）设A为n×n实对称正定矩阵，b∈R^n。考虑迭代x_{k+1}=x_k+ω(b−Ax_k)，其中ω>0。证明：当0<ω<2/λ_max时，迭代收敛，且最优ω=2/(λ_min+λ_max)使谱半径最小。答案：迭代矩阵G=I−ωA，特征值μ_i=1−ωλ_i，|μ_i|<1⇔0<ω<2/λ_i，对所有i成立需ω<2/λ_max。谱半径ρ(G)=max|1−ωλ_i|。最小化max{|1−ωλ_min|,|1−ωλ_max|}，设两直线交点1−ωλ_min=−(1−ωλ_max)，解得ω=2/(λ_min+λ_max)，此时谱半径(λ_max−λ_min)/(λ_max+λ_min)。──────────────────────────────七、系统与硬件（共60分）23.（30分）某5级流水线RISC核：取指、译码、执行、访存、写回。分支在译段解析，无延迟槽。预测位表4096项，2位饱和计数器。现测得某分支指令序列，全局条件分支共1e9次，实际跳转60%，预测正确率85%。若将预测位表增至16384项，假设无aliasing，则正确率可升至88%。求：(1)原CPI惩罚；(2)新CPI惩罚；(3)若主频2GHz，求每秒节省的流水线刷新周期数。答案：(1)预测失败率15%，每次刷新需2周期（译段到取指），故CPI惩罚0.15×2=0.3。(2)新失败率12%，CPI惩罚0.12×2=0.24。(3)每秒分支数1e9×(1/5)=2e8，节省2e8×(0.15−0.12)×2=1.2e7周期。24.（30分）实现一个无锁并发队列，支持多生产者单消费者，内存顺序仅需acquire-release。要求：enqueue平均O(1)，无异常抛掷；dequeue严格O(1)；总代码≤80行。答案：```cppstructNode{std::atomic<Node>next;intdata;Node(intd):data(d),next(nullptr){}};std::atomic<Node>head;Nodetail=nullptr;voidenqueue(intx){Noden=newNode(x);Nodeprev=head.exchange(n,std::memory_order_acq_rel);prev->next.store(n,std::memory_order_release);}intdequeue(){staticNodelocalHead=nullptr;if(!localHead)localHead=tail;Noden=localHead->next.load(std::memory_order_acquire);if(!n)return-1;intx=n->data;localHead=n;returnx;}```初始化时head存储哑节点，tail指向哑节点。──────────────────────────────八、数据科学（共60分）25.（30分）给定1e8条用户点击日志(user_id,item_id,ts)，需实时计算过去1小时每item的UV。内存限制8GiB，延迟要求≤5s。设计算法并给出误差界。答案：采用滑动窗口Count