E. A Bit Similar
题意：
寻找长度为(k)且字典序最小的(01)串(t)，满足(01)串(s)的所有长度为(k)的子串均与(t)至少存在一个位置有相同的字符（位置需对应）
思路：
(s)取反后取出所有长度为(k)的子串，则(t)除了这(n-k+1)个串都可以取，取字典序最小的即可
#include <bits/stdc++.h>
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 << '
';
}
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 <bits/stdc++.h>
#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
", ans == 1e9 ? -1 : ans - 1);
return 0;
}