A.直接做。
1 #include<vector> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 7 typedef long long ll; 8 using namespace std; 9 10 const int N=100010; 11 int n,m,a[N],cnt[N],tot; 12 vector<int> pos[N]; 13 ll ans; 14 15 int main(){ 16 scanf("%d%d",&m,&n); 17 rep(i,1,n) scanf("%d",&a[i]),pos[a[i]].push_back(i); 18 rep(i,1,m){ 19 if (i>1){ 20 if (pos[i].empty()) ans++; 21 else{ 22 int x=pos[i][0]; 23 if (pos[i-1].empty() || pos[i-1][pos[i-1].size()-1]<x) ans++; 24 } 25 } 26 if (pos[i].empty()) ans++; 27 if (i<m){ 28 if (pos[i].empty()) ans++; 29 else{ 30 int x=pos[i][0]; 31 if (pos[i+1].empty() || pos[i+1][pos[i+1].size()-1]<x) ans++; 32 } 33 } 34 } 35 cout<<ans<<endl; 36 return 0; 37 }
B.显然转的角度是n的约数，枚举约数暴力判断是否合法即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 using namespace std; 6 7 const int N=100010; 8 int n,m,x,y; 9 vector<int>E[N]; 10 11 vector<int>work(vector<int>a,int b){ 12 int sz=a.size(),p=0; 13 rep(i,1,sz-1) if((a[i]+b)%n<(a[p]+b)%n)p=i; 14 vector<int>c(sz); 15 rep(i,p,sz-1) c[i-p]=(a[i]+b)%n; 16 rep(i,0,p-1) c[i+sz-p]=(a[i]+b)%n; 17 return c; 18 } 19 20 int main(){ 21 scanf("%d%d",&n,&m); 22 rep(i,1,m) scanf("%d%d",&x,&y),x--,y--,E[x].push_back(y),E[y].push_back(x); 23 rep(i,0,n-1) sort(E[i].begin(),E[i].end()); 24 rep(k,1,n-1) if (n%k==0){ 25 int flag=1; 26 rep(i,0,n-1) if (work(E[i],k)!=E[(i+k)%n]){ flag=0; break; } 27 if (flag){ puts("Yes"); return 0; } 28 } 29 puts("No"); 30 return 0; 31 }
C.数据范围明显欺诈，讲一下我的思路，不是严谨证明。尝试从最终局面倒推：
最后局面：有石子的堆数小于n/2。（必败）
倒数第二步：至少有一堆没有石子，这样就可以通过拿走n/2堆的全部石子来转移到最终局面。（必胜）
倒数第三步：所有堆都有石子，且至少有n/2+1个堆的石子个数为1。因为面临此局面的人一定不希望制造出一个没有石子的堆，只有迫不得已的情况下才会制造出，也就是所选堆中有至少一个堆只有一个石子。（必败）
倒数第四步：至少有一堆有且仅有一个石子，这样就可以通过让另外n/2堆都只剩一个石子来达到倒数第三步的局面。（必胜）
倒数第五步：至少有n/2+1个堆的式子个数为2，分析与倒数第三步类似。（必败）
根据上面的分析可以得出，当含有最小石子数的堆数超过半数时必败，否则必胜。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 typedef long long ll; 7 using namespace std; 8 9 const int N=110,inf=1e9; 10 int n,mn=inf,tot,a[N]; 11 12 int main(){ 13 scanf("%d",&n); 14 rep(i,1,n) scanf("%d",&a[i]),mn=min(mn,a[i]); 15 rep(i,1,n) if (a[i]==mn) tot++; 16 if (tot<=n/2) puts("Alice"); else puts("Bob"); 17 return 0; 18 }
D.显然b的位数就是|s|，枚举a的位数m。然后可以通过题目条件得到一些形如“a[i]与a[j]相同”“b[i]与b[j]相同”“a[i]与b[j]相同”“a[i]与b[j]不同”“a[i]为0/1”“b[i]为0/1”的约数。我的做法是，建立n+m+2个点分别表示b的每一位、a的每一位、0、1。对于“相同”约束连权值为0的边，“不同”约束连1边。若图中存在奇环或存在长度为偶数的0到1的路径时无解。否则对于一个连通块，确定其中一个值就可以确定所有值，而这个连通块的取值与连通块之外的点无关，于是答案就是2^(除0和1所在的连通块之外的连通块数)。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 7 typedef long long ll; 8 using namespace std; 9 10 const int N=2010,M=N*20,mod=998244353; 11 bool flag; 12 char s[N]; 13 int n,ans,cnt,h[N],vis[N],to[M],nxt[M],val[M]; 14 15 void add(int u,int v,int w){ 16 to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; 17 to[++cnt]=u; val[cnt]=w; nxt[cnt]=h[v]; h[v]=cnt; 18 } 19 20 void dfs(int x){ 21 For(i,x) if (~vis[k=to[i]]){ 22 if ((vis[x]^val[i])!=vis[k]){ flag=1; return; } 23 }else vis[k]=vis[x]^val[i],dfs(k); 24 } 25 26 int main(){ 27 scanf("%s",s+1); n=strlen(s+1); 28 rep(m,1,n-1){ 29 cnt=0; int res=1; flag=0; 30 rep(i,1,n+m+2) h[i]=0,vis[i]=-1; 31 add(n,n+m+2,0); add(m+n,n+m+2,0); 32 rep(i,1,n) add(i,n-i+1,0); 33 rep(i,1,m) add(i+n,m-i+1+n,0); 34 rep(i,1,m){ 35 if (s[n-i+1]=='0') add(i,i+n,0); 36 if (s[n-i+1]=='1') add(i,i+n,1); 37 } 38 rep(i,m+1,n){ 39 if (s[n-i+1]=='0') add(i,n+m+1,0); 40 if (s[n-i+1]=='1') add(i,n+m+2,0); 41 } 42 vis[n+m+1]=0; dfs(n+m+1); 43 if (vis[n+m+2]==0) continue; 44 vis[n+m+2]=1; dfs(n+m+2); 45 rep(i,1,n+m) if (vis[i]==-1) vis[i]=0,res=2*res%mod,dfs(i); 46 if (flag) continue; 47 ans=(ans+res)%mod; 48 } 49 printf("%d ",ans); 50 return 0; 51 }