题目链接

A. Shell Game

题意：一个游戏，有三个位置为 左 中 右，分别对应三张牌 0 1 2，奇数次交换左和中的数字 ，偶数次交换中和右的数字。问第n轮之后第x个位置的数字是多少。

题解：直接草稿纸上模拟一遍，发现每6轮一个循环。(0打成6了，wa了两发qwq)

#include<bits/stdc++.h> using namespace std; int main() { long long n,k; cin>>n>>k; n=n%6; if(n==0) n=6; if(k==0){ if(n<=2) puts("1"); else if(n<=4) puts("2"); else puts("0"); } else if(k==2){ if(n==3||n==2) puts("0"); else if(n==4||n==5) puts("1"); else puts("2"); } else { if(n==1||n==4) puts("0"); else if(n==2||n==5) puts("2"); else puts("1"); } }

 

 

B. Game of Credit Cards

题意：有两个人有两个长度相等的序列。在第i位上，如果第一个人的数字大于第二个人的，那么第一个人获得一个flicks，反之第二个人获得一个flicks。现在你可以对第二个序列进行任意排序，问怎样排序，可以使得第二个人获得的flicks最少。怎样排序，可以使得第一个人获得的flicks最多。这两个问题的排序方法可以不同。

题解：贪心题。虽然题目要求只能对第二个序列进行排序，但其实也可以对第一个序列进行排序(对第一个序列进行排序，就相当于对第二个序列进行排序，仔细想想)。于是将两个序列都从小到大排序。对于第一个问题：遍历第一个序列a数组，从第二个序列找出剩下的数中第一个大于等于a[i]的。第二个问题：找出第一个大于a[i]的就行了。

#include<bits/stdc++.h> using namespace std; const int maxn =1010; char s1[maxn],s2[maxn]; int a1[maxn],a2[maxn]; int main() { int n; cin>>n>>s1+1>>s2+1; for(int i=1;i<=n;i++) { a1[i]=s1[i]-'0'; a2[i]=s2[i]-'0'; } sort(a1+1,a1+1+n); sort(a2+1,a2+1+n); int ans1=1,ans2=1; for(int i=1;i<=n;i++){ if(a2[i]>=a1[ans1]) ans1++; } for(int i=1;i<=n;i++){ if(a2[i]>a1[ans2]) ans2++; } cout<<n-ans1+1<<endl; cout<<ans2-1<<endl; }

 

 

C. Alyona and Spreadsheet

题意：给你一个二维数组，有q个询问，每个询问给出L和R，问第L行到第R行是否存在至少一列的元素递增。

题解：先预处理出每一行所能到的最远距离，然后以O(1)的时间输出就行了。具体预处理方法看代码。

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int c[maxn],d[maxn]; int main() { int n,m; cin>>n>>m; int a[n+5][m+5]={0}; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; int k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ k=i; if(d[j]>=i) k=d[j];//如果d[j]大于i，说明这个元素还在这个递增序列中。 else while(a[k+1][j]>=a[k][j]&&k<n) k++;//找到这个元素能到的最远距离 d[j]=k;//d[j]代表第j列能达到的最远距离 c[i]=max(k,c[i]);//c[i]代表第i行能到的最远距离 } } int q,l,r; cin>>q; while(q--){ cin>>l>>r; puts(c[l]>=r?"Yes":"No"); } }

 

 

D. Cloud of Hashtags

题意：删除最少的字符，使得这n个字符串以字典序排序。

题解：从后往前更新答案，对于第i个字符串以及第i+1个字符串。如果s[i][j]>s[i+1][j],那就直接从这里截断。如果s[i][j]<s[i+1][j]，那就保存这整个字符串。我定义了一个数组len来存入每个字符串合法的长度。建议使用string，用char会爆内存，或者因为长度不够导致wrong answer。

#include<bits/stdc++.h> using namespace std; const int maxn = 5e5+100; string s[maxn]; int len[maxn]; int main() { int n; cin>>n; int cur=0; for(int i=1;i<=n;i++) cin>>s[i],len[i]=s[i].size()-1;//保存每个字符串的长度 for(int i=n-1;i>=1;i--){ int flag=1; for(int j=1;j<=min(len[i+1],len[i])&&flag;j++){ if(s[i+1][j]>s[i][j]) flag=0; if(s[i+1][j]<s[i][j]) { len[i]=j-1; flag=0; } } if(flag) len[i]=min(len[i],len[i+1]);//如果flag=1，说明两个字符串前部分是相同的，截取相同的部分 if(len[i]==0) {//如果某个字符串已经是空串了，那前面的也就无法更新1了 cur=i; break; } } for(int i=cur;i>=1;i--) len[i]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=len[i];j++) printf("%c",s[i][j]); puts(""); } }

 

 

E. Hanoi Factory

题意：有n个圆盘，每个原盘有对应的内径，外径以及高度。圆盘能叠加到一起，前提是上面的圆盘的外径小于等于下面的外径，并且大于下面的内径，问怎样叠放可以使圆盘最高。

题解：贪心，先对外径b从大到小排序，b相同的要按照a从大到小排序，这样就能使得b相同的圆盘，最上一层的内径最小，所能再放的圆盘的外径范围最大。可以使用栈来模拟，对于一个圆盘，如果不能再放进去了，那么他后面的圆盘也肯定不能再放进去，那么我们要把之前的圆盘拿出来，直到找到一个满足要求的圆盘。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+10; struct node{ ll a,b,h; bool friend operator < (node c,node d){ if(c.b==d.b) return c.a>d.a; return c.b>d.b; } }e[maxn]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>e[i].a>>e[i].b>>e[i].h; sort(e+1,e+1+n); stack<node>s; ll ans=0,sum=0; for(int i=1;i<=n;i++){ while(!s.empty()&&e[i].b<=s.top().a){ sum-=s.top().h; s.pop(); } sum+=e[i].h;//保存栈里圆盘的高度 ans=max(ans,sum);//更新答案 s.push(e[i]); } cout<<ans<<endl; }