Tag

构造，背包。

Description

给定 \(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\).

Solution

不难发现如果想要拼出一个大小为 \(V\) 的水桶，瓶颈在于如何得到 \(V \bmod k\) 的水，因为其他的水都可以很容易处理出来。

不难发现我们实际上就是要求一种方案使得 \(\sum a_i \equiv V \pmod k\)。

实际上就是做一个背包的过程，特判一下不要从自己转移到自己就可以了，复杂度为 \(O(nk)\)，发现 \(n,k\) 都不大，所以可以过去。

剩下的水就可以全部倒进一个水桶里面，然后只用处理两个水桶就可以了。

时间复杂度 \(O(nk)\)，操作次数 \(O(n)\)。

细节很多，我在 VP 的时候硬是没搞出来然后死在这一题了。

Code

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 ;
}

Final

如果您在开赛两个小时后发现了某题是大水题但是过题队伍数小于 \(5\)，立刻换题，并立即忘掉这题您想的做法。