就算是签到题也带点思维，第一次打cf，自己模拟了一下比赛，看着前3道都是签到题，2h内拼了老命居然只a了第三道，实在是惭愧。赛后补题，较少人a的就不管了，实力不够，等实力够了再去看，事半功倍。
A题到现在都没读懂具体题意，看着ac人数就知道是水题，懒得管它了，比赛让队友上就行了。
B：Long Number-（暴力）
比赛时理解错题意，以为全部都可以换，求最大，一直wa。赛后看题解原来是换一段区间，英语没学好真惨。
从高位开始，能换就换，到低位不能使数字变大就停止，先确定一段换的区间，在遍历一遍置换，输出。
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #include<string> #include<vector> #include<iostream> #include<cstring> #include<queue> #define inf 0x3f3f3f3f #define ll long long using namespace std; char a[15]; int n; int main() { while(scanf("%d",&n)!=EOF) { string s,ans=""; cin>>s; for(int i=1;i<=9;i++) { getchar(); scanf("%c",&a[i]); } int sta=-1,over=n-1;///换的起始下标和结束下标 for(int i=0;i<n;i++) { if(s[i]<a[ s[i]-'0' ] && sta==-1 ) sta=i; if(s[i]>a[ s[i]-'0'] && sta!=-1 ) { over=i-1; break; } } if(sta==-1)///没得换 cout<<s<<endl; else { for(int i=0;i<n;i++) { if( i>=sta && i<=over ) ans=ans+a[ s[i]-'0' ]; else ans=ans+s[i]; } cout<<ans<<endl; } } return 0; }
C1:Increasing Subsequence (easy version)-（贪心）
各个数不同，设构造数组的最后一个为last，
1.左右两边都大于last，贪心取较小者
2.一边大于last，取那一边
3.都小于last，退出
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #include<string> #include<vector> #include<iostream> #include<cstring> #include<queue> #define inf 0x3f3f3f3f #define ll long long using namespace std; int n; int a[200005]; int main() { while(cin>>n) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=1,r=n; string ans=""; int sum=0,last=-1; while(l<=r) { if( l==r && a[l]>last)///最后一个，跟着样例取左 { last=a[l]; sum++; l++; ans=ans+"L"; } else if( a[l]>last && ( a[l]<a[r] || a[r]<last ) ) ///取左边的 { last=a[l]; sum++; l++; ans=ans+"L"; } else if( a[r]>last && ( a[r]<a[l] || a[l]<last ) ) { last=a[r]; sum++; r--; ans=ans+"R"; } else break; } cout<<sum<<" "<<ans<<endl; } return 0; }
C2：Increasing Subsequence (hard version)-（贪心+模拟）
记构造数组最后一个为last
1.左右都大于last
（1）左右不等，贪心取小（2）左右相等，只能选一边一条路走到黑，递增序列另一边回不去分别模拟这条路能走多远，取远的那边
2.一边大于last，取那一边
3.都小于last，退出
#include<algorithm> #include<cstring> #include<iostream> #include<math.h> #include<string> #include<stdio.h> #include<map> #include<queue> #define ll long long #define inf 0x3f3f3f3f using namespace std; int a[200086]; int n; int cnt1(int l,int r,int last)///模拟左边能走多远 { int res=0; while(l<=r && last<a[l]) { res++; last=a[l];///注意先赋值在自增自减，随便写栽了几分钟 l++; } return res; } int cnt2(int l,int r,int last)///模拟右边能走多远 { int res=0; while(l<=r && last<a[r]) { res++; last=a[r]; r--; } return res; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); int last=-1,sum=0,l=1,r=n; string ans=""; while(l<=r) { if(a[l]>last && a[r]>last)///左右都比last大 { if( a[l]>a[r] ) { last=a[r]; ans=ans+"R"; sum++; r--; } else if( a[l]<a[r] ) { last=a[l]; ans=ans+"L"; sum++; l++; } else { int num1=cnt1(l,r,last);///左边走到黑 int num2=cnt2(l,r,last);///右边走到黑 if(num1>num2) { while(l<=r && a[l]>last) { last=a[l]; ans=ans+"L"; sum++; l++; } } else///相等也是选右边，看样例3是选右，跟他走 { while(l<=r && a[r]>last) { last=a[r]; sum++; ans=ans+"R"; r--; } } } } else if( a[l]>last && a[r]<=last )///左边 { last=a[l]; ans=ans+"L"; sum++; l++; } else if( a[r]>last && a[l]<=last )///右边 { last=a[r]; ans=ans+"R"; sum++; r--; } else break; } cout<<sum<<" "<<ans<<endl; } return 0; }
E：Minimum Array（set+二分）
把数组bi放进集合se里，multiset可以存储重复元素。
对于ci=(ai+bi)%n，要求序列最小，显然从0开始。
对于每个ai，找一个bi和它相加使得ci最小，举例说明
比如n=20
(1)ai=15，为了使ci最小，最优是0，其次是1，再其次是2...
则bi最优取5，其次是6，再其次是7...
假设x=n-ai=5，x是最优解，找得到最好，没有就找一个就比它大一点点的就行，se.lower_bound(x)用二分查找找到最优的bi
(2)ai=0,为了使ci最小，最优是0，其次是1，再其次是2...
则bi最优取0（bi范围只能是0-19），其次是1，再其次是2...
假设x=n-ai=20,x是最优解，但在0-19的集合里，20是不存在的，返回的迭代器end()为空。要么判空要么...
解决措施：多插入一个巨大的数inf，找不到20就会找inf，显然越过最后一个回到第一个才是最优解，特判再令迭代器指向begin(),取最小的元素。
遍历形成ci数组后输出，时间复杂度O(n*logn)
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #include<string> #include<vector> #include<iostream> #include<cstring> #include<map> #include<queue> #include<set> #define inf 0x3f3f3f3f #define ll long long using namespace std; int n,x,r; int a[200005]; int b[200005]; int c[200005]; int main() { while(cin>>n) { multiset<int>se;///和set不同，可以有重复元素 for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) { scanf("%d",&b[i]); se.insert(b[i]); } se.insert(inf); for(int i=0;i<n;i++) { int x=n-a[i]; set<int>::iterator it=se.lower_bound(x); if(*it==inf) it=se.begin(); c[i]=(*it+a[i])%n; se.erase(it);///用se.erase(*it)会出错？？？ } for(int i=0;i<n;i++) printf("%d ",c[i]); printf(" "); } return 0; } /** 用GNU G++14 6.4.0提交 用Microsoft Visual C++ 2010提交编译错误 */