CF 979 Review
喜闻乐见的C题不锻炼码力的场，可惜早早地做完了C之后就开始想D，到最后知道怎么做了，但是写不来代码。
实际上还是脑子不够好使，想不出来简单的写法；只有复杂的思路，但却没有相应的码力。
A
分析
很明显的一个贪心，注意考虑一下边界条件即可。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
inline void out(int x){wr(x),putchar('\n');}
int n,m,T;
int main()
{re(T);int tmp;while(T--){re(n);int mx=-1,mn=1000000,s=0;for(int i=1;i<=n;++i){cin>>tmp;s+=tmp;mx=max(mx,tmp);mn=min(mn,tmp);}out(n*(mx-mn)-mx+mn);}return 0;}
B
分析
推式子题，用到了组合数的求和公式，也还是比较容易，最后得到的结论就是输出 \(n-1\) 个 \(0\) ，注意特判一下 \(n=1\) 的情况即可。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
inline void out(int x){wr(x),putchar('\n');}
int n,m,T;
int main()
{re(T);while(T--){re(n);if(n==1){puts("0");}else{for(int i=1;i<=n-1;++i)putchar('0');puts("1"); }}return 0;}
C
很好的一道思维题博弈论
分析
首先如果端位有 \(1\) 那么肯定是先手赢。
开始的想法是，对于两人中的任意一个人来说，在 \(11\) 中间进行操作都是没有意义的，所以整个串可以缩写为 \(010101...1010\) 的形式。
这样看来那么先手不论下在哪里，后手都可以使得先手这一步变得无效，最后一定是后手赢。
交上去发现 WA 了。
问题在于缩写的这个过程并不恰当。
假设有一个 \(0110\) 的串，如果先手在最中间放一个，那么后手无论堵哪一个，下一个先手都可以再放一个 "|" 使得有一个 \(1\) 被完全包含，也就是最终的答案一定是 \(1\) 。推而广之，只要有若干个连续的 \(1\) ，就一定能赢。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
inline void out(int x){wr(x),putchar('\n');}
int n,m,T;
char s[200010];
int main()
{re(T);while(T--){re(n);scanf("%s",&s);if(s[0]=='1'||s[n-1]=='1'){puts("YES");goto A;}else {for(int i=1;i<n;++i){if(s[i]==s[i-1]&&s[i]=='1'){puts("YES");goto A;}}}puts("NO");A:;}return 0;}
D
分析
很早就推出了一个结论：任意的 \(RRRRR...RLLLLL...L\) 一定可以通过冒泡排序的原理来使得整个子序列达到有序。
言下之意就是，\(LR\) 对应的一定是一个断点 ，左边无法往右，右边无法往左，我们不妨用左边的 \(L\) 对应的下标来代表这个断点所在的位置。
想让这个排列变得有序，我们必须让所有元素回到其对应的位置上，设一个元素 \(x\) 现在的位置是 \(pos\) ，那么它应该回到 \(x\) 的下标上。
也就是说我们需要 从 \(idx\rightarrow x\) 的路径上是不间断的，在我们对断点的定义下，要求 \(idx\rightarrow(x-1)\) 的路径中所有下标都不能是断点。
并且对于每一个元素都必须有以上性质成立。
那么我们可以维护有哪些点被至少一条路径依赖，并把其中所有断点丢进一个set中，在修改操作的时候动态地进行插入和删除。
如果在操作过后set里面没有断点，也就是说所有路径都是畅通的，这时候答案就是yes，否则就是no。
盲区
scanf字符串的时候不要加取地址！！！
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
inline void out(int x){wr(x),putchar('\n');}
int n,m,T,q,pos;
char upd[200010];
int a[200010],s[200010];
int main()
{re(T);while(T--){re(n),re(q);for(register int i=1;i<=n;++i)s[i]=0;for(register int i=1;i<=n;++i){re(a[i]);s[min(i,a[i])]++;s[max(i,a[i])]--; }scanf("%s",upd+1);set<int> err; for(register int i=1;i<=n;++i){s[i]+=s[i-1];if(upd[i]=='L'&&upd[i+1]=='R'&&i!=n&&s[i])err.insert(i);}
// for(register int i=1;i<=n;++i)cout<<s[i]<<' ';
// cout<<endl;auto modify=[&](int pos){if(upd[pos]=='L'){if(upd[pos+1]=='R'&&pos!=n&&err.count(pos))err.erase(pos);if(upd[pos-1]=='L'&&pos!=1&&s[pos-1])err.insert(pos-1);upd[pos]='R';}else {if(upd[pos-1]=='L'&&pos!=1&&err.count(pos-1))err.erase(pos-1);if(upd[pos+1]=='R'&&pos!=n&&s[pos])err.insert(pos); upd[pos]='L';}};while(q--){re(pos);modify(pos); puts(err.empty()?"YES":"NO");}}return 0;} /*3
5 3
1 4 2 5 3
RLRLL
2
4
3
8 5
1 5 2 4 8 3 7 6
RRLLRRRL
4
3
5
3
4
6 2
1 2 3 4 5 6
RLRLRL
4
5*/
总结
非常紧迫的一个问题就是要强化自己的代码实现能力，可以去学一些巧妙的stl用法等。
