2025年信息競賽決賽試題及答案【注意事項】1.比賽時間300分鐘，滿分400分。2.所有代碼須使用C++17或Python3.10提交，內(nèi)存限制512MiB，時間限制以題目為準(zhǔn)。3.提交文件命名：{題號}.{cpp/py}，主函數(shù)返回0。4.禁止攜帶任何紙質(zhì)或電子資料，禁止訪問網(wǎng)絡(luò)，禁止通信。5.閱卷以官方評測機結(jié)果為準(zhǔn)，無人工干預(yù)。──────────────────────────────一、單項選擇（每題3分，共30分）1.給定一棵n個結(jié)點的有根樹，父結(jié)點編號小于子結(jié)點。若用32位無符號整數(shù)對每條邊編號，則邊編號的最大安全范圍是A.0…n?2B.0…n?1C.0…2n?3D.0…n答案：A。邊數(shù)n?1，編號0…n?2足夠且無溢出。2.在128×128的二維網(wǎng)格上執(zhí)行四叉樹分割，若葉子結(jié)點存儲的像素值完全相同則停止分割，則最壞情況下結(jié)點總數(shù)為A.16384B.21845C.32768D.65536答案：B。T(n)=4T(n/4)+1，遞推得(4^k?1)/3，k=7時21845。3.以下關(guān)于并查集按秩合并的陳述正確的是A.路徑壓縮后秩可能減小B.秩表示子樹大小C.秩指樹高的上界D.秩與集合元素個數(shù)無關(guān)答案：C。4.設(shè)哈希表長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字節(jié)內(nèi)部指針，加8字節(jié)判別域。6.若浮點數(shù)采用1-8-23格式，最接近π的數(shù)與π的絕對誤差約為A.1.2e-7B.2.4e-7C.3.6e-7D.5.0e-7答案：A。單位舍入誤差2^(?24)·π≈1.2e-7。7.對長度為n的隨機排列，快速排序劃分次數(shù)的期望是A.nlnn?0.423nB.nlnn+γnC.2nlnnD.nlog2n答案：A。調(diào)和級數(shù)精確期望。8.以下哪種圖算法最適合在MPC模型下以O(shè)(1)輪數(shù)計算連通分量A.Bor?vkaB.KruskalC.PrimD.A答案：A。每輪可并行收縮。9.若RSA模數(shù)N2048位，e=65537，則私鑰指數(shù)d的位寬約為A.1024B.2048C.4096D.與p,q選擇無關(guān)答案：B。10.在C++20協(xié)程中，co_await表達(dá)式必然觸發(fā)A.promise.await_transformB.promise.initial_suspendC.awaiter.await_readyD.編譯器合成coroutine_handle答案：C。──────────────────────────────二、不定項選擇（每題5分，共30分，多選少選均不得分）11.關(guān)于std::ranges::views::lazy_split，下列說法正確的是A.時間復(fù)雜度與輸入規(guī)模線性B.可作用于非共通序列C.返回子范圍視圖D.分隔串可為空答案：ACD。12.以下哪些措施可降低CPU分支預(yù)測失敗懲罰A.使用__builtin_expectB.采用條件傳送指令C.循環(huán)展開D.將熱路徑代碼置于同一64B緩存行答案：ABCD。13.對n個點的三維凸包，下列算法復(fù)雜度正確的是A.增量法O(n^2)B.分治法O(nlogn)C.Quickhull期望O(nlogn)D.Chan’s算法O(nlogh)答案：ACD。14.在LLVMIR中，下列屬性可標(biāo)記于函數(shù)以啟用優(yōu)化A.nounwindB.readonlyC.convergentD.sanitize_address答案：ABC。15.若圖G的treewidth≤k，則下列問題可線性時間求解A.最大獨立集B.最小支配集C.三染色D.Hamilton圈答案：ABCD。16.以下關(guān)于Z3求解器的描述正確的是A.支持位向量理論B.支持非線性實數(shù)算術(shù)C.支持quantifiereliminationD.支持優(yōu)化目標(biāo)答案：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。──────────────────────────────四、算法設(shè)計（共60分）17.（30分）給定長為n≤5×10^6的整數(shù)序列a_i∈[0,10^9]，求S=∑_{i=1}^{n}∑_{j=i+1}^{n}(a_i⊕a_j)·(a_i+a_j)mod998244353，其中⊕為按位異或。答案：按位拆分。設(shè)第k位權(quán)值w_k=2^k。對每一位統(tǒng)計c0=該位為0的個數(shù)，c1=該位為1的個數(shù)，s0=該位為0的數(shù)和，s1=該位為1的數(shù)和。則該位對答案貢獻(xiàn)w_k·[c1·s0+c0·s1+w_k·(c1·(c1?1)/2+c0·(c0?1)/2)]累加所有位后取模。時間O(nlogmax_a)，內(nèi)存O(n)。18.（30分）交互題。隱藏一棵n≤2×10^5的無根樹，邊權(quán)1。你最多可詢問5×10^4次，每次給出結(jié)點集U?V,|U|≤20，系統(tǒng)返回U的Steiner樹邊數(shù)。求直徑長度。答案：隨機取200個樞軸點p_i，對每個p_i用二分+集合詢問求出離p_i最遠(yuǎn)的點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次，遠(yuǎn)小于上限。──────────────────────────────五、綜合編程（共120分）19.（60分）題目名稱：量子門調(diào)度給定n≤1e5個量子門，每個門g_i作用在二維網(wǎng)格的qubit坐標(biāo)(x_i,y_i)，x_i∈[0,4095],y_i∈[0,255]。兩個門沖突當(dāng)且僅當(dāng)它們作用qubit的切比雪夫距離≤1。求最小劃分輪數(shù)，使得每輪內(nèi)無沖突。輸入：第一行n，隨后n行每行x_iy_i。輸出：最小輪數(shù)m，隨后m行，每行先給出該輪門數(shù)k，隨后k個門的原始編號（任意順序）。答案：將網(wǎng)格按(x//3,y//3)分塊，共1365×85塊。每塊內(nèi)最多9個qubit，塊內(nèi)門構(gòu)成單位沖突圖，最大團(tuán)≤9，可暴力求色數(shù)。塊間無沖突，可并行染色。總復(fù)雜度O(n+B·2^9)，B為塊數(shù)，可過1e5。20.（60分）題目名稱：可撤銷并查集維護(hù)一個初始為n個孤立點的圖，支持q≤1e6次操作：1uv合并u,v所在集合，若已連通則忽略；2uv撤銷最近一次成功合并u,v的操作；3uv查詢u,v是否連通；4k返回當(dāng)前連通塊數(shù)；5u返回u所在集合大小。強制在線，最后需輸出所有操作3,4,5的結(jié)果異或和。答案：使用可持久化數(shù)組維護(hù)父指針與秩。每次合并在持久化數(shù)組新版本上執(zhí)行路徑壓縮與按秩合并，并記錄操作棧。撤銷時彈出棧頂，回滾父指針與秩，連通塊數(shù)同步維護(hù)?？倳r間O(qα(n)logn)，空間O(qlogn)。──────────────────────────────六、理論證明（共60分）21.（30分）定義：稱無向圖G是k-流密的，當(dāng)且僅當(dāng)對任意非空真子集S?V，|δ(S)|≥k·min{|S|,|V\S|}。證明：若G是3-流密且|V|≥4，則G必為3-頂點連通。答案：反證。假設(shè)存在頂點割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|}，聯(lián)立得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無重邊，可構(gòu)造反例？進(jìn)一步觀察：若|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|，當(dāng)|A|,|B|≥2時|A||B|<1.5(|A|+|B|)不成立，故必有一側(cè)大小為1。設(shè)|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分）設(shè)A為n×n實對稱正定矩陣，b∈R^n?？紤]迭代x_{k+1}=x_k+ω(b?Ax_k)，其中ω>0。證明：當(dāng)0<ω<2/λ_max時，迭代收斂，且最優(yōu)ω=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|}，設(shè)兩直線交點1?ωλ_min=?(1?ωλ_max)，解得ω=2/(λ_min+λ_max)，此時譜半徑(λ_max?λ_min)/(λ_max+λ_min)。──────────────────────────────七、系統(tǒng)與硬件（共60分）23.（30分）某5級流水線RISC核：取指、譯碼、執(zhí)行、訪存、寫回。分支在譯段解析，無延遲槽。預(yù)測位表4096項，2位飽和計數(shù)器?，F(xiàn)測得某分支指令序列，全局條件分支共1e9次，實際跳轉(zhuǎn)60%，預(yù)測正確率85%。若將預(yù)測位表增至16384項，假設(shè)無aliasing，則正確率可升至88%。求：(1)原CPI懲罰；(2)新CPI懲罰；(3)若主頻2GHz，求每秒節(jié)省的流水線刷新周期數(shù)。答案：(1)預(yù)測失敗率15%，每次刷新需2周期（譯段到取指），故CPI懲罰0.15×2=0.3。(2)新失敗率12%，CPI懲罰0.12×2=0.24。(3)每秒分支數(shù)1e9×(1/5)=2e8，節(jié)省2e8×(0.15?0.12)×2=1.2e7周期。24.（30分）實現(xiàn)一個無鎖并發(fā)隊列，支持多生產(chǎn)者單消費者，內(nèi)存順序僅需acquire-release。要求：enqueue平均O(1)，無異常拋擲；dequeue嚴(yán)格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存儲啞節(jié)點，tail指向啞節(jié)點。──────────────────────────────八、數(shù)據(jù)科學(xué)（共60分）25.（30分）給定1e8條用戶點擊日志(user_id,item_id,ts)，需實時計算過去1小時每item的UV。內(nèi)存限制8GiB，延遲要求≤5s。設(shè)計算法并給出誤差界。答案：采用滑動窗口Count