Codeforces Round 877 (Div. 2) ABCD

A. Blackboard List
solve:
1、生成的数一定不是负数，所以有负数的情况下，负数一定是原来的数。
2、没有负数的情况下，最大的数一定是原来的数，因为操作只能使数变小。

void solve()
{cin>>n;for(int i=0;i<n;i++)cin>>b[i];sort(b,b+n);if(b[0]<0){cout<<b[0]<<'\n';}else cout<<b[n-1]<<'\n';
}

B. Minimize Permutation Subarrays
1、在1和2的中间插n，这样使得子区间的排列只存在1本身及1-n的（整个区间）排列。

void solve()
{cin>>n;int pos1=0,pos2=0,pos3=0,posn=0;for(int i=1;i<=n;i++){cin>>b[i];if(b[i]==1)pos1=i;if(b[i]==2)pos2=i;if(b[i]==n)posn=i;}if((pos1<posn&&posn<pos2)||(pos2<posn&&posn<pos1)){cout<<pos1<<" "<<pos2<<'\n';}else if(posn<min(pos1,pos2)){cout<<posn<<" "<<min(pos1,pos2)<<"\n";}else if(posn>max(pos1,pos2)){cout<<posn<<" "<<max(pos1,pos2)<<'\n';}//在1和2之间插进一个n
}

C. No Prime Differences
1、n，m存在偶数的情况下，可以直接按顺序排。

形如：
4 5
1 5 9 13 17
2 6 10 14 18
3 7 11 15 19
4 8 12 16 205 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

2、n、m全为奇数。可以把先按顺序排，再把前n/2行 分别 插空放在剩下n/2+1行的 两行之间。

形如：
5 7
15 16 17 18 19 20 21
1 2 3 4 5 6 7
22 23 24 25 26 27 28
8 9 10 11 12 13 14
29 30 31 32 33 34 35
//把1所在的行以及8所在的行 分别插在 15与22所在行之间，及22与29所在行之间。

ll x[1005][1005];
void solve()
{cin>>n>>m;ll cnt=1;if(n%2==0){for(int j=1;j<=m;j++)for(int i=1;i<=n;i++)x[i][j]=cnt++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<x[i][j]<<" \n"[j==m];}else if(m%2==0){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)x[i][j]=cnt++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<x[i][j]<<" \n"[j==m];}else {for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)x[i][j]=cnt++;int y=n/2,z=0;for(int i=1;i<=n/2;i++){for(int j=1;j<=m;j++)cout<<x[y+i][j]<<" \n"[j==m];for(int j=1;j<=m;j++)cout<<x[z+i][j]<<" \n"[j==m];}for(int j=1;j<=m;j++)cout<<x[n][j]<<" \n"[j==m];}
}

D. Bracket Walk
先看题目规则：
给你一个长度为n的字符串，q次指定修改位置x。你现在可以从字符串第一个字符开始，左右随意走，结束的位置必须是字符串最后一个位置。问你走过形成的字符串，能不能实现括号匹配。

solve：
1、匹配情况应形如（）这样此时可以直接走。
2、什么时候需要折返？一边的括号不够，需要多凑几次，以便另一方配对的情况。
3、set容器记录 可以给 另一边括号缺少的情况下 提供括号的位置坐标。
4、（）形如此时，'(‘在偶数位，’)‘在 奇数位。（（））这样的情况可以提供贡献，只有（）不行。
5、所以，set存’(‘在奇数位，’)‘在 偶数位此时的坐标。
6、修改指定位置时，当set里若存在位置，那该位置的括号变成正确的，无法提供贡献。反之，可以提供贡献，折返可产生新的括号。
7、n为奇数时，（）无法成功匹配。
8、当set里有数，且最小位置的的括号为’)‘或最大位置的括号为’('时，无法匹配。

void solve()
{cin>>n>>m>>s;set<ll>st;for(ll i=0;i<n;i++){if(i%2==1&&s[i]=='(')st.insert(i);if(i%2==0&&s[i]==')')st.insert(i);}while(m--){ll pos;cin>>pos;pos--;if(st.count(pos)!=0)st.erase(pos);else st.insert(pos);if(n&1){cout<<"NO\n";}else if(st.size()!=0&&(*st.begin()%2==0||*st.rbegin()%2==1)){//cout<<(*st.rbegin())<<"* ";cout<<"NO\n";}else cout<<"YES\n";}}