目录
Contest InfoSolutions A. Keanu ReevesB. Number CircleC. Candies!D1. Add on a TreeD2. Add on a Tree: RevolutionE. Count PairsPractice Link
SolvedABCD1D2EF6/7ØØØØØØ- O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到题。
#include <bits/stdc++.h> using namespace std; #define N 1100 char s[N]; int n; int main() { while (scanf("%d%s", &n, s + 1) != EOF) { int cnt = 0; for (int i = 1; i <= n; ++i) { if (s[i] == '1') ++cnt; else --cnt; } if (cnt) { puts("1"); puts(s + 1); } else { puts("2"); printf("%c %s\n", s[1], s + 2); } } return 0; }题意： 有一个序列\(a_1, a_2, \cdots, a_n\)，要求重新排列构成一个环，任意一个数都要满足严格小于旁边两数之和。 输出方案；
思路： 本来的想法是最大的放中间，次大，第三大的放旁边这样一次放下去，但是发现这样并不总能构造出解。 后来想想，直接降序排，那么其中除了最大的一个元素可能不满足，其他元素肯定都满足。 那么我们先降序排，有\(a_n, a_{n - 1}, \cdots, a_1\) 然后将\(a_{n - 1}\)移到最后一个，依然满足其他元素都满足，最大的那个元素可能不满足。 但是这个情况下，如果最大的元素都不满足，那肯定满足不了了，因为和最大的元素相邻的是次大的和第三大的。
代码:
#include <bits/stdc++.h> using namespace std; #define N 100010 int n, a[N], b[N]; bool ok(int *a) { if (a[2] + a[n] <= a[1]) return 0; if (a[1] + a[n - 1] <= a[n]) return 0; for (int i = 2; i < n; ++i) { if (a[i - 1] + a[i + 1] <= a[i]) { return 0; } } return 1; } int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d", a + i); sort(a + 1, a + 1 + n, [](int x, int y) { return x > y; }); b[1] = a[1]; for (int i = 3; i <= n; ++i) b[i - 1] = a[i]; b[n] = a[2]; if (ok(b)) { puts("YES"); for (int i = 1; i <= n; ++i) printf("%d%c", b[i], " \n"[i == n]); } else { puts("NO"); } } return 0; }题意： 有\(n\)个数\(s_i(0 \leq s_i \leq 9)\)，定义这样一种过程：
对于长度为\(2\)的幂次的子区间\([a_1, a_2, \cdots, a_{2^k}]\)，每次替换\((a_{2i}, a_{2i + 1})(0 \leq i < 2^{k -1})\)为\((a_{2i} + a_{2i + 1}) \bmod 10\)。如果某一步的\(a_{2i} + a_{2i + 1} >= 10\)，那么会获得一个糖果重复操作，知道序列中数的个数变为\(1\)。 每次询问\(f[a_1, a_2, \cdots, a_{2^k}]\)表示\([a_1, a_2, \cdots, a_{2^k}]\)这个区间执行上述操作最后得到的糖果个数是多少。思路：\(f[i][j]\)表示以第\(i\)位为起点，长度为\(j\)的区间的糖果个数多少，倍增即可。
代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 #define D 20 int n, q, l, r, a[N]; int f[N][20], g[N][20]; int main() { while (scanf("%d", &n) != EOF) { memset(f, 0, sizeof f); memset(g, 0, sizeof g); for (int i = 1; i <= n; ++i) scanf("%d", a + i), g[i][0] = a[i]; for (int j = 1; j <= 20; ++j) { for (int i = 1; i <= n; ++i) { if (i + (1 << j) - 1 > n) break; int nx = (i + (1 << (j - 1))); f[i][j] = f[i][j - 1] + f[nx][j - 1]; g[i][j] = g[i][j - 1] + g[nx][j - 1]; if (g[i][j] >= 10) { ++f[i][j]; g[i][j] %= 10; } } } scanf("%d", &q); while (q--) { scanf("%d%d", &l, &r); int t = r - l + 1, q = 0; while (t) { ++q; t /= 2; } --q; printf("%d\n", f[l][q]); } } return 0; }题意： 有一棵树，每次可以选取两个叶子结点，将这两个叶子的简单路径上的所有边的边全加上\(x\)。 询问给定任意一种边权方案，是否都能通过有限次这种操作完成。
思路： 当且仅当树中没有度数为\(2\)的点的时候，可以。
代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 int n, a[N], d[N]; int main() { while (scanf("%d", &n) != EOF) { memset(d, 0, sizeof d); for (int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); ++d[u]; ++d[v]; } bool F = 1; for (int i = 1; i <= n; ++i) if (d[i] == 2) F = 0; puts(F ? "YES" : "NO"); } return 0; }题意： 和D1的不同之处在于每次加的\(x\)都是整数，而且这次给出边的需求边权，要求一种方案。并且边权都是偶数。
思路： 当且仅当树中没有度数为\(2\)的点的时候, 为什么？ 首先，除了叶子结点意外以外，其他结点的度数都\(>= 3\)。 那么我们考虑其中一个点\(u\)，有三个点\(l_1, l_2, v\)分别属于\(u\)的三个不同子树。 那么我们要想改变\((u, v)\)这条边的边权为\(x\)，那么我们这么操作：
\((g[v], g[l_1])\) 加 \(\frac{x}{2}\)\((g[v], g[l_2])\)加\(\frac{x}{2}\)\((g[l_1], g[l_2])\)加\(-\frac{x}{2}\)其中\(g[u]\)表示的是\(u\)子树下的某个叶子结点。 这样之后我们发现我们将\((g[l_1], g[l_2])\)上的边的边权恢复原状了。 而只改动了\((u, g[v])\)路径上的边，并且\((u, v)\)这条边已经达到要求了。 而\((v, g[v])\)这些边直接更改他们的需求，递归下去做即可。
代码：
#include <bits/stdc++.h> using namespace std; #define N 1100 int n, leaf[N], W[N], g[N], root; int e[N][3]; vector <vector<int>> G; struct node { int u, v, w; node() {} node(int u, int v, int w) : u(u), v(v), w(w) {} }; vector <node> res; bool ok() { for (int i = 1; i <= n; ++i) { if (G[i].size() == 2) { return 0; } if (root == -1 || G[i].size() > G[root].size()) { root = i; } } return 1; } int getleaf(int u) { if (G[u].size() == 0) return u; for (auto v : G[u]) { return getleaf(v); } } int fa[N]; void pre(int u) { for (auto v : G[u]) if (v != fa[u]) { fa[v] = u; pre(v); } } void DFS(int u) { if (G[u].empty()) return; for (auto v : G[u]) leaf[v] = getleaf(v); int sze = (int)G[u].size(); if (sze >= 2) { g[G[u][0]] = leaf[G[u][1]]; } for (int i = 1; i < sze; ++i) { g[G[u][i]] = leaf[G[u][i - 1]]; } for (int sze = (int)G[u].size(), i = 0; i < sze; ++i) { int v = G[u][i]; int nx, nnx; if (u == root) { if (i == 0) { nx = leaf[G[u][1]], nnx = leaf[G[u][2]]; } else if (i == sze - 1) { nx = leaf[G[u][i - 1]], nnx = leaf[G[u][i - 2]]; } else { nx = leaf[G[u][i - 1]], nnx = leaf[G[u][i + 1]]; } } else { nx = g[u]; if (i == 0) { nnx = leaf[G[u][1]]; } else { nnx = leaf[G[u][i - 1]]; } } res.push_back(node(leaf[v], nx, W[v] / 2)); res.push_back(node(leaf[v], nnx, W[v] / 2)); res.push_back(node(nx, nnx, -W[v] / 2)); //cout << v << " " << nx << " " << nnx << endl; int it = leaf[v]; while (it != v) { W[it] -= W[v]; it = fa[it]; } } for (auto v : G[u]) DFS(v); } int main() { while (scanf("%d", &n) != EOF) { G.clear(); G.resize(n + 1); for (int i = 1; i < n; ++i) { int &u = e[i][0], &v = e[i][1], &w = e[i][2]; scanf("%d%d%d", &u, &v, &w); G[u].push_back(v); G[v].push_back(u); } root = -1; if (!ok()) { puts("NO"); } else { if (n == 2) { printf("YES\n1\n"); printf("1 2 %d\n", e[1][2]); continue; } res.clear(); pre(root); G.clear(); G.resize(n + 1); for (int i = 1; i < n; ++i) { if (fa[e[i][0]] == e[i][1]) { swap(e[i][0], e[i][1]); } G[e[i][0]].push_back(e[i][1]); W[e[i][1]] = e[i][2]; } DFS(root); puts("YES"); printf("%d\n", (int)res.size()); assert(res.size() <= 100000); for (auto it : res) { printf("%d %d %d\n", it.u, it.v, it.w); } } } return 0; }题意： 给出\(n\)个数\(a_i\)，询问有多少对\((i, j)\)满足\((a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p\)
思路：\[ \begin{eqnarray*} (a_i + a_j)(a_i^2 + a_j^2) &\equiv& k \bmod p \rightarrow \\ (a_i + a_j)(a_i - a_j)(a_i^2 + a_j^2) &\equiv& k(a_i - a_j) \bmod p \rightarrow \\ (a_i^4 - a_j^4) &\equiv& k(a_i - a_j) \bmod p \rightarrow \\ (a_i^4 - ka_i) - (a_j^4 - ka_j) &\equiv& 0 \bmod p \rightarrow \\ a_i^4 - ka_i &\equiv& a_j^4 - ka_j \bmod p \end{eqnarray*} \] 然后直接统计即可。
代码：
#include <bits/stdc++.h> using namespace std; #define N 300010 #define ll long long int n; ll p, k, a[N]; map <ll, int> mp; int main() { while (scanf("%d%lld%lld", &n, &p, &k) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%lld", a + i); a[i] = (a[i] * a[i] % p * a[i] % p - k + p) % p * a[i] % p; } sort(a + 1, a + 1 + n); mp.clear(); ll res = 0; for (int i = 1; i <= n; ++i) { if (mp.find(a[i]) != mp.end()) { res += mp[a[i]]; } // if (mp.find(p - a[i]) != mp.end()) { // res += mp[p - a[i]]; // } mp[a[i]]++; } printf("%lld\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11144057.html
