本文最后更新于 132 天前，其中的信息可能已经有所发展或是发生改变。
Before the Beginning
转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1405/
前言
补题。
C
给定一个字符串和 $k$，要求每个长度为 $k$ 的子串都有 $\dfrac{k}{2}$ 个 $0$ 与 $\dfrac{k}{2}$ 个 $1$.
字符串中有部分 ?，可以决定 ? 为 $0$ 或 $1$，问是否能实现。
可以发现，给 ? 赋值并非完全自由。
例如从 $[1,k]$ 移动到 $[2,k+1]$ 时，若 $s_{k+1}$ 为确定值，则 $s_1$ 也可以被确定。
因为公共部分 $[2,k]$ 且 $[1,k]$ 满足条件，则减少一个 $1$ 一定要补充一个 $1$，反之同理。
另外，若某个区间内已确定的值有过半的，则一定不行。
#include <cstdio>
const int maxn = 3e5 + 100;
int T,n,k;
char s[maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
scanf("%s", s + 1);
int one = 0,zero = 0;
for (int i = 1; i < k; ++i) one += (s[i] == '1'), zero += (s[i] == '0');
for (int i = 1; i <= n - k + 1; ++i)
{
one -= (s[i - 1] == '1'), zero -= (s[i - 1] == '0');
one += (s[i + k - 1] == '1'), zero += (s[i + k - 1] == '0');
if (one > k / 2 || zero > k / 2) goto fail;
if (i + k > n) break;
if (s[i + k] != '?')
{
if (s[i] != '?') { if (s[i] != s[i + k]) goto fail; }
else s[i] = s[i + k];
}
else if (s[i] != '?') s[i + k] = s[i];
}
one = zero = 0;
for (int i = 1; i < k; ++i) one += (s[i] == '1'), zero += (s[i] == '0');
for (int i = 1; i <= n - k + 1; ++i)
{
one -= (s[i - 1] == '1'), zero -= (s[i - 1] == '0');
one += (s[i + k - 1] == '1'), zero += (s[i + k - 1] == '0');
if (one > k / 2 || zero > k / 2) goto fail;
}
printf("%s\n", s + 1);
puts("YES");
continue;
fail:
puts("NO");
}
return 0;
}B
$a_i := a_i – 1$,$a_j := a_j + 1$，若 $i < j$ 则无需花费，否则花一元。
求多少次后数组变零，保证有解。
考虑先将无需花费的全部消去。
从后往前，维护小于零的数的和，用于消去大于零的数。若无法消去，计答案。
#include <cstdio>
const int maxn = 3e5 + 100;
int T,n;
int a[maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
long long sum = 0,res = 0;
for(int i = n;i;--i)
{
if(a[i] < 0) sum -= a[i];
else
{
if(a[i] >= sum) res += a[i] - sum,sum = 0;
else sum -= a[i];
}
}
printf("%lld\n",res);
}
}A
显然倒过来即可。
#include <cstdio>
#include <algorithm>
int T,n,a[110];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i = 1; i <= n; ++i) scanf("%d",a+i);
for (int i = n; i; --i) printf("%d ", a[i]);
puts("");
}
return 0;
}D
若干次移动后，若先手能追上后手，则先手胜， 否则后手胜。
- 先手一步能追上后手，先手胜。
- 先手一步距离大于树的直径的一半，走到中心后一步可到达任意点，先手胜。
- 后手距离大于两倍先手距离，则后手总是可以移动到先手一步范围之外，后手胜。
- 后手距离小于等于两倍先手距离，则先手不断逼近后手，最后后手无法横跨先手支配领域，而另一方向空间不足，先手必胜。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
static char c;
static int flag;
flag = 1, r = 0;
for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
return r *= flag;
}
const int maxn = 1e5 + 100;
struct node
{
int to, next;
} E[maxn << 1];
int head[maxn], tot;
inline void add(const int& x, const int& y) { E[++tot].next = head[x], E[tot].to = y, head[x] = tot; }
int T, n, a, b, da, db, d;
int dep[maxn], maxx[maxn], secx[maxn];
void dfs(int u, int fa)
{
maxx[u] = secx[u] = 0;
for (int p = head[u]; p; p = E[p].next)
{
int v = E[p].to;
if (v == fa) continue;
dep[v] = dep[u] + 1, dfs(v, u);
if (maxx[v] + 1 > maxx[u]) secx[u] = maxx[u], maxx[u] = maxx[v] + 1;
else if (maxx[v] + 1 > secx[u]) secx[u] = maxx[v] + 1;
}
d = std::max(maxx[u] + secx[u], d);
}
int main()
{
read(T);
while (T--)
{
tot = d = 0;
read(n), read(a), read(b), read(da), read(db);
for (int i = 1; i <= n; ++i) head[i] = maxx[i] = secx[i] = dep[i] = 0;
for (int i = 1; i < n; ++i)
{
int x, y;
read(x), read(y), add(x, y), add(y, x);
}
dfs(a, 0);
int dis = dep[b];
if (dis <= da) puts("Alice");
else if (da * 2 >= d) puts("Alice");
else if (db > da * 2) puts("Bob");
else puts("Alice");
}
return 0;
}E
当 $a_i = i$ 时，可以删除该元素。
每次删除后，其后元素前移。
回答 $q$ 个问题，将前 $x$ 个元素与后 $y$ 个元素替换为 $n+1$ 使它们不可能被删除后，最多能删除多少个数。
预处理：$a_i := i – a_i$，此时 $a_i$ 表示，其前方删除 $a_i$ 个数后当前数可以删除。
若 $a_i < 0$，则显然永远无法删除，令 $a_i = n + 1$.
每次一个数变成 $0$ 后，将其后的所有数减一。
将询问排序，从右向左处理，若能删除则在线段树上区间减一。
若 $a_i > 0$ 则插入线段树等待维护。
每次有零时，更新线段树，再找到最右端的零，继续更新。在此过程中，将零产生的对答案的贡献插入树状数组中。
而已经记过答案的位置，为了避免重复计，赋一个极大值。
#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <vector>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
static char c;
static int flag;
flag = 1, r = 0;
for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
return r *= flag;
}
const int maxn = 3e5 + 100;
int n, m, a[maxn];
struct query
{
int l, r, id;
} Q[maxn];
int ANS[maxn];
bool cmp(const query& a, const query& b) { return a.l > b.l; }
namespace Bit
{
int sum[maxn];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int k) { for (; x <= n; x += lowbit(x)) sum[x] += k; }
inline int ask(int x)
{
int res = 0;
for (; x > 0; x -= lowbit(x)) res += sum[x];
return res;
}
inline int ask(int l, int r) { return ask(r) - ask(l - 1); }
} // namespace Bit
namespace Seg
{
int minr[maxn << 2], minn[maxn << 2], tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushdown(const int& p)
{
if (!tag[p]) return;
minn[ls] += tag[p], minn[rs] += tag[p];
tag[ls] += tag[p], tag[rs] += tag[p];
tag[p] = 0;
}
void build(int l, int r, int p)
{
minr[p] = r, minn[p] = 1 << 30;
if (l == r) return;
int mid = l + r >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
inline void pushup(const int& p)
{
minn[p] = std::min(minn[ls], minn[rs]);
if (minn[rs] == minn[p]) minr[p] = minr[rs];
else minr[p] = minr[ls];
}
void modify(int l, int r, int p, int ll, int rr, int k)
{
if (ll > rr) return;
if (l >= ll && r <= rr) return (void)(minn[p] += k, tag[p] += k);
int mid = l + r >> 1;
pushdown(p);
if (ll <= mid) modify(l, mid, ls, ll, rr, k);
if (rr > mid) modify(mid + 1, r, rs, ll, rr, k);
pushup(p);
}
void set(int l, int r, int p, int pos, int k)
{
if (l == r) return (void)(minn[p] = k);
pushdown(p);
int mid = l + r >> 1;
if (pos <= mid) set(l, mid, ls, pos, k);
else set(mid + 1, r, rs, pos, k);
pushup(p);
}
pair<int, int> ask(int l, int r, int p, int ll, int rr)
{
if (l >= ll && r <= rr)
{
if (minn[p] == 0) return make_pair(0, minr[p]);
return make_pair(1 << 30, 0);
}
int mid = l + r >> 1;
pair<int, int> res;
res.first = 1 << 30, res.second = 0;
pushdown(p);
if (ll <= mid) res = ask(l, mid, p << 1, ll, rr);
if (rr > mid)
{
pair<int, int> t = ask(mid + 1, r, p << 1 | 1, ll, rr);
if (res.first >= t.first) res = t;
}
return res;
}
} // namespace Seg
int main()
{
read(n), read(m);
for (int i = 1; i <= n; ++i) read(a[i]), a[i] = i - a[i];
for (int i = 1; i <= m; ++i) read(Q[i].l), read(Q[i].r), Q[i].l++, Q[i].r = n - Q[i].r, Q[i].id = i;
std::sort(Q + 1, Q + 1 + m, cmp);
Seg::build(1, n, 1);
int p = n;
for (int i = 1; i <= m; ++i)
{
while (p >= Q[i].l)
{
if (a[p] > 0) Seg::set(1, n, 1, p, a[p]);
else if (a[p] == 0)
{
Seg::modify(1, n, 1, p + 1, n, -1);
Bit::add(p, 1);
pair<int, int> t = Seg::ask(1, n, 1, p + 1, n);
while (t.first != (1 << 30))
{
Bit::add(t.second, 1);
Seg::modify(1, n, 1, t.second + 1, n, -1);
Seg::set(1, n, 1, t.second, n + 100);
t = Seg::ask(1, n, 1, p + 1, n);
}
}
--p;
}
ANS[Q[i].id] = Bit::ask(Q[i].l, Q[i].r);
}
for (int i = 1; i <= m; ++i) printf("%d\n", ANS[i]);
return 0;
}