Codeforces Round #665 (Div. 2)解题报告

Codeforces Round #665 (Div. 2)

A. Distance and Axis

题目大意

给定横轴$OX$，其中$A$点坐标为$x$，每次你可以使得$x-1$或$x+1$，问你操作多少次后满足条件的点$B$存在，其中： $$|OB-AB|=k$$

解题思路

假设$B$点坐标为$y$，最终$A$点坐标为$n$，则：

$y<n$ $|y-(n-y)|=k\Rightarrow n=2y\pm k$ 可以看出此时$n\pm k$为偶数，所以只需将$x$变成奇数或偶数即可，此时答案为$0$或$1$$y\ge n$ $|y-(y-n)|=k\Rightarrow n=k$ 那么此时答案为$|x-k|$

AC代码

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T; cin >> T; while(T--) { int n, k; cin >> n >> k; int res = abs(n - k); if((n + k) % 2 == 0) { int x = (n + k) / 2; if(x <= n) res = 0; } else { if(n + k >= 1) { int x = (n + k - 1) / 2; if(x <= n) res = min(res, 1); } else { int x = (n + k + 1) / 2; if(x <= n) res = min(res, 1); } } cout << res << '\n'; } return 0; }

B. Ternary Sequence

题目大意

定义两个序列$a$和$b$，其中$a$序列中有$x_1$个$0$，$y_1$个$1$，$z_1$个$2$，同理，$b$中有$x_2$个$0$，$y_2$个$1$，$z_2$个$2$，现在让你重新排列$a$和$b$使得${\sum }_{i=1}^n{c}_i$最大，其中$c_i$其中定义如下： $$c_i=\{\begin{array}{l}{a}_i{b}_i{a}_i>b_i\\ 0a_i=b_i\\ -a_i{b}_i{a}_i<b_i\end{array}$$

解题思路

我们可以把所有的情况列举出来

$a_i$$b_i$$c_i$00001002010011012-2200212220

那么我们很显然要将$a$中的$2$尽量与$b$中的$1$进行匹配，将$b$中的$2$尽量与$a$中匹配后剩余的$2$、$0$进行匹配，那么答案即为： $$2\times min(z_1,y_2)-2\times max(0,z_2-x_1-(z_1-min(z_1,y_2)))$$

AC代码

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T; cin >> T; while(T--) { int x1, y1, z1; int x2, y2, z2; cin >> x1 >> y1 >> z1; cin >> x2 >> y2 >> z2; cout << 2 * min(z1, y2) - 2 * max(0, z2 - x1 - (z1 - min(z1, y2))) << '\n'; } return 0; }

C. Mere Array

题目大意

给定一个序列$a$，若$gcd(a_i,a_j)=mi{n}_{i=1}^n{a}_i$，那么你可以将$a_i$与$a_j$进行交换，问你经过若干次操作后是否能将$a$序列变为一个非递减序列

解题思路

模拟发现对于任意两个最小值的倍数之间可以通过最小值作为中转站进行交换，而非最小值的倍数的位置无法改变，故将其倍数挑选出来排序后$O(n)$遍历判断其是否为非递减序列即可

AC代码

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int Min = INT_MAX; int a[maxn], d[maxn]; struct Node { int w, id; Node() { w = id = 0; } Node(int ww, int iid) { w = ww, id = iid; } bool operator< (const Node& obj) { if(w != obj.w) return w < obj.w; return id < obj.id; } }b[maxn], c[maxn]; bool check(int n) { for(int i = 1; i <= n; ++i) { if(d[i] < d[i - 1]) return false; } return true; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T; cin >> T; while(T--) { int n; cin >> n; Min = INT_MAX; for(int i = 1; i <= n; ++i) { cin >> a[i]; Min = min(a[i], Min); d[i] = 0; } int cntb = 0, cntc = 0; for(int i = 1; i <= n; ++i) { if(a[i] % Min != 0) b[++cntb] = Node(a[i], i); else c[++cntc] = Node(a[i], i); } sort(c + 1, c + cntc + 1); for(int i = 1; i <= cntb; ++i) { d[b[i].id] = b[i].w; } int cnt = 0; for(int i = 1; i <= n; ++i) { if(d[i]) continue; d[i] = c[++cnt].w; } if(check(n)) cout << "YES" << '\n'; else cout << "NO" << '\n'; } return 0; }

D. Maximum Distributed Tree

题目大意

给定$n$个节点构成的一颗树，其各个边权值未知，现在然你为其$n-1$条边分别赋权，并且满足以下三个条件：

边权大于0所有边权的乘积为$k$权值为$1$的边要尽量少

定义$f(u,v)$为树上节点$u$到$v$的路径和，并给定$k$的所有质数因子$p_i$，即$k={\prod }_{i=1}^m{p}_i$，问你${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^{n}f(i,j)$的最大值是多少

结果对$1e^9+7$取模

解题思路

模拟发现，我们只需要求出每条边$(u,v)$被经过的次数即可，假设现将边$(u,v)$断开，那么该数被切割成两个子树，假设$v$所在子树节点数为$x$，总节点数为$n$，那么边$(u,v)$被经过的次数$nu{m}_{(u,v)}=C_{n-x}^1{C}_x^1=x\times (n-x)$，以任意节点为根节点做一次$dfs$即可

然后将其经过次数排序分别与$p_i$一一对应即可

要注意的是若$m>n-1$则需要将多余的边赋权为$1$，若$m\le n-1$需要将最大的那些$p_i$乘起来与经过次数最多的边对应

AC代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 1e5 + 10; ll a[maxn], b[maxn]; int sz[maxn], n, cnt; vector<int> v[maxn]; void dfs(int u, int fa) { sz[u] = 1; int len = v[u].size(); for(int i = 0; i < len; ++i) { if(v[u][i] == fa) continue; dfs(v[u][i], u); sz[u] += sz[v[u][i]]; b[++cnt] = sz[v[u][i]] * 1ll * (n - sz[v[u][i]]); } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T; cin >> T; while(T--) { cnt = 0; cin >> n; for(int i = 1; i <= n; ++i) v[i].clear(); for(int i = 1; i < n; ++i) { int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); a[i] = 1; } int m; cin >> m; for(int i = 1; i <= m; ++i) cin >> a[i]; dfs(1, 0); if(m > n - 1) { sort(a + 1, a + m + 1); for(int i = n; i <= m; ++i) { a[n - 1] = a[n - 1] * a[i] % mod; } reverse(a + 1, a + n); } else sort(a + 1, a + n, greater<ll>()); ll res = 0; sort(b + 1, b + n, greater<ll>()); for(int i = 1; i < n; ++i) { res = (res + a[i] * (b[i] % mod) % mod) % mod; } cout << res << '\n'; } return 0; }