构造,背包。
给定 \(n\) 个水桶,每一个水桶初始有 \(a_i\) 的水,给定一个大小为 \(k\) 的勺子,每一次可以从一个水桶里面搞 \(\min(a_i, k)\) 的水到另一个桶里面。
求如何搞出一个水为 \(V\) 的水桶。
\(\texttt{data range:} n,k\leq 5\times 10^3, V \leq 10^9, \sum a_i \leq 5\times 10^8\).
不难发现如果想要拼出一个大小为 \(V\) 的水桶,瓶颈在于如何得到 \(V \bmod k\) 的水,因为其他的水都可以很容易处理出来。
不难发现我们实际上就是要求一种方案使得 \(\sum a_i \equiv V \pmod k\)。
实际上就是做一个背包的过程,特判一下不要从自己转移到自己就可以了,复杂度为 \(O(nk)\),发现 \(n,k\) 都不大,所以可以过去。
剩下的水就可以全部倒进一个水桶里面,然后只用处理两个水桶就可以了。
时间复杂度 \(O(nk)\),操作次数 \(O(n)\)。
细节很多,我在 VP 的时候硬是没搞出来然后死在这一题了。
const int N = 5e3 + 10; int n, k, V, al; int a[N], b[N], cnt[N], pre[N]; inline void input() { n = rd, k = rd, V = rd; FOR(i, 1, n) a[i] = rd, al += a[i]; return ; } inline void init() { FOR(i, 1, n) b[i] = a[i] % k, cnt[i] = a[i] / k; return ; } void dfs(int u) {dfs(u + 1);} inline void work() { int tot = 0; int lft = V % k; FOR(i, 1, n) if(a[i] == V) return void(puts("YES")); pre[0] = n + 1; FOR(i, 1, n) ROF(j, k - 1, 0) { if(b[i] == 0) break; if(pre[j] && pre[j] != i && !pre[(j + b[i]) % k]) pre[(j + b[i]) % k] = i; } FOR(i, 0, k - 1) cerr << pre[i] << ' '; if(!pre[lft]) return void (puts("NO")); if(al < V) return void (puts("NO")); puts("YES"); int st = pre[lft]; lft -= b[pre[lft]]; while(lft) { if(lft < 0) lft += k; printf("%d %d %d\n", cnt[pre[lft]] + 1, pre[lft], st), tot++; a[st] += a[pre[lft]], a[pre[lft]] = 0; lft -= b[pre[lft]]; } int ed = (st == n ? st - 1 : st + 1); if(st == n + 1) { st = 1, ed = 2; printf("%d %d %d\n", cnt[st] + (b[st] != 0), st, ed), tot++; a[ed] += a[st], a[st] = 0; } if(a[st] == V) return ; FOR(i, 1, n) if(a[i] != 0 && i != st && i != ed) { printf("%d %d %d\n", cnt[i] + (b[i] != 0), i, ed), tot++; a[ed] += a[i], a[i] = 0; } if(a[st] > V) { printf("%d %d %d\n", (a[st] - V) / k, st, ed); } else { printf("%d %d %d\n", (V - a[st]) / k, ed, st); } return ; } inline void solve() { input(); init(); work(); return ; }
如果您在开赛两个小时后发现了某题是大水题但是过题队伍数小于 \(5\),立刻换题,并立即忘掉这题您想的做法。