2026CCPC 题解
A 完全不知道思路；其他题或多或少都自己敲了一些。
A
对这道题没有啥印象。
C
签到题。
考虑记录 \(ans_k\) 表示对于第 \(k\) 个循环移位的匹配度；
答案为 \(n-max_{i=0}^k(ans_i)\)。
很显然，找到当前位置是哪个循环移位，是很简单的。
E
非常逆天的大分类讨论题，不太想再写一遍思路。
考虑到 \(a_2=n-1\) 无解，其他情况都是有解的。
我按 \(a_1=0,a_1=1,a_1\geq 2\) 三种情况分类讨论。
对于 \(a_1=0\) 和 \(a_1=1\)，内部也进行了一些神秘的分类讨论。
#include
#define pb push_back
using ll=long long;
using namespace std;
typedef pairpii;
void Silverwolf(){vectora(4,0);int n;cin>>n;for(int i=1;i<=3;i++)cin>>a[i];vectortr;if(a[2]==n-1)return cout<<-1<<'\n',void();if(a[1]==0){if(a[2]==0){//a[3]==n-1tr={{1,7},{1,2},{2,3},{3,4},{2,5},{1,6},{6,8}};vectorp={0,1,4,5,6,3,7,8,2};for(int i=9;i<=n;i++)p.pb(i);int u=1;for(int i=9;i<=n;i++){if(i==9)tr.pb({2,9});else{tr.pb({u,i});u^=7;}}for(auto [u,v]:tr)cout<p={0,1,3,4,5,6,7,2,8};int u=1;for(int i=9;i<=n;i++){p.pb(i);tr.pb({i,u});u^=3;}for(auto [u,v]:tr)cout<p={0,1,3,4};int lst=5;for(int i=3;i<=a[2];i++){tr.pb({2,lst});p.pb(lst);lst++;}lst--;if(a[3]<3)return cout<<-1<<'\n',void();tr.pb({3,lst});tr.pb({2,lst+1});tr.pb({1,lst+2});p.pb(lst);p.pb(lst+1);p.pb(lst+2);lst+=3;p.pb(2);int u=5;for(int i=4;i<=a[3];i++){if(i==4){p.pb(lst);tr.pb({lst-3,lst});lst++;}else if(i==5){tr.pb({3,lst});p.pb(lst);}elsetr.pb({u,lst});p.pb(lst);u^=6;}}if(a[1]==1&&a[2]==0){tr={{1,2},{1,3},{3,5},{1,5},{2,7},{2,6},{1,8}};vectorp={0,1,2,4,5,6,3,7,8};int u=2;for(int i=9;i<=n;i++){p.pb(i);tr.pb({u,i});u^=3;}for(auto [u,v]:tr)cout<>e(n+1);vectorfa(n+1,0);auto add=[&](int u,int v){tr.push_back({u,v});e[u].pb(v);e[v].pb(u);fa[v]=u;};for(int i=1;i<=a[1];i++){add(j,j+1);j++;}// cout<int{vectordis(n+1,n+2);vectorvis(n+1,0);dis[u]=0;vis[u]=1;queueque;que.push(u);while(que.size()){auto now=que.front();que.pop();for(int v:e[now]){if(vis[v])continue;vis[v]=1;dis[v]=dis[now]+1;que.push(v);if(dis[v]==d)return v;}}// for(int i=1;i<=n;i++)cout<>T;while(T--)Silverwolf();return 0;
}
G
一个非常不错的思维题。
首先，将字符串 \(s\) 变成 \(t\)，就等价于将 \("000...000"\) 变成 \(s\oplus t\)，其中这里的异或指的是对于每个位置都取异或。记 \(a=s\oplus t\)。
我们不喜欢区间异或，不妨在差分后的序列去做吧，记 \(b_i=a_i\oplus a_{i-1}\)，其中 \(1\leq i\leq n+1\)。
这样，对于一段区间 \([l,r]\) 的异或就等价于 \(b_l\) 和 \(b_{r+1}\) 的单点异或。
考虑这样的子问题：首先考虑不删除任何一次区间差分的机会该怎么做呢？
我们可以考虑将 \(l\) 和 \(r+1\) 进行建图。
hint1：对于一个连通块内，我们的操作可以推广到任意两点 \(u,v\)，将其单点异或。
这是容易证明的。
对于一条长度为 \(3\) 的链 \(u-v-w\)：
选取 \(u,v\) 或 \(v,w\)，这本身就能做到。
选取 \(u,v\) 和 \(v,w\)，这样就能得到 \(u,w\)。
容易推广到整个连通块。
hint2：一个连通块内，我无论修改多少次，该连通块内被修改的 1 的个数总是偶数个。
因为一次修改，对于 \(1\) 的增量来说，有且仅有 +2,0,-2 这三种情况。这一点是好证明的。
很好，上述的子问题就被解决了，我这 \(m\) 个区间，假设没有任意一个区间要被删除，使得从 \(s\) 变到 \(t\) 合法，当且仅当每个连通块内 \(1\) 的数量都是偶数个。这可以很轻松的用并查集维护。
接下来，考虑第 \(i\) 条边是否可删。
如果第 \(i\) 条边不是割边，那删掉后对连通块没有影响，显然是可删去的。
如果第 \(i\) 条边是割边，那么需要考虑一下被删去后的两个连通块内 \(1\) 的个数分别是不是偶数个。
思路部分阐述完了，接下来是算法实现的流程。
- 使用 tarjan 算法求出所有的割边
- 通过割边将图分割成不同的连通块，并给这些连通块分别确定颜色（似乎我铸币了，tarjan 跑出来的不在同一边双内，显然颜色是不同的）
- 缩点后建新图，维护每个新点中 1 的数量
- 缩点后的结构显然是一棵树，通过树的叶子节点开始去做一个类似 topo 排序的东西，然后可以维护出砍断每一条割边后，两个连通分量中 1 的数量。若均为偶数个，说明这条边可以被删去。
时间复杂度 \(O(n+m)\)。
#include
#define pb push_backusing ll=long long;
using namespace std;
typedef pairpii;
class Bin{
public:int n;vectorf,sz,g;Bin(int _n){n=_n;f.resize(n+1);g.assign(n+1,0);for(int i=1;i<=n;i++)f[i]=i;}int find(int x){return x==f[x]?x:f[x]=find(f[x]);}bool merge(int x,int y){int fx=find(x);int fy=find(y);if(fx==fy)return false;g[fx]+=g[fy];f[fy]=fx;return true;}
};
class Tarjan{
public:int n,idx,top;vectordfn,low,col,into;vectoredg;vector>e;//原图vector>scc;//新图vectorstk;vectorin;vector>dp;vectorisg;ll ans=1;Tarjan(int n):n(n){idx=0,top=0;e.resize(n+1);scc.resize(n+1);//先这样搞吧dfn.assign(n+1,0);low.assign(n+1,0);col.assign(n+1,0);into.assign(n+1,0);stk.assign(n+1,0);in.assign(n+1,false);}void add(int u,int v,int w){// if(u==v)return;e[u].pb({v,w});e[v].pb({u,w});}void tarjan2(){for(int i=1;i<=n;i++){if(!dfn[i])tarjan2(i,0);}}void tarjan2(int u,int f){//割边满足low[v]>dfn[u]dfn[u]=low[u]=++idx;for(auto [v,id]:e[u]){if(v==f)continue;if(!dfn[v]){tarjan2(v,u);low[u]=min(low[u],low[v]);if(low[v]>dfn[u]){//割边isg[id]=1;// edg.pb({u,v});}}else low[u]=min(low[u],dfn[v]);}}void print(int m){for(int i=1;i<=m;i++)cout<<0;cout<<'\n';}void work(){//这里面的所有n都已经等于 a+1 了int m;cin>>m;string s,t;cin>>s>>t;vectora(n+1,0);for(int i=1;ib(n+1,0);for(int i=1;i<=n;i++){b[i]=a[i-1]^a[i];}a=b;Bin bc(n);for(int i=1;i<=n;i++)bc.g[i]=a[i];vectoredg(m+1);for(int i=1;i<=m;i++){int l,r;cin>>l>>r;edg[i]={l,r+1};bc.merge(l,r+1);add(l,r+1,i);}//先判一定无解的情况for(int i=1;i<=n;i++){if(a[i]&&bc.g[bc.find(i)]&1)return print(m);}isg.assign(m+1,0);tarjan2();//处理出所有的割边vectorsumg(n+1,0),col(n+1,0);vector>scc(n+1);auto bfs=[&](int u,int c)->void{queueque;que.push(u);col[u]=c;sumg[c]+=a[u];while(que.size()){auto now=que.front();que.pop();for(auto v:scc[now]){if(col[v])continue;col[v]=c;sumg[c]+=a[v];que.push(v);}}};for(int i=1;i<=m;i++){if(!isg[i]){auto [u,v]=edg[i];scc[u].pb(v);scc[v].pb(u);}}for(int i=1;i<=n;i++)if(!col[i])bfs(i,i);// for(int i=1;i<=n;i++)cout<>dele(n+1);//这些是割边vectordu(n+1,0);for(int i=1;i<=m;i++){if(isg[i]){auto [u,v]=edg[i];u=col[u];v=col[v];dele[u].pb({v,i});dele[v].pb({u,i});du[u]++;du[v]++;}}vectorvis(n+1,0);vectorge(m+1,0);auto topo=[&]()->void{queueque;for(int i=1;i<=n;i++){if(col[i]==i&&du[i]==1){que.push(i);}}while(que.size()){auto now=que.front();que.pop();vis[now]=1;for(auto [v,id]:dele[now]){if(--du[v]==1){que.push(v);}if(vis[v])continue;int sum=bc.g[bc.find(now)];int r1=sumg[now];int r2=sum-r1;if(r1%2==0&&r2%2==0)ge[id]=1;sumg[v]+=sumg[now];sumg[now]=0;}}};topo();// for(int i=1;i<=m;i++)cout<>n;Tarjan tar(n+1);tar.work();
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// get_prim();int T;cin>>T;while(T--)Silverwolf();return 0;
}
/*
18 300 1 2 3 4 5 0 0 0 6 7 8 9 10 11 12 13 013 1011 2 3 4 5 6 7 8 9 10 11 12 13
*/
I
一道非常好的思维题。
（完全不是正解，但通过了 ）
由于次数必须在 \(\lfloor \frac{3n}{2} \rfloor\) 的次数内完成，我能想到的一种方法就是：能不能用三位信息，去保存每两个位的位置？
我们先考虑 \(n\) 是偶数的情况。
对于连续三个位置，合法的字符串有：\(001,010,011,110,101,100\)
在赛时尝试了很多种分配方案后，我发现了以下一种合理的分配方式：
11：101
00：010
10：001 110
01：011 100
这样去设置有什么好处呢？
对于 10 和 01 中，设置的两个字符串都是可以互相接通的；
11 和 00 是可以互相接通的；
10，01 至少都存在一个和 11，00 接通的字符串。
对于 11 和 00 没啥悬念；
对于 10 和 01，我们可以 dp 一下当前位置放哪个字符串。
\(n\) 是奇数怎么办？
在开头多放一个 \(1\) 或 \(0\) 即可。
#include
#define pb push_back
using ll=long long;
using namespace std;
typedef pairpii;
map>rev;
mapmp={{"001","10"},{"110","10"},{"101","00"},{"1","1"},{"0","0"},{"010","11"},{"100","01"},{"011","01"}
};
map,int>ok;//能不能这样拼接
int r;
bool chk(string str){for(int i=2;i>n;string s;cin>>s;string str;if(n&1){str+=s[0];string ss;ss.pb(s[0]);vector>dp={{1}};vector>pre={{0}};vector>lsts={{ss}};for(int i=1;indp;vectornpre;vectornlst;mapvis;for(auto y:rev[tmp]){for(int ii=0;iiv;int j=0;for(int i=dp.size()-1;i>=0;i--){v.push_back(lsts[i][j]);j=pre[i][j];}string sss;for(int i=v.size()-1;i>=0;i--){sss+=v[i];}assert(sss.length()==(n*3/2));cout<>dp;vector>pre;vector>lsts;lsts.push_back(rev[tmp]);int cnt=rev[tmp].size();vectorndp;vectornpre;for(int i=0;indp;vectornpre;vectornlst;mapvis;for(auto y:rev[tmp]){for(int ii=0;iiv;int j=0;for(int i=dp.size()-1;i>=0;i--){v.push_back(lsts[i][j]);j=pre[i][j];}string sss;for(int i=v.size()-1;i>=0;i--){sss+=v[i];}assert(sss.length()==(n*3/2));cout<>m;string s;cin>>s;string str;if(m%3==1){str+=s[0];for(int i=1;i>T>>r;if(r==1){while(T--)First();}else{while(T--)Second();}return 0;
}
J
每个位是独立的，可以按位贪心。
对于每个二进制位，显然 \(a_u \& a_v=1\) 的限制更强，我们将 \(a_u,a_v\) 都设置成 \(1\)。
接下来我们处理 \(a_u\& a_v=0\) 的询问，若此时出现了 \(a_u=a_v=1\) 就说明无解。
剩下的我们就按 \(0\) 放就好了。
时间复杂度 \(O(mk)\)
M
考虑从中间开始往外拓展区间。
当前区间为 \([l,r]\)。
很显然的是，答案与 \(gcd(|a_l-a_r|,|a_{l+1}-a_{r-1}|,...)\) 的因子的个数有关。累计答案是 \(d_x-1\)，设 \(d_x\) 表示其因子的个数。
\(O(n^2)\) 枚举区间。
\(O(m)\) 欧拉筛求出 \([1,m]\) 每个数的最小质因子
\(O(m\log m)\) 求解 \([1,m]\) 每个数的因子的个数。