这次是第二次参加 CodeChef Starters
我觉得还蛮有趣的
这次六题里写出了五题
排在 div2 的第二
这场比完就到六星 2302
似乎有些比较简单比赛的就不能比了
https://i.imgur.com/6nOAwem.png
今天尝试不用他那个慢的要死的线上IDE
改在本地写+测试后再复制贴上
体验整个就好很多
P1 CONCATPAL
https://www.codechef.com/problems/CONCATPAL
因为可以随便排顺序
所以只需要看各个字母的出现次数
能成功若且唯若长的和短的抵消后
每个字母出现次数 >= 0
且出现次数是奇数的字母数 <= 1
（可以当中心点）
P2 THREENUMBERS
https://www.codechef.com/problems/THREENUMBERS
目标是要让三个数都一样
把两个数加一且另一数减一
其实就等价于把一个数减二
答案就是与最小值的距离总和除二
P3 KPAL
https://www.codechef.com/problems/KPAL
这题是 corner cases 题，分成
1. N = K (直接看 A 是不是回文)
2. N 是奇数 (一定成功)
3. N 是偶数，K 是奇数（一定成功）
4. N, K 都是偶数（看两个半边奇偶性是否一致）
P4 SORTXOR
https://www.codechef.com/problems/SORTXOR
从这题开始有挑战一点
可以用三次 xor 交换两个值
但如果只用到两两交换的话
会超出 3N/2 的限制（最多需要 3(N - 1) 次操作）
不过经过在纸上一阵乱试
会发现对于 permutation 的一个长度是 k 的 cycle
实际上只需要 k + 1 次操作
像是 (1 3 4) 这个 cycle
只需要作出
1: [1 3 4]
3: [1 3 4]
4: [1 3 4]
1: [1 3 4]
就可以直接排好位置
因为长度是 1 的 cycle 不用做事
所以最多就是 3/2 倍，刚好就是他的限制
记得把一开始的值转成 ranking 形式的 permutation 即可
P5 SORTSTR
https://www.codechef.com/problems/SORTSTR
这题我蛮喜欢的，因为题目简洁但最后的结果又出乎我意料
对于一个字串，如果相邻的两个字符的值也是相邻的就可以交换
例如 aabbd 中的 ab 交界可以互换，但 bd 交界不行
要找出能形成的字典序最小的字串
假如某个字符是 k
一个很重要的观察是这个位置不可能 >= k + 2 也不能 <= k - 2
例如想要变成 k - 2，首先必须变成 k - 1
但 (k, k-1) 交换后变成 (k-1, k) 后
就又变成需要把后面的 k 变成 k-2 才能让前面的 k-1 变小
所以不可能达成
要字典序最小，可以 greedy 的让第一个最小
假如第一个字符是 k
根据刚才的观察，我们只有机会让他变 k-1
所以只有不断的进 k 或是 k-2 才有机会一路交换上来变成 k-1
维护一个 queue 就会变成像下面这样只由 k 及 k-2 组成