A. Vus the Cossack and a Contest
签。
#include <bits/stdc++.h> using namespace std; int main() { int n, m, k; while (scanf("%d%d%d", &n, &m, &k) != EOF) { if (min(m, k) >= n) { puts("YES"); } else { puts("NO"); } } return 0; }C. Vus the Cossack and Strings
题意： 给出\(a, b\)两个01串，\(|a| \geq |b|\)，询问\(a\)中所有长度等于\(|b|\)的子串和\(b\)异或之后\(1\)的个数为偶数的子串有多少个。
思路： 最自然的想法是枚举\(a\)中所有长度为\(|b|\)的子串。 其实最终我们不需要关心\(1\)的个数有多少个，只需要关心奇偶性。 那么我们暴力弄出第一个子串异或之后的\(1\)的个数模2的值。 再考虑，指针往右移动一位，会发生什么？ 比如说 011000 00110
01100 -> 11000 会发生什么？
我们注意到，这个过程相当于将\(b\)串往右移动一位， 那么对于\(a\)串来说，是去掉第一个字符和增加最后一个字符，中间的字符不变。 那么对于中间的字符来说，它对应的\(b\)中的值是前一位之前对应的\(b\)中的值，那么你要继承它的状态。 那么如果你和前一位是相同的，那么前一位之前对应的\(b\)中的值移过来的时候不会改变答案的奇偶性。 否则会改变。 前缀异或一下即可。
代码：
#include <bits/stdc++.h> using namespace std; #define N 1000010 char s[N], t[N]; int main() { while (scanf("%s%s", s + 1, t + 1) != EOF) { int lens = strlen(s + 1), lent = strlen(t + 1); int res = 0, Xor = 0, tot = 0; for (int i = 1; i <= lent; ++i) { if (s[i] != t[i]) { tot ^= 1; } if (i > 1 && s[i] != s[i - 1]) Xor ^= 1; } res += tot ^ 1; for (int i = lent + 1; i <= lens; ++i) { if (s[i] != s[i - 1]) Xor ^= 1; int pre = i - lent; if (pre > 1 && s[pre] != s[pre - 1]) Xor ^= 1; tot ^= Xor; res += tot ^ 1; } printf("%d\n", res); } return 0; }D. Vus the Cossack and Numbers
题意： 给出\(n\)个实数，他们的和为\(0\)，现在要求将每个实数上取整或者下去整，使得它们的和还是为\(0\)。
思路： 先将所有数都下去整，然后看差多少，就补回来。
处理实数的时候用字符串，忘记考虑0和-0的问题FST了。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 int n; char s[110]; int a[N], b[N], c[N]; int main() { while (scanf("%d", &n) != EOF) { int can = 0; ll sum = 0; for (int i = 1; i <= n; ++i) { scanf("%s", s + 1); a[i] = 0, b[i] = 0; int j = 1, len = strlen(s + 1); int f = 1; if (s[1] == '-') ++j, f = -1; for (; j <= len && s[j] != '.'; ++j) { a[i] = a[i] * 10 + s[j] - '0'; } for (++j; j <= len; ++j) { b[i] = b[i] * 10 + s[j] - '0'; } a[i] *= f; if (b[i] != 0) { ++can; if (f == -1) { --a[i]; } } sum += a[i]; } sum = abs(sum); //assert(sum <= can); for (int i = 1; i <= n; ++i) { if (sum > 0 && b[i] != 0) { ++a[i]; --sum; } } for (int i = 1; i <= n; ++i) { printf("%d\n", a[i]); } } return 0; }F. Vus the Cossack and a Graph
题意： 有一张\(n\)个点，\(m\)条边的图。要求最多保留\(\left \lceil \frac{n + m}{2} \right \rceil\)条边，使得每个点的新的度数\(f_i \geq \left \lceil \frac{d_i}{2} \right \rceil\)，其中\(d_i\)为原来的度数。
思路： 显然，可以理解为删去\(m - \left \lceil \frac{n + m}{2} \right\rceil\)条边，因为要保留尽量多的边没有坏处， 那么我们可以考虑每个点最多删去的度数为\(D_i = d_i - \left \lceil \frac{d_i}{2} \right \rceil\)，那么我们优先删去\(D_i\)小的点邻接的\(D_i\)大的点的边。 因为这样贪心能够保证\(D_i\)小的点邻接的边能够被优先删除，否则这些\(D_i\)小的点邻接的边对应的那个点可能因为被删除了其它边，导致可用度数不够而这些边不能被删除。 而对于可用度数大的点来说，删去哪些边的影响不大。 而我们找到了一个\(D_i\)最小的点，那么要怎么去选择它邻接的边去删除呢？ 要选择邻接的边对应的点的\(D_i\)大的删除。 因为如果选择\(D_i\)小的，那可能删完它们的\(D_i\)都变为0，不能删了。 但是可能存在这两个点都邻接一个\(D_i\)大的点，这样就可以删两条边，否则只能删一条边。
代码：
#include <bits/stdc++.h> using namespace std; #define N 1000010 #define pii pair <int, int> #define fi first #define se second int n, m; int del[N]; vector < vector <pii> > G; int d[N], a[N]; int e[N][2]; int main() { while (scanf("%d%d", &n, &m) != EOF) { memset(del, 0, sizeof del); memset(d, 0, sizeof d); G.clear(); G.resize(n + 1); int needdel = m - (n + m + 1) / 2; for (int i = 1, u, v; i <= m; ++i) { scanf("%d%d", &e[i][0], &e[i][1]); u = e[i][0], v = e[i][1]; G[u].push_back(pii(v, i)); G[v].push_back(pii(u, i)); ++d[u]; ++d[v]; } if (needdel <= 0) { printf("%d\n", m); for (int i = 1; i <= m; ++i) { printf("%d %d\n", e[i][0], e[i][1]); } continue; } priority_queue <pii, vector <pii>, greater <pii> > pq; for (int i = 1; i <= n; ++i) { d[i] = d[i] - (d[i] + 1) / 2; pq.push(pii(d[i], i)); } int u, v; while (needdel > 0) { u = 0; while (!pq.empty()) { u = pq.top().se; pq.pop(); if (d[u] <= 0) { u = 0; continue; } else break; } if (u == 0) break; sort(G[u].begin(), G[u].end(), [](pii x, pii y) { return d[x.fi] > d[y.fi]; }); for (auto it : G[u]) { if (del[it.se]) continue; v = it.fi; if (d[v] <= 0) continue; del[it.se] = 1; --d[u]; --needdel; --d[v]; if (d[v] > 0) { pq.push(pii(d[v], v)); } if (d[u] <= 0 || needdel <= 0) break; } } int sze = (n + m + 1) / 2; printf("%d\n", sze); int cnt = 0; for (int i = 1; i <= m; ++i) { if (del[i] == 0) { ++cnt; printf("%d %d\n", e[i][0], e[i][1]); } } assert(sze == cnt); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11105590.html
