Codeforces Round #519 by Botan Investments（前五题题解）
开个新号打打codeforces（以前那号玩废了），结果就遇到了这么难一套。touristD题用了map，被卡掉了（其实是对cf的评测机过分自信），G题没过， 700多行代码，码力惊人。关键是这次tourist掉到第二了，掉了200多分，为神节哀。
做了4道，要不是第4题一直炸第5题也能做出来。本来想着上蓝名的。然后我第二题挂了，判断循环节写错了。绝望啊～～～～
比赛传送门：http://codeforces.com/contest/1043
A. Elections
这题很简单，就是说有n个人，每人投k张票，给你或你对手。第i个人会给你的对手投ai票，让你求最少的k。使得你的票数比你的对手多。模拟一下就好了，不多说。然而这题我又犯傻忘记了k >= max{ai}，wa了一次。
弱弱地放上我的代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define repd(x, r, l) for(int x = r; x >= l; x--)
#define clr(x,y) memset(x, y, sizeof(x))
#define mp(x, y) make_pair(x, y)
#define INF 1 << 30
#define MAXN
using namespace std;
typedef long long LL;
typedef pair<int,int> par; int main(){
int n;
scanf("%d", &n);
int sum = , maxx = ;
rep(i, , n){
int x;
scanf("%d", &x);
sum += x;
maxx = max(maxx, x);
}
int ans = * sum / n + ;
if(ans < maxx) ans = maxx;
printf("%d\n", ans);
return ;
}
Problem-A
B. Lost Array
这题是给你个数组a，长度为n，满足
（k是x的长度）。当k = 3， x = {1, 2, 3}, n = 5时a如下图。
让你求所有x数组的方案数和，以及每种方案的长度k（从大到小）。
这题看上去很麻烦，其实很简单。只要求出他们相邻的差，就是一种x的方案。另外的其他几个方案就是由这串差的循环节组成（为什么？自己试试就知道了）。
然而我找循环节炸了，我也不知道为啥，主要还是代码太丑。后来听了大佬的建议，才改进了一点。
改过后的代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
#define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
#define clr(x,y) memset(x, y, sizeof(x))
#define mp(x, y) make_pair(x, y)
#define INF 1 << 30
#define MAXN 1005
using namespace std;
typedef long long LL;
typedef pair<int,int> par; int n;
int a[MAXN], b[MAXN], ansk[MAXN]; bool judge(int len){
rep(i, len, n - )
if(a[i] != a[i % len]) return ;
return ;
} int main(){
scanf("%d", &n);
rep(i, , n){
scanf("%d", &b[i]);
a[i - ] = b[i] - b[i - ];
}
int ans = ;
rep(i, , n)
if(judge(i)) ansk[++ans] = i;
printf("%d\n", ans);
rep(i, , ans) printf("%d ", ansk[i]);
puts("");
return ;
}
Problem-B
C. Smallest Word
这题大意就是给你一个字符串s（只由a和b组成），你每次可以将这个字符串的任意前缀翻转，让你求得到字典序最小的字符串的任意一种操作。
因为这个字符串只有ab，所以这题最后得到的字符串一定前面都是a，后面都是b（这是一定能得到的，至于为什么，我说不清），所以对于每次翻转，都要把所有的a放一起，b放一起。
然后我们开始模拟一下，随便写个字符串ababbaaababaaab。（懒得画图）
我们的算法就是把所有a和b分开放。
这是原先的字符串ab|abbaaababaaab
|
旋转ab 旋转baa 旋转aabbb 旋转bbbaaaaa 旋转aaaaabbbb 旋转bbbbaaaaaa 旋转aaaaaabbbbb 旋转bbbbbaaaaaaaaa |
变成baa|bbaaababaaab 变成aabbb|aaababaaab 变成bbbaaaaa|babaaab 变成aaaaabbbb|abaaab 变成bbbbaaaaaa|baaab 变成aaaaaabbbbb|aaab 变成bbbbbaaaaaaaaa|b 变成aaaaaaaaabbbbbb |
中间的竖杠之前的就是已经将a和b区分开来的字符串，然后我们发现，竖杠之前就是要旋转的地方（为了使a或b连在一起）。然后进一步发现旋转的地方就是a和b的交界线（why？no why！）。
所以我们只要找到所有a和b的交界线就好了，还有就是如果最后一位是a就要在最后将整个字符串旋转（我居然因为这个wa了一次……
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
#define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
#define clr(x,y) memset(x, y, sizeof(x))
#define mp(x, y) make_pair(x, y)
#define INF 1 << 30
#define MAXN 1005
using namespace std;
typedef long long LL;
typedef pair<int,int> par; char st[MAXN];
bool flag[MAXN]; int main(){
scanf("%s", st + );
int len = strlen(st + );
rep(i, , len - )
if(st[i] != st[i + ]) flag[i] = ;
if(st[len] == 'a') flag[len] = ;
rep(i, , len) printf("%d ", flag[i]);
puts("");
return ;
}
Problem-C
D. Mysterious Crime
这题是真的坑，一开始压根没思路，辛亏后来开窍了。
这题是说给你一个m*n(1≤n≤100000, 1≤m≤10)的矩阵，每行都是一个[1,n]的排列。让你每行删掉任意长度的前缀和后缀（也可以不删），使得每行剩下的序列相等。问你方案总数。其实就是有多少个序列是每行都拥有的。（然而我一开始还读了半天题）
然而我一开始读错数据，把n和m的大小读反了，main包似乎也是。然我我一开始想到了暴力+kmp，main想到了搜索。然后我就wa了一次，居然给过样例了，不可思议。
听dalao说好像是什么后缀数组（听都没听说过），然后就想到了一个很……的代码。似乎没几个人和我代码思路一样，除了tourist（然后他T了，掉下了rating榜第一名）
因为每行n个数各自只出现一次，所以说只要用s[a[1][j]].nxt记录第一行每个数字a[1][j]的下一个数字a[1][j + 1]，一个长为l序列s是每行都拥有仅当每行的s[i]都的下一个元素为s[i + 1]（1 <= i < l)。所以用s[a[1][j]].cnt记录下有多少行中a[1][j]的下一个为a[1][j + 1]即s[a[1][j]].nxt。
然后我们找到所有cnt为m - 1即所有行都出现过的相邻的数，但是如果A->B和B->C在后m-1行都出现，那么A，B，C也是一个满足每行拥有的序列。所以我们还要记录所有连续的串的长度（如A->B->C都满足就为3），答案为所有长度*（长度 + 1）/ 2的总和（为什么？这不是小学数学吗。）
还有一个单独的点长度算1，因为单独一个数也算是一个序列，且每行都有。
不过回过头来一看，上面这段话说了什么自己也看不懂，算了凑合凑合，看下代码吧：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
#define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
#define clr(x,y) memset(x, y, sizeof(x))
#define mp(x, y) make_pair(x, y)
#define INF 1 << 30
#define MAXN 15
#define MAXM 100005
using namespace std;
typedef long long LL;
typedef pair<int,int> par; struct node{
int nxt;
LL cnt;
}s[MAXM];
int a[MAXN][MAXM]; int main(){
int n, m;
scanf("%d%d", &n, &m);
rep(i, , m)
rep(j, , n) scanf("%d", &a[i][j]);
rep(i, , n - ){
s[a[][i]].nxt = a[][i + ];
s[a[][i]].cnt = ;
}
rep(i, , m)
rep(j, , n - )
if(s[a[i][j]].nxt == a[i][j + ]) s[a[i][j]].cnt++;
LL sum = , ans = ;
rep(i, , n - ){
if(s[a[][i]].cnt != m) ans += sum * (sum + ) / , sum = ;
else sum++;
}
if(sum > ) ans += sum * (sum + ) / ;
cout << ans << endl;
return ;
}
Problem-D
E. Train Hard, Win Easy
上一次看错题了，搞了半天样例打错，之前的题解是错的，抱歉，现在改了。
这题时说有n个大佬去打比赛（就两题），第i个大佬第一题会得a[i]分，第二题会得b[i]分，现在每次选俩大佬打模拟赛，每道题各选一个大佬，使获得的总分最少（为啥最少，我也不知道）。然后有m对大佬不会一起打。让你求每个大佬每次比赛中团队的总分。
当i和j一起打，
假设i做第一道
所以说a[i] + b[j] < a[j] + b[i]
那么a[i] - b[i] < a[i] - b[j]
所以说我们只要将a[i] - b[i]排序，如果j在i的前面，那么第i个人就要做一次第二题，否则做一次第一题。
我们用id[i]记录排序后i所在的位置，那么i就要做id[i] - 1次第二题，n - id次第一道，另外因为记录每次比赛团队总分，所以答案还得加上a[1] ~ a[id[i] - 1]和b[id[i] + 1] ~ b[n]。所以还需要开个前缀和和后缀和。
再判断不会一起打的人在他的前面还是后面，减去。
时间复杂度为O(n + m)。
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
#define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
#define clr(x,y) memset(x, y, sizeof(x))
#define mp(x, y) make_pair(x, y)
#define all(x) begin(x), end(x)
#define MAXN 500005
#define fi first
#define se second
#define Size(x) ((int)size(x))
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<LL, int> pli;
typedef pair<LL, LL>pll;
const int INF = << ;
const int p = ;
//by DYH pli c[MAXN];
pll sum[MAXN];
int id[MAXN];
LL a[MAXN], b[MAXN], ans[MAXN]; int main(){
int n, m;
scanf("%d%d", &n, &m);
rep(i, , n){
scanf("%I64d%I64d", &a[i], &b[i]);
c[i] = mp(a[i] - b[i], i);
}
sort(c + , c + n + );
rep(i, , n) id[c[i].se] = i;
sum[] = mp(, );
sum[n + ] = mp(, );
rep(i, , n) sum[i].fi = sum[i - ].fi + a[c[i].se];
repd(i, n, ) sum[i].se = sum[i + ].se + b[c[i].se];
rep(i, , n) ans[i] = a[i] * (n - id[i]) + b[i] * (id[i] - ) + sum[id[i] - ].fi + sum[id[i] + ].se;
rep(times, , m){
int x, y;
scanf("%d%d", &x, &y);
if(id[x] < id[y]) ans[x] -= a[x] + b[y], ans[y] -= a[x] + b[y];
else ans[x] -= a[y] + b[x], ans[y] -= a[y] + b[x];
}
rep(i, , n) printf("%I64d ", ans[i]);
puts("");
return ;
}
Problem-E
终于打完啦！2018-10-31 15:58:34
这是tourist的TLE代码，CF的c++11导致tourist掉了200分并且掉下rating榜第一的代码。
/**
* author: tourist
* created: 28.10.2018 18:47:36
**/
#include <bits/stdc++.h> using namespace std; int main() {
ios::sync_with_stdio(false);
cin.tie();
int n, m;
cin >> n >> m;
map<pair<int,int>,int> mp;
for (int i = ; i < m; i++) {
int foo;
cin >> foo;
foo--;
for (int j = ; j < n; j++) {
int bar;
cin >> bar;
bar--;
mp[make_pair(foo, bar)]++;
foo = bar;
}
}
vector<int> to(n, -), from(n, -);
for (auto &p : mp) {
if (p.second == m) {
to[p.first.first] = p.first.second;
from[p.first.second] = p.first.first;
}
}
long long ans = ;
for (int i = ; i < n; i++) {
if (from[i] == -) {
int len = ;
int x = i;
while (to[x] != -) {
x = to[x];
len++;
}
ans += (long long) len * (len + ) / ;
}
}
cout << ans << '\n';
return ;
}
Problem-D TLE by tourist
摆上tourist怒刷一波评测证明了以后我们cf要交C++14不要交C++11（C++19:？？？）
