ZYZ28 2026.5.26 Round 记录

ZYZ28 2026.5.26 Round 记录

A - 我要在家睡觉！

原题链接：LGP11605 [PA 2016] 运算 / Jedynki

分析

写过……

正解

#include<bits/stdc++.h>usingnamespacestd;string ans="";voidwork(intk){if(k==1){ans+="1";return;}if(k%2==0){ans+="((1+1)*";work(k/2);ans+=")";}else{ans+="(1+(1+1)*";work(k/2);ans+=")";}}intT,k;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;while(T--){cin>>k;ans="";work(k);cout<<ans<<'\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 x=0x=0的性质，哦，这里就省了一步最终类似于通分的东西。那，这个怎么写呢？思考一下……
也就是说，这个东西，对于边界，权值一定而概率不一定；对于终点，概率一定而权值不一定。我好像出了提取公因数什么都想不到/ll
好吧，我似乎知道了对于边界的通式：
a n s 1 = x × ( ∑ i = n n + m − 1 2 − i + ∑ i = m n + m − 1 2 − i ) ans_1=x\times(\sum\limits_{i=n}^{n+m-1}{2^{-i}}+\sum\limits_{i=m}^{n+m-1}{2^{-i}})ans1​=x×(i=n∑n+m−1​2−i+i=m∑n+m−1​2−i)
哦，这个还要把分母上变成……反正就是再乘上点什么，使得分母变成2 − ( n + m − 1 ) 2^{-(n+m-1)}2−(n+m−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_{i+1,j,k\oplus b_{i+1,j}} = dp_{i+1,j,k\oplus b_{i+1,j}}+\tfrac{1}{2}dp_{i,j,k}\\ dp_{i,j+1,k\oplus b_{i,j+1}} = dp_{i,j+1,k\oplus b_{i,j+1}}+\tfrac{1}{2}dp_{i,j,k}dpi+1,j,k⊕bi+1,j​​=dpi+1,j,k⊕bi+1,j​​+21​dpi,j,k​dpi,j+1,k⊕bi,j+1​​=dpi,j+1,k⊕bi,j+1​​+21​dpi,j,k​
追问一步：

所以，在之后有类似与临近的可以转移的，就是显然的DP了。
lyx 的博客

正解

#include<bits/stdc++.h>#definemod1000000007usingnamespacestd;constintN=1005;intn,m,x,a[N][N];longlongdp[N][N][2];structnode{unsignedlonglongx;intqpow(){longlongres=1,a=x%mod,b=mod-2;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}returnres;}};signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>x;for(inti=1;i<=n;++i)for(intj=1;j<=m;++j)cin>>a[i][j];node tmp1{2};node tmp2{tmp1.qpow()};node ans{0};for(intu=0;u<30;u++){for(inti=1;i<=n;i++){for(intj=1;j<=m;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(inti=1;i<=n;i++){for(intj=1;j<=m;j++){for(intk=0;k<=1;k++){(dp[i+1][j][k^((a[i+1][j]>>u)&1)]+=dp[i][j][k]*tmp2.x%mod)%=mod;(dp[i][j+1][k^((a[i][j+1]>>u)&1)]+=dp[i][j][k]*tmp2.x%mod)%=mod;}}}(ans.x+=dp[n][m][1]*(1<<u)%mod)%=mod;}(ans.x+=(1-(dp[n][m][1]+dp[n][m][0])%mod+mod)%mod*x%mod)%=mod;cout<<ans.x;return0;}

被取模击败了/ll

C - @黑芝麻汤圆 再睡回去文化课

原题链接：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，且经过同一点是没有意义的，所以，建出操作树（前缀树，即字典树）。然后就可以啊吧啊吧了！所以，操作次数有限时，即可建树。

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;intn,q,c[N];structquery{intl,r,lca;}inp[N];intfa[N];intdsu[N];intfind(intx){while(x!=dsu[x]){x=dsu[x]=dsu[dsu[x]];}returnx;}voidmerge(intx,inty){intfx=find(x),fy=find(y);if(fx==fy)return;dsu[fx]=fy;}map<int,int>ch[N];intcnt;intde[N],id[N];boolvis[N];vector<pair<int,int>>ask[N];voiddfs(intx){de[x]=de[fa[x]]+1;vis[x]=true;for(autotmp:ch[x]){inty=tmp.second;dfs(y);merge(y,x);}for(autotmp:ask[x]){if(vis[tmp.first]){inp[tmp.second].lca=find(tmp.first);}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>q;for(inti=1;i<=n;++i)cin>>c[i];id[0]=1;cnt=1;stack<int>stk;for(inti=1,pos=1;i<=n;++i){if(!stk.empty()&&stk.top()==c[i]){stk.pop();pos=fa[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;pos=ch[pos][c[i]];}id[i]=pos;}for(inti=1,l,r;i<=q;++i){cin>>l>>r;l=id[l-1];r=id[r];inp[i]={l,r};ask[l].push_back({r,i});ask[r].push_back({l,i});}for(inti=1;i<=cnt;++i)dsu[i]=i;dfs(1);for(inti=1;i<=q;++i)cout<<de[inp[i].l]+de[inp[i].r]-2*de[inp[i].lca]<<'\n';return0;}