CF每日5题

将不高兴的同学计数cnt
不高兴的同学之间两两交换，一定不会在$p_i=i$的位置上，贡献是cnt/2
如果cnt%2>0，那就多交换一次

void solve()
{int n;cin>>n;int cnt=0;forr(i,1,n){int p;cin>>p;if(i==p)cnt++;}int ans=cnt/2+cnt%2;cout<<ans<<endl;
}

• $\frac{y}{x}=k^n$可以变成$\frac{y}{k^n}=x$
• x可以连续取，题中$l_1\le x\le r_1$，由上可得$\frac{l_2}{k^n}\le x\le \frac{r_2}{k^n}$，枚举n取交集求和
  一开始想成了$y=k^n\cdot x$求y的范围，但是y不是连续取的，不能直接取交集

void solve()
{int k,l1,r1,l2,r2;cin>>k>>l1>>r1>>l2>>r2;int ans=0;int kp=1;while (l1*kp<=r2){if(r1*kp<l2){kp*=k;continue;}// cout<<kp<<' '<<l<<' '<<r<<endl;int rt=min(r1,r2/kp),lt=max(l1,(l2+kp-1)/kp);ans+=rt-lt+1;kp*=k;}cout<<ans<<endl;
}

题意：两个图F,G，在F中进行多少次删边添边能让F=G ——理解错题意了，是对所有$(u,v)\in F$，在G中连通性相同

• 两个图连通关系相同，使用并查集表示连通关系，在一个集里就是连通
• 对F中的每条边（即是连通），在G中找它的连通性
• 删边：F中连通，但G中不连通，应该删去
• 加边：F的集合数-G的集合数 是F中最少应该连通的边，让多出来的集合连通进去（两个集合连通为一个）

const int N=2e5+10;
int f[N],g[N];
int find(int x,int a[]){if(a[x]==x)return x;else return a[x]=find(a[x],a);
}
void solve()
{int n,m1,m2;cin>>n>>m1>>m2;forr(i,1,n)f[i]=i,g[i]=i;vector<int>u(m1+1),v(m1+1);forr(i,1,m1){cin>>u[i]>>v[i];}forr(i,1,m2){int x,y;cin>>x>>y;int gx=find(x,g),gy=find(y,g);if(gx==gy)continue;else g[gx]=gy;}int ans=0;forr(i,1,m1){int gu=find(u[i],g),gv=find(v[i],g);//在一个连通里if(gu==gv){int fu=find(u[i],f),fv=find(v[i],f);f[fu]=fv;}else ans++;//删边计数}// cout<<ans<<endl;int cntg=0,cntf=0;forr(i,1,n){if(g[i]==i)cntg++;if(f[i]==i)cntf++;}// cout<<cntg<<' '<<cntf<<endl;cout<<ans+(cntf-cntg)<<endl;
}

一层层绕 找就可以

const int N=1e3+10;
string a[N],fd="1543",s;
int ans;
int rr,cr;//循环截止的地方 防止重复转圈
int fg,ed;
void op(int r,int c){// cout<<r<<' '<<c<<' '<<s<<' ';if(s.size()==4){if(rr==r&&cr==c){ed=1;return;}if(fg==1)rr=r,cr=c,fg=0;//记录每一层第一个满4判断的地方if(s==fd){ans++;// cout<<"+1"<<' ';}s.erase(0,1);}// cout<<endl;
}
void solve()
{int n,m;cin>>n>>m;forr(i,1,n){cin>>a[i];a[i]=' '+a[i];}ans=0,rr=0,cr=0;forr(i,1,min(n,m)/2){//遍历每一层s="";fg=1;//转圈int r=i,c;for(c=i;c<=m-i+1;c++){// cout<<c<<endl;s+=a[r][c];op(r,c);}c=m-i+1;for(r=i+1;r<=n-i+1;r++){s+=a[r][c];op(r,c);}r=n-i+1;for(c=m-i;c>=i;c--){s+=a[r][c];op(r,c);}c=i;for(r=n-i;r>=i;r--){s+=a[r][c];op(r,c);}ed=0;//判断到没到要结束的地方while(s.size()<4){r=i;for(c=i+1;c<=m-i+1;c++){s+=a[r][c];op(r,c);if(ed)break;}if(ed)break;c=m-i+1;for(r=i+1;r<=n-i+1;r++){s+=a[r][c];op(r,c);if(ed)break;}if(ed)break;r=n-i+1;for(c=m-i;c>=i;c--){s+=a[r][c];op(r,c);if(ed)break;}if(ed)break;}}cout<<ans<<endl;
}

题意：点1~n连成一个圈，每个点都是相邻点的MEX，给出的x,y是除了圈的边另外连的边

• 可知相邻的数不相同

• 偶数个点的圈，可以0101交替
  

• 奇数个点，两个数交替会出现相邻数相同的情况，其中一个数是2
  

• 另外连的(x,y)把一个圈分成了两个圈，先构造(x,y)，再根据奇偶性构造两边的圈
  

void solve()
{int n,x,y;cin>>n>>x>>y;int cir1=y-x+1,cir2=n-cir1+2;// cout<<cir1<<' '<<cir2<<endl;vector<int>a(n+1);a[x]=0,a[y]=1;//第一个圈forr(i,x+1,y-1){a[i]=a[i-1]^1;}if(cir1&1)a[y-1]=2;//奇数a[y]=a[y-1] 就把相同a[y-1]的换成2//第二个圈int pre=y;forr(i,y+1,x+n-1){int id=i;if(i>n)id=i%n;// cout<<id<<endl;a[id]=a[pre]^1;pre=id;}if(cir2&1){if(x-1<1)a[x-1+n]=2;//注意绕圈else a[x-1]=2;}forr(i,1,n)cout<<a[i]<<' ';cout<<endl;
}