https://codeforces.com/contest/1373
E. Sum of Digits
题意：给定n，k，问最小的x，满足 f(x)+f(x+1)+⋯+f(x+k)=n，其中 f(x) 为 x 的各位数字和。1≤n≤150,0≤k≤9
贪心
由给定数据范围可知 x 最多进位一次。
枚举x的位数和最高位，对于每一种位数和最高位，只需要枚举后20个数。
对于任意一个数（位数足够多），一定可以变成次低位为8或9的数，且保持和不变，例如 479，可以变成 389。
且不能再缩小范围了，因为次低位小于8的可以变成8，但是次低位为8的和次低位为9的可能k个数和不同，因为9有进位。
而需要枚举最高位则是因为防止由于总和不够而增加位数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int T;
int n, k;
int cal(ll x) {
int ans = 0;
while (x) {
ans += x % 10;
x /= 10;
}
return ans;
}
ll sol() {
for (ll i = 10; i < 1e17; i *= 10) {
for (int j = 1; j < 10; j++) {
for (int p = 20; p >= 0; p--) {
ll t = i * j - p;
if (t < 0)continue;
int tmp = 0;
for (int q = 0; q <= k; q++) {
tmp += cal(t + q);
}
if (tmp == n)return t;
}
}
}
return -1;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
printf("%lld\n", sol());
}
return 0;
}
|
F. Network Coverage
题意：n 个点环形排列，每点需要 a[i] 电力，每点有一个供电站，电量为 b[i]，能为 i 和 (i+1)%n 供电，问能否满足所有点。
首先要发现流量是可以传递的，且沿着 i−>i+1 单向传递。
所以考虑向网络流一样先预流，再看能否往回流。
先把 b[0] 所有的流量都给 a[1]，且后面所有节点每次优先使用 b[i−1] 来填充 a[i]，这样必然使得后面能获得的流量最多，如果这还不能满足，则直接GG。
但是这会使得 a[0] 没有流量，所以要把后面多余的流量再回流回来。
在预流的过程中维护 c[i]，记录 a[i] 从 b[i−1] 获得了多少流量。
再从后向前遍历，如果还有 b[i]，表示有多余，所以用 b[i] 代替 c[i] 中等量的一部分，流回 b[i−1]，即 b[i−1]+=min(b[i],c[i])。最后判断 a[0] 能否满足。
注意 b[n−1] 不能回流！其它点需要回流是因为其它点的 b[i] 没法直接对 a[0] 做出贡献，因此只能回流，而由于 b[n−1] 可以直接加到 a[0] 里，所以不需要回流，并且由于回流的过程中可能受到容量限制，而流量变小，所以 b[n−1] 更不能回流。
还有一种二分的思路。如果已知 b[0] 流多少到 a[1]，则问题就解决了，所以要二分出 b[0] 流多少。如果全部流的话，必然要多出流量（否则直接GG），所以当某一刻流量不多了，这时的流量就是分界点，用这时的流量既能满足后面的，又能给 a[0] 有最多的流量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int T;
int n;
ll a[N], b[N], c[N];
bool ck1() {
for (int i = 1; i < n; i++) {
if (b[i - 1] + b[i] < a[i])return false;
c[i] = min(a[i], b[i - 1]);
b[i - 1] -= c[i];
b[i] -= a[i] - c[i];
}
return true;
}
bool ck2() {
for (int i = n - 2; i > 0; i--) {
b[i - 1] += min(b[i], c[i]);
}
return b[0] + b[n - 1] >= a[0];
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)scanf("%lld", &a[i]);
for (int i = 0; i < n; i++)scanf("%lld", &b[i]);
fill(c, c + n, 0);
if (ck1() && ck2())puts("YES");
else puts("NO");
}
return 0;
}
|
