场次链接

后悔啊后悔，当天晚上打的时候工作室网炸了，开场五分钟镜像页面才看到题目，A题读完就想到判断最前面和最后面能不能加就行了（字符串渣第一时间没想到直接在原字符串上加，反而去判断s[0]和s[n-1]等不等于’a’然后再写，饶了好大一圈）。写完了准备交的时候原网站也刷出来了，看了一下A过题人数已经有2300了，就没急着交，先去读了一下B和C，吗的读B的时候漏翻了一个prefix，以为可以在任意位置翻转，想了一下卧槽好像很复杂，不对劲啊，这场这么难吗？然后读了下C，发现是个字符串构造，想的时候刷新了一下题目列表，网又炸了，直接跑路 ^ - ^

第二天补题的时候，才发现B是前缀修改…C题在草稿纸上画了一下就发现了规律，D题互动题感觉也是送的，E题也写过类似的题，在知乎上刷ICPC昆明站相关回答的时候看到一个大二的同学这场上了200紫名了，tql，感觉最近cf都比较偏思维，DE的代码量都不大，希望学校网下次给个面子，开局慢五分钟太炸心态了……

A. Déjà Vu
题意：问是否可以在给出字符串中加一个’a’且不变成回文串，并把符合的情况输出出来。

思路：显然如果’a’加在最前面是回文串的话，那么加在最后面肯定就不是了（除了全是a的情况），所以两种情况判断一下如果加完都是回文串就说明是全’a’字符串。

这道有手就行就不贴代码了（其实是因为写的太臭了没脸放:)

B. Flip the Bits
题意：给两个01串，给一个操作可以把长度为x的前缀字符串中的01翻转（0变成1,1变成0），但是这个前缀字符串中的0和1的数量相等，问第一个字符串可不可以通过这个操作变成第二个字符串。

思路：因为操作次数是不限的，所以只要是符合条件的串都可以随意操作，那么每一段01数量相等的终点就是一个节点，节点之间的串就是可以操作的串，判断一下这些串是不是全部相同或者全部不相同即可。

#include<bits/stdc++.h>
#define LL long long
#define INF INT64_MAX
#define MOD 1000000007
#define stree SegTree[root]
#define lson SegTree[root << 1]
#define rson SegTree[root << 1 | 1]
using namespace std;
const int N = 300005;
char s[N], ss[N];
int main()
{int t, n;cin>>t;while(t--){cin>>n>>s>>ss;int tem = 0, a = 0, b = 0, fla = 0, cnt1 = 0, cnt0 = 0;for(int i = 0;i < n;i++){if(s[i]=='1') cnt1++;else cnt0++;if(s[i]==ss[i]){a++;}else if(s[i]!=ss[i]){b++;}if(cnt1==cnt0){if(a&&b){fla = 1;break;}else{cnt1=cnt0=a=b=0;}}}if(b) fla = 1;if(fla) printf("NO\n");else printf("YES\n");}return 0;
}

C. Balance the Bits

题意：给一个01字符串，让你构造两个由’(‘和’)'组成的合法字符串，1的位置要求两个串相同，0的位置要求两个串不同。

思路：构造题一定要多动手，这道题只要有0和1是偶数次并且起点和终点都是1就必然存在，0的情况一个串可以0跟0一起玩，另一个串就要跟起点和终点的1一起玩了，具体看代码吧，讲起来太复杂，动动手就通了。

#include<bits/stdc++.h>
#define LL long long
#define INF INT64_MAX
#define MOD 1000000007
#define stree SegTree[root]
#define lson SegTree[root << 1]
#define rson SegTree[root << 1 | 1]
using namespace std;
const int N = 300005;
char s[N];
int main()
{int t, n;cin>>t;while(t--){cin>>n>>s;string s1, s2;int cnt = 0, tem = 1;for(int i = 0;i < n;i++){if(s[i]=='0') cnt++;}if(s[0]!='1' || s[n-1]!='1' || cnt%2){printf("NO\n");continue;}bool f1 = 1, f2 = 1;s1+='(', s2+='(';for(int i = 1;i < n-1;i++){if(s[i]=='1'){if(f1){s1+='(';s2+='(';f1 = 0;}else{s1+=')';s2+=')';f1 = 1;}}else{if(tem <= cnt-2){if(f2){s1+='(';s2+=')';f2 = 0;}else{s1+=')';s2+='(';f2 = 1;}}else{if(f2){s1+=')';s2+='(';f2 = 0;}else{s1+='(';s2+=')';f2 = 1;}}tem++;}}s1+=')', s2+=')';cout<<"YES"<<endl<<s1<<endl<<s2<<endl;}return 0;
}

