Codeforces Round #486 (Div. 3)
pantw
2018-06-04 23:20:41
emmm
第一次领着萌新们打cf。（OI队六一联欢晚会2333
本来觉得Div3应该会友好一点emmm
结果撞上一场披着Div3皮的Div2。（怒怼出题人
本来当天晚上想讲题结果发现时间不早（
于是就坑到了今天(2018 Jun. 6th)。
一放高考假肚子疼了半个晚上躺在床上动都不想动一下emmm
最后还是lijyya来催了催才开工。（
好的！
那么以下就是原创中文版题解咯。
------------
# 解题报告
- ## A
- ### 题意：
从$n$名学生中选$k$名参赛，每个人的能力值$a_i$不一样。给出$n$和$k$以及每个人的能力值$a_i$，要求判定能否按照要求选出这$k$名学生？要求输出方案。
$(1≤k≤n≤100, 1≤a_i≤100)$
- ### 思路：
我们观察到$a_i$的值域非常小，这说明我们可以用一个数组记录这个值我们是否选过。对每个值我们只能选1个人，也就是说有多少种能力值就能选多少人。
也就是说，我们从头往尾扫，有k种能力值时我们就停下来，这时已经满足条件。
如何输出方案：对每种能力值记录它第一次出现在谁身上。
其余实现细节详见代码。
- ### Code：
```cpp
#include <cstdio>
#define maxn 105
int a[maxn], cnt[maxn];
bool yes[maxn];
int main(){
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
if(k && !cnt[a[i]]++) yes[i] = true, --k;
}
if(!k) {
puts("YES");
for(int i = 1; i <= n; i++) if(yes[i]) printf("%d ", i);
}
else puts("NO");
return 0;
}
```
- ## B
- ### 题意：
给$n$个字符串，求能否将其顺序重排，使得对任意一个串，排在它前面的都是它的子串。若能，输出方案。
$1≤n≤100$，字符串中字母均为小写，且串的长度$S_i$满足$1 \le S_i \le 100$。
- ### 思路：
我们可以发现：
1. 子串的长度一定小于等于原串的长度。
所以长度小的串一定要排在前面。
2. 对于长度相等的串，它们的内容必须相同。
所以我们只需要判定长度相等的串是否相同即可。
基于以上两点我们可以方便地利用string类来解决这个问题。
关于string类、string::find()函数的使用，请参阅：[string](http://zh.cppreference.com/w/cpp/string/basic_string)及[string::find()](http://zh.cppreference.com/w/cpp/string/basic_string/find)
其余实现细节详见代码。
- ### Code：
```cpp
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 105
using namespace std;
string s[maxn];
bool cmp(const string &a, const string &b) {
return a.length() < b.length();
}
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> s[i];
sort(s + 1, s + n + 1, cmp);
bool valid = true;
for(int i = 2; i <= n; ++i) {
if(s[i-1].length() == s[i].length() && s[i-1] != s[i]) valid = false;
for(int j = 1; j < i; ++j) {
if(s[i].find(s[j]) == s[i].npos) valid = false;
}
}
puts(valid ? "YES" : "NO");
if(valid) for(int i = 1; i <= n; ++i) cout << s[i] << endl;
return 0;
}
```
- ## C
- ### 题意：
给$k$个数组，每个数组长度$n_i$，其元素之和为$S_i$，求是否存在4个正整数$i,x,j,y$满足$i\neq j$且$S_i$减去第$i$个数组的第$x$个元素等于$S_j$减去第$j$个数组的第$y$个元素。存在则输出方案。
元素的绝对值在区间[-10000,10000]上。
$(2 \le k \le 2 \times 10^5, 1 \le n_i \le 2 \times 10^5, \sum_{i=1}^{k} n_i ≤ 2\times 10^5$
- ### 思路：
我们对每个元素枚举它所在的数组的元素和减去它所得到的值。
我们希望在发现第二个同样的值时终止程序，输出方案，从而解决这个问题。
因此我们需要一个能快速存储、查找值的数据结构。同时它还要维护值与位置信息之间的对应关系。
我们可以想到用STL容器中的map来解决这个问题。
先用struct定义位置信息这个类型。然后用map<int, 位置信息>这个类型的对象来存储信息。这样我们就完美地解决了这个问题。
其余实现细节详见代码。
- ### Code：
```cpp
#include <cstdio>
#include <vector>
#include <map>
#define maxn 200010
using namespace std;
vector<int> a[maxn];
int n[maxn];
struct R{
int i, x;
};
map<int, R> M;
int main(){
int k, t;
scanf("%d", &k);
for(int i = 1; i <= k; i++){
scanf("%d", n + i);
int sum = 0;
for(int j = 1; j <= n[i]; ++j) scanf("%d", &t), a[i].push_back(t), sum += t;
for(int j = 1; j <= n[i]; ++j) {
R r;
r.i = i, r.x = j;
if(M.find(sum - a[i][j-1]) == M.end()) {
M[sum - a[i][j-1]] = r;
}
else {
R r_ = M[sum - a[i][j-1]];
if(r_.i != i) {
puts("YES");
printf("%d %d\n%d %d\n", r_.i, r_.x, i, j);
return 0;
}
}
}
}
return puts("NO"), 0;
}
```
- ## D
- ### 题意：
数轴上有$n$个不重合的点，坐标分别为$x_1,x_2,...,x_n$。从这些点中选出若干个点组成集合$S$，使得$\forall x_i,x_j\in S,\exists k\in N,|x_i-x_j|=2^k.$
求集合$S$最多能包含几个元素。输出方案。
- ### 思路：
经过缜密的思考我们可以发现，$S$不会包含超过3个元素。
证明：
若S包含3个以上的元素，取其最大的4个元素，从小到大设为$a,b,c,d$，则$d-c=2^i,c-b=2^j,d-b=2^k.$
易证当且仅当$i=j=k-1$时，$d-c=2^i,c-b=2^j,d-b=2^k$同时成立。即$d-c=2^i,c-b=2^i=d-c$。
同理可证$b-a=c-b$。
$\therefore d-c=c-b=c-a=2^i$
$\therefore d-a=3\times 2^i \neq 2^k$，矛盾。
因此S中元素数不会超过3。
接下来我们只需要枚举答案即可。
答案可能的取值有：1,2,3。
对答案为1的情况：随便输出一个点。
对答案为2的情况：对每一个$a_i$，枚举$1\le k \le 31$，判断是否存在坐标为$a_i+2^k$的点。
对答案为3的情况：对每一个$a_i$，枚举$1\le k \le 31$，判断坐标为$a_i\pm 2^k$的点是否同时存在。
我们用一个set来存储所有点的坐标，这样可以快速查找某坐标对应的点是否存在。
其余实现细节详见代码。
- ### Code：
```cpp
#include <cstdio>
#include <set>
#define maxn 200010
using namespace std;
int a[maxn];
set<int> S;
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", a + i);
S.insert(a[i]);
}
for(int i = 1; i <= n; ++i) {
for(int k = 0; k <= 30; ++k) {
int x = a[i], d = 1 << k;
if(S.find(x - d) != S.end() && S.find(x + d) != S.end()) {
puts("3");
printf("%d %d %d", x - d, x, x + d);
return 0;
}
}
}
for(int i = 1; i <= n; ++i) {
for(int k = 0; k <= 30; ++k) {
int x = a[i], d = 1 << k;
if(S.find(x - d) != S.end()) {
puts("2");
printf("%d %d", x - d, x);
return 0;
}
}
}
puts("1");
printf("%d", a[1]);
return 0;
}
```
- ## E
- ### 题意：
求能否将一个数经过合法交换相邻数字变成能被25整除的数。
- ### 思路：
这是一道公认的毒瘤题。
暴力枚举末两位数，贪心地移动数字。
细节较多，容易写错。
puts()、sscanf()、swap()以及strcpy()的用法请自行查阅cppreference。
其余实现细节详见代码。（其实本来可以不写这么长的emmm但是现场急着A题就没去管代码复用率）
- ### Code：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20
using namespace std;
char s[maxn], t[maxn];
int cnt[maxn];
int main(){
int n, ans = 0x3f3f3f3f, i, j;
long long d;
scanf("%s", s);
sscanf(s, "%I64d", &d);
n = strlen(s);
for(int i = 0; i < n; ++i) cnt[s[i] - '0']++;
if(n <= 1) return puts("-1"), 0;
if(n == 2) {
if(d == 25 || d == 50 || d == 75) return puts("0"), 0;
else if(d == 52 || d == 57) return puts("1"), 0;
else return puts("-1"), 0;
}
if(cnt[0] >= 2) {
int ta = 0;
strcpy(t, s);
for(j = n - 1; t[j] != '0'; --j);
for(; j < n - 1; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = n - 2; t[j] != '0'; --j);
for(; j < n - 2; ++j) swap(t[j], t[j + 1]), ++ta;
if(ta < ans) ans = ta;
}
if(cnt[0] >= 1 && cnt[5] >= 1) {
int ta = 0;
strcpy(t, s);
for(j = n - 1; t[j] != '0'; --j);
for(; j < n - 1; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = n - 2; t[j] != '5'; --j);
for(; j < n - 2; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = 0; t[j] == '0'; ++j) ++ta;
if(j < n - 2 && ta < ans) ans = ta;
}
if(cnt[2] >= 1 && cnt[5] >= 1) {
int ta = 0;
strcpy(t, s);
for(j = n - 1; t[j] != '5'; --j);
for(; j < n - 1; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = n - 2; t[j] != '2'; --j);
for(; j < n - 2; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = 0; t[j] == '0'; ++j) ++ta;
if(j < n - 2 && ta < ans) ans = ta;
}
if(cnt[7] >= 1 && cnt[5] >= 1) {
int ta = 0;
strcpy(t, s);
for(j = n - 1; t[j] != '5'; --j);
for(; j < n - 1; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = n - 2; t[j] != '7'; --j);
for(; j < n - 2; ++j) swap(t[j], t[j + 1]), ++ta;
for(j = 0; t[j] == '0'; ++j) ++ta;
if(j < n - 2 && ta < ans) ans = ta;
}
printf("%d", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
```
- ## F
- ### 题意：
暂请自行阅读题面。
- ### 思路：
一道DP题emmm
状态：$f[i][j]$表示走到i，拿着j点的伞时的最小疲劳度。
转移方程及其余实现细节详见代码。
- ### Code：
```cpp
#include <cstdio>
#include <cstring>
#define maxn 2010
bool rain[maxn], um[maxn];
int w[maxn];
int f[maxn][maxn];
inline void cmin(int &p, int x) {
if(x < p) p = x;
}
int main(){
memset(f, 0x3f, sizeof f);
memset(w, 0x3f, sizeof w);
int a, n, m, l, r;
scanf("%d%d%d", &a, &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &l, &r);
++l, ++r;
for(int j = l; j < r; ++j) rain[j] = true;
}
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &l, &r);
++l;
um[l] = true;
cmin(w[l], r);
}
f[1][0] = w[0] = 0;
for(int i = 1; i <= a + 1; ++i) {
for(int j = 0; j <= a + 1; ++j) {
if(um[i]) cmin(f[i][i], f[i][j]); // Switch to i if point i did have an umbrella
cmin(f[i][0], f[i][j]); // Throw away the umbrella
// Walk one unit distance
if(rain[i]) { // If the interval is raining we could only walk with umbrella
if(j) cmin(f[i + 1][j], f[i][j] + w[j]); // By carrying the umbrella with us, we'll be accumulating w[j] units of fatigue
}
else {
cmin(f[i + 1][j], f[i][j] + w[j]); // We could carry the umbrella even if there isn't any rain.
}
}
if(!rain[i]) cmin(f[i + 1][0], f[i][0]);
cmin(f[i + 1][i], f[i][i] + w[i]);
}
int ans = 0x3f3f3f3f;
for(int j = 0; j <= a + 1; ++j) cmin(ans, f[a + 1][j]);
printf("%d", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
```