ZYZ28 2026.5.26 Round 记录A - 我要在家睡觉原题链接LGP11605 [PA 2016] 运算 / Jedynki分析写过……正解#includebits/stdc.husingnamespacestd;string ans;voidwork(intk){if(k1){ans1;return;}if(k%20){ans((11)*;work(k/2);ans);}else{ans(1(11)*;work(k/2);ans);}}intT,k;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinT;while(T--){cink;ans;work(k);coutans\n;}}B - 你们讨论OI的热情就像打游戏一样[崇拜]原题链接LGP10267 机器人分析bur我不会期望啊最开始想当然了那么我思考一下对于每个点到达该点的概率是确定的只是路径权值不确定而对于超出边框而言这个权值是确定的。我们所需要思考的就是所有到达( n , m ) (n,m)(n,m)的权值如何在O ( m n ) O(mn)O(mn)的复杂度内算出来。还是先看部分分吧一会再思考异或的性质。前30 p t s 30pts30pts似乎可以爆搜。对于x 0 x0x0的性质哦这里就省了一步最终类似于通分的东西。那这个怎么写呢思考一下……也就是说这个东西对于边界权值一定而概率不一定对于终点概率一定而权值不一定。我好像出了提取公因数什么都想不到/ll好吧我似乎知道了对于边界的通式a n s 1 x × ( ∑ i n n m − 1 2 − i ∑ i m n m − 1 2 − i ) ans_1x\times(\sum\limits_{in}^{nm-1}{2^{-i}}\sum\limits_{im}^{nm-1}{2^{-i}})ans1x×(in∑nm−12−iim∑nm−12−i)哦这个还要把分母上变成……反正就是再乘上点什么使得分母变成2 − ( n m − 1 ) 2^{-(nm-1)}2−(nm−1)次方。对吗先不管他。那么对于另一个东西呢这个引入一下异或的性质从二进制位上考虑思考每一个二进制位是否可以在最终答案中体现。但是我还是想不到O ( m n ) O(mn)O(mn)在哪确实是个绿就差这一点/ll不过不用慌一个暑假应该可以把我的实力提升到切蓝冲紫。还是先看后面的吧。我们想到了什么呢就是对于每个二进制位进行操作这样得到一个0 / 1 0/10/1矩阵。那么就差最后一步了我们进行DP设d p i , j , 0 / 1 dp_{i,j,0/1}dpi,j,0/1表示走到了( i , j ) (i,j)(i,j)当前位为0 / 1 0/10/1的概率。转移显然。d p i 1 , j , k ⊕ b i 1 , j d p i 1 , j , k ⊕ b i 1 , j 1 2 d p i , j , k d p i , j 1 , k ⊕ b i , j 1 d p i , j 1 , k ⊕ b i , j 1 1 2 d p i , j , k dp_{i1,j,k\oplus b_{i1,j}} dp_{i1,j,k\oplus b_{i1,j}}\tfrac{1}{2}dp_{i,j,k}\\ dp_{i,j1,k\oplus b_{i,j1}} dp_{i,j1,k\oplus b_{i,j1}}\tfrac{1}{2}dp_{i,j,k}dpi1,j,k⊕bi1,jdpi1,j,k⊕bi1,j21dpi,j,kdpi,j1,k⊕bi,j1dpi,j1,k⊕bi,j121dpi,j,k追问一步所以在之后有类似与临近的可以转移的就是显然的DP了。lyx 的博客正解#includebits/stdc.h#definemod1000000007usingnamespacestd;constintN1005;intn,m,x,a[N][N];longlongdp[N][N][2];structnode{unsignedlonglongx;intqpow(){longlongres1,ax%mod,bmod-2;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}};signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmx;for(inti1;in;i)for(intj1;jm;j)cina[i][j];node tmp1{2};node tmp2{tmp1.qpow()};node ans{0};for(intu0;u30;u){for(inti1;in;i){for(intj1;jm;j){dp[i][j][0]dp[i][j][1]0;}}dp[1][1][(a[1][1]u)1]1;dp[1][1][(~a[1][1]u)1]0;for(inti1;in;i){for(intj1;jm;j){for(intk0;k1;k){(dp[i1][j][k^((a[i1][j]u)1)]dp[i][j][k]*tmp2.x%mod)%mod;(dp[i][j1][k^((a[i][j1]u)1)]dp[i][j][k]*tmp2.x%mod)%mod;}}}(ans.xdp[n][m][1]*(1u)%mod)%mod;}(ans.x(1-(dp[n][m][1]dp[n][m][0])%modmod)%mod*x%mod)%mod;coutans.x;return0;}被取模击败了/llC - 黑芝麻汤圆 再睡回去文化课原题链接LGP12561 [UTS 2024] Matrix分析大概我会一个O ( n 4 ) O(n^4)O(n4)的暴力和另外一个按照前缀和弄得吧……前缀和那个我真的会吗难道说再开一维吧一些信息“立起来”我连最基础的暴力都不会打了/ll嗯场上有一个大概是O ( m n k 2 ) O(mnk^2)O(mnk2)的暴力但是没有写出来。对于那个a i , j ≤ 1 a_{i,j}\le 1ai,j≤1的特殊情况本来想着前缀和确实方便不过三角形处理起来确实恶心最后都没做成按理说……前缀和那个似乎可以一列一列搞不过确实代码能力堪忧。那看看具体怎么写吧看到了四个DP吓哭了/jk明天再写。whk启动日后再写D - 玩第五人格会让年级RK 950原题链接LGP15850 [NOISG 2026 Finals] 宝石 / Gemstones分析哦我们只需要考虑怎么使这个永远无法删除的构造即可。好的我放弃了对。16点50分我决定开始补题。其实这次模拟赛还是比较失败的唯一过的是之前写过的我无法确定再来一次我是否还能自己写出来。无论如何除了T3其他都想到了一些思路吧可能还是临门一脚的感觉。加油一个暑假一个奇迹我绝对写过这类东西好像结论是这些颜色是相互独立的然后删删删没了难道是Codeforces的吗反正挺熟悉的。哦并查集好的我们继续看题解。我们对于[ 1 , i ] [1,i][1,i]的序列能删的就删剩下的建出来一棵字典树状物这个过程似乎可以模拟。那么我们对于一个数可能向其父亲去删或儿子去删所以出现了一个非简单的树。然后对于操作截取[ l − 1 , r ] [l-1,r][l−1,r]的路径答案为l − 1 l-1l−1和r rr的距离。问号问号问号……补充一下发现操作只有push_back和pop_back且经过同一点是没有意义的所以建出操作树前缀树即字典树。然后就可以啊吧啊吧了所以操作次数有限时即可建树。正解#includebits/stdc.husingnamespacestd;constintN1000005;intn,q,c[N];structquery{intl,r,lca;}inp[N];intfa[N];intdsu[N];intfind(intx){while(x!dsu[x]){xdsu[x]dsu[dsu[x]];}returnx;}voidmerge(intx,inty){intfxfind(x),fyfind(y);if(fxfy)return;dsu[fx]fy;}mapint,intch[N];intcnt;intde[N],id[N];boolvis[N];vectorpairint,intask[N];voiddfs(intx){de[x]de[fa[x]]1;vis[x]true;for(autotmp:ch[x]){intytmp.second;dfs(y);merge(y,x);}for(autotmp:ask[x]){if(vis[tmp.first]){inp[tmp.second].lcafind(tmp.first);}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cinnq;for(inti1;in;i)cinc[i];id[0]1;cnt1;stackintstk;for(inti1,pos1;in;i){if(!stk.empty()stk.top()c[i]){stk.pop();posfa[pos];}else{stk.push(c[i]);if(ch[pos].find(c[i])ch[pos].end())ch[pos][c[i]]cnt;fa[ch[pos][c[i]]]pos;posch[pos][c[i]];}id[i]pos;}for(inti1,l,r;iq;i){cinlr;lid[l-1];rid[r];inp[i]{l,r};ask[l].push_back({r,i});ask[r].push_back({l,i});}for(inti1;icnt;i)dsu[i]i;dfs(1);for(inti1;iq;i)coutde[inp[i].l]de[inp[i].r]-2*de[inp[i].lca]\n;return0;}
ZYZ28 2026.5.26 Round 记录
ZYZ28 2026.5.26 Round 记录A - 我要在家睡觉原题链接LGP11605 [PA 2016] 运算 / Jedynki分析写过……正解#includebits/stdc.husingnamespacestd;string ans;voidwork(intk){if(k1){ans1;return;}if(k%20){ans((11)*;work(k/2);ans);}else{ans(1(11)*;work(k/2);ans);}}intT,k;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinT;while(T--){cink;ans;work(k);coutans\n;}}B - 你们讨论OI的热情就像打游戏一样[崇拜]原题链接LGP10267 机器人分析bur我不会期望啊最开始想当然了那么我思考一下对于每个点到达该点的概率是确定的只是路径权值不确定而对于超出边框而言这个权值是确定的。我们所需要思考的就是所有到达( n , m ) (n,m)(n,m)的权值如何在O ( m n ) O(mn)O(mn)的复杂度内算出来。还是先看部分分吧一会再思考异或的性质。前30 p t s 30pts30pts似乎可以爆搜。对于x 0 x0x0的性质哦这里就省了一步最终类似于通分的东西。那这个怎么写呢思考一下……也就是说这个东西对于边界权值一定而概率不一定对于终点概率一定而权值不一定。我好像出了提取公因数什么都想不到/ll好吧我似乎知道了对于边界的通式a n s 1 x × ( ∑ i n n m − 1 2 − i ∑ i m n m − 1 2 − i ) ans_1x\times(\sum\limits_{in}^{nm-1}{2^{-i}}\sum\limits_{im}^{nm-1}{2^{-i}})ans1x×(in∑nm−12−iim∑nm−12−i)哦这个还要把分母上变成……反正就是再乘上点什么使得分母变成2 − ( n m − 1 ) 2^{-(nm-1)}2−(nm−1)次方。对吗先不管他。那么对于另一个东西呢这个引入一下异或的性质从二进制位上考虑思考每一个二进制位是否可以在最终答案中体现。但是我还是想不到O ( m n ) O(mn)O(mn)在哪确实是个绿就差这一点/ll不过不用慌一个暑假应该可以把我的实力提升到切蓝冲紫。还是先看后面的吧。我们想到了什么呢就是对于每个二进制位进行操作这样得到一个0 / 1 0/10/1矩阵。那么就差最后一步了我们进行DP设d p i , j , 0 / 1 dp_{i,j,0/1}dpi,j,0/1表示走到了( i , j ) (i,j)(i,j)当前位为0 / 1 0/10/1的概率。转移显然。d p i 1 , j , k ⊕ b i 1 , j d p i 1 , j , k ⊕ b i 1 , j 1 2 d p i , j , k d p i , j 1 , k ⊕ b i , j 1 d p i , j 1 , k ⊕ b i , j 1 1 2 d p i , j , k dp_{i1,j,k\oplus b_{i1,j}} dp_{i1,j,k\oplus b_{i1,j}}\tfrac{1}{2}dp_{i,j,k}\\ dp_{i,j1,k\oplus b_{i,j1}} dp_{i,j1,k\oplus b_{i,j1}}\tfrac{1}{2}dp_{i,j,k}dpi1,j,k⊕bi1,jdpi1,j,k⊕bi1,j21dpi,j,kdpi,j1,k⊕bi,j1dpi,j1,k⊕bi,j121dpi,j,k追问一步所以在之后有类似与临近的可以转移的就是显然的DP了。lyx 的博客正解#includebits/stdc.h#definemod1000000007usingnamespacestd;constintN1005;intn,m,x,a[N][N];longlongdp[N][N][2];structnode{unsignedlonglongx;intqpow(){longlongres1,ax%mod,bmod-2;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}};signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmx;for(inti1;in;i)for(intj1;jm;j)cina[i][j];node tmp1{2};node tmp2{tmp1.qpow()};node ans{0};for(intu0;u30;u){for(inti1;in;i){for(intj1;jm;j){dp[i][j][0]dp[i][j][1]0;}}dp[1][1][(a[1][1]u)1]1;dp[1][1][(~a[1][1]u)1]0;for(inti1;in;i){for(intj1;jm;j){for(intk0;k1;k){(dp[i1][j][k^((a[i1][j]u)1)]dp[i][j][k]*tmp2.x%mod)%mod;(dp[i][j1][k^((a[i][j1]u)1)]dp[i][j][k]*tmp2.x%mod)%mod;}}}(ans.xdp[n][m][1]*(1u)%mod)%mod;}(ans.x(1-(dp[n][m][1]dp[n][m][0])%modmod)%mod*x%mod)%mod;coutans.x;return0;}被取模击败了/llC - 黑芝麻汤圆 再睡回去文化课原题链接LGP12561 [UTS 2024] Matrix分析大概我会一个O ( n 4 ) O(n^4)O(n4)的暴力和另外一个按照前缀和弄得吧……前缀和那个我真的会吗难道说再开一维吧一些信息“立起来”我连最基础的暴力都不会打了/ll嗯场上有一个大概是O ( m n k 2 ) O(mnk^2)O(mnk2)的暴力但是没有写出来。对于那个a i , j ≤ 1 a_{i,j}\le 1ai,j≤1的特殊情况本来想着前缀和确实方便不过三角形处理起来确实恶心最后都没做成按理说……前缀和那个似乎可以一列一列搞不过确实代码能力堪忧。那看看具体怎么写吧看到了四个DP吓哭了/jk明天再写。whk启动日后再写D - 玩第五人格会让年级RK 950原题链接LGP15850 [NOISG 2026 Finals] 宝石 / Gemstones分析哦我们只需要考虑怎么使这个永远无法删除的构造即可。好的我放弃了对。16点50分我决定开始补题。其实这次模拟赛还是比较失败的唯一过的是之前写过的我无法确定再来一次我是否还能自己写出来。无论如何除了T3其他都想到了一些思路吧可能还是临门一脚的感觉。加油一个暑假一个奇迹我绝对写过这类东西好像结论是这些颜色是相互独立的然后删删删没了难道是Codeforces的吗反正挺熟悉的。哦并查集好的我们继续看题解。我们对于[ 1 , i ] [1,i][1,i]的序列能删的就删剩下的建出来一棵字典树状物这个过程似乎可以模拟。那么我们对于一个数可能向其父亲去删或儿子去删所以出现了一个非简单的树。然后对于操作截取[ l − 1 , r ] [l-1,r][l−1,r]的路径答案为l − 1 l-1l−1和r rr的距离。问号问号问号……补充一下发现操作只有push_back和pop_back且经过同一点是没有意义的所以建出操作树前缀树即字典树。然后就可以啊吧啊吧了所以操作次数有限时即可建树。正解#includebits/stdc.husingnamespacestd;constintN1000005;intn,q,c[N];structquery{intl,r,lca;}inp[N];intfa[N];intdsu[N];intfind(intx){while(x!dsu[x]){xdsu[x]dsu[dsu[x]];}returnx;}voidmerge(intx,inty){intfxfind(x),fyfind(y);if(fxfy)return;dsu[fx]fy;}mapint,intch[N];intcnt;intde[N],id[N];boolvis[N];vectorpairint,intask[N];voiddfs(intx){de[x]de[fa[x]]1;vis[x]true;for(autotmp:ch[x]){intytmp.second;dfs(y);merge(y,x);}for(autotmp:ask[x]){if(vis[tmp.first]){inp[tmp.second].lcafind(tmp.first);}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cinnq;for(inti1;in;i)cinc[i];id[0]1;cnt1;stackintstk;for(inti1,pos1;in;i){if(!stk.empty()stk.top()c[i]){stk.pop();posfa[pos];}else{stk.push(c[i]);if(ch[pos].find(c[i])ch[pos].end())ch[pos][c[i]]cnt;fa[ch[pos][c[i]]]pos;posch[pos][c[i]];}id[i]pos;}for(inti1,l,r;iq;i){cinlr;lid[l-1];rid[r];inp[i]{l,r};ask[l].push_back({r,i});ask[r].push_back({l,i});}for(inti1;icnt;i)dsu[i]i;dfs(1);for(inti1;iq;i)coutde[inp[i].l]de[inp[i].r]-2*de[inp[i].lca]\n;return0;}
