Codeforces Round #547 (Div3) 个人思路与大牛题解
引言
刚刚打完了 Codeforces #547 ...
这篇文章用来记录一下 CF#547 的我自己的想法和（日后）研究的别人的解法。
因为自学的编程为主所以算法一直很菜，学校上课其实并不能教到多少，然后我又不打 ACM 和 OI（接触晚）也没有真的仔细研究过算法竞赛相关的东西..
总之就还是打打这些 Contest 然后多看看别人的代码比较自己的思路来学习吧..
然后发现 typecho 的 markdown 不支持 latex 而且不能粘贴图片（什么时候改一下代码吧
（四个空格插入代码块的语法好反人类）什么时候也改一下吧
3.20 16:20 更新
刚刚上去看了一下发现 C 题挂在第 42 个测试点了，看了一下测试点的数据....慢慢恶意
总之就是累加过程直接溢出了，加个上界/下界判断应该就可以过了，思路是正确的，加多一个判断。
（代码暂时还没有更新）
3.20 18:13 更新
回到宿舍了... 看了一下 D 题的测试点，发现居然是在样例输出挂的..... 打 contest 的时候居然..没发现
重读了一下自己的代码发现自己犯了弱智错误(((
思路是没问题的，把两个 if 改成 while 提交就 AC 了... AC 了...
D 题代码已经更新为正确的版本了
引言(2)
先说结果吧... 反正就是菜的不行
E 题写完提交就只剩 5 分钟了，等判定出 WA 也没空看哪里有问题了，也就没管了... ABC 三题写得倒是很顺（毕竟签到题），基本都是本地测试完一次过，C 跑了一次 WA，还是因为少判定了一种情况，看到 WA 马上就修好本地重跑完就提交了。
而且最终等 hack 完和最终判定出来之后之后说不定前三题也还有错的呢（小声
A - Game23
Problem
决定还是不在这里直接放原题题目了，之后就描述大意并且附题目地址了（
题目大意
输入两个数 n 和 m，可以对 n 进行乘二或者乘三的操作，问多少次变化能把 n 变成 m？
如果不能的话输出 -1。
原题链接
思路
这道题说输入两个数 n 和 m，问能不能通过不断乘 2 或乘 3 的方式让 n 变成 m；
也就是说让 m 不断的除 2 或者除 3 得到 n 就可以了，输出操作次数。
大致想法如下：
- 首先判断 n 能不能整除 m，如果不能，那肯定不能变换，直接输出 -1
- 令 r = m / n，也就是先算出商，问题就变成了商能不能被 2 和 3 除(
玩弄)成 1，如果可以的话输出步数 - 循环让 r 不断除 2 和 3 直到其不能被 2 或 3 整除
- 如果 r 被玩弄成 1 了，那就输出次数，否则输出 -1
代码
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
if (a == b) {
cout << 0;
return 0;
}
if (b % a != 0) {
cout << -1;
return 0;
}
int r = b / a;
int steps = 0;
for (;r > 1; ++steps) {
if (r % 2 == 0) {
r /= 2;
continue;
}
if (r % 3 == 0) {
r /= 3;
continue;
}
if (r == 1) break;
steps = -1;
break;
}
cout << steps;
return 0;
}
B - Maximal Continuous Rest
Problem
题目大意
现在输入一串 1 和 0 的字符串代表某人的工作 schedule，1 代表休息，0 代表工作，问这个人最长连续休息时间是多少个单位？（求连续的 1 的长度）
思路
嘛反正这题就是简单的求最长连续字串的长度，而且是直接求 1 的字串长度，那就没什么好说的了，直接搜索完事；
不过题目也提醒了一下，因为是每天的 schedule，所以一天的结束是可以接到一天的开始的，所以这个要额外处理一下。
算法步骤如下：
- 直接扫描一遍记录最长的连续长度
- 从头部向后扫描，看看头部有多少个连续的 1
- 从尾部向前扫描，看看尾部有多少个连续的 1，但是最多扫描到第二步停止的位置（否则会重复）
- 把第二步和第三步的结果加起来，然后看看和第一步的结果哪个长，输出长的那个就可以了
代码
#include <iostream>
using namespace std;
bool s[200001];
int main()
{
int n;
cin >> n;
int cur = 0, max = 0;
for (int i = 0; i < n; ++i) {
cin >> s[i];
if (s[i] == true)
++cur;
else {
if (cur > max) max = cur;
cur = 0;
}
}
cur = 0;
int i = 0;
for (; i < n; ++i) {
if (s[i] == true) ++cur;
else break;
}
for (int j = n - 1; j > i; --j) {
if (s[j] == true) ++cur;
else break;
}
if (cur > max) max = cur;
cout << max;
return 0;
}
C - Polycarp Restores Permutation
Problem
题目大意
有一种数组叫 permutation，当且仅当其所包含的元素不重复且覆盖 1-n 的每一个数。
现在输入 n - 1 个数，代表某个数组内后一个元素与前一个元素的差值，要求利用这个差值重建出对应的 permutation 数组，如果重建出的数组不符合条件，输出 -1。
思路
在交完代码 AC 之后又想到了另外一个应该是写起来更不容易出 BUG 的一个版本，这里都记录一下吧
思路1
首先想办法找到最大元素或者最小元素的位置，这里我思考了一会儿，通过以下方法可以实现：
- 初始化
pivot = 0, sum = 0 - 正向扫描累加到
sum上，然后每次sum更新变大的时候（用一个 max 变量来记录），记录这个位置到pivot
这样扫描一遍之后就能保证 pivot 所指的位置就是最大元素的位置了。
之后就是从 pivot 位置向左和向右出发，分别重建出数组的各个元素
最后判断重建出的数组是否满足题目所说的 permutation 条件。
思路2
上面思路1的做法可行，但是在处理重建的时候 pivot 挺容易搞崩的，边界条件要仔细琢磨（我在草稿纸上琢磨了一会儿才写了的），感觉不仔细思考一下很容易写 bug，特别是向左和向右分别扫描的过程那一块。后来我想到好像可以用下面的思路来重建数组（还没有写代码验证）：
- 直接假设第一个元素为
0 - 把后面每个元素按照输入的那些差值计算，计算出一个初始数组（这时候初始数组内各个元素的相对值应该已经正确了）
扫描一遍数组里的最小负数，把它变成 1（其他所有元素也同步变大）
- 也就是说假设数组里最小的数是 -M（M>0），那么把整个数组的数都加上
M + 1使得数组最小的数是 1
- 也就是说假设数组里最小的数是 -M（M>0），那么把整个数组的数都加上
- 判断数组是否满足
permutation条件
用这种算法来做写起来应该不容易出错，也更容易理解一些。
代码
因为我写的时候是先想到的思路一，所以暂时只有思路一的代码（不过思路二的代码那么简单，随便写写就出来啦）
#include <iostream>
#include <cstring>
using namespace std;
int arr[200001];
int d[200001];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
cin >> d[i];
}
int maxi = 0, pivot = 0;
int cur = 0;
for (int i = 0; i < n - 1; ++i) {
cur += d[i];
if (cur > maxi) {
pivot = i + 1;
maxi = cur;
}
}
cur = n;
for (int i = pivot; i < n; ++i) {
arr[i] = cur;
cur += d[i];
}
cur = n;
for (int i = pivot - 1; i >= 0; --i) {
cur -= d[i];
arr[i] = cur;
}
memset(&d, 0, sizeof(d));
for (int i = 0; i < n; ++i) {
d[arr[i]]++;
}
for (int i = 1; i <= n; ++i) {
if (d[i] != 1) {
cout << "-1";
return 0;
}
}
if (n > 0) cout << arr[0];
for (int i = 1; i < n; ++i)
cout << ' ' << arr[i];
return 0;
}
D - Colored Boots
Problem
题目大意
输入两个长度相等的字符串，字符串中只包含26种小写字母和问号字符，两个字符串分别代表A类和B类，两类字母相同可以互相匹配，问号字符可以匹配任何字符。
问输入的字符串最多有多少组配对的，并输出配对方式（下标），如果有多种配对方式，输出任意一种即可。
思路
Hmmmm 我觉得我的思路应该没问题（大概），不过提交上去就直接挂在第四个测试点了....（相当前的测试点）
思路确实是没问题的... 写的时候弱智了，把两个 if 改成了 while 就过了..
我的思路是这样的：
这其实是一个字符串配对问题，而且其实并不用管顺序，所以首先处理好数据结构也就是怎么存储的问题。
一开始我直接想着用两个哈希表也就是 map<char, int> 来存两边各个字母出现的次数，然后就能很快的计算出配对的数量，用伪代码表示的话大概就是：
数量 = min(n,
sum(foreach 字母 in [a-z]: min(l[字母], r[字母]))
+ l['?'] + r['?']
)没有 latex 太草了
然后突然发现题目还要求输出是怎么配对的... 心中一阵 woc（
之后就加了两个 queue<int>[27] 来保存 26 + 1 个字符的下标，之所以用 queue 是因为我在输入的时候 push，在配对的时候直接取队列头的元素然后 pop 出来表示其已经被配对了。
实际写的时候也还是不太好写，上面输出配对的总数量的就很朴素，直接计算输出，然后是输出配对规则的部分，我分为了以下几个步骤
- 对 l 中的 26 个字母循环（不包括 '?'），在 r 中对应的字母中 pop 出元素配对直到结束
- 对 l 中的 '?' 元素，循环配对 r 中的非 '?' 元素
- 对 r 中的 '?' 元素，循环配对 l 中的非 '?' 元素
- 配对 l 和 r 的 '?' 元素
以上，我自我感觉没有任何问题，实例输入输出也都跑通过了，我自己写的测试输入也都没有问题... 不过还是 WA 了... 回头看看到底是什么东西 WA 了顺便看看别人的解法...
思路没问题，编码犯彩笔错误（
代码
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define QUESTION ('z' + 1 - 'a')
int main()
{
map<char, int> l, r;
queue<int> idxl[27];
queue<int> idxr[27];
int n;
char c;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c;
l[c]++;
if (c == '?') c = 'z' + 1;
idxl[c - 'a'].push(i);
}
for (int i = 1; i <= n; ++i) {
cin >> c;
r[c]++;
if (c == '?') c = 'z' + 1;
idxr[c - 'a'].push(i);
}
int result = 0;
for (char it = 'a'; it <= 'z'; ++it) {
result += min(l[it], r[it]);
}
result += l['?'];
result += r['?'];
if (result > n) result = n;
cout << result;
if (result > 0) {
for (char it = 'a' - 'a'; it <= 'z' - 'a';) {
if (idxl[it].size() > 0 && idxr[it].size() > 0) {
cout << "\n" << idxl[it].front() << ' ' << idxr[it].front();
idxl[it].pop();
idxr[it].pop();
} else {
++it;
}
}
while (idxl[QUESTION].size() > 0) {
int i = 0;
for (; i < 27; ++i) {
if (idxl[QUESTION].size() <= 0) break;
while (idxr[i].size() > 0 && idxl[QUESTION].size() > 0) {
// printf("\n[debug] l['?']: %d, idxr['%c']", idxl[QUESTION].size(), i + 'a');
cout << "\n" << idxl[QUESTION].front() << ' ' << idxr[i].front();
idxl[QUESTION].pop();
idxr[i].pop();
}
}
if (i == 27) break;
}
while (idxr[QUESTION].size() > 0) {
int i = 0;
for (; i < 27; ++i) {
if (idxr[QUESTION].size() <= 0) break;
while (idxl[i].size() > 0 && idxr[QUESTION].size() > 0) {
// printf("\n[debug] r['?']: %d, idxl['%c']", idxr[QUESTION].size(), i + 'a');
cout << "\n" << idxl[i].front() << ' ' << idxr[QUESTION].front();
idxr[QUESTION].pop();
idxl[i].pop();
}
}
if (i == 27) break;
}
while (idxl[QUESTION].size() > 0 && idxr[QUESTION].size() > 0) {
cout << "\n" << idxl[QUESTION].front() << ' ' << idxr[QUESTION].front();
idxl[QUESTION].pop();
idxr[QUESTION].pop();
}
}
return 0;
}
E - Superhero Battle
Problem
题目大意
打怪游戏，怪有 H 点血，回合制游戏，每个回合分为 n 个阶段，已知每个阶段（在攻击或者buff下）怪的 HP 变化情况（可能是正可能是负数），每个回合都相同，问这只怪能不能在有限的回合内杀死？如果可以，输出最小所需要的阶段总和。
思路（虽然WA但是写博客的时候修改了一下，还没有测试）
开始看这道题的时候大概还剩个二十来分钟... 写完就剩十分钟不到了，提交就只剩 4 分钟左右了....然后还 WA 了（哭
这道题比上一道题简单很多，不过时间确实不够所以在打 contest 的时候没仔细琢磨了
（然后现在我写这文章的时间不早了我先睡了）（逃
关于 E 的思路和其他的东西明天再补（也可能是日后
at 2019.3.20 01:58好的我来补更了
at 2019.3.20 15:45
因为题目给的数字范围并不算小，已经接近 int 上限了，而且每个阶段的变化值其实可以非常小，所以暴力应该会 TLE（姑且写了一个暴力模拟的方法来测试，在确定有解的情形下跑了好几秒都没停）
这道题首先要判断有没有解，简单的通过累加一个回合所有阶段的变化情况判断即可。
如果其大于 0，那么一定无解（是错的思路）
- 当时我做 contest 的时候就直接这么判断了... 现在写博客一写到这里我特么就发现错误了
- 和大于 0 的情况应该也要合并到第二种情况来判断，也就是判断能否在一个回合内杀死怪物。
- 如果其等于 0，那么判断是否能在一个回合内杀死怪物，因为只有一个回合，那这种情况直接暴力模拟完事儿，O(n)复杂度。
如果和小于 0，那么怪是一定会死的，所以只要计算多久能死就完事儿了
- 首先把符号调整成正方便计算
- 求整数除法，跳过中间过多无用的回合，计算血量剩余值（这样可以保证剩下的血量可以在一个回合内完成死亡结算）
- 回退一个回合，修正相应的变量（因为可能上一个回合的前半部分怪就死了，但是后半部分的回复让其活了过来；所以第二步求的回合数其实是怪物死亡的回合或其之后的一个回合）
- 从这个回合开始暴力模拟，最坏时间复杂度 O(2n)=O(n)
代码
因为用板子写的博客所以暂时没有代码，新的思路也还没有提交评测
后面的题目
（因为做 contest 的时候没有看，现在也还暂时没有看，所以就暂时咕着）（逃
Written at 2019.3.20 16:09