A 签到
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int main(){ 5 ll n,k; 6 cin>>n>>k; 7 ll ans=n/k; 8 if(ans%2==1){ 9 cout<<"YES"; 10 } 11 else cout<<"NO"; 12 }
B 模拟题，注意细节即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 bool zi[26]; 5 int main(){ 6 string s,t,tt; 7 cin>>s>>t; 8 for(int i=0;i<s.size();i++){ 9 zi[s[i]-'a']=true; 10 } 11 int n; 12 cin>>n; 13 for(int i=0;i<n;i++){ 14 cin>>tt; 15 int aa=0,kk; 16 bool f1=true; 17 18 for(int j=0;j<t.size();j++){ 19 kk=j+aa; 20 if(t[j]!='?'&&t[j]!='*'&&t[j]!=tt[kk]){ 21 cout<<"NO "; 22 f1=false; 23 break; 24 } 25 26 if(t[j]=='?'){ 27 bool flag=false; 28 if(zi[tt[kk]-'a']) flag=true; 29 if(flag) continue; 30 else{ 31 cout<<"NO "; 32 f1=false; 33 break; 34 } 35 } 36 if(t[j]=='*'){ 37 int len=tt.size()-t.size(); 38 if(len<-1){ 39 cout<<"NO "; 40 f1=false; 41 break; 42 } 43 if(len==-1){ 44 aa--; 45 continue; 46 } 47 bool flag=false; 48 for(int k=0;k<=len;k++){ 49 if(zi[tt[k+kk]-'a']){ flag=true;break;} 50 } 51 if(flag){ 52 cout<<"NO "; 53 f1=false; 54 break; 55 } 56 else{ 57 aa+=len; 58 continue; 59 } 60 } 61 if(j==t.size()-1&&kk!=tt.size()-1){ 62 cout<<"NO "; 63 f1=false; 64 break; 65 } 66 } 67 if(f1) cout<<"YES "; 68 } 69 }
C
D LCA模板以及距离的求法，注意用O（n）的模板会超时，据说树链剖分也可做。
1 #include<bits/stdc++.h> 2 #define maxv 100005 3 using namespace std; 4 typedef long long ll; 5 vector<int>G[maxv]; 6 int root; 7 int parent[20][maxv]; 8 int depth[maxv]; 9 int a,b,c; 10 int n,q,t; 11 void dfs(int v,int p,int d){ 12 parent[0][v]=p; 13 depth[v]=d; 14 for(int i=0;i<G[v].size();i++){ 15 if(G[v][i]!=p) dfs(G[v][i],v,d+1); 16 } 17 } 18 19 void init(){ 20 dfs(0,-1,0); 21 for(int k=0;k+1<20;k++){ 22 for(int v=0;v<n;v++){ 23 if(parent[k][v]<0) parent[k+1][v]=-1; 24 else parent[k+1][v]=parent[k][parent[k][v]]; 25 } 26 } 27 } 28 29 int lca(int u,int v){ 30 if(depth[u]>depth[v]) swap(u,v); 31 for(int k=0;k<20;k++){ 32 if((depth[u]-depth[v])>>k&1){ 33 v=parent[k][v]; 34 } 35 } 36 if(u==v) return u; 37 for(int k=20-1;k>=0;k--){ 38 if(parent[k][u]!=parent[k][v]){ 39 u=parent[k][u]; 40 v=parent[k][v]; 41 } 42 } 43 return parent[0][u]; 44 } 45 int dis(int a,int b,int u){ 46 return depth[a]+depth[b]-2*depth[u]; 47 } 48 int main(){ 49 cin>>n>>q; 50 for(int i=0;i<n-1;i++){ 51 cin>>t; 52 G[i+1].push_back(t-1); 53 G[t-1].push_back(i+1); 54 } 55 init(); 56 for(int j=0;j<q;j++){ 57 cin>>a>>b>>c; 58 a-=1; 59 b-=1; 60 c-=1; 61 int v1,v2,v3; 62 v1=lca(a,b); 63 v2=lca(b,c); 64 v3=lca(c,a); 65 int ab,bc,ac; 66 ab=dis(a,b,v1); 67 bc=dis(b,c,v2); 68 ac=dis(a,c,v3); 69 int ans=max(max(ab+bc-ac,bc+ac-ab),ac+ab-bc)/2+1; 70 printf("%d ",ans); 71 } 72 return 0; 73 }
E待补