Codeforces Round #717 (Div. 2)

Codeforces Round #717 (Div. 2)

A - Tit for Tat

int a[105];
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> k;
        rep (i, 1, n) cin >> a[i];
        rep (i, 1, n - 1) {
            if (!k) break;
            int c = min(a[i], k);
            a[i] -= c; k -= c; a[n] += c;
        }
        rep (i, 1, n) cout << a[i] << char(" 
"[i == n]);
    }
    return 0;
}

B - AGAGA XOOORRR

sb, 看完题, 就忘了连续的条件, 写了3个线性基, 一直wa4

连续好做多不用线性基了直接判断, 异或前缀和为(0), 那必定可以分成两个 (x),

异或和为(k) 那目标就是找三个(x), 找两个分界点即可

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n; bool f = 0;
        rep (i, 1, n) cin >> a[i], a[i] ^= a[i - 1];
        rep (i, 1, n - 2) rep (j, i + 1, n - 1)
            if (a[i] == (a[j] ^ a[i]) && a[i] == (a[n] ^ a[j])) f = 1;
        cout << (f || a[n] == 0 ? "YES
" : "NO
");
    }
    return 0;
}

C - Baby Ehab Partitions Again

背包问题

int a[N];
bool f[N];

int main() {
    IOS; cin >> n;
    rep (i, 1, n) cin >> a[i], k = a[i] & 1 ? i : k;
    while (!k) rep (i, 1, n) if ((a[i] >>= 1) & 1) k = i;
    rep (i, 1, n) m += a[i]; f[0] = 1;
    rep (i, 1, n) per (j, m, a[i]) f[j] |= f[j - a[i]];
    if ((m & 1) || !f[m >> 1]) cout << 0;
    else cout << "1
" << k;
    return 0;
}

D - Cut

倍增DP, 预处理每个位置倍增等到的点就好了

int a[N], ls[N], st[N][17];
int pri[N], tot, v[N], qp[17];

void init(int n) {
    rep(i, 2, n) {
        if (!v[i]) pri[++tot] = i, v[i] = i;
        for (int j = 1; j <= tot && pri[j] <= n / i; ++j) {
            v[i * pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
 
int main() {
    read(n, m); init(1e5); qp[0] = 1;
    rep (i, 1, n) read(a[i]);
    rep (i, 1, 16) qp[i] = qp[i - 1] << 1, st[n + 1][i] = n + 1;
    per (i, n, 1) {
        st[i][0] = st[i + 1][0];
        while (a[i] - 1) {
            int q = v[a[i]];
            if (ls[q]) umin(st[i][0], ls[q]); ls[q] = i;
            while (a[i] % q == 0) a[i] /= q;
        }
    }
    per (i, n, 1) rep (j, 1, 16) st[i][j] = st[st[i][j - 1]][j - 1];
    rep (i, 1, m) {
        int l, r, s = 1; read(l, r);
        per (j, 16, 0) if (st[l][j] <= r) l = st[l][j], s += qp[j];
        write(s); puts("");
    }
    return 0;
}