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