2020-2021:teams:manespace:cf_658_div.2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:cf_658_div.2 [2020/08/07 12:52] quantumbolt |
2020-2021:teams:manespace:cf_658_div.2 [2020/08/07 12:54] (当前版本) quantumbolt |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | Codeforces round 658 Div.2 链接:https:%%//%%codeforces.com/contest/1381 | + | Codeforces round 658 Div.2 |
| + | |||
| + | 链接:https://codeforces.com/contest/1381 | ||
| 本来是上周就应该写完的，拖了好久，这周上传。 | 本来是上周就应该写完的，拖了好久，这周上传。 | ||
| 行 27: | 行 29: | ||
| ===== 题意： ===== | ===== 题意： ===== | ||
| - | 有$a,b$两个01的串，现需要你执行如下操作，将$a$变成$b$.选定$a$的前缀反转0和1，然后把这个前缀倒过来 ## 题解： 简单版本就直接暴力了，每次用$a$字符串的第一个字符和$b$字符串的最后一个字符进行判断。如果不相等。则翻转整个$a$字符串。然后两个字符串长度减一。如果相等的话，就先对$a$的第一个字符进行反转操作。然后再反转整个$a$。 | + | 有$a,b$两个01的串，现需要你执行如下操作，将$a$变成$b$.选定$a$的前缀反转0和1，然后把这个前缀倒过来 |
| + | |||
| + | ===== 题解： ===== | ||
| + | |||
| + | 简单版本就直接暴力了，每次用$a$字符串的第一个字符和$b$字符串的最后一个字符进行判断。如果不相等。则翻转整个$a$字符串。然后两个字符串长度减一。如果相等的话，就先对$a$的第一个字符进行反转操作。然后再反转整个$a$。 | ||
| ====== C2 Prefix Flip (Hard Version) ====== | ====== C2 Prefix Flip (Hard Version) ====== | ||
| 行 33: | 行 39: | ||
| ===== 题意： ===== | ===== 题意： ===== | ||
| - | 同C1 ## 题解： 题目说操作的步数不能超过$2n$步。而且hard version的数据也更强，n的范围也变了，所有暴力是不行的了。 现在我们先用$n$个操作将$a$串变成同一个字符，再去跟$b$串每个位置作比较 从后往前保证修改过的值不被影响。 每次修改后记录当前位置往前的串的样子，重复上述操作。直至满足题意。 | + | 同C1 |
| + | |||
| + | ===== 题解： ===== | ||
| + | |||
| + | 题目说操作的步数不能超过$2n$步。而且hard version的数据也更强，n的范围也变了，所以暴力是不行的了。 现在我们先用$n$个操作将$a$串变成同一个字符，再去跟$b$串每个位置作比较 从后往前保证修改过的值不被影响。 每次修改后记录当前位置往前的串的样子，重复上述操作。直至满足题意。 | ||
| ====== D Unmerge ====== | ====== D Unmerge ====== | ||
| 行 39: | 行 49: | ||
| ===== 题意： ===== | ===== 题意： ===== | ||
| - | 给出一个长度为$2n$的序列，问这个序列是否可以由两个长度为$n$的序列$a$和$b$按特定的规则归并而成。 ## 题解： 现对长度为$2n$的序列分组，再01背包判断选出几组刚好能构成长度为$n$的数组 | + | 给出一个长度为$2n$的序列，问这个序列是否可以由两个长度为$n$的序列$a$和$b$按特定的规则归并而成。 |
| + | |||
| + | ===== 题解： ===== | ||
| + | |||
| + | 现对长度为$2n$的序列分组，再01背包判断选出几组刚好能构成长度为$n$的数组 | ||
| ====== E Mastermind ====== | ====== E Mastermind ====== | ||
| 行 45: | 行 59: | ||
| ===== 题意： ===== | ===== 题意： ===== | ||
| - | 对两个长度为$n$的数组，数组中的元素有$x$个是相同的，有$y$个是不同的，但是可以通过换序使其相同。现在给出其中一个数组，$x,y$。问是否存在另一个数组满足题意。 ## 题解： 暂时咕一下，感觉还是有些难度的。过段时间来补 | + | 对两个长度为$n$的数组，数组中的元素有$x$个是相同的，有$y$个是不同的，但是可以通过换序使其相同。现在给出其中一个数组，$x,y$。问是否存在另一个数组满足题意。 |
| + | |||
| + | ===== 题解： ===== | ||
| + | |||
| + | 暂时咕一下，感觉还是有些难度的。过段时间来补 | ||
2020-2021/teams/manespace/cf_658_div.2.1596775940.txt.gz · 最后更改: 2020/08/07 12:52 由 quantumbolt
