AGC048

• A - atcoder < S
  • 题意：给一个字符串，每次可以翻转相邻的两个字符，问最少需要翻转多少次，可以使得翻转后的字符串字母序大于"atcoder"。
  • 题解：我们注意到对于任意原字符串>'a'的那个字符移动到首字母即可，以及大于't'的移动到第二位即可，最小值就是答案。但是为什么'c'不用看了呢，因为如果需要移动到第三位才能满足大于'atcoder'，那么第二位一定是't'，如果第二位是't'，那么直接把't'移动到'a'即可，不需要考虑'c'的情况。
  • 代码：https://atcoder.jp/contests/agc048/submissions/18237244
• B - Bracket Score
  • 题意：一种string由小括号和中括号组成，这个string是good的如果string括号是完美匹配，且每个匹配的pair间没有交叉的情况，比如[], ([()])和()[()]这些是good string，())和([)]这俩不是。现在给一个偶数n(n<1e5)，表示string的长度，然后给A数组和B数组，表示第i位如果是小括号，权重是A[i]，如果是中括号，权重是B[i]，现在让构造一个good string，使得权重和最大。
  • 题解：首先我们可以先都是小括号，然后我们考虑替换一些大权重的中括号，我们注意到合法替换序列里，两个中括号pair之间一定是偶数，既左右中括号的pos不同奇偶，而且主要到，对于任意的不同奇偶的pair，一定可以替换构造出这么个合法序列。所以就是对奇数和偶数的b[i]-a[i]分别去sort，然后贪心，取替换后总体sum会增加的pair就行。
  • 代码：https://atcoder.jp/contests/agc048/submissions/18235682
• C - Penguin Skating
  • 题意：给1-L个坐标，然后有n个企鹅，每个企鹅在坐标A[i]上，然后企鹅可以向左向右移动，知道碰到另一个企鹅或者碰到0和L+1，现在给另一组坐标B[i]，问至少需要移动多少次企鹅，使得企鹅坐标从A变成B。
  • 题解：显然企鹅最终能停的位置一定是1，A[1]...A[n]，L这些点的左右两边，并且如果第i个企鹅只能在第i-1的右边，或者第i+1的左边，所以B[i]-i的所有取值都要在A[i]-i中找到，然后贪心就ok了。。好题！想不到。。
  • 代码：https://atcoder.jp/contests/agc048/submissions/18239990