Educational Codeforces Round 101

E. A Bit Similar

题意：

寻找长度为\(k\)且字典序最小的\(01\)串\(t\)，满足\(01\)串\(s\)的所有长度为\(k\)的子串均与\(t\)至少存在一个位置有相同的字符（位置需对应）

思路：

\(s\)取反后取出所有长度为\(k\)的子串，则\(t\)除了这\(n-k+1\)个串都可以取，取字典序最小的即可

#include 
using namespace std;
typedef long long ll;
const int maxn = 1000010;
char s[maxn];
int sum[maxn], vis[maxn];
void output(int n, int k) {
    string ans = "";
    while (n) {
        if (n & 1)
            ans += '1';
        else
            ans += '0';
        n >>= 1;
    }
    while (ans.size() < k) ans += '0';
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}
int main() {
    int t, n, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%s", &n, &k, s + 1);
        for (int i = 1; i <= n; i++) {
            s[i] ^= 1;
            sum[i] = sum[i - 1] + s[i] - '0';
        }
        int top;
        if (k <= 20) {
            top = min((1 << k) - 1, n - k + 2);
            for (int i = 0; i <= top; i++) vis[i] = 0;
            for (int i = 1; i <= n - k + 1; i++) {
                ll cnt = 0, base = (1 << (k - 1));
                for (int j = 0; j < k; j++) {
                    if (s[i + j] == '1')
                        cnt += base;
                    base >>= 1;
                }
                if (cnt <= top) vis[cnt] = 1;
            }
        } else {
            top = n - k + 2;
            for (int i = 0; i <= top; i++) vis[i] = 0;
            for (int i = 1; i <= n - k + 1; i++) {
                if (sum[i + k - 19] - sum[i - 1]) continue;
                ll cnt = 0, base = (1 << 19);
                for (int j = 0; j < 20; j++) {
                    if (s[i + k - 20 + j] == '1')
                        cnt += base;
                    base >>= 1;
                }
                if (cnt <= top) vis[cnt] = 1;
            }
        }
        int flag = 0;
        for (int i = 0; i <= top; i++) {
            if (!vis[i]) {
                puts("YES");
                flag = 1;
                output(i, k);
                break;
            }
        }
        if (!flag) puts("NO");
    }
    return 0;
}

F. Power Sockets

题意：

有\(n\)条链，节点都是白色的，一开始有个白色的根节点，每条链可以选择一个点和已经生成的树上的一个白色节点连一条边，之后这俩节点就变成黑色，问离根节点第\(k\)近的白色节点的距离，链不必用完

思路：

链从长的开始加入，每次选择树上深度最小的白色节点与链中心相连，\(cnt[i]\)表示深度为\(i\)的白色节点数量，用线段树维护区间加，每次加完一条链要查询\(cnt\)数组前缀和第一次大于等于\(k\)的下标，在线段树上二分实现

#include 
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 200010;
ll cnt[maxn << 2], lazy[maxn << 2], sum[maxn << 2];
int l[maxn], pos, mx, ans;
void up(int rt) {
    sum[rt] = sum[ls] + sum[rs];
}
void down(int rt, int ln, int rn) {
    if (lazy[rt]) {
        lazy[ls] += lazy[rt];
        lazy[rs] += lazy[rt];
        sum[ls] += (ll)ln * lazy[rt];
        sum[rs] += (ll)rn * lazy[rt];
        lazy[rt] = 0;
    }
}
void upd(int rt, int l, int r, int v, int L, int R) {
    if (L <= l && r <= R) {
        sum[rt] += (ll)v * (r - l + 1);
        lazy[rt] += v;
        return;
    }
    int m = (l + r) >> 1;
    down(rt, m - l + 1, r - m);
    if (L <= m) upd(ls, l, m, v, L, R);
    if (R > m) upd(rs, m + 1, r, v, L, R);
    up(rt);
}
ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return sum[rt];
    }
    int m = (l + r) >> 1;
    ll ans = 0;
    down(rt, m - l + 1, r - m);
    if (L <= m)
        ans += query(ls, l, m, L, R);
    if (R > m)
        ans += query(rs, m + 1, r, L, R);
    return ans;
}
int get(int rt, int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int m = (l + r) >> 1;
    down(rt, m - l + 1, r - m);
    if (query(1, 1, mx, 1, m) >= k)
        return get(ls, l, m, k);
    else
        return get(rs, m + 1, r, k);
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    memset(cnt, 0, sizeof(cnt));
    memset(lazy, 0, sizeof(lazy));
    cnt[1] = 1;
    for (int i = 0; i < n; ++i) scanf("%d", &l[i]);
    sort(l, l + n);
    reverse(l, l + n);
    pos = 1, mx = l[0] + 500, ans = 1e9;
    upd(1, 1, mx, 1, pos + 2, pos + 1 + (l[0] - 1) / 2);
    upd(1, 1, mx, 1, pos + 2, pos + 1 + l[0] / 2);
    int res = get(1, 1, mx, k);
    if (query(1, 1, mx, 1, res) >= k)
        ans = min(ans, res);
    for (int i = 1; i < n; i++) {
        while (query(1, 1, mx, pos, pos) == 0) pos++;
        upd(1, 1, mx, -1, pos, pos);
        upd(1, 1, mx, 1, pos + 2, pos + 1 + (l[i] - 1) / 2);
        upd(1, 1, mx, 1, pos + 2, pos + 1 + l[i] / 2);
        res = get(1, 1, mx, k);
        if (query(1, 1, mx, 1, res) >= k)
            ans = min(ans, res);
    }
    printf("%d\n", ans == 1e9 ? -1 : ans - 1);
    return 0;
}