A题
模拟题,就是从每个i开始看看是否能找到这一串
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; char a[200][200]; int cnt[N]; int st[200][200]; int dx[]={-1,-2,1,2,1,2,-1,-2}; int dy[]={-2,-1,-2,-1,2,1,2,1}; int n; string res=" ICPCASIASG"; bool dfs(int x,int y,int cnt){ int i; if(cnt==11){ return true; } for(i=0;i<8;i++){ int tmpx=x+dx[i]; int tmpy=y+dy[i]; if(tmpx<0||tmpx>=n||tmpy<0||tmpy>=n) continue; if(a[tmpx][tmpy]==res[cnt]){ if(dfs(tmpx,tmpy,cnt+1)) return true; } } return false; } int main(){ ios::sync_with_stdio(false); cin>>n; int i,j; string s; cin>>s; for(i=0;i<n;i++){ for(j=0;j<n;j++){ a[i][j]=s[i*n+j]; } } int flag=0; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[i][j]=='I'){ if(dfs(i,j,2)){ flag=1; break; } } } if(flag){ break; } } if(flag){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } }View Code
B题
原来是递减,现在是递增,说明转化的位置是固定的
因此用并查集维护互换的集合,看看是否所有的都能换到
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int n,k; int a[N],b[N]; int p[N]; int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } int main(){ ios::sync_with_stdio(false); int i; cin>>n>>k; for(i=1;i<=n;i++){ p[i]=i; } for(i=1;i<=k;i++){ cin>>a[i]>>b[i]; int pa=find(a[i]); int pb=find(b[i]); if(pa!=pb){ p[pa]=pb; } } int flag=0; for(i=1;i<=n;i++){ int pa=find(i); int pb=find(n-i+1); if(pa!=pb){ flag=1; break; } } if(flag){ cout<<"No"<<endl; } else{ cout<<"Yes"<<endl; } }View Code
D题
模板题,找一下桥然后dfs一下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10,M=2e6+10; int h[N],ne[M],e[M],idx; int scnt,cnt[N],ins[N],in[N]; stack<int> q; int id[N],dfn[N],low[N]; int times; int f[N]; int isce[M]; int st[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u){ dfn[u]=low[u]=++times; int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!dfn[j]){ f[j]=u; tarjan(j); low[u]=min(low[u],low[j]); if(dfn[u]<low[j]) isce[j]=1; } else if(j!=f[u]) low[u]=min(low[u],dfn[j]); } } int ans=0; void dfs(int u,int fa){ int i; ans++; st[u]=1; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa||isce[j]) continue; if(st[j]) continue; dfs(j,u); } } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int i; int n,m; cin>>n>>m; for(i=1;i<=m;i++){ int a,b; cin>>a>>b; add(a,b); add(b,a); } tarjan(0); dfs(0,-1); cout<<ans<<endl; }View Code
E题
这题本来想的是二分check然后状压一下
但是发现状态有点多,但是二分很显然,那么其实可以转化为二分图,求最大流
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e6+10; const int M=2e6+10; const int inf=0x3f3f3f3f; int n,E; int h[N],ne[N],e[N]; int f[N],idx; int c[N]; int S,T; int d[N],cur[N]; int a[200][200]; int st[200][200]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++; e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++; } int bfs(){ memset(d,-1,sizeof d); d[S]=0; cur[S]=h[S]; queue<int> q; q.push(S); while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(d[j]==-1&&f[i]){ cur[j]=h[j]; d[j]=d[t]+1; if(j==T) return true; q.push(j); } } } return false; } int find(int u,int limit){ if(u==T){ return limit; } int i; int flow=0; for(i=cur[u];i!=-1&&flow<limit;i=ne[i]){ cur[u]=i; int j=e[i]; if(d[j]==d[u]+1&&f[i]){ int t=find(j,min(f[i],limit-flow)); if(!t) d[j]=-1; else{ f[i]-=t; f[i^1]+=t; flow+=t; } } } return flow; } int dinic(){ int flow; int r=0; while(bfs()){ while(flow=find(S,inf)) r+=flow; } return r; } bool check(){ S=0,T=2*n+1; idx=0; memset(h,-1,sizeof h); int i,j; for(i=1;i<=n;i++){ add(S,i,1); } for(i=n+1;i<=2*n;i++){ add(i,T,1); } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(st[i][j]){ add(i,n+j,1); } } } return dinic()>=n; } int main(){ ios::sync_with_stdio(false); cin>>n; int i,j; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>a[i][j]; } } int l=1,r=1e6; while(l<r){ int mid=l+r+1>>1; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ st[i][j]=0; if(a[i][j]>=mid) st[i][j]=1; } } if(check()){ l=mid; } else{ r=mid-1; } } cout<<l<<endl; }View Code
F题
分块思路,用sqrt作为分界线,大于他的暴力处理
而小于他的先预处理,之后查询即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e6+10; const int M=2e6+10; const int inf=0x3f3f3f3f; ll cnt[510][510]; int block; ll d[N]; int main(){ ios::sync_with_stdio(false); int n,q; cin>>n>>q; int i; block=sqrt(n); while(q--){ int opt; cin>>opt; if(opt==1){ int a,b,c; cin>>a>>b>>c; if(b<=block) cnt[b][a]+=c; else{ for(i=a;i<=n;i+=b){ d[i]+=c; } } } else{ int a; cin>>a; ll ans=d[a]; for(i=1;i<=block;i++){ ans+=cnt[i][a%i]; } cout<<ans<<endl; } } }View Code
H题
模拟题,就是把图形转化一下,然后建图爆搜,处理出有几条边