# Codeforces Round #572 (Div. 2)

2022年11月23日
0 收藏 808 点赞 4,674 浏览 5607 个字

## Contest Info

Solved A B C D1 D2 E F
6/7 Ø Ø Ø Ø Ø Ø
• O 在比赛中通过
• Ø 赛后通过
• ! 尝试了但是失败了
• – 没有尝试

## Solutions

### A. Keanu Reeves

#include <bits/stdc++.h>using namespace std; #define N 1100char 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;}

### B. Number Circle

#include <bits/stdc++.h>using namespace std; #define N 100010int 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;}

### C. Candies!

• 对于长度为$$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 20int 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;}

### D1. Add on a Tree

#include <bits/stdc++.h>using namespace std;#define N 100010int 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;}

### D2. Add on a Tree: Revolution

• $$(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}$$

#include <bits/stdc++.h>using namespace std;#define N 1100int 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;}

### E. Count Pairs

$\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 longint 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;}

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用