这是正式开始练习团队赛的的第一场。本场难度适中但是教育意义很好。对去年的我们很有挑战赛后认为对当时没太大意义没补。本次打完之后收获颇多。在vp的过程中第5、6题均有出现题目理解错误的情况需调整本场链接Attachments - 2025 National Invitational of CCPC (Zhengzhou)Problem F. 幻形之路本题是个搜索问题赛时思路还是比较清晰。开始通过推导我想到标记后二重暴力取最小值只是我们都在担心可能会超时。前面的还没敲完我又提议使用多源BFS因为没看清题意导致一直错误后边也没返回使用暴力的方法。先从左上搜索把左上#放到队列中如果搜通直接0从右下搜索将右下#进行标记之后有两种处理方式多源BFS如果碰到右下#就直接弹出双重循环暴力搜索两边的点取距离最小值#includebits/stdc.husingnamespacestd;#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineendl\n#definepbpush_back#defineall(x)x.begin(),x.end()// const int mod 998244353;constintmod1e97;constintINF1e18;constintN1e65;intn,m;string s;intdx[]{0,-1,0,1};intdy[]{-1,0,1,0};structp{intst;intx,y;};voidsolve(){cinnm;vectorvectorchara(n5,vectorchar(m5));vectorvectorboolvi(n5,vectorbool(m5));autompvi;// 标记后#for(inti1;in;i)for(intj1;jm;j)cina[i][j];queuepq,q1;q.push({1,1,1});// 左上开始搜while(q.size()){autocuq.front();q.pop();intstcu.st,xcu.x,ycu.y;if(xnym)//搜通直接退出{cout0endl;return;}if(a[x][y]#)//左上的源点放入q1{q1.push({1,x,y});continue;}for(inti0;i4;i){inttxxdx[i];inttyydy[i];if(tx1||ty1||txn||tym||vi[tx][ty])continue;vi[tx][ty]1;q.push({st1,tx,ty});}}for(inti1;in;i)fill(all(vi[i]),0);q.push({1,n,m});//右下开始搜while(q.size()){autocuq.front();q.pop();intstcu.st,xcu.x,ycu.y;if(a[x][y]#)//标记终点#{mp[x][y]1;continue;}for(inti0;i4;i){inttxxdx[i];inttyydy[i];if(tx1||ty1||txn||tym||vi[tx][ty])continue;vi[tx][ty]1;q.push({st1,tx,ty});}}for(inti1;in;i)fill(all(vi[i]),0);while(q1.size())// 多源BFS{autocuq1.front();q1.pop();intstcu.st,xcu.x,ycu.y;if(mp[x][y])//找到右下#{coutstendl;return;}for(inti0;i4;i){inttxxdx[i];inttyydy[i];if(tx1||ty1||txn||tym||vi[tx][ty])continue;vi[tx][ty]1;q1.push({st1,tx,ty});}}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;cinT;while(T--)solve();return0;}Problem M. 川陀航空学院并查集模板。#includebits/stdc.husingnamespacestd;#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineendl\n#definepbpush_back#defineall(x)x.begin(),x.end()// const int mod 998244353;constintmod1e97;constintINF1e18;constintN1e65;intn,m;string s;vectorintp(N),sz(N);intfind(intx){if(x!p[x])p[x]find(p[x]);returnp[x];}voidunite(intx,inty){xfind(x),yfind(y);if(xy)return;if(sz[x]sz[y])swap(x,y);p[x]y;sz[y]sz[x];}voidsolve(){cinnm;intans0;for(inti1;in;i)p[i]i,sz[i]1;for(inti0;im;i){intu,v;cinuv;if(find(u)find(v))ans;elseunite(u,v);}intcnt0;for(inti1;in;i)cnt(p[i]i);//联通块个数anscnt-1;coutansendl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;// cin T;while(T--)solve();return0;}Problem H. 树论函数公式推导、打表原公式f ( n ) f ( a ) ⋅ f ( b ) f(n)f(a)·f(b)f(n)f(a)⋅f(b)。f ( a ) ⋅ f ( a 1 ) a ( a 1 ) ( a 1 ) ( a 2 ) f(a)·f(a1)a(a1)(a1)(a2)f(a)⋅f(a1)a(a1)(a1)(a2) a ( a 2 ) ( a 1 ) ( a 1 ) a(a2)(a1)(a1)a(a2)(a1)(a1) ( a 2 2 a ) ( a 2 2 a 1 ) (a^22a)(a^22a1)(a22a)(a22a1)设b a 2 2 a ba^22aba22a有f ( b ) f ( a ) ⋅ f ( a 1 ) f(b)f(a)·f(a1)f(b)f(a)⋅f(a1)则任意相邻节点都有某个点和他们相连接所以所有的点都是相连的既然所有都相连直接输出区间长度即可Problem E. 双生魔咒字符串哈希本题可用字符串/字典树解决在这介绍字符串哈希的解法。要使前缀尽量多肯定要先进行排序。字符串的排序就是从头到尾对比相似度。其次涉及到如何存的问题。如果把所有字符串的所有前缀都存起来那么是会超内存的并且字符串的比较也是很慢还会超时间字符串哈希会把字符串映射成对应的哈希值存储数字一个只有8字节并且比较操作也很快。#includebits/stdc.husingnamespacestd;#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineendl\n#definepbpush_back#defineall(x)x.begin(),x.end()#defineullunsignedlonglong// const int mod 998244353;constintmod1e97;constintINF1e18;constintN1e65;intn,m;string s;constintP131;voidsolve(){cinn;vectorstringa(2*n1);for(inti1;i2*n;i)cina[i];sort(a.begin()1,a.end());unordered_mapint,intmp;intcnt0;for(inti1;i2*n;i2){ull cu0;string k a[i];for(intj1;jk.size();j){cucu*Pk[j];mp[cu];}}for(inti2;i2*n;i2){ull cu0;string k a[i];for(intj1;jk.size();j){cucu*Pk[j];if(mp.count(cu))cntmp[cu];}}coutcntendl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;// cin T;while(T--)solve();return0;}