唉。真的不行,E题其实还是有“期待可能性”想到的,但是确实没想到。看了别人的题解之后感觉茅塞顿开。说明思维的差距还是非常显然的。还得多练,多练。
E. Travelling Salesman Problem
题意
现在有n个城市,每个城市有一个美丽度a。然后如果从城市$i$跳到城市$j$,需要花费$\max{(c_i,\ a_j-a_i)}$。问,每个城市走一遍,并且回到1点,最小花费是多少。
题解
没想出来。参考了上面这份题解。唉,思维能力的差距还是得承认的。
代码
https://codeforces.com/contest/1504/submission/112084741
D. 3-Coloring
交互式的题目还是有点好玩。但这个博弈比较偏构造,算是比较简单。不过我的做法可能写起来有点恶心,不知道有没有别的做法。
C. Balance the Bits
题意
给你一个二进制串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了一发。忘了奇数之类的导致最后剩下东西的情况。
B. Flip the Bits
题意
给你两个个长度为n的01串a和b。每次操作你可以选择一个0和1个数一样的前缀,把里面的0和1都反转。问你能不能从a变到b。
题解
从后面开始往前操作。模拟一下就有了。
代码
A. Déjà Vu
题意
给你一个字符串,要你一定要且仅要往字符串里插入一个‘a'。问你能不能插完之后的串不是回文串。如果不行输出no,如果可以输出你的串。
题解
模拟。往开头和结尾都插一下试试。如果都是回文串,就输出no。不然哪个不是输出哪个。