宜 360° 自我评估，忌盲目自信 / 自卑。
无论任何时候，周遭人们所看到的我，都比我看到的自己更多。
——小川糸《山茶文具店》
A. 数字游戏
http://222.180.160.110:1024/contest/4424/problem/1
闲话
一开始忘了怎么做的然后从 Cindy 的做法开始回忆，一边回忆一边写下文，结果发现写着写着变成 wjf 的做法了 /cf
upd：变成菌的做法了 /cf /cf /cf
upd：变成 zmq 的做法了，我已经懒得 /cf 了。
题意转化一下，大致就是一个每次往右拓展一位的询问区间，每次查询该询问区间内最大值并拿走之。
我们先感性地想，对于一个 很大的值，它一进入询问范围就会被当场拿走。
那如果没有被拿走是因为什么呢？因为在前面积存下来的元素中还有比它大的。
那为什么前面的比它大的元素没有被当场拿走呢？因为在更前面积存下来的有比这个元素大的…… 那么最开始的积存是怎么来的呢？是最初询问区间为 \([1,p_i]\) 而非 \([1,1]\) 导致的。
被积存下的数被拿出来用掉的时刻，就是往后碰到了一个比它小的值，然后顶替掉这个值被用掉。被顶替的就进入积存区。
所以这个时候我们直接 模拟 积存数被用掉的过程。
对于全序列中的最大值，当场用掉。次大值呢，若它比最大值先进入询问区间，皆大欢喜，当场用掉；又因为最大值不可能被积存，就算它在最大值之后，也可以当场用掉。
第三大的，就可能进积存区。假设它要出来，首先要满足出来的时间（在进入积存区之后，有点废话），然后如果它一出来就碰到了比它更大的，很不幸，出不来了。但是因为除了最大和次大之外没有元素比它大了，它就可以在剩下的位置里面随便挑——当然是挑最靠前的。后面的和第三大道理就差不多了。
所以这个时候我们就可以得到一个大致的做法了，我们把元素从大到小排序，顺便记录一下它进入询问范围的时间 \(t\)。然后我们优先让这个值在 \(t\) 时刻直接被拿走。那假如 \(t\) 这个位置已经被更大的元素占领了，就找这之后第一个空位。
那么这个「第一个空位」怎么找呢？我们用一个初值为 \(1\) 的 \(pos\)，对于当场拿走的情况，肯定是不会有冲突的，所以冲突都发生在积存区。积存区又都是从 \(1\) 开始的，所以我们只需要对于不是当场拿走的情况，把 \(pos\) 移到距离 当前值 最近的空位然后放进去就可以了。因为 \(pos\) 全程只会右移，摊出来是 \(\mathcal O(n)\) 的。
因为我们只要在最开始排个序，总时间复杂度 \(\mathcal O(n\log n + nq)\)。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
struct _ {
int x, i;
bool operator< (const _ &q) const {
return x > q.x;
}
};
_ a[maxn];
int flag[maxn];
int n, m, p, res, pos;
int main() {
#ifdef ONLINE_JUDGE
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
#endif
read(n), read(m);
for (int i = 1; i <= n; ++i)
read(a[i].x), a[i].i = i;
std::sort(a + 1, a + n + 1);
while (m--) {
read(p), res = 0, pos = 1;
for (int i = 1; i <= n; ++i)
flag[i] = 0;
for (int i = 1; i <= n; ++i) {
int id =
(a[i].i < p ? 1 : a[i].i - p + 1);
if (flag[id]) {
while (flag[pos]) ++pos;
flag[pos] = i;
}
else flag[id] = i;
}
for (int i = 1, j = 1;
i <= n; ++i, j = -j)
res += j * a[flag[i]].x;
print(res, '\n');
}
return 0;
}
} // namespace XSC062
#undef int
B. 过河卒II
http://222.180.160.110:1024/contest/4424/problem/2
以及 这 是原题。
读错题了整整 3.5h /youl
我们接下来把「特殊格子」记为 -，「特殊格子」四个方向相邻的点记作 O，除此之外的点因为没有可能被选到，我们不做讨论。
-
- O -
-
对于一个关键点，我们发现找 T 字本身不太方便，所以我们可以把这个转化成在十字里面抠掉一个最小值。
接下来，我们假设有另一个关键点的十字和这一个的十字有重合并不相邻，那么大抵是形如这个样子的：
- -
- O - O -
- -
这个时候，我们发现一共有 7 个 -，一共需要 6 个 -，所以我们试着随便抠掉一个。
X | -
- O - | O -
- | -
我们发现这个时候一定是能找到一个 确定的 方案去划分 T 字的。
所以对于两个 O 的情况，我们抠掉七个 - 当中的最小值即可。
接下来假设有三个 O，那么会有 10 个 -，但我们需要 9 个，于是抠掉最小值，依然存在一种 确定的 方案去划分 T 字。
不难发现，\(n\) 彼此影响还不相邻的 O 会带来 \(3\times n-1\) 个 -（小学数学计算即可），我们将最小者删除即可得到最大答案。
推广一下结论，其实是我们对于 \(x\) 个相互影响的 O（注意这里 没有强调 不相邻），删掉一些使得 - 的数量为 \(3x\)。
那么我们又知道对于最理想的情况，也就是上面讲到的相互影响又不相邻，- 的个数是 \(3\times x+1\)，我们又只能进行抠掉 - 这一个操作。
所以对于一个 O/- 连通块，要求其 - 的个数要么是 \(3x\)（不然 - 就不够用了，以及 - 的缺失是相邻的 O 和边界导致的；边界外的 - 肯定是不能算的），要么为 \(3x+1\)（只用删一个也保证了正确性）。
所以我们跑一个类 Flood-fill，一边搜一边找最小的 -，还要统计 - 和 O 的总个数，还要计算 \(sum\)。然后就完了。
虽然说这个 Flood-fill 没什么技术含量，但是我们要注意只能从 - 出发只能通往 O 而非另一个 -，因为相邻的两个 - 其实是不会互相交叉的相互影响的。
Flood-fill 带来的总时间复杂度为 \(\mathcal O(nm)\)。
namespace XSC062 {
using namespace fastIO;
const int maxk = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const int fx[] = { 0, 0, 1, -1 };
const int fy[] = { 1, -1, 0, 0 };
int n, m, k, x, y, res;
int mn, sum, cnt1, cnt2;
std::vector<std::vector<int> > a, b, c;
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
void DFS(int x, int y) {
sum += a[x][y];
if (b[x][y] == 1) ++cnt1;
else ++cnt2, mn = min(mn, a[x][y]);
c[x][y] = 1;
for (int i = 0; i < 4; ++i) {
int nx = x + fx[i],
ny = y + fy[i];
if (!nx || !ny || nx > n || ny > m)
continue;
if (c[nx][ny]) continue;
if ((b[x][y] == 1 && b[nx][ny] == 1)
|| (b[x][y] == 1 && b[nx][ny] == 2)
|| (b[x][y] == 2 && b[nx][ny] == 1))
DFS(nx, ny);
}
return;
}
int main() {
#ifdef ONLINE_JUDGE
freopen("pawn.in", "r", stdin);
freopen("pawn.out", "w", stdout);
#endif
read(n), read(m);
a.push_back(std::vector<int>(m + 1));
b.push_back(std::vector<int>(m + 1));
for (int i = 1; i <= n; ++i) {
a.push_back(std::vector<int>(m + 1));
b.push_back(std::vector<int>(m + 1));
for (int j = 1; j <= m; ++j)
read(a[i][j]);
}
c = b, read(k);
for (int i = 1; i <= k; ++i) {
read(x), read(y), ++x, ++y;
b[x][y] = 1;
if (x + 1 <= n && !b[x + 1][y])
b[x + 1][y] = 2;
if (y + 1 <= m && !b[x][y + 1])
b[x][y + 1] = 2;
if (x - 1 >= 1 && !b[x - 1][y])
b[x - 1][y] = 2;
if (y - 1 >= 1 && !b[x][y - 1])
b[x][y - 1] = 2;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (b[i][j] && !c[i][j]) {
mn = inf;
cnt1 = cnt2 = sum = 0;
DFS(i, j);
if (cnt2 == cnt1 * 3)
res += sum;
else if (cnt2 == cnt1 * 3 + 1)
res += sum - mn;
else {
puts("No");
return 0;
}
}
}
}
print(res, '\n');
return 0;
}
} // namespace XSC062
C. 树图
http://222.180.160.110:1024/contest/4424/problem/3
DJ：你们去打一下动态树 DP 的板子就可以了。
此时无声胜有声。
这里仅仅介绍一下 40pts 的做法。我们理所当然地想到 DP 一个点染成某种颜色所需的最小代价。
这里说的染成某种颜色其实不太准确，应该是「代表着」哪种颜色。像 0 可以代表 1 也可以代表 2，1 就只能代表 1，2 也只能代表 2。
令 \(f_{u,1}\) 表示以 \(u\) 为根的子树中不保留颜色 2 的最小代价（代表 1），\(f_{u, 2}\) 表示以 \(u\) 为根的子树中不保留颜色 1 的最小代价（代表 2）。
那么对于颜色已经确定为 \(1\) 的点 \(u_1\)，\(f_{u_1,2}=\inf\)；对于颜色已经确定为 \(2\) 的点 \(u_2\)，\(f_{u_2,1}=\inf\)；颜色为 0 的 \(u_0\) 就不用管。
然后如果 \(u_1\) 有一个 2 颜色的儿子 \(v_2\)，就要切断这条边；反之，如果这个儿子的颜色为 1，就不用切断。
所以有：
那么就完了。每次询问的时候跑一个完整的树 DP，或者我们也可以发现只用更新 \(u\) 到目标点这一条链上的 DP 值，然后就可以根据这个做一个并不会实际改进复杂度的优化。
总体时间复杂度 \(\mathcal O(nq)\)。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int col[maxn];
int f[maxn][3];
int n, x, y, q;
std::vector<int> g[maxn];
int min(int x, int y) {
return x < y ? x : y;
}
void DFS(int x, int fa, int to) {
f[x][1] = f[x][2] = 0;
if (col[x] == 1) f[x][2] = inf;
else if (col[x] == 2) f[x][1] = inf;
for (auto i : g[x]) {
if (i == fa) continue;
if (x != to) DFS(i, x, to);
f[x][1] += min(f[i][1], f[i][2] + 1);
f[x][2] += min(f[i][2], f[i][1] + 1);
}
return;
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
#ifdef ONLINE_JUDGE
freopen("diagrams.in", "r", stdin);
freopen("diagrams.out", "w", stdout);
#endif
read(n);
for (int i = 1; i < n; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
read(q);
while (q--) {
read(x), read(y);
col[y] = (x <= 2) ? x : 0;
DFS(1, -1, y);
print(min(f[1][1], f[1][2]), '\n');
}
return 0;
}
} // namespace XSC062
E. 字符串 string
http://222.180.160.110:1024/contest/4423/problem/5
怪话
兔子：我谴责你。
我：？
兔子：为什么你的 last 要缩写成 la。我没看你题解直接看的代码看了半天没看懂。
我：不缩写成 la 难道要写成 lst 吗？
兔子：不然呢？
好吧，辅音党和前缀党的世纪大战。
可以很简单的想到，最终字符串一定由原串中的部分字符，按照其在原串中的顺序，经过若干次重复得到。那么我们把一段连续的相同字符视为一个字符，得到的这个串就是原串的一个子序列。
所以我们只需要求出原串的不同子序列个数，再经过一定的排列组合就可以求出方案数。
比如，我们知道一个长度为 \(n\) 的串中有 \(k\) 个长度为 \(m\) 的子序列，那么由插板法可得这 \(k\) 个子序列会贡献 \(C_{n-1}^{m-1}\times k\) 的方案数。
那么不同子序列个数怎么求呢？显而易见需要 DP，规定 \(f_{i,j}\) 表示一个长度为 \(i\) 的子序列最后一位为 \(s_j\) 的方案数，就可以直接 \(f_{i,j}=\sum f_{i-1,k}\)。
但这样做有一个问题，就是会重复计算。假如原串中在 \(i\) 位置有一个 'o'，\(i+1\) 位置又有一个 'o'，两个都可以从前面某个位置（假设为 \(j\)；假设 \(j\) 上其中一个被计入方案数的合法子序列为 "hyac"），那么转移到 \(i\) 时，计算了 "hyaco"，到了 \(i+1\)，依然可以从 \(j\) 处得到 "hyaco"，就会重复计算。
那么怎么避免这一点呢？对于一个位置 \(i\)，假设其上一个相同字母的位置为 \(last_i\)，我们规定其仅可从 \((last_i,i)\) 进行转移即可（注意两边都是开区间）。
初始化是对于每一个没有前驱的 \(i\)，\(f_{1,i}=1\)。
实现上，因为 \(n\) 的大小是 \(5\times 10^3\)，转移区间又是连续的，我们用一个前缀和进行优化即可。
时间复杂度 \(\mathcal O(n^2)\)，应该比官方题解讲的方法具象一些。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int mod = 1e9 + 7;
const int maxn = 5e3 + 5;
int n, res;
char s[maxn];
int fac[maxn];
int la[maxn], p[maxn];
int f[maxn][maxn], u[maxn][maxn];
int max(int x, int y) {
return x > y ? x : y;
}
int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1) (res *= x) %= mod;
(x *= x) %= mod, y >>= 1;
}
return res;
}
int inv(int x) {
return qkp(x, mod - 2);
}
int A(int n, int m) {
return fac[n] * inv(fac[n - m]) % mod;
}
int C(int n, int m) {
return A(n, m) * inv(fac[m]) % mod;
}
int main() {
scanf("%lld %s", &n, s + 1);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
la[i] = p[s[i] - 'a' + 1];
if (!la[i]) f[1][i] = 1, ++res;
u[1][i] = u[1][i - 1] + f[1][i];
p[s[i] - 'a' + 1] = i;
fac[i] = (fac[i - 1] * i) % mod;
}
for (int i = 2; i <= n; ++i) {
int sum = 0;
for (int j = i; j <= n; ++j) {
int k = max(i - 1, la[j] + 1);
if (k <= j - 1)
f[i][j] = (u[i - 1][j - 1] - u[i - 1][k - 1]) % mod;
u[i][j] = (u[i][j - 1] + f[i][j]) % mod;
(sum += f[i][j]) %= mod;
}
res += C(n - 1, i - 1) * sum % mod;
res %= mod;
}
res = (res + mod) % mod;
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int
F. Good Set Query
https://atcoder.jp/contests/abc328/tasks/abc328_f
一个加权并查集。
我们用并查集维护关系，在合并两个集合的时候给被合并者的原本根打一个懒标记，意为该并查集需要整体更新的 delta。
在每次 find 时，路径上的点均从 直系父亲 处继承懒标记。然后因为有了路径压缩，所以每个点在查询时均能得到不重复的懒标记（因为自己的祖先已经被直系父亲继承过了）。
同样也是因为弱势一方才被打标记，保证了根节点上不会有标记，路径压缩后就将父亲更新为根，保证不会因为多次 find 导致标记重复计算。
每次尝试合并的时候，因为首先需要进行 find，保证 \(x\) 和 \(y\) 均是最新状态。若 \(x\) 和 \(y\) 已经在同一个集合了，直接判断两个差值是否为 \(d\)；否则，合并两个集合并给弱势方打上标记。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 5;
int n, q, x, y, d;
int f[maxn], u[maxn];
int find(int x) {
if (f[x] == x) return x;
int fa = find(f[x]);
u[x] += u[f[x]];
return f[x] = fa;
}
bool merge(int x, int y, int d) {
int fx = find(x), fy = find(y);
if (fx == fy) return u[x] - u[y] == d;
f[fx] = fy, u[fx] = d - (u[x] - u[y]);
return 1;
}
int main() {
read(n), read(q);
for (int i = 1; i <= n; ++i)
f[i] = i;
for (int i = 1; i <= q; ++i) {
read(x), read(y), read(d);
if (merge(x, y, d))
print(i, ' ');
}
putchar('\n');
return 0;
}
} // namespace XSC062
#undef int
F. Points
http://codeforces.com/problemset/problem/1701/F
我们先考虑对于一个单点 \(p\)，假设 \([p-d, p)\) 中共有 \(k\) 个点，那么答案就是 \(C_k^2=\dfrac {k(k-1)}2\)。
假如范围内新加入了一个点，\(k\gets k+1\)，那么答案就是 \(C_{k+1}^2=\dfrac {k(k+1)}{2}\)，较原来增加了 \(k\)。相应地，若范围内减少了一个点，\(k\gets k-1\)，答案较原来就会减少 \(k-1\)。
当我们加入一个点 \(p\)，区间 \((p,p+d]\) 都会收到影响。假设该区间内原本的每个点之 \(k\) 的和是 \(s_k\)，那么总体的答案就会减少 \(s_k\)。
那么 \(s_k\) 怎么去维护呢？插入点 \(p\) 时，答案先加上当前 \(s_k\) 和新点的 \(k\)，再将 \((p, p+d]\) 内的 \(s_k\) 全部 +1；删除点 \(p\) 时，答案减去 \(s_k-c\) 和待删点的答案（其中 \(c\) 是 \((p,p+d]\) 中的点数），再将 \((p, p+d]\) 内的 \(s_k\) 全部 -1。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 2e5;
const int maxn = 2e5 + 5;
#define lt (p << 1)
#define rt (lt | 1)
struct _ { int u, p, d, l, r; };
_ t[maxn << 2];
int q, d, x, res;
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
void pushdown(int p) {
if (t[p].d) {
t[lt].u += t[lt].p * t[p].d;
t[rt].u += t[rt].p * t[p].d;
t[lt].d += t[p].d;
t[rt].d += t[p].d;
t[p].d = 0;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].p;
int res = 0,
mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) res = ask(lt, l, r);
if (r > mid) res += ask(rt, l, r);
return res;
}
int qry(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
int res = 0,
mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (l <= mid) res = qry(lt, l, r);
if (r > mid) res += qry(rt, l, r);
return res;
}
void upd(int p, int l, int r, int x) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d += x;
t[p].u += t[p].p * x;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (l <= mid) upd(lt, l, r, x);
if (r > mid) upd(rt, l, r, x);
t[p].u = t[lt].u + t[rt].u;
return;
}
void clr(int p, int x) {
--t[p].p;
if (t[p].l == t[p].r) {
res -= t[p].u * (t[p].u - 1) / 2;
t[p].u = t[p].d = t[p].p = 0;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (x <= mid) clr(lt, x);
else clr(rt, x);
t[p].u = t[lt].u + t[rt].u;
return;
}
void add(int p, int x, int v) {
++t[p].p;
if (t[p].l == t[p].r) {
res += v * (v - 1) / 2;
t[p].u = v, t[p].p = 1;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (x <= mid) add(lt, x, v);
else add(rt, x, v);
t[p].u = t[lt].u + t[rt].u;
return;
}
void upd(int l, int r, int x) {
upd(1, min(l, lim), min(r, lim), x);
return;
}
int qry(int l, int r) {
return qry(1, min(l, lim), min(r, lim));
}
int ask(int l, int r) {
return ask(1, max(1, min(l, lim)),
max(1, min(r, lim)));
}
int main() {
read(q), read(d);
bld(1, 1, lim);
while (q--) {
read(x);
if (ask(x, x)) {
int u = qry(x + 1, x + d)
- ask(x + 1, x + d);
res -= u;
upd(x + 1, x + d, -1);
clr(1, x);
}
else {
int u = qry(x + 1, x + d);
res += u;
upd(x + 1, x + d, 1);
add(1, x, ask(x - d, x - 1));
}
print(res, '\n');
}
return 0;
}
} // namespace XSC062
#undef int
E. Partition Game
https://codeforces.com/problemset/problem/1527/E
怪话
我：我要做哪道题。感觉哪道题都没人 A，不是很敢做。
721：你看 D 题。D 题有人 A。
我：D 题不是只有一只猴子 A 了吗（头被锤飞）。
我：哦哦好吧 A 题有一只兔子，一个神明，一头绵羊和一个卡先生 A 了，共计一个人，我开 A 题。