Codeforces Round #640 (Div. 4)
A.Sum of Round Numbers
题意:
把一个数拆成若干个除首位都是0的数字的和
题解:
取出各位上的数判断是否为即可
#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; void solve() { vector<int> v; v.clear(); int n, base = 1; scanf("%d", &n); while (n) { if (n % 10) v.push_back(n % 10 * base); n /= 10; base *= 10; } printf("%d\n", v.size()); for (auto i : v) printf("%d ", i); puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Same Parity Summands
题意:
构造一个长度为的序列要求满足所有元素奇偶性相同且和为。
题解:
仅为偶数且或奇偶性相同且时可以满足。
#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; void solve() { int n, k; scanf("%d%d", &n, &k); if (!(n & 1) && (n >= (k << 1))) { puts("YES"); for (int i = 1; i < k; i++) printf("2 "); printf("%d\n", n - 2 * (k - 1)); return; } if (!((n - k) & 1) && (n >= k)) { puts("YES"); for (int i = 1; i < k; i++) printf("1 "); printf("%d\n", n - k + 1); return; } puts("NO"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.K-th Not Divisible by n
题意:
求第小个不能被整除的整数。
题解:
每个区间内为个数。除一下算出来是第几个区间的第几个数乘上原长度即可。
#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; void solve() { int n, k; scanf("%d%d", &n, &k); ll a = k / (n - 1), b = k % (n - 1); printf("%lld\n", b ? a * n + b : a * n - 1); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Alice, Bob and Candies
题意:
A从左边取物,B从右边取物。要求当前人取物总和尽可能小,但要求至少大于另一个人上一次取物总和。最后不够时取完游戏结束。求取物次数以及A,B的取物总和。
题解:
用双指针模拟即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, a[maxn]; void solve() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int l = 1, r = n, cnt = 0, suml = 0, sumr = 0, lst = 0; while (l <= r) { int now = 0; while (l <= r && now <= lst) now += a[l++]; cnt++, suml += now, lst = now, now = 0; if (l > r) break; while (l <= r && now <= lst) now += a[r--]; cnt++, sumr += now, lst = now, now = 0; } printf("%d %d %d\n", cnt, suml, sumr); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E.Special Elements
题意:
如果数组里的某个数等于该数组某一个连续区间内的所有数字之和,那么该数字即为特殊点。求整个数组的特殊点数量。
题解:
用前缀和求出所有连续区间的和,遍历数组判断是否存在值相等的区间即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 8e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[maxn], pre[maxn], n; bool check[maxn]; void solve() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), check[i] = false; for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + a[i]; for (int j = 0; j < i - 1; j++) if (pre[i] - pre[j] <= n) check[pre[i] - pre[j]] = true; } int ans = 0; for (int i = 1; i <= n; i++) if (check[a[i]]) ans++; printf("%d\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
F.Binary String Reconstruction
题意:
要求构造一个二进制串,使得所有长度为的子序列满足:的个数分别为,,
题解:
因为没有限制二进制串的长度,所以可以先后最后。注意和以及和交界处会多出两个序列。要注意特判为的情况,由于题目保证一定有解,所以不用担心时同时不为的情况。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 8e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int a, b, c; scanf("%d%d%d", &a, &b, &c); if (b == 0) { if (a) for (int i = 0; i <= a; i++) putchar('0'); if (c) for (int i = 0; i <= c; i++) putchar('1'); puts(""); return; } for (int i = 0; i <= a; i++) putchar('0'); for (int i = 0; i <= c; i++) putchar('1'); for (int i = 0; i < b - 1; i++) printf("%d", i % 2); puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
G.Special Permutation
题意:
用构造一个长度为的序列满足任意相邻数字之差的绝对值在区间中。
题解:
。其中当 时无解
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 8e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); if (n <= 3) puts("-1"); else { for (int i = n; i >= 1; i--) if (i & 1) printf("%d ", i); printf("4 2 "); for (int i = 6; i <= n; i += 2) printf("%d ", i); puts(""); } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }