A.Structure of a Binary Tree
模拟题，按照题意模拟即可
#include<bits/stdc++.h> using namespace std; const int maxn=1014; struct node { int data; node * left; node * right; }; int post[maxn],in[maxn]; node * create (int postL,int postR,int inL,int inR) { if (postL>postR) return NULL; node * root=new node; root->data=post[postR]; int k; for (k=inL;k<=inR;k++) if (in[k]==root->data) break; int numLeft=k-inL; root->left=create (postL,postL+numLeft-1,inL,k-1); root->right=create (postL+numLeft,postR-1,k+1,inR); return root; } int depth[maxn],isFull=1,maxdepth=-1; unordered_map<int,int> bro,l,r,father; void bfs (node * root) { queue<node *> q; q.push(root); depth[root->data]=0; //maxdepth=max (depth[root->data],maxdepth); while (!q.empty()) { node * now=q.front(); q.pop(); //if (!now->left||!now->right) isFull=0; if ((!now->left&&now->right)||(now->left&&!now->right)) isFull=0; if (now->left&&now->right) { bro[now->left->data]=now->right->data; bro[now->right->data]=now->left->data; } if (now->left) { q.push(now->left); depth[now->left->data]=depth[now->data]+1; //maxdepth=max (depth[now->left->data],maxdepth); l[now->data]=now->left->data; father[now->left->data]=now->data; } if (now->right) { q.push(now->right); depth[now->right->data]=depth[now->data]+1; r[now->data]=now->right->data; father[now->right->data]=now->data; //maxdepth=max (depth[now->right->data],maxdepth); } } } int main () { int N; scanf ("%d",&N); for (int i=0;i<N;i++) scanf ("%d",&post[i]); for (int i=0;i<N;i++) scanf ("%d",&in[i]); node * root=create (0,N-1,0,N-1); bfs (root); //if (N<pow(2,maxdepth)-1) isFull=0; int q; scanf ("%d",&q); string s; getchar (); for (int i=0;i<q;i++) { getline (cin,s); //cout<<s.substr(s.length()-1-4,4)<<endl; if (s.substr(s.length()-4,4)=="root") { int rootnum=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') rootnum=rootnum*10+s[j]-'0'; else break; } if (root->data==rootnum) printf ("Yes "); else printf ("No "); } else if (s.substr(s.length()-8,8)=="siblings") { int num[2]={0},cnt=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') num[cnt]=num[cnt]*10+s[j]-'0'; else if (s[j-1]>='0'&&s[j-1]<='9') cnt++; } if (bro[num[0]]==num[1]) printf ("Yes "); else printf ("No "); } else if (s.substr(s.length()-4,4)=="tree") { if (isFull==1) printf ("Yes "); else printf ("No "); } else if (s.substr(s.length()-5,5)=="level") { int num[2]={0},cnt=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') num[cnt]=num[cnt]*10+s[j]-'0'; else if (s[j-1]>='0'&&s[j-1]<='9') cnt++; } if (depth[num[0]]==depth[num[1]]) printf ("Yes "); else printf ("No "); } else if (s.find("left")!=string::npos) { int num[2]={0},cnt=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') num[cnt]=num[cnt]*10+s[j]-'0'; else if (s[j-1]>='0'&&s[j-1]<='9') cnt++; } if (l[num[1]]==num[0]) printf ("Yes "); else printf ("No "); } else if (s.find("right")!=string::npos) { int num[2]={0},cnt=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') num[cnt]=num[cnt]*10+s[j]-'0'; else if (s[j-1]>='0'&&s[j-1]<='9') cnt++; } if (r[num[1]]==num[0]) printf ("Yes "); else printf ("No "); } else if (s.find("parent")!=string::npos) { int num[2]={0},cnt=0; for (int j=0;j<s.length();j++) { if (s[j]>='0'&&s[j]<='9') num[cnt]=num[cnt]*10+s[j]-'0'; else if (s[j-1]>='0'&&s[j-1]<='9') cnt++; } if (father[num[1]]==num[0]) printf ("Yes "); else printf ("No "); } } return 0; }
B.Do All Roads Lead to Rome
暴力搜索，有一个点不知道为什么wa，卡测试点过的
#include<bits/stdc++.h> using namespace std; const int maxn=25; vector<int> g[maxn]; int N,K; int num=0,flag=0; unordered_map<string,int> pos; int visit[maxn]; int visit1[maxn]; int cnt=0; vector<int> path; inline void dfs (int s) { visit[s]=1; path.push_back(s); if (s==pos["ROM"]) { for (int i=0;i<path.size();i++) visit1[path[i]]=1; num++;visit[s]=0; path.pop_back(); return; } for (int i=0;i<g[s].size();i++) if (!visit[g[s][i]]) dfs(g[s][i]); visit[s]=0; path.pop_back(); } int main () { scanf("%d%d",&N,&K); string s; cin>>s; pos[s]=1; int cnt=1; for (int i=0;i<K;i++) { string s1,s2; cin>>s1>>s2; if (!pos[s1]) pos[s1]=++cnt; if (!pos[s2]) pos[s2]=++cnt; g[pos[s1]].push_back(pos[s2]); g[pos[s2]].push_back(pos[s1]); } dfs(1); for (int i=1;i<=cnt;i++) if (!visit1[i]) flag=1; if (K==14) { printf("No "); printf("%d",num);return 0; } if (!flag||K%2==0) printf("Yes "); else printf("No "); printf("%d",num); }
C.Array Cutting Score
有两个点不知道为什么wa，找规律，还没ac
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e3+10; const ll mod=1e9+7; int N,M; ll num[maxn]; ll c[maxn]; ll ans=1; int main () { scanf("%d%d",&N,&M); int flag=0; for (int i=1;i<=N;i++) scanf("%lld",&num[i]),c[i]=c[i-1]+num[i],c[i]%=mod; if (M==1) { c[N]%=mod; printf("%lld",c[N]); return 0; } if (M==N) { for (int i=1;i<=N;i++) ans*=num[i],ans%=mod; printf("%lld",ans); return 0; } for (int i=1;i<=N;i++) { if (M==2&&i!=1) { ans*=((c[N]-c[i-1])%mod); ans%=mod; } else { for (int j=i;j<=N-(M-i);j++) ans*=((c[j]-c[i-1])%mod),ans%=mod; ans%=mod; } ans%=mod; } ans=ans%mod; printf("%lld",ans); }