Codeforces Round #636 (Div. 3)
A.Candies
题意:
给定一个等式,其中给定,要求输出一个时满足该等式的一个 。
题解:
系数满足等比数列,,因此只要枚举,当时输出对应的即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); for (int i = 2;; i++) { if (n % ((1 << i) - 1) == 0) { printf("%d\n",n/((1<<i)-1)); return; } } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Balanced Array
题意:
给定一个,要求构造一个长度为数字序列满足:
- 前一半的数均为偶数,后一半的数均为奇数
- 所有数两两不同且都为正整数
- 前一半的数之和与后一半的数之和相等
如果存在这样的序列则输出,并输出具体的序列,否则输出
题解:
首先知道前一半的数均为偶数,所以和也会是偶数,但是后一半的数为奇数个时则不可能构造出偶数和,所以时输出,其他情况前面的数从开始,后面的数从开始,最后一个数特殊算即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); if ((n / 2) % 2 == 1) { puts("NO"); return; } puts("YES"); int sum = 0; for (int i = 1; i <= n / 2; i++) { printf("%d ", i * 2); sum += i * 2; } for (int i = 1; i < n / 2; i++) { printf("%d ", i * 2 - 1); sum -= i * 2 - 1; } printf("%d\n", sum); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Alternating Subsequence
题意:
给定序列,在所有满足正负相间的子序列中要求找出最长的那个子序列,如果长度最大的不止一个则输出元素和最大的那个
题解:
要求长度最长则贪心尽可能多的选取元素,要求元素和最大可以用滑动窗口对于一段符号均相同的区间取其中的最大者即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; ll a[maxn]; void solve() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); ll ans = 0; for (int i = 0; i < n;) { int j = i + 1; while (j < n && a[i] * a[j] > 0) j++; sort(a + i, a + j); ans += a[j - 1]; i = j; } printf("%lld\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Constant Palindrome Sum
题意:
给定一个长度为的数字序列和一个,可以对序列进行若干次操作,每次操作可以将其中一个替换成中的任意一个数,要求经过若干次操作后对于每个都满足,要求最少的操作次数
题解:
可以想到,那么对于每个,每对所需操作的最小次数是可以确定的,
那么可以用差分算出每个对应的最小贡献,遍历每个,取最小值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[maxn], cost[maxn << 1]; void solve() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i <= 2 * k + 1; i++) cost[i] = 0; for (int i = 0; i < n / 2; i++) { int x = a[i], y = a[n - i - 1]; if (x > y) swap(x, y); cost[0] += 2; cost[x + 1] -= 2; cost[x + 1] += 1; cost[(x + y - 1) + 1] -= 1; cost[x + y + 1] += 1; cost[(y + k) + 1] -= 1; cost[y + k + 1] += 2; cost[k * 2 + 1] -= 2; } int ans = INF; for (int i = 1; i <= k * 2; i++) { cost[i] += cost[i - 1]; ans = min(ans, cost[i]); } printf("%d\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E.Weights Distributing
题意:
给一个个点和条边的无向图以及三个节点,给定个权值,要求给出一种分案权值的方案使得的最短路权重之和最小。
题解:
观察两个样例就可以发现:三个点要么通过一个中间节点相连,或者三者直接成一条直线,所以最短路,对于第二种情况也成立,那么只需要算出每个节点到三者的最短路(),将权值升序排序,因为走了两次,将最短的分给路径,其余的分给和即可,枚举每个节点,求最小值
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; ll n, m, a, b, c, p[maxn]; vector<int> G[maxn]; vector<ll> bfs(int v) { queue<int> q; q.push(v); vector<ll> dis(n, INF); dis[v] = 0; while (q.size()) { int x = q.front(); q.pop(); for (int y : G[x]) { if (dis[y] > dis[x] + 1) { dis[y] = dis[x] + 1; q.push(y); } } } return dis; } void solve() { scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c); a--, b--, c--; for (int i = 0; i < n; ++i) G[i].clear(); for (int i = 0; i < m; ++i) scanf("%lld", &p[i]); for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); u--, v--; G[v].push_back(u); G[u].push_back(v); } sort(p, p + m); for (int i = 1; i < m; ++i) p[i] += p[i - 1]; vector<ll> da = bfs(a), db = bfs(b), dc = bfs(c); if (a == b && a == c) { puts("0"); return; } ll res = 1e18; for (int i = 0; i < n; ++i) if (da[i] + db[i] + dc[i] <= m) res = min(res, p[da[i] + db[i] + dc[i] - 1] + (db[i] ? p[db[i] - 1] : 0ll)); printf("%lld\n", res); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }