在学考复习的时候偷偷打了这场cf，今天才有时间把题目都订正，囧
B
题目大意：n个人，每个人向一些人发邮件（都会给自己发），然后构造一个确定某些人发邮件的方案，使得每个人收到的邮件 $\neq a[i]$
题解：因为每个人都会给自己发，所以当某人$= a[i]$时就把他自己选上
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define rep(i, l, r) for (int i = l; i <= r; i++) 8 #define drep(i, r, l) for (int i = r; i >= l; i--) 9 typedef long long ll;10 const int N = 108;11 int n, a[N], d[N], ans[N];12 char Map[N][N];13 int main()14 {15 #ifndef ONLINE_JUDGE16 freopen("input.txt","r",stdin);17 //freopen("output.txt","w",stdout);18 #endif19 scanf("%d", &n);20 rep(i, 1, n) scanf("%s", Map[i] + 1);21 rep(i, 1, n) scanf("%d", &a[i]);22 bool flag = false;23 while (!flag)24 {25 flag = 1;26 rep(i, 1, n) if (a[i] == d[i]) 27 {28 flag = 0;29 ans[++ans[0]] = i;30 rep(j, 1, n) if (Map[i][j] == '1') d[j]++;31 break;32 }33 }34 sort(ans + 1, ans + ans[0] + 1);35 printf("%d\n", ans[0]);36 rep(i, 1, ans[0]) printf("%d ", ans[i]); printf("\n");37 #ifndef ONLINE_JUDGE38 fclose(stdin); fclose(stdout);39 #endif40 return 0;41 }
C
题目大意：S和D玩游戏，S先手。一共n堆石头，每次可以拿走一堆，剩下k堆就结束。S希望最后留下的石头总数是奇数，D希望是偶数
题解：特判n = k的情况，然后注意到最后一次操作时，如果奇偶石头都有，那么操作的人就获胜了。根据这个来分类讨论
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define rep(i, l, r) for (int i = l; i <= r; i++) 8 #define drep(i, r, l) for (int i = r; i >= l; i--) 9 typedef long long ll;10 const int N = 2e5 + 8;11 int n, k, a[N], c[2];12 void out(int x)13 //x:最后的奇偶性 14 {15 printf("%s\n", x == 1 ? "Stannis " : "Daenerys");16 }17 void solve()18 //先手奇数，后手偶数 19 {20 if (!c[1]) { out(0); return;}21 if (!c[0]) { out(k & 1); return;}22 if ((n - k) & 1)23 //先手控制最后一步 24 {25 int x = (n - k) / 2 + 1, y = n - k - x; x--; 26 if (y >= c[1]) out(0);27 else if (y < c[0]) out(1);28 else out(k & 1);29 }30 else31 //后手控制最后一步 32 {33 int x = (n - k) / 2, y = n - k - x; y--;34 if (x >= c[0]) out(k & 1);35 else out(0);36 }37 }38 int main()39 {40 #ifndef ONLINE_JUDGE41 freopen("input.txt", "r", stdin);42 //freopen("output.txt", "w", stdout);43 #endif44 scanf("%d%d", &n, &k);45 rep(i, 1, n) scanf("%d", &a[i]), c[(a[i] & 1) ? 1 : 0]++;46 if (n == k)47 {48 out(c[1] & 1);49 return 0;50 }51 solve();52 #ifndef ONLINE_JUDGE53 fclose(stdin); fclose(stdout);54 #endif55 return 0;56 }
D
题目大意：给一个$n \times m$的矩阵，矩阵有黑白格子，选择最少的前缀矩阵，使得可以计算所有黑格子上的权值和-白格子权值和
题解：倒着扫一遍，贪心选择，使得白格子是-1，黑格子是1
D
E
不会
F
题目大意： 给定一个序列，求有多少个长度大于等于2的区间满足区间和$-$区间最大值是$k$的倍数
题解： 递归解决。假设现在处理区间$[l, r]$，先找到最大值，然后只遍历短的那一边，计算当前的和，然后算出另一边应该是多少，则问题变成了求一段区间等于某个值的有多少个，可以用主席树解决
时间复杂度$O(n{log^2}n)$
#include#include #include #include #include using namespace std;#define rep(i, l, r) for (int i = l; i <= r; i++)#define drep(i, r, l) for (int i = r; i >= l; i--)typedef long long ll;const int N = 3e5 + 8, Log = 23;int n, k, tot, a[N], sum[N], st[Log][N], son[N], rt[N];ll ans;struct Node{ int l, r, s;}t[N * Log];void Insert(int x, int o, int l, int r, int p, int d){ t[x].s = t[o].s + d; if (l == r) return; int mid = l + r >> 1; if (p <= mid) t[x].r = t[o].r, Insert(t[x].l = ++tot, t[o].l, l, mid, p, d); else t[x].l = t[o].l, Insert(t[x].r = ++tot, t[o].r, mid + 1, r, p, d);}int query(int x, int o, int l, int r, int p){ if (l == r) return t[x].s - t[o].s; int mid = l + r >> 1; if (p <= mid) return query(t[x].l, t[o].l, l, mid, p); return query(t[x].r, t[o].r, mid + 1, r, p);}void init(){ rep(i, 1, n) { son[i] = son[i - 1]; if ((1 << son[i] + 1) == i) son[i]++; } rep(i, 1, n) st[0][i] = i; rep(i, 1, son[n]) rep(j, 1, n) if (j + (1 << i) - 1 <= n) { int x = st[i - 1][j], y = st[i - 1][j + (1 << i - 1)]; st[i][j] = a[x] > a[y] ? x : y; } rep(i, 0, n) { if (i) sum[i] = (sum[i - 1] + a[i]) % k; Insert(rt[i + 1] = ++tot, rt[i], 0, k - 1, sum[i], 1); }}int stquery(int l, int r){ int k = son[r - l + 1]; int x = st[k][l], y = st[k][r - (1 << k) + 1]; return a[x] > a[y] ? x : y;}void solve(int l, int r){ if (l == r) {ans++; return;} if (l > r) return; int p = stquery(l, r); //printf("_______%d %d %d\n", l, r, p); ll tmp = ans; if (p - l + 1 <= r - p + 1) { int s = 0; drep(i, p, l) { if (i != p) s = (s + a[i]) % k; int x = (-s + k + sum[p]) % k; ans += query(rt[r + 1], rt[p], 0, k - 1, x); } } else { int s = 0; rep(i, p, r) { if (i != p) s = (s + a[i]) % k; int x = (sum[p - 1] + k - (-s + k)) % k; //printf("%d %d %d\n", x, p - 1, max(l - 2, 0)); ans += query(rt[p], rt[l - 1], 0, k - 1, x); } } //printf("%I64d\n", ans - tmp); solve(l, p - 1); solve(p + 1, r);}int main(){#ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);#endif scanf("%d%d", &n, &k); rep(i, 1, n) scanf("%d", &a[i]); init(); solve(1, n); ans -= n; printf("%I64d\n", ans);#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout);#endif return 0;}
G
题目大意：给一个序列，每次可以交换$a[i]$和$a[i + 1]$，但是交换前$a[i]$要给一块钱给$a[i + 1]$，如果$a[i]$为$0$就不能交换，求最后的序列，使得序列不降
题解： 如果把n个数放在楼梯上（也就是$a[i] + i$），那么交换两个数就相当于把楼梯这两级包括上面的一起交换。显然要把高的往后面放。所以直接按照$a[i] + i$排序，然后再复原，检验答案
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define rep(i, l, r) for (int i = l; i <= r; i++) 8 #define drep(i, r, l) for (int i = r; i >= l; i--) 9 typedef long long ll;10 const int N = 200008;11 int n, a[N];12 int main()13 {14 #ifndef ONLINE_JUDGE15 freopen("input.txt","r",stdin);16 //freopen("output.txt","w",stdout);17 #endif18 scanf("%d", &n);19 rep(i, 1, n) scanf("%d", &a[i]), a[i] += i;20 sort(a + 1, a + n + 1);21 rep(i, 1, n) a[i] -= i;22 rep(i, 1, n - 1) if (a[i] > a[i + 1]) 23 {24 printf(":(\n"); return 0;25 }26 rep(i, 1, n) printf("%d ", a[i]); printf("\n");27 #ifndef ONLINE_JUDGE28 fclose(stdin); fclose(stdout);29 #endif30 return 0;31 }
H
题目大意：给出矩阵$A$，构造权值为0矩阵$B$，使得$A - B$每一项绝对值的最大值最小
题解：二分答案，然后A的四个值变成了四个范围，然后求出$ac$和$bd$的范围，判断是否相交。注意因为有负数所以最小值乘最小值不一定就是最小值
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define rep(i, l, r) for (int i = l; i <= r; i++) 8 #define drep(i, r, l) for (int i = r; i >= l; i--) 9 typedef long long ll;10 typedef double real;11 #define double long double12 const double eps = 1e-10;13 int a, b, c, d;14 double ans;15 double getmin(double x, double y, double z)16 {17 double v1 = (x - z) * (y - z);18 double v2 = (x + z) * (y - z);19 double v3 = (x + z) * (y + z);20 double v4 = (x - z) * (y + z);21 return min(v1, min(v2, min(v3, v4)));22 }23 double getmax(double x, double y, double z)24 {25 double v1 = (x - z) * (y - z);26 double v2 = (x + z) * (y - z);27 double v3 = (x + z) * (y + z);28 double v4 = (x - z) * (y + z);29 return max(v1, max(v2, max(v3, v4)));30 }31 int main()32 {33 #ifndef ONLINE_JUDGE34 freopen("input.txt","r",stdin);35 //freopen("output.txt","w",stdout);36 #endif37 scanf("%d%d", &a, &b);38 scanf("%d%d", &c, &d);39 double l = 0, r = 1e9;40 while (fabs(r - l) > eps)41 {42 double mid = (l + r) / 2.0;43 double l1 = getmin(a, d, mid);44 double r1 = getmax(a, d, mid);45 double l2 = getmin(b, c, mid);46 double r2 = getmax(b, c, mid);47 if (r2 < l1 || l2 > r1) l = mid;48 else r = mid;49 }50 printf("%.10lf\n", (real)l);51 #ifndef ONLINE_JUDGE52 fclose(stdin); fclose(stdout);53 #endif54 return 0;55 }