Codeforces Round #722 (Div. 2) A~D题解
Codeforces Round #722 (Div. 2) A~D题解
补题链接:Here
1529A. Eshag Loves Big Arrays
【题意描述】
给定一个长度为 n 的正整数数组 a ,现在可执行若干次操作(可为 0)
具体操作为:选定某个序列,删除严格大于序列的平均数的元素
请问最多能删去多少个元素
【解题思路】
观察一下样例容易发现,在若干次操作之后,一定是最小的元素留下,所以我们只需要统计最小值元素个数,然后输出 n−Mincnt
【AC 代码】
void solve() { int n; cin >> n; int a[n + 1]; for (int i = 1; i <= n; ++i)cin >> a[i]; sort(a + 1, a + 1 + n); int cnt = 0; for (int i = 1; i <= n; ++i)if (a[i] == a[1])cnt++; cout << n - cnt << "\n"; }
1529B. Sifid and Strange Subsequences
【题意描述】
先有一个长度为 n 的数组,定义“奇怪数组”:数组中任意两个元素的绝对值差值大于等于数组中的最大值,即 |ai−aj|>=Max ,请问由原数组中最大能选出多少个元素构成“奇怪数组”
【解题思路】
很容易证明一个奇怪的子序列不能包含一个以上的正元素。
所以最好选择所有的非正元素,现在我们最多只能选择一个正元素。
假设x是数组中最小的正元素。如果已经选取的集合中没有两个元素(如a和b)以a的方式存在,我们可以选取 |x−b|<x。
要检查这一点,我们只需对已经拾取的元素进行排序,并查看相邻元素对之间的差异。
复杂性:O(nlog n)
【AC 代码】
void solve() { int n; cin >> n; vector<int>a(n); for (int &x : a)cin >> x; sort(a.begin(), a.end()); int ans = 0, cnt0 = 0, cnt = 0; for (int i = 0; i < n; ++i) { if (a[i] < 0)ans++; else if (a[i] == 0)cnt0++; } int res = ans + cnt0, Min = 1e9; for (int i = 0; i + 1 < n; ++i) { if (a[i + 1] > 0)break; Min = min(Min, a[i + 1] - a[i]); } for (int i = 0; i < n; ++i)if (a[i] > 0 and a[i] <= Min)cnt++; res = max(res, ans + (cnt0 > 0) + (cnt > 0)); cout << res << "\n"; }
1529C. Parsa's Humongous Tree
【题意描述】
给你一棵树,树上的每个节点 i 都有一个值域 [li,ri] ,我们需要从值域中确定一个值 ai∈[li,ri] ,而 (u,v) 边权值则为∣au−av∣ 。我们的目的就是要让所有的边权值之和最大。求出最大权值之和。
【解题思路】
感觉AtCoder上有一道很像的题
【AC 代码】
using ll = long long;const int N = 1e5 + 10;vector<int>g[N];int a[N][2], n; ll f[N][2];void dfs(int v, int p) { for (int s : g[v]) if (s != p) { dfs(s, v); f[v][0] += max(f[s][0] + abs(a[s][0] - a[v][0]), f[s][1] + abs(a[s][1] - a[v][0])); f[v][1] += max(f[s][0] + abs(a[s][0] - a[v][1]), f[s][1] + abs(a[s][1] - a[v][1])); } }void solve() { cin >> n; for (int i = 0; i < n; ++i)cin >> a[i][0] >> a[i][1]; for (int i = 0, u, v; i + 1 < n; ++i) { cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } dfs(0, -1); cout << max(f[0][0], f[0][1]) << "\n"; for (int i = 0; i < n; ++i) { g[i].clear(); f[i][0] = f[i][1] = 0; } }
1529D. Kavi on Pairing Duty
【题意描述】
【解题思路】
设 dpi 为 2i 点的良好配对数。
显然,答案是 dpn 。
引理:表示x为与点1匹配的点。注意每个点p(x<p≤2n )属于长度等于 [1,x] 长度的线段。
证明:假设某点p(x<p≤2n )与点q配对(q>p),因为[p,q]不在 [1,x] 之内,所以它们的大小必须相等,配对才是好的。
为了计算dpn,考虑以下情况:
x>n :类似于上述引理,可以证明每个点p(1≤p≤2n−x+1)与点i+x配对−1,剩余的未配对x−n−1个点形成一个连续的子阵列,该子阵列位于每个当前对内,因此它们可以在dpx中配对−n−1种方式。
x≤n:在这种情况下,由于上述引理,所有的线段必须具有相同的长度,因此它们的长度必须是n的一个除数,在这种情况下,它们可以以D(n)的方式配对;其中D(n)是n的除数。
所以 dpn=D(n)+∑n−1i=0dpi。
注意 dp0=dp1=1。
【AC 代码】
const int N = 1e6 + 10, MOD = 998244353;int n, dp[N], S;void solve() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = i + i; j <= n; j += i) { dp[j]++; } } dp[0] = S = 1; for (int i = 1; i <= n; i++) { dp[i] = (dp[i] + S) % MOD; S = (S + dp[i]) % MOD; } cout << dp[n] << endl; }
The desire of his soul is the prophecy of his fate
你灵魂的欲望,是你命运的先知。
来源:https://www.cnblogs.com/RioTian/p/14808932.html