题解：CF356D Bags and Coins

每个袋子统计的硬币数和自己放的硬币与所有子袋子的硬币的和一样。

结构是一棵树，总共有

n-1

条边。

每条边会导致一个袋子被重复统计一次，所以总硬币数和输入的关系是

s = \sum a_i - (n-1)

。

因此第一步就是检查这个条件，不满足直接输出

-1

。

构造方法很简单：

找一个袋子作为根，通常选

a_i

最大的把其他袋子全放到根里。根袋子放的硬币数为

a_{root} - \sum others

，这里

other

表示其他袋子。其他袋子只放自己的硬币，不再嵌套。

CPP

#include <bits/stdc++.h>
using namespace std;
const int A = 1e5 + 10;
typedef long long B;
namespace C {
const int D = (1 << 21) + 1;
char E[D], *F, *G, H, I[40];
int J;
#define K()                                                                \
    (F == G ? (G = (F = E) + fread(E, 1, D, stdin), (F == G ? EOF : *F++)) \
            : *F++)
template <class L>
inline void readint(L& N) {
    L O = 1;
    for (H = K(); H < '0' || H > '9'; H = K())
        if (H == '-')
            O = -1;
    for (N = 0; H >= '0' && H <= '9'; H = K())
        N = (N << 3) + (N << 1) + (H & 15);
    N *= O;
}
template <class L>
inline void P(L N, char Q = '\0') {
    J = 0;
    if (N < 0)
        putchar('-'), N *= -1;
    do {
        I[J++] = N % 10 | 48;
        N /= 10;
    } while (N);
    do {
        putchar(I[--J]);
    } while (J);
    if (Q)
        putchar(Q);
}
}  // namespace C
using C::P;
using C::readint;
int R, S;
struct T {
    int U, V;
} W[A];
bool X(T Y, T Z) {
    return Y.U > Z.U;
}
bool aa(T Y, T Z) {
    return Y.V < Z.V;
}
int cnt[A], blk[A], ad, res[A], ans[A], ag[A], ah[A];
bitset<A> _A, _B;
bool tot[A];
int main() {
    readint(R), readint(S);
    for (int i = 1; i <= R; i++) {
        readint(W[i].U), W[i].V = i;
        if (W[i].U > S) {
            puts("-1");
            return 0;
        }
    }
    sort(W + 1, W + 1 + R, X);
    S -= W[1].U;
    _A[0] = 1;
    for (int i = 2; i <= R; i++) {
        _B = _A;
        _A |= _A << W[i].U;
        _B ^= _A;
        for (int k = _B._Find_first(); k < A; k = _B._Find_next(k))
            blk[k] = i;
    }
    if (_A[S] == 0) {
        puts("-1");
        return 0;
    }
    int _cnt = S;
    while (_cnt) {
        tot[blk[_cnt]] = 1;
        res[W[blk[_cnt]].V] = W[blk[_cnt]].U;
        _cnt -= W[blk[_cnt]].U;
    }
    for (int al = 1; al <= R; al++)
        if (!tot[al])
            cnt[++ad] = W[al].V;
    sort(W + 1, W + 1 + R, aa);
    for (int al = 2; al <= ad; al++) {
        res[cnt[al - 1]] = W[cnt[al - 1]].U - W[cnt[al]].U;
        ans[cnt[al - 1]] = cnt[al];
    }
    res[cnt[ad]] = W[cnt[ad]].U;
    for (int al = 1; al <= R; al++) {
        P(res[al], ' ');
        if (ans[al])
            P(1, ' '), P(ans[al], '\n');
        else
            puts("0");
    }
    return 0;
}

题解：CF356D Bags and Coins

文章操作

相关推荐

评论

题解：CF356D Bags and Coins