CodeCraft-20 (Div. 2)
这一场的B和C都很好玩。题目链接：https://codeforces.com/contest/1316
A - Grade Allocation
诚心诚意的送分题。
*B - String Modification
挺好玩的一个题目，找规律找了半天。
题意：给一个长度不超过5000的字符串s，要求选择一个k(1<=k<=n)，使得字符串s经过一个变换后的字典序最小，假如有多个这样的k，选择最小的一个。这个变换是：对于所有的i∈[1,n-k+1]，依次翻转区间[i,i+k-1]，例如：
s="123456" k=2
"[21]3456"
"2[31]456"
"23[41]56"
"234[51]6"
"2345[61]"
s="123456" k=3
"[321]456"
"3[412]56"
"34[521]6"
"345[612]"
看到这里，就感觉像是一个轮换，但是仔细观察会发现最后一段是有可能反过来的，比如：
s="12345" k=3
"[321]45"
"3[412]5"
"34[521]"
果断猜测是和奇偶性有关。强行构造出所有的变换，然后sort一遍就完事了。k=x，开头就是s[x]，这个是显然的，而且后面的字符一个一个一直跟着直到s[x]~s[n]，这个也是显然的，前面的s[1]~s[x-1]的“连接状态”不会被改变，这个也是显然的。关键是前面的s[1]~s[x-1]一共经过了n-k+1次翻转，所以有可能是反序的。
*C - Primitive Primes
题意：给一个n个项的多项式，系数都是整数，且未知数项为[0,n-1]次，保证所有的n个系数的gcd为1。再同理给出另一个m个项的多项式。再给一个质数p，求他们两个的多项式乘积的系数中，第几次项的系数不是p（p是质数）的倍数，显然这是有解的，假如多解输出其中任意一解。
题解：n和m太大，跑不动FFT，但是好像有人还真能卡过去（1497ms）。当时比赛的时候在想为什么题目说“显然这是有解的”，而且也不懂为什么要求p是质数，以及为什么要保证系数的gcd的1。画出多项式乘积的系数的计算方法 (C_k=sumlimits_{i=0}^{k}A_iB_{k-i}) 后，可以看出相邻的两项的系数之间貌似不存在什么转移关系。
一次偶然的直觉，想到会不会是两个多项式分别的第一个非p的倍数，假设其是x,y，则可以得到：
p p x ...
p p p y ...
也就是
p p x a b c ...
p p p y d e ...
ep+dp+xy+ap+bp+cp
不管a,b,c,d,e是不是p的倍数，交叉组合之后都被乘了一个p，而xy也不可能是p的倍数，因为p是一个质数。所以上面这个式子模p不为0。
那么他们的系数的gcd为1，意思就是保证了至少存在一个非p的倍数，否则他们都是p的倍数，gcd至少就是p。也就是说他们本身gcd是不是1倒不影响，只要能找到一个不是p的倍数的数就行了。
D - Nash Matrix
题意：给一个n，然后一个n*n(n<=1e3)的矩阵，每个格子的信息表示从其出发最终会停留在哪个点，-1表示永远循环。要求构造一个相同大小的矩阵其中每个格子都唯一标有'U','D','L','R'其中之一或者'X'，X表示停留在此处。要求任何时候都不能走出棋盘。
题解：被样例的构造误导到了奇怪的地方，以为“无限走”就要不断经过起始格子，实际上可以走到某个“核心”处然后在核心处绕圈圈。所以就找出所有的'X'格子，然后从他们开始bfs就把一整块都标记完了，然后找任意一个-1格子，假如它是孤立的-1格子则无解，否则两个-1格子就可以组成一个“核心”，再从这个两个格子的“核心”开始多源bfs就把一整块也标记完了。这时假如还有没被标记的格子，说明它和它的终点格子（一定有终点格子）不连通。
假如-1是要求经过起始格子并无限循环，除了要求一个连通块大小为偶数之外，还要要求“黑格”和“白格”的数量相等（并不是所有的偶数大小的连通块都可以形成回路），然后应该就是从度数最小的“凸起”格子开始贪心，写一个巨复杂的优先队列，注意删除一个格子的时候是删除一对格子，要把附近的总共6个格子的度数全部减1。
int n;
int x[1005][1005];
int y[1005][1005];
int vis[1005][1005];
int deg[1005][1005];
char ans[1005][1005];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
char dans[4] = {'R', 'L', 'U', 'D'};
char adans[4] = {'L', 'R', 'D', 'U'};
queue<pii> Q;
void bfs1(int ux, int uy) {
vis[ux][uy] = 1;
ans[ux][uy] = 'X';
Q.push({ux, uy});
while(!Q.empty()) {
int vx = Q.front().first;
int vy = Q.front().second;
Q.pop();
for(int i = 0; i < 4; ++i) {
int tx = vx + dx[i];
int ty = vy + dy[i];
if(1 <= tx && tx <= n && 1 <= ty && ty <= n) {
if(x[tx][ty] == ux && y[tx][ty] == uy && vis[tx][ty] == 0) {
vis[tx][ty] = 1;
ans[tx][ty] = dans[i];
Q.push({tx, ty});
}
}
}
}
}
void bfs2(int ux, int uy) {
vis[ux][uy] = 1;
Q.push({ux, uy});
for(int i = 0; i < 4; ++i) {
int tx = ux + dx[i];
int ty = uy + dy[i];
if(1 <= tx && tx <= n && 1 <= ty && ty <= n) {
if(x[tx][ty] == -1 && y[tx][ty] == -1 && vis[tx][ty] == 0) {
vis[tx][ty] = 1;
ans[ux][uy] = adans[i];
ans[tx][ty] = dans[i];
Q.push({tx, ty});
break;
}
}
}
if(Q.size() == 1) {
puts("INVALID");
exit(0);
}
while(!Q.empty()) {
int vx = Q.front().first;
int vy = Q.front().second;
Q.pop();
for(int i = 0; i < 4; ++i) {
int tx = vx + dx[i];
int ty = vy + dy[i];
if(1 <= tx && tx <= n && 1 <= ty && ty <= n) {
if(x[tx][ty] == -1 && y[tx][ty] == -1 && vis[tx][ty] == 0) {
vis[tx][ty] = 1;
ans[tx][ty] = dans[i];
Q.push({tx, ty});
}
}
}
}
}
void test_case() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%d%d", &x[i][j], &y[i][j]);
ans[i][j] = '.';
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(vis[i][j] == 0 && x[i][j] == i && y[i][j] == j)
bfs1(i, j);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(vis[i][j] == 0 && x[i][j] == -1 && y[i][j] == -1)
bfs2(i, j);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(vis[i][j] == 0) {
puts("INVALID");
exit(0);
}
}
}
puts("VALID");
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j)
putchar(ans[i][j]);
putchar('
');
}
}
E - Team Building
题意：从n(<=1e5)个人里面，选出恰好p(<=7)个球员和恰好k(p+k<=n)个观众。p个球员对应p种不同的位置，给出每个人作为每种位置的收益，以及作为观众的收益。求最大的收益。
题解：看见这个p的数据量，感觉像是状压，但是k范围很大，定状态为dp[i][j]表示前i个人位置的占用状态为j的时候，忽略已经选了观众的人数，导致不知道一共选了多少个观众。但是仔细想想这个问题其实很好解决，按作为观众的收益从大到小排序，然后dp到前p+k个人的选法。后面的人就只能成为球员，不能成为观众。
细节：其实不是简单区分i和p+k等变量的关系，而是要数一数当前占用的观众数量，也就是i个人减去状态j中1的数量，就是观众的数量，假如观众还没满则可以转移观众，否则一定不优。最后会发现过不了样例3，显然是初始化没有标记非法状态的原因。
int n, p, k;
struct Node {
int a, s[7];
bool operator<(const Node &nd)const {
return a > nd.a;
}
} nd[100005];
ll dp[2][1 << 7];
int count1(int x) {
return __builtin_popcount(x);
}
void test_case() {
scanf("%d%d%d", &n, &p, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &nd[i].a);
for(int i = 1; i <= n; ++i) {
for(int b = 0; b < p; ++b)
scanf("%d", &nd[i].s[b]);
}
sort(nd + 1, nd + 1 + n);
memset(dp, -LINF, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= n; ++i) {
int t = i & 1;
for(int j = 0; j < (1 << p); ++j) {
dp[t][j] = dp[1 - t][j];
if(i - count1(j) <= k)
dp[t][j] += nd[i].a;
}
for(int j = 0; j < (1 << p); ++j) {
for(int b = 0; b < p; ++b) {
if(j & (1 << b))
continue;
dp[t][j | (1 << b)] = max(dp[t][j | (1 << b)], dp[1 - t][j] + nd[i].s[b]);
}
}
/*cout << "nd[" << i << "]=" << nd[i].a;
for(int b = 0; b < p; ++b)
cout << "," << nd[i].s[b];
cout << endl;
for(int j = 0; j < (1 << p); ++j)
cout << "dp[" << i << "][" << bitset<7>(j) << "]=" << dp[t][j] << endl;
cout << endl;*/
}
printf("%lld
", dp[n & 1][(1 << p) - 1]);
}