A. Shell Game
题意：给定n个操作奇数操作可以把在0和1之间交换，偶数个操作可以在1和2之间交换，给出最后的位置，求最开始的位置。
思路：打表找规律。。。。。
#include<bits/stdc++.h> using namespace std; int main(){ int n,x; /*while(~scanf("%d%d",&n,&x)){ while(n){ if(n%2){ if(x==0) x=1; else if(x==1) x=0; n--; } else{ if(x==1) x=2; else if(x==2) x=1; n--; } }*/ scanf("%d%d",&n,&x); int ans; if(n%2==0){ if((n%3)==2){ if(x==0) puts("1"); else if(x==1) puts("2"); else if(x==2) puts("0"); } else if((n%3)==1){ if(x==0) puts("2"); else if(x==1) puts("0"); else if(x==2) puts("1"); } else if((n%3)==0){ if(x==0) puts("0"); else if(x==1) puts("1"); else if(x==2) puts("2"); } } else{ if((n%3)==1){ if(x==0) puts("1"); else if(x==1) puts("0"); else if(x==2) puts("2"); } else if((n%3)==0){ if(x==0) puts("2"); else if(x==1) puts("1"); else if(x==2) puts("0"); } else if((n%3)==2){ if(x==0) puts("0"); else if(x==1) puts("2"); else if(x==2) puts("1"); } } //printf("%d\n",x); }B. Game of Credit Cards
题意：给定两个相等长度的字符串，如果对于位置i使得s1i<s2i那么你就不高兴，问使得第一个人不高兴的最小值已及使得第二个人不高兴的最大值。
思路：模拟即可，要使得最小肯定优先选等于的其次选大于的，要使得最大那么每次选第一个比他大的即可。
#include<bits/stdc++.h> using namespace std; int a[11],b[11]; int main(){ int n; string s,t; memset(a,0,sizeof(a)); scanf("%d",&n); cin>>s; cin>>t; for(int i=0;i<n;i++){ a[t[i]-'0']++; b[t[i]-'0']++; } int s1=n,s2=0; for(int i=0;i<n;i++){ if(a[s[i]-'0']>0){ a[s[i]-'0']--; s1--; } else{ for(int j=s[i]-'0'+1;j<=9;j++) if(a[j]>0){ a[j]--; s1--; break; } } } for(int i=0;i<n;i++){ for(int j=s[i]-'0'+1;j<=9;j++){ if(b[j]>0){ s2++; b[j]--; break; } } } printf("%d\n%d\n",s1,s2); }C. Alyona and Spreadsheet
题意：给定矩阵，k个提问，问l到r行的是否有一列非递减。
思路：模拟，每次看那一行能扩展到哪一行。用前缀和竟然wa100。。。
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; scanf("%d%d",&n,&m); int a[n+5][m+5]; int b[n+5][m+5]; int res[n+5]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=m;i++){ int s=1,p=0,f; while(s<n){ f=n,p=s; for(int j=s;j<n;j++){ if(a[j+1][i]<a[j][i]){ f=j; break; } } for(int j=s;j<=f;j++) b[j][i]=f; s=f+1; } } for(int i=1;i<=m;i++) b[n][i]=n; for(int i=1;i<=n;i++){ res[i]=0; for(int j=1;j<=m;j++){ res[i]=max(b[i][j],res[i]); } } for(int i=1;i<=n;i++) printf("%d\n",res[i]); int k; scanf("%d",&k); while(k--){ int l,r; scanf("%d%d",&l,&r); int f=0; if(res[l]>=r){ f=1; puts("Yes"); } if(f==0){ puts("No"); continue; } } }D. Cloud of Hashtags
题意：给定n给字符串，每次删除后缀，使得n个字符按字典序排列。
思路：二分。
#include<bits/stdc++.h> using namespace std; string s[500005]; void solve(string &s1,string &s2){ int l=1,r=s1.size(),m; string s; while(r-l>1){ s=s1; m=(l+r)/2; if(s.erase(m)<s2) l=m; else if(s.erase(m)>s2) r=m; else{ l=m+1; break; } } if(s1.erase(l)<=s2){ cout<<s1<<"\n"; s1.erase(l); } else s1.erase(l-1); } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) cin>>s[i]; for(int i=n-1;i>0;i--){ if(s[i-1]>s[i]){ solve(s[i-1],s[i]); } } for(int i=0;i<n;i++) cout<<s[i]<<"\n"; }E. Hanoi Factory
题意：给定一些圆环来堆汉络塔，问能堆的最高的高度：
思路：单调栈加贪心。
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ int a,b,h; }c[100005]; int cmp(node x,node y){ if(x.b==y.b) return x.a>y.a; return x.b>y.b; } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].h); sort(c,c+n,cmp); ll t1=c[0].h,ans=c[0].h; stack<node>s; s.push(c[0]); for(int i=1;i<n;i++){ while(!s.empty()&&s.top().a>=c[i].b){ t1-=s.top().h; s.pop(); } t1+=c[i].h; ans=max(ans,t1); s.push(c[i]); } printf("%lld\n",ans); }
