Codeforces Round #712 Div2题解

唉。真的不行，E题其实还是有“期待可能性”想到的，但是确实没想到。看了别人的题解之后感觉茅塞顿开。说明思维的差距还是非常显然的。还得多练，多练。

E. Travelling Salesman Problem

现在有n个城市，每个城市有一个美丽度a。然后如果从城市$i$跳到城市$j$，需要花费$\max{(c_i,\ a_j-a_i)}$。问，每个城市走一遍，并且回到1点，最小花费是多少。

没想出来。参考了上面这份题解。唉，思维能力的差距还是得承认的。

交互式的题目还是有点好玩。但这个博弈比较偏构造，算是比较简单。不过我的做法可能写起来有点恶心，不知道有没有别的做法。

给你一个二进制串s，要你构建两个括号串a, b。如果$s_i=0$则${a_i}\neq{b_i}$，如果$s_i=1$则${a_i}={b_i}$。要求构建出来的连个括号，是按能匹配的那种。

经典括号配对问题，我们从左到右计算前缀和，如果是'('则+1，如果是')'则-1，则立刻有整个过程中，前缀和大于等于0。

那么考量$s_i=0$的情况。无非是a和b里面一个+1，另一个-1。那显然是谁剩的'('多谁-1。且如果遇到s里面连续一段都是0的话，那么宏观的说，这一串0是不影响前缀和的。

接着考量$s_i=1$的情况。显然，这个情况一定会对前缀和造成影响。既然$s_i=0$其实不影响前缀和，那就前一半不停的加，后一半不停的减就行了。

手滑WA了一发。忘了奇数之类的导致最后剩下东西的情况。

给你两个个长度为n的01串a和b。每次操作你可以选择一个0和1个数一样的前缀，把里面的0和1都反转。问你能不能从a变到b。

从后面开始往前操作。模拟一下就有了。

给你一个字符串，要你一定要且仅要往字符串里插入一个‘a'。问你能不能插完之后的串不是回文串。如果不行输出no，如果可以输出你的串。

模拟。往开头和结尾都插一下试试。如果都是回文串，就输出no。不然哪个不是输出哪个。