D. 3-Coloring

题意：互动题，有三个颜色，爱丽丝先选一个颜色，你要在n*n的棋盘上把一个格子涂成除了这个颜色以外的一个颜色，要求相邻边不能相同。

思路：互动题一般都是有规律的构造，找到定式就能很快写出来。这道题有点像下五子棋，斜着交叉放一个颜色，然后剩下的格子就可以另外两个颜色随便放了。代码有点长，但是当时写的时候顺着思路一下就写完了。

#include<bits/stdc++.h>
#define LL long long
#define INF INT64_MAX
#define MOD 1000000007
#define stree SegTree[root]
#define lson SegTree[root << 1]
#define rson SegTree[root << 1 | 1]
using namespace std;
const int N = 300005;
struct node
{int x, y;
}tem;
int main()
{int n, x;cin>>n;queue<node> v1, v2;for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){if((i+j)%2==0){tem.x = i;tem.y = j;v2.push(tem);}else{tem.x = i;tem.y = j;v1.push(tem);}}}for(int i = 1;i <= n*n;i++){cin>>x;if(x==1){if(!v1.empty()){tem = v1.front();v1.pop();cout<<"2 "<<tem.x<<" "<<tem.y<<endl;}else{tem = v2.front();v2.pop();cout<<"3 "<<tem.x<<" "<<tem.y<<endl;}}else if(x==2){if(!v2.empty()){tem = v2.front();v2.pop();cout<<"1 "<<tem.x<<" "<<tem.y<<endl;}else{tem = v1.front();v1.pop();cout<<"3 "<<tem.x<<" "<<tem.y<<endl;}}else{if(!v1.empty()){tem = v1.front();v1.pop();cout<<"2 "<<tem.x<<" "<<tem.y<<endl;}else{tem = v2.front();v2.pop();cout<<"1 "<<tem.x<<" "<<tem.y<<endl;}}}return 0;
}

E. Travelling Salesman Problem

题意：n座城市，每座城市有两个属性分别是ai和ci，第i座城市到第j座城市要花费max(aj-ai, ci)，求从1出发到其他城市各一次并最后回到1的最小花费。

思路：因为ci是不变的，所以我们要做的就是让所有aj-ai尽可能的不比ci大，那么先尽可能走到ai大的城市，然后再依次往ai小的城市走，这样就是最优的策略，所以按ai的值排个序，再进行判断，需要注意的是起点是1，所以要跑两遍。

#include<bits/stdc++.h>
#define LL long long
#define INF INT64_MAX
#define MOD 1000000007
#define stree SegTree[root]
#define lson SegTree[root << 1]
#define rson SegTree[root << 1 | 1]
using namespace std;
const int N = 300005;
struct node
{LL val, cost, pos;
}a[N];
bool cmp(node x, node y)
{if(x.val==y.val) return x.cost<y.cost;else return x.val<y.val;
}
int main()
{int t, n;cin>>n;LL ans = 0;for(int i = 1;i <= n;i++){cin>>a[i].val>>a[i].cost;a[i].pos = i;ans += a[i].cost;}sort(a+1, a+1+n, cmp);LL tem = a[1].val+a[1].cost, num = 0;//printf("tem = %lld\n", tem);for(int i = 2;i <= n;i++){if(tem>=a[i].val){tem = max(tem, a[i].val+a[i].cost);}else{ans += a[i].val-tem;tem = a[i].val+a[i].cost;//printf("1ans = %lld, tem = %lld, a[%d].val = %lld\n", ans,tem,i, a[i].val);}if(a[i].pos==1){num = i;break;}}tem = max(tem, a[num].val+a[num].cost);if(num){for(int i = num+1;i <= n;i++){if(tem>=a[i].val){tem = max(tem, a[i].val+a[i].cost);}else{ans += a[i].val-tem;tem = a[i].val+a[i].cost;//printf("2ans = %lld, tem = %lld, a[%d].val = %lld\n", ans,tem,i, a[i].val);}}}printf("%lld\n", ans);return 0;
}