B.
按要求建图，判欧拉路径
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; //vector<int> g[maxn]; int N,M; int T; int x; char s[maxn]; int inDegree[maxn]; int father[maxn]; int isRoot[maxn]; int findfather(int x) { int a=x; while(x!=father[x]) x=father[x]; while(a!=father[a]) { int z=a; a=father[a]; father[z]=x; } return x; } void Union (int a,int b) { int faA=findfather(a); int faB=findfather(b); if (faA!=faB) father[faA]=faB; } int main () { scanf("%d",&T); while(T--) { memset(inDegree,0,sizeof(inDegree)); memset(isRoot,0,sizeof(isRoot)); scanf("%d %d",&N,&M); for (int i=0;i<N*M;i++) father[i]=i; for (int i=0;i<N;i++) for (int j=0;j<M;j++) cin>>s[i*M+j]; for (int i=0;i<N;i++) { for (int j=0;j<M;j++) { scanf("%d",&x); if (s[i*M+j]=='u') { if (i-x<0) continue; inDegree[(i-x)*M+j]++; Union(i*M+j,(i-x)*M+j); } else if (s[i*M+j]=='d') { if (i+x>=N) continue; inDegree[(i+x)*M+j]++; Union(i*M+j,(i+x)*M+j); } else if (s[i*M+j]=='l') { if (j-x<0) continue; inDegree[(i*M+j-x)]++; Union(i*M+j,i*M+j-x); } else if (s[i*M+j]=='r') { if (j+x>=M) continue; inDegree[i*M+j+x]++; Union(i*M+j,i*M+j+x); } } } int ans=0; for (int i=0;i<N*M;i++) isRoot[findfather(i)]++; for (int i=0;i<N*M;i++) if (isRoot[i]) ans++; //printf("%d\n",ans); if (ans>1) { printf("No\n"); continue; } int cnt=0; for (int i=0;i<N*M;i++) { if (inDegree[i]==0) cnt++; } if (cnt>=2) printf("No\n"); else printf("Yes\n"); } return 0; }
C.
构造
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; typedef long long ll; ll a[5]; string s; int main () { int T; scanf("%d",&T); while (T--) { for (int i=0;i<4;i++) a[i]=0; cin>>s; ll len=s.length(); for (int i=0;i<len;i++) { if (s[i]=='0') a[0]++; if (s[i]=='6') a[1]++; if (s[i]=='8') a[2]++; if (s[i]=='9') a[3]++; } ll ans=(1+len)*(ll)len/2+1; ans-=(1+a[0])*a[0]/2;//0 ans-=(1+a[2])*a[2]/2;//8 ans-=a[1]*a[3];//69 if (a[1]==len||a[3]==len) ans--; printf("%lld\n",ans); } return 0; }
D.
套个二分
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; string s; int a[maxn]; int b[maxn]; int len; int cal (int l) { int ans=0; for (int i=1;i<=len;i++) { if (a[i]==1) { ans++; for (int j=i;j<i+l;j++) if (a[j]) a[j]=0; } } return ans; } int main () { int T,N,K; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&K); memset(a,0,sizeof(a)); cin>>s; for (int i=1;i<=s.length();i++) a[i]=s[i-1]=='1',b[i]=a[i]; len=s.length(); int l=1; int r=len; while (l<r) { int mid=(l+r)>>1; for (int i=1;i<=len;i++) a[i]=b[i]; int ans=cal(mid); if (ans>K) l=mid+1; else { r=mid; } } printf("%d\n",l); } return 0; }
I.
DFS序列确定每个节点的限制区间，前缀和扫描确定根
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+14; struct node { int from; int to; int next; int c; }edge[maxn*3]; int head[maxn]; int tol; int dfn[maxn]; int dfo[maxn]; int N; int cnt; int l1[maxn]; int l2[maxn]; int l3[maxn]; int r1[maxn]; int r2[maxn]; int r3[maxn]; int xz[maxn]; int visit[maxn]; int qzh[maxn]; int a[maxn]; void init () { memset(head,-1,sizeof(head)); tol=0; cnt=0; memset(l1,0,sizeof(l1)); memset(l3,0,sizeof(l3)); memset(visit,0,sizeof(visit)); memset(xz,0,sizeof(xz)); } void addedge (int u,int v,int c) { edge[tol].from=u; edge[tol].to=v; edge[tol].c=c; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].c=c; edge[tol].next=head[v]; head[v]=tol++; } void dfs (int u) { visit[u]=1; dfn[u]=++cnt; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if (!visit[v]) dfs(v); } dfo[u]=cnt; } int check (int u) { int cnt[30]={0}; for (int i=head[u];i!=-1;i=edge[i].next) cnt[edge[i].c]++; int sum=0; for (int i=0;i<26;i++) { if (cnt[i]>2) return 0; if (cnt[i]==2) sum++; } if (sum>1) return 0; return 1; } int isTrie () { for (int i=1;i<=N;i++) if (!check(i)) return 0; return 1; } void getSeg (int u) { vector<int> a[30]; //int ck[26]={0}; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; a[edge[i].c].push_back(v); } for (int i=0;i<26;i++) { if (a[i].size()<2) continue; int t1=a[i][0]; int t2=a[i][1]; if (dfn[t1]>dfn[t2]) swap(t1,t2); //printf("%d %d\n",t1,t2); if (dfn[u]>dfn[t1]) { l1[u]=1; r1[u]=dfn[u]-1; l2[u]=dfn[t2]; r2[u]=dfo[t2]; l3[u]=dfo[u]+1; r3[u]=N; } else { l1[u]=dfn[t1]; r1[u]=dfo[t1]; l2[u]=dfn[t2]; r2[u]=dfo[t2]; } break; } //printf("%d %d %d %d\n",l1[u],r1[u],l2[u],r2[u]); } int main () { int T; scanf("%d",&T); int u,v; char ch; while (T--) { scanf("%d",&N); init(); for (int i=1;i<=N-1;i++) { scanf("%d %d %c",&u,&v,&ch); int c=ch-'a'; addedge(u,v,c); } if (!isTrie()) { printf("0\n");continue; } dfs(1); for (int i=1;i<=N;i++) getSeg(i); int root=0; int ck=0; memset(qzh,0,sizeof(qzh)); memset(a,0,sizeof(a)); for (int i=1;i<=N;i++) { if (!l1[i]) { ck++;continue; } qzh[l1[i]]++; qzh[r1[i]+1]--; qzh[l2[i]]++; qzh[r2[i]+1]--; if (!l3[i]) continue; qzh[l3[i]]++; qzh[r3[i]+1]--; } int sum=0; for (int i=1;i<=N;i++) { sum+=qzh[i]; a[i]+=sum; if (a[i]==N-ck) root++; } printf("%d\n",root); } }