Codeforces Round #712 Div2题解

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


E. Travelling Salesman Problem

题意

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

题解

Codeforces Round #712 Div.2(A ~ F) 超高质量题解(每日训练 Day.15 )_繁凡さん的博客-CSDN博客
Codeforces Round #712 Div.2(A~F) 题解A. Déjà VuProblem给你一个字符串。问能否在该字符串里插入一个字母 a,使得它不是回文字符串。Solution显然不想让他变成回文字符串,那就破坏它成为回文字符串的条件,我们只能插入字符 a ,所以我们直接算一下该字符串前缀、后缀里各有有几个 a ,把我们能插入的 a 放到 a 多的地方即可。Code// Problem: A. Déjà Vu// Contest: Codeforces - Codefor

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

代码

https://codeforces.com/contest/1504/submission/112084741


D. 3-Coloring

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

Codeforces Round #712 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了一发。忘了奇数之类的导致最后剩下东西的情况。

Submission #112003295 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Flip the Bits

题意

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

题解

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

代码

Submission #112001224 - Codeforces
Codeforces. Programming competitions and contests, programming community

A. Déjà Vu

题意

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

题解

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

代码

Submission #112000245 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论