4月每日总结

4 月 1 日#

我尽力，我无悔。

T1#

对于那种只输入一两个数的题，首先不要去想正解，先猜半个小时结论看看猜不猜的出来。多半是猜的出来的

可是我写 T2 去了。

发现从 $0$ 有 $\frac{1}{n}$ 的概率一发入魂。而剩下 $\frac{n - 1}{n}$ 的概率就是在 $[1,n - 1]$。对于每个点都有 $\frac{1}{n}$ 的概率赢，有 $\frac{n - 2}{n}$ 的概率留在 $[1,n - 1]$，那么对于每个 $i \in [1,n - 1]$ 都是一样的。期望是 $1 + \frac{(n - 1)^2}{n}$。

T2#

赛时想法：设 $dp_{i,j}$ 表示第 $i$ 个点取值为 $j$ 的方案数。显然有：$dp_{i,j} = \sum\limits_{k = 1}^{a_i}dp_{i - 1,k} \times [k \neq j]$。复杂度 $O(nV^2)$，可以通过全局和优化到 $O(nV)$，然后拿到 $20$ 的好成绩。
我们发现这玩意可以简化成三个操作：区间取反，区间赋值，区间加。前面两个都是特化的区间乘。我们直接动开线段树，花了 2h 的时间获得的 $60$ 的好成绩。

正解是这样的：正难则反。我们想要求恰好有 $0$ 个非法点的情况数，我们就尝试求钦定有 $i$ 个非法点的情况数 $F(i)$，然后反演一下得到最终的答案。

考虑如何求 $F(i)$。设 $dp_{i,j}$ 表示前 $i$ 个数分 $j$ 段的方案数。显然有 $F(i) = dp_{i,n - i}$。有显然的转移：$dp_{i,j} = \sum\limits_{k = 1}^{i}dp_{k - 1,j - 1} \times \min\limits_{l = k}^{i}a_l$。复杂度 $O(n^3)$，可以拿到 $0$ 分的好成绩。

我们发现我们不关心 $j$ 的值，只关心它的奇偶性。我们就可以每次转移都乘一个 $-1$，变成 $dp_i = \sum\limits_{k = 1}^{i}-dp_{k - 1} \times \min\limits_{l = k}^{i}a_l$。复杂度 $O(n^2)$，可以获得 $60$ 的好成绩。

最后用单调栈优化到 $O(n)$ 即可通过。

T3#

我们发现如果对于一个可行的方案，每个数都异或一个 $x$，最终答案也可行。且总的异或和也异或了 $y$。所以我们不用考虑具体的方案，求出总方案数除以 $2^k$ 就行。

考虑先填好第二行，方案数 $2^k \times (2^k - 1) \times (2^k - 2) \times \cdots \times (2^k - n)$，然后钦定第一行有 $i$ 个与第二行冲突，方案数为 $(2^k - i) \times (2^k - i - 1) \times (2^k - i - 2) \times \cdots \times (2^k - n + 1)$。直接反演得到恰好有 $0$ 个与之冲突的方案数。

后日谈#

今天就是纯纯的数学题综合训练。于是开始预习复习概率与期望。

我尽力，我无悔。

4 月 2 日#

不计代价。

不过我要是真的能做到 不计代价 的学习的话，我就不会那么菜了。

DFS Order 2#

我们想到，一个子树内的 dfs 序肯定是连续的，我们考虑跑一个背包。设 $dp_{u,i}$ 表示 $u$ 在第 $i$ 个被访问的方案数。我们先想总共有多少个 dfs 序。那么显然，如果有 $tot_u$ 个子树，那么就有 $tot_u !$ 个子树排列的方式。每个子树又有自己的排列方式，乘起来就是了。$dp_{1,1}$ 就是总的排列方式数。初始化就完了。

考虑如何转移：我们想从 $dp_{u,i} \to dp_{v,j}$。我们发现，一次加的肯定是一整个子树。那么我们想：做背包！设 $tmp_j$ 表示 两个点在 dfs 序上相距 $j$ 的方案数。转移有显然的 $dp_{v,j} \leftarrow dp_{u,i} + tmp_{j - i}$。

但是我们发现：子树之间是不分顺序的，我们转移 $v$ 的时候还得扣掉 $v$ 的子树。我们不可能对于每个子树都做个不考虑它的背包，那么复杂度直奔 $O(n^4)$，显然不可取。

我们想：效仿淀粉质！每次扣掉 $v$ 的子树所做的贡献，转移完再加回来。我们在每个 $u$ 的子树转移时设单独的 $f_{i,j}$。表示在 $i$ 个子树内总共选了 $j$ 个点的方案数。那么初始化有 $f_{0,0} = 1$。转移有显然的 $f_{i,j} \leftarrow f_{i - 1,j - siz_v}$。

那么我们又如何从 $f \to tmp \to dp$ 呢？对于 $f \to tmp$，有 $tmp_{j + 1} = f_{i,j} \times i! \times (tot_u - i - 1)!$，三项分别表示 $i$ 个子树内的方案数，$i$ 个儿子排列的方案数，剩下儿子排列的方案数。

但是我们输出发现：比例正确，值错误。我们直接化到最简。我们发现比例正确但是值不正确的原因是有 $tmp_i$，所以就是直接化到最简。

Core code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

\\ 预处理
int dfs1(int u,int fa)
{
    int res = 1;
    siz[u] = 1,tot[u] = 0;
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        res = res * dfs1(v,u) % mod;
        siz[u] += siz[v],tot[u]++;
    }
    return res * fac[tot[u]] % mod;
}

\\ 转移
void dfs2(int u,int fa)
{
    memset(f,0,sizeof f);
    f[0][0] = 1;
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        for (int i = tot[u]; i >= 1; i--)
            for (int j = siz[u]; j >= siz[v]; j--)
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
    }
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        for (int i = 1; i <= tot[u]; i++)
            for (int j = siz[v]; j <= siz[u]; j++)
                f[i][j] = (f[i][j] - f[i - 1][j - siz[v]] + mod) % mod;
        memset(tmp,0,sizeof tmp);
        for (int i = 0; i < tot[u]; i++)
            for (int j = 0; j <= siz[u]; j++)
                tmp[j + 1] = (tmp[j + 1] + fac[i] * fac[tot[u] - 1 - i] % mod * f[i][j] % mod) % mod;
        for (int i = 1; i <= n; i++)
            for (int j = 1; i + j <= n; j++)
                dp[v][i + j] = (dp[v][i + j] + dp[u][i] * tmp[j]) % mod;
        for (int i = tot[u]; i >= 1; i--)
            for (int j = siz[u]; j >= siz[v]; j--)
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
    }
    for (auto v : g[u])
        if (v != fa)
            dfs2(v,u);
}

\\ 输出化简
for (int i = 1; i <= n; i++)
{
    int sum = 0;
    for (int j = 1; j <= n; j++)
        sum = (sum + dp[i][j]) % mod;
    int tmp = binpow(sum,mod - 2);
    for (int j = 1; j <= n; j++)
        printf("%lld%c",dp[i][j] * dp[1][1] % mod * tmp % mod," \n"[j == n]);
}

Great Expectations#

原题也做不起吗？

我们考虑 ctj 设 $dp_{i,j}$ 表示在 $i$ 个困难之后花费了 $j$ 分钟的方案数。那么有转移：

具体来讲，就是如果还有可能破纪录，就尝试能不能破纪录。反之直接重开。但是我们发现这玩意有后效性，直接高斯消元。高斯消元肯定是不可取的，毕竟有个 $\min$ 在那里镇着。我们考虑二分 $dp_{0,0}$。如果最终的 $dp_{0,0}$ 比 $mid$ 小，就说明有些本该重开的我们选择了继续打，往小二分。反之往大二分。

糖果大战#

高斯消元 yyds

游走#

此游走非彼游走。

设总共有 $cnt$ 条路径，总长为 $len$。那么直接 dfs 搜出每个以每个点为起点的路径数量和路程总长，一加一除就出来了。

如果这题没模我不炸了？

汉堡 Burger#

题意简化：有一个 01 串，0 的数量和 1 的数量各占一半。且最后的两个是连续的 1，求出这么滴的概率。

正难则反。设 $ans_i$ 为长度为 $i$ 的不成立的概率。那么显然有 $\displaystyle ans_n = \frac{\binom{n - 2}{\frac{n}{2} - 1}}{2^{n - 2}}$。我们发现这题没模，不能预处理阶乘。考虑推式子。推得 $ans_i = ans_{i - 2} \times \frac{i - 1}{i}$。答案就是 $1 - ans_n$。

后日谈#

我都写 Java 了我还管常数吗？

好想念小学时无忧无虑的周末啊。。。

4 月 6 日#

沟槽的构造题。

今天早上打 VP，直接被构造题创飞，于是开始练习构造。

好像练了 dp 就只会 dp 一样。其实 dp 也不够会，其他都不会做。

Arcology On Permafrost#

考虑 $f(a)$ 的最大值。首先一定有 $f(a) \le n - m \times k$，因为一个序列的 $\operatorname{MEX}$ 不可能大于它的长度。还有 $f(a) \le \lfloor \frac{n}{m + 1} \rfloor$，因为为了在 $m$ 次里，每个数都有剩的，每个数的出现次数必须大于 $m + 1$。

考虑如何构造：

• 当 $n - m \times k < \lfloor \frac{n}{m + 1} \rfloor$，那么我们有 $i \in [0,n),a_i = i \bmod k$，这样可以保证无论删掉哪几个子串，最后都会有 $a_i = i$，使得 $\operatorname{MEX}$ 最大。
• 当 $n - m \times k \ge \lfloor \frac{n}{m + 1} \rfloor$，我们可以构造 $i \in [0,n),a_i = i \bmod \lfloor \frac{n}{m + 1} \rfloor$。这样可以保证相同的数字之间至少有 $k$ 的距离，每个数还有至少 $m + 1$ 个。

Happy Birthday! 3#

神金区间 dp。

自己写的 solution

后日谈#

自己抓了一点构造题来练，我连黄的构造题都做不太出来我还去做蓝色的构造题，我扯吧我。

忽然发现今天好像就做了这几道题，也是十分的颓废。

4 月 7 日#

今天也是不颓。

所以到底是颓还是不颓？

Blossom#

没搞懂。

等洛谷上有题解了再去看一遍。

Roller Coaster#

神 tm Adhoc。

考虑对于一个已经选好的路径，我们找到高度相差最大的两个点，显然有结论：在这俩点里转来转去肯定是比当前路径更优的。于是我们直接找到一对 $|h_u - h_v|$ 最大的 $u,v$，答案就是 $\frac{|h_u - h_v|}{2}$

只能说我太蠢了。

Big XOR Game#

自己想到了 $75\%$，还是挺不错的。
下次能想到 $100\%$ 就更好了。

想到之前考试有道题。设所有的数异或和为 $sum$，当 $sum = 0$ 时肯定平局。否则一定在 $sum$ 的最高位决出胜负。问题转化为：有 $n$ 个数，里面有奇数个 $1$，先后手轮流取，取了奇数个 $1$ 的人获胜。

考虑分类讨论，设有 $cnt$ 个 $1$：

有偶数数个 $0$（$n$ 为奇数）

• 当 $cnt \equiv 1 \pmod 4$
  Alice 先取一个 $1$，之后都和 Bob 取相同的。Alice 取了奇数个 $1$，Alice 得了 MVP！！！
• 当 $cnt \equiv 3 \pmod 4$
  Bob 总和 Alice 取相同的，Bob 取了奇数个 $1$，Bob 得了 MVP！！！

有奇数个 $0$（$n$ 为偶数）

• 当 $cnt \equiv 1 \pmod 4$
  同上情况 1，必胜。
• 当 $cnt \equiv 3 \pmod 4$
  Alice 取了 $0$，变成上面的情况 2 的后手，必胜。

Bracket Sequence#

唐题。

我们考虑 dp。$dp_i$ 表示到 $i$ 的 h 的数量（其实就是方案数啦）。考虑转移：$dp_i = dp_{i - 1} + \sum dp_j$。其中 $j$ 满足 $(j,i]$ 是一个合法的括号序列。

考虑如何快速求这个 $\sum dp_j$。我们想到记录一个 $bel_i$ 表示将 ( 视为 $1$，) 视为 $-1$ 的前缀和。维护一个 $sum_j$ 表示所有 $bel_i = j$ 的 $dp_i$ 之和。但是我们发现一个问题：这个括号序列：()()，第 $3$ 个会从第 $1$ 个转移而来。但是很显然，)( 并不是一个合法的括号序列。我们考虑如何 ban 掉这种情况。

我们发现出现这种情况当且仅当有 $k \in (j,i]$ 满足 $bel_k < bel_i$。我们考虑开一颗线段树。下标为 $i$ 的地方维护 $bel_i$ 出现的最后一个地方。对于每个 $bel$ 开一个队列。在线段树上查询 $lst$ 表示 $[1,bel_i - 1]$ 的区间最小值，把队列里在 $lst$ 之前的全扔出去，并从 $sum_{bel_i}$ 中减去。然后转移 $dp_i = dp_{i - 1} + sum_{bel_i}$。然后更新线段树，将 $i$ 压进队列并将 $sum_{bel_i}$ 加上 $dp_i$。

最后的答案就是 $dp_n$。

还是 赛格门特吹 好用。

Colourful Bottles#

听 dpfs 讲的。

考虑 dp，设 $dp_i$ 表示以 $i$ 结尾，满足 $k$ 连续的最小代价。考虑转移：

其中 $sumw_i$ 表示 $w$ 的前缀和。$sumc_i$ 表示与 $i$ 颜色相同的前缀和。第二个方程具体来说就是：删掉 $[j,i]$ 之间的所有数，但是同色的不能删，于是把它加回来。而我们不知道 $j$ 的相同颜色的前驱是啥，于是直接减掉 $sumc_j - w_j$。$j$ 要满足 $[j,i]$ 之间至少有 $k$ 个同颜色的。

考虑优化。对于每个颜色开一个 $min$ 数组表示 $dp_j - sumw_{j - 1} - sumc_j + w_j$ 的最小值。又对于每个颜色开一个队列。当队列长度等于 $k - 1$ 时，就把对头取出，更新 $min$ 数组。然后转移 $dp_i = \min\{dp_{i - 1} + w_i,min_{c_i} + sumw_i + sumc_i\}$。转移完了扔进队列。

后日谈#

明天的模拟赛和重庆八中联考。又可以丢 CW 的脸了。

每次一看到这个高达 $\color{#ff0000}16.7\%$ 的得分率我就头大。明明打的对的题，总是因为一些莫名其妙的愿因挂分。要么是实现太优秀，常数爆炸，要么是没注意细节。

There’s no time left.

4 月 8 日#

今天是真的不颓。

T1#

如果说有这样的 $a = \{1,2\}$ 和 $b = \{100,101\}$，显然我们不能先加 $a_1$，而应该先加 $a_2$。而后又看到 $x$ 可以为负，想到如果说将 $a_i$ 加上 $x$ 使得 $a_i = b_i$ 且 $a_i > a_{i + 1}$，我们就连一条 $i + 1 \to i$ 的边。可以证明这是一个有向无环图。因此我们一定有用 $\sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次的方法使得 $a = b$。

现在我们考虑使代价更小。考虑对于一个 $(a_i - b_i)^2$，要使它变小，我们考率分多次。显然等分最优。赛时想到了做背包 dp，复杂度 $O(nm^2)$。可以拿到 $\color{#5ec05e}{50}$ 的好成绩。看这个绿色就知道确实很好。

正解是整一个大根堆。将每个 $(a_i - b_i)^2$ 多分一个的负贡献插入，比如初始就放每个 $(a_i - b_i)^2$ 从 $1$ 次到 $2$ 次的负贡献。取 $m - \sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次就好。

没放代码是因为下次再做的时候希望能自己写出来。

T2#

听 HD0X 讲的。

看到冒泡排序，想到逆序对。离线，从大到小枚举 $i$，并枚举每个 $x = i$ 的查询，计 $u$ 表示 $i$ 位置前面的比它大的数量，$v$ 表示 $i$ 位置后面的比它大的数量。让我们分类讨论一下（下文的 $k$ 都指查询的 $k$，$id$ 指查询编号，$pos_i$ 指 $i$ 的原位置）：

• $k \le u$
  这样的话，$i$ 前面的会在 $k$ 次冒泡后跑到 $i$ 后面去并把 $i$ 往前挤，$ans_{id} = pos_i - k$。
• $k \le u + v$
  从头开始考虑 $k$ 次冒泡。每次冒泡，一定会有一个比 $i$ 更大的数 $P_j$ 被一个更大的数 $P_{j + 1}$ 堵住，且位置比 $P_{j + 1}$ 左一个。
  我们掏个样例出来：$\{4,3,5,1,2\}$。我们想要查询 $3$ 在第 $2$ 次冒泡后的位置。
  第 $1$ 次冒泡：$\{3,4,1,2,5\}$，$4$ 被 $5$ 堵住，位置 $-1$。
  第 $2$ 次冒泡：$\{3,1,2,4,5\}$，$3$ 被 $4$ 堵住，位置 $-1$。
  这样我们看到 $3$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $2$ 次 $-1$ 后得到的。
  我们再掏一个样例：$\{3,4,2,5,1\}$。我们想要查询 $2$ 在第 $3$ 次冒泡后的位置。
  第 $1$ 次冒泡：$\{3,2,4,1,5\}$，$4$ 被 $5$ 堵住，位置 $-1$。
  第 $2$ 次冒泡：$\{2,3,1,4,5\}$，$3$ 被 $4$ 堵住，位置 $-1$。
  第 $3$ 次冒泡：$\{2,1,3,4,5\}$，$2$ 被 $3$ 堵住，位置 $-1$。
  $2$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $3$ 次 $-1$ 得到的。
  我们发现，因为在这 $k$ 次里会被堵 $k$ 次，所以最初的位置（就是上文的 $5$ 的最初的位置）一定是比 $i$ 大的数按照原序列的顺序的第 $k$ 个。而每次被堵会使得下标 $-1$，所以答案就是比 $i$ 大的数的第 $k$ 个的位置减 $k$。
• $k > u + v$
  显然这个时候 $i$ 归位了，$ans_{id} = n - u - v$。

实现可以这样：因为我们从大到小枚举 $i$，用线段树维护。每次算完 $i$ 都将线段树 $pos_i$ 的地方置为 $1$。$u$ 就是 $[1,pos_i]$ 的区间和，$v$ 就是 $[pos_i,n]$ 的区间和。“比 $i$ 大的数按照原序列的顺序的第 $k$ 个”可以通过线段树上二分找到第 $k$ 个 $i$。因为只有 $k > u$ 时才会询问第 $k$ 个，所以第 $k$ 个一定在 $i$ 原位置的右边。

T3 & T4#

补题速度还是太快了一点，没看。

后日谈#

之前的考试挂分 $\color{#ff0000}{50}$ 起步，今天只挂了 $\color{#5ec05e}{10}$ 分，可喜可贺。

要是 T1 没有被背包误导的话就更好了。好歹有 50 分嘛

今天晚上有 div.3，打不打呢？

4 月 9 日#

弄懂每一题。然而我太蠢了

Square Subsequences#

谁能给我讲讲 bitset 优化 LCS 啊？

简而言之就是枚举中间的分界点，然后对于两边的子串跑 bitset 优化 LCS。记录最大的 LCS 长度与其对应的 bitset。然后通过 bitset 反推 dp 数组，从而反推方案。时间复杂度 $O(\frac{n^3}{\omega} + n^2)$，时限 $2$ s，在 CF 神机上跑了 $1.5$ s，换别的 OJ 还不一定跑的完。

然而我太蠢了没弄懂 bitset 优化 LCS。

Adjacent Delete#

自从学了 C# 和 Java 以来，代码风格愈发面向对象了。与之而来的还有更大的常数。希望不要搞出在赛场上因为常数太大而 TLE 的事。

考虑没有相邻的限制如何做。显然是最大的 $\frac{n}{2}$ 个减去最小的 $\frac{n}{2}$ 个。现在考虑相邻的限制，这个上界也是可行的。我们把每个最大的 $\frac{n}{2}$ 的标成 +，最小的那几个标成 -。显然无论如何都会有一对 + 和 - 相邻。

对于偶数 $n$ 显然就是那个上界。对于奇数 $n$，因为会留下一个，留下的这个会将 $a$ 数组分成两半，而两边都会取完，所以两边的长度肯定都是偶数。所以留下的只能是 $a_1,a_3,a_5,\dots$，对于两边，就是上文的上界。我们可以用两个 multiset 维护。一个小根的维护大的那几个数，大根的维护小的那那几个数。每次如果插入的 $x$ 大于等于小根堆的堆顶，就插入小根堆。否则插入大根堆。并维护一个堆内和。

放下我的常数超大代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 5;
int n;
int a[maxn];
class two_set
{
    private:
    multiset<int,less<>> mx;// 小根堆维护最大的几个数
    multiset<int,greater<>> mi;// 大根堆维护最小的几个数。
    void balance()
    {
        if (mx.size() > mi.size() + 1)
        {
            _min += *mx.begin();
            _max -= *mx.begin();
            mi.insert(*mx.begin());
            mx.erase(mx.begin());
        }
        if (mi.size() > mx.size())
        {
            _max += *mi.begin();
            _min -= *mi.begin();
            mx.insert(*mi.begin());
            mi.erase(mi.begin());
        }
    }
    public:
    int _min,_max;// 分别表示最小的数的和，最大的数的和。
    void insert(int x)
    {
        if (mx.empty() || x >= *mx.begin())
        {
            _max += x;
            mx.insert(x);
        }
        else
        {
            _min += x;
            mi.insert(x);
        }
        balance();
    }
    void erase(int x)
    {
        auto it = mx.find(x);
        if (it != mx.end())
        {
            _max -= x;
            mx.erase(it);
        }
        else
        {
            _min -= x;
            it = mi.find(x);
            assert(it != mi.end());
            mi.erase(it);
        }
        balance();
    }
}s1,s2;
void solve1()// 起码这里挺简洁的
{
    for (int i = 1; i <= n; i++)
        s2.insert(a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        s2.erase(a[i]);
        if (i & 1)
            ans = max(ans,s1._max - s1._min + s2._max - s2._min);
        s1.insert(a[i]);
    }
    printf("%lld",ans);
}
void solve2()
{
    sort(a + 1,a + n + 1);
    int _max = 0,_min = 0;
    for (int i = 1; i <= n >> 1; i++)
        _min += a[i];
    for (int i = (n >> 1) + 1; i <= n; i++)
        _max += a[i];
    printf("%lld",_max - _min);
}
signed main()
{
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++)
        scanf("%lld",a + i);
    if (n & 1)
        solve1();
    else
        solve2();
    return 0;
}

后日谈#

yzp 因为鞋子没垫鞋垫导致他极其不舒服。然后今天也是十分颓废，只做了 $3$ 题。

yzp 说他想回家，我的评价是：住校生是这样的。

不过住校生不开心还可以逃回家，走读生逃回家也没用，因为天天回家，对家已经无感了。不开心的时候只能畅想去到异世界。中二病

4 月 11 日#

沟槽的树套树，沟槽的体考。

Two Permutations#

我们发现，$P_i$ 和 $Q_i$ 是绑定的，不会分开。如果 $P,Q$ 都无序十分的难做且 $P,Q$ 的顺序是不变的。我们可以将 $P$ 排序，然后考虑 $Q$。

我们建一个模型：将 $P,Q$ 和与之对应的 $R$ 看作上下两排。如果有 $u < v$，那么就建一条 $u \to v$ 的边。边可以是横着（$P,Q$ 内部建边），也可以是竖着 （$P \to Q$ 或 $Q \to P$）。非法当且仅当出现了环。

我们考虑 $Q$ 中的最大值 $Q_u$。

• 如果 $u$ 是向上建边的起点，说明 $S_u$ 及 $S$ 从 $u$ 开始的后缀都是 $0$，往上建边。因为 $P$ 已经按照从小到大排序了，后面的一定比前面的大。而 $Q$ 这里又是最大值，后面一定比 $Q_u$ 小，那么说明这段后缀都是向上建边。这有什么用？这就说明后面不会成环且 $S$ 确定了，不用考虑了。
• 如果 $u$ 是向下建边的终点，只能说明 $S_u = 1$。但是因为 $Q_u$ 是最大值，所以它的边一定是往左右的，不会成环。

所以我们可以把题意转化成这样：有一个序列 $Q$，每轮可以执行一次两种操作：

1. 把 $Q$ 的最大值 $Q_u$ 及从 $u$ 开始的后缀删掉。
2. 只删掉 $Q$ 的最大值 $Q_u$。

求出删完 $Q$ 的方案数。

结论：答案就是 $Q$ 的上升可空子序列数量。如何理解？我们只考虑操作 1。上升子序列就是一种操作 1 的操作序列。因为每次取走的是一段后缀且 $Q_u$ 是最大值，所以下一个操作的就只能是 $u$ 前面的比 $Q_u$ 小的数。

那有人要问了？操作 2 你没考虑啊？其实也是考虑的。因为是子序列，所以里面可能夹杂着有空位，这些空位就是操作 2 的地方。因为操作 2 的 $S$ 只能是 $1$，方案数是 $1$，所以不用计算。

树状数组优化 dp 即可。

Guess Sequence#

我们对于 $S_i \to T_i$ 建一条边。那么整个图一定是一棵树。如果不是一棵树那么就一定有点没被连边，这个点就可以乱取。

我们考虑对于一个点 $u$，如果 $b_u$ 乘上了 $x$，那么 $b_v$（$v$ 是与 $u$ 相邻的点）为了乘积不变，就得乘上 $\frac{1}{x}$。经过一番推导，我们发现，点 $v$ 的深度与 $u$ 的奇偶性相同，$b_u$ 乘上了 $x$，$b_v$ 也得乘上 $x$，反之乘上 $\frac{1}{x}$。这样我们就把 $n$ 个点分成了两个集合。深度为奇的成一个集合，深度为偶的成另一个集合。

我们发现，如果一个集合的数里有个共同的因数 $x$，那么就可以把当前集合里的的乘上 $\frac{1}{x}$，另一个集合里的就乘上 $x$，可以构造一个新的 $b$，显然不行。所以我们需要把 $a$ 分成两个 $\gcd$ 为 $1$ 的集合，如果可行就是 Yes，反之就是 No。

后日谈#

什么两米八三，我才跳了一米八三。

事情的起因是这样的：我们去体考，考立定跳远。前面的贾皓博第一跳只跳了 $2.4$ 米多。我就在想：是不是成外的测量器具有问题啊？我之前的 $2.6$ 米是不是不真啊？于是第一跳就全力。大概是腿太粗？力量太大？

跑完 $1000$ 米直接燃尽了，整个下午都没法学习。

4 月 13 日#

一起把周六的日记也写了吧。

考试爆零。机房 rating $16.7 \to 13.7$，决心 $-\inf$。

T1#

神秘小 dp，没改，明天改。

T2#

想到了可持久化并查集，没想到和那个可持久化并查集一起的 Kruskal 重构树。

我这么菜不适合 Kruskal 这个英文名。

T3#

主席书双 $\log$ 做法还没调出来，单 $\log$ 做法待会再说。

但是我拿测速代码测了 cwoi 的机子每秒大概 $4.1 \times 10^8$，而 $3 \times 10^5$ 的双 $\log$ 也才 $1.1 \times 10^8$，没准双 $\log$ 卡卡常能过？

T4#

神经分讨。

考虑 $[l,r]$ 区间内的最大值 $a_x$ 出现在三个区间中的哪个位置。

• 中间
  显然中间对于答案的贡献无论如何都是 $a_x$，而两边的段随着长度的减小，贡献显然不会增加。那么最优方案就是 $a_l + a_r + a_x$。
• 左边
  显然左边的代价无论如何都是 $a_x$。根据上文的结论，第二个区间的长度越小贡献越小。所以整个段的答案就是 $a_x + \min\limits_{r' = x + 1}^{r - 1}\{a_{r'} + \max\limits_{i = r' + 1}^{r}\{a_i \}\}$。我们离线，从 $1 \to n$ 枚举每个 $r$ 及其对应的询问。设 $f_i$ 表示当前 $r$ 所对应的 $\min\limits_{r' = x + 1}^{r - 1}\{a_{r'} + \max\limits_{i = r' + 1}^{r}\{a_i \}\}$。用单调栈 + 线段树维护。具体而言是这样的：维护一个单调递减的单调栈。如果当前的 $a_r$ 把栈顶 $stk_{top}$ 弹出了，由于 $a_{stk_{top}}$ 是之前的 $r' \in [stk_{top - 1},stk_{top})$ 的 $\max\limits_{i = r' + 1}^{r}\{a_i \}$，现在被 $a_r$ 替换了，所以在线段树上的 $[stk_{top - 1},stk_{top})$ 区间加 $-a_{stk_{top}} + a_{r}$。还要单独更新 $r - 1$。枚举每个 $r_i$ 是当前枚举的 $r$ 的询问， 那么答案就是 $a_x + \min\limits_{i = x + 1}^{r - 1}\{f_i\}$，直接线段树区间查最小值就是了。
• 右边
  把整个序列翻转，然后做左边一样的就行。

后日谈#

感觉我一事无成。

4 月 14 日#

想说点什么但是说不出来。

Transforming Pairs S#

也是切上绿题了。

看到这玩意很像 $\gcd$ 的求法，我们看看能不能往 $\gcd$ 上面想。

口胡了一个做法：我们钦定 $c < d$。首先我们对 $d$ 进行操作。将 $d$ 减去 $\lfloor \frac{d - b}{c} \rfloor \times c$。这样可以保证 $d \ge b$。对 $c$ 进行同样的操作，减去 $\lfloor \frac{c - a}{d} \rfloor$，同样为了保证 $c \ge a$。

继续口胡的证明：感性理解，我们为了让 $c$ 和 $d$ 尽快的减成 $a$ 和 $b$，每次减的肯定要尽可能多。于是我们每次进行辗转相减，减到再减一次就会爆炸的程度，每次减得就尽可能多了。

Moo Decomposition G#

Java 的常数还是太优秀了。

我们发现 $L \le 1 \times 10^{18}$，直接把整个序列拎出来做肯定是不现实的。但是我们发现一个性质：每段的方案数相互独立。那么我们就可以把每段的方案数单独求出来然后快速幂了。

考虑如何求每段的方案数：从后往前枚举每个字符，我们设 $cnt$ 表示当前遇到的 $\texttt{O}$ 的个数。

• 遇到了个 $\texttt{O}$
  显然是 $cnt \leftarrow cnt + 1$。
• 遇到了个 $\texttt{M}$
  这个 $\texttt{M}$ 可以从前面的 $cnt$ 个 $\texttt{O}$ 里面任意取 $k$ 个，方案数乘上 $\binom{cnt}{k}$。然后因为用掉了 $k$ 个 $\texttt{O}$，我们需要把 $cnt$ 减去 $k$。

Bessie’s Function G#

一道基环树板子题硬控我一下午。

我也并非人类。

我们发现这玩意可以套一个典中典的模型：对于每个 $i$，连一条 $i \to a_i$ 的边。因为总共有 $n$ 条边，所以一定是一个基环树森林。

我们发现如果要修改 $a_i$，一定是要把 $a_i$ 修改成 $i$，因为这样不仅可以使得 $i$ 变得满足条件，还能使出边连接到 $i$ 的点满足条件。但是为了方便 dfs，不可能建内向的基环树，肯定是建外向的基环树，就变成了让 $a_i = i$ 可以使得 $i$ 的儿子们也满足条件，我们就可以把题意转化一下：

对于每个点 $u$，都可以花费代价 $c_u$ 进行一次操作。操作必须要满足以下条件：如果你不操作那你的所有前驱就必须操作（在树上“前驱”表示儿子，在环上表示上一个节点。），反之你的前驱爱咋咋地。求最小代价。

我们这个题意都把方程给你写出来了。设 $dp_{u,0/1}$ 表示 $u$ 操作或者不操作。在树上就是：

在环上也类似。如何处理环上 dp 呢？我们考虑钦定 $cir_0$ 的状态。比如我们钦定 $cir_0$ 选，那么 $dp_{cir_0,1}$ 就设成 $\inf$，最后统计答案最后一个点 $u$ 就爱选不选，$tmp = \min\{dp_{u,0},dp_{u,1}\}$。反之就是 $dp_{cir_0,0} = \inf$，$tmp = dp_{u,1}$。最后 $ans$ 加上两个 $tmp$ 的最小值就是了。

以后有向图找环还是老老实实 dfs 吧。

Shorten the Array#

都想到了 $85\%$ 了为啥不再想一会呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include<bits/extc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e5 + 5;
int n,k,cnt;
int ch[maxn * 30][2],pos[maxn * 30];
void ins(int x,int id)// 字典树插入
{
    int rt = 1;
    for (int i = 30; i >= 0; i--)
    {
        bool dig = (x >> i) & 1;
        if (!ch[rt][dig])
            ch[rt][dig] = ++cnt;
        rt = ch[rt][dig];
        pos[rt] = max(pos[rt],id);// 维护这个这个子树内的最大 id
    }
}
int que(int x)
{
    int sum = 0,res = 0,rt = 1;
    for (int i = 30; i >= 0; i--)
    {
        bool dig = (x >> i) & 1;
        if (ch[rt][dig ^ 1])
        {
            if ((sum ^ (1 << i)) >= k)
            {
                res = max(res,pos[ch[rt][dig ^ 1]]);
                rt = ch[rt][dig];
                // 如果可以 >= k 就记录答案，然后往另一个子树走，看看能不能更大。
            }
            else
            {
                // 否则肯定要异或。
                sum ^= (1 << i);
                rt = ch[rt][dig ^ 1];
            }
        }
        else if (ch[rt][dig])
            rt = ch[rt][dig];
        else
            break;
    }
    return res;
}
void solve()
{
    for (int i = 1; i <= cnt; i++)
        ch[i][0] = ch[i][1] = pos[i] = 0;
    cnt = 1;
    scanf("%d%d",&n,&k);
    int ans = inf;
    for (int i = 1,x; i <= n; i++)
    {
        scanf("%d",&x);
        ins(x,i);
        if (int tmp = que(x); tmp)
            ans = min(ans,i - tmp + 1);
    }
    if (k == 0)
        return (void)puts("1");
    if (ans == inf)
        puts("-1");
    else
        printf("%d\n",ans);
}
signed main()
{
    int t;
    scanf("%d",&t);
    while (t--)
        solve();
    return 0;
}

后日谈#

今天也是终于把 Java 的传参搞懂了。

4 月 15 日#

人不要太贪心。$110$ pts 达成目标了就行了不要再想更高的分。

机房 rating $13.7 \to 15.0$。

T1#

考虑对于每个 scc 分别算贡献。因为只有 $n$ 条边，所以只会形成基环森林，不会形成那些乱七八糟形态的环套环。

• 如果这个 scc 里一个没取，那么对于答案的贡献就是 $1 \times 2^{n - siz}$，因为有总共的一个 scc，而外面的怎么取都无所谓，方案数是 $2^{n - siz}$。
• 否则枚举这个 scc 里取了 $j$ 个点，那么会形成 $siz - j$ 个 scc，方案数是 $\binom{siz}{j}$，外面是方案数还是 $2^{n - siz}$，那么贡献就是 $(siz - j) \times \binom{siz}{j} \times 2^{n - siz}$。

因为每个 scc 的点数和是 $n$，所以时间复杂度 $O(n)$。

T2 & T3 & T4#

只打了个 T4 的暴力。据说 T4 是线性 dp？

jmr 的话我也信？

后日谈#

之前为了抵御我的颓废之心，我就一直在心里给自己说：你看你都菜成这样你还颓废？然而现在是不颓废了，但是这个想法似乎是被深渊侵蚀了一样，考好了依然有，导致考多少都不知足。这是个大问题，不仅让我晚上睡不着觉，重要的是脑子里的奖励机制废了。没有来自内心的动力，我就变成了傀儡。

4 月 16 日#

你甘心停留在 C 组吗？

T2#

我们发现 $m \le 1 \times 10^6$，这个 $q$ 我们直接不管他，我们预处理 $ans_i$ 表示询问 $i$ 时的答案，到时候直接 $O(1)$ 查询就是了。

考虑如何求 $ans_i$。发现对于每个 $i$，如果独立的求显然不好做。考虑如何从 $ans_{i - 1}$ 递推。我们发现这是一个神经的倍增。而上面的那一半和下面的那一半跳的步数是一样的。考虑求上面的那一半然后乘 $2$。

如何求上面那一半呢？考虑何时 $p$ 会继续往下跳。发现，会造成影响的只有 $a_1,a_3,a_5,\dots,a_{2^n - 1}$，因为只跳的到这些位置。显然只有 $O(\log_2 n)$ 个位置。我们直接枚举当前跳到了 $a_p$。何时它会继续往下跳，并造成 $2$ 的贡献？（这里的贡献按 $2$ 算了就不用执行上文的乘 $2$ 了）

发现当且仅当 $a_p \le i$ 的时候会继续往下跳并造成贡献。$a_p \in [1,i - 1]$ 的我们已经在 $ans_{i - 1}$ 里算过了，所以我们只考虑 $a_p = i$。那么这个位置会造成的贡献就是 $\binom{i - 1}{p - 1} \times \binom{m - i}{n - p} \times 2$。具体来说，因为 $a$ 是单调递增的，所以我们要把 $i - 1$ 个数取 $p - 1$ 个填进 $[1,p - 1]$ 这个范围内。后面同理。最后乘上一个 $2$ 作为贡献，就可以加进 $ans_i$ 了。

T3#

我不想也不能。

这是一个无根树。考虑如果有根（也就是有一个固定的终点怎么做）。我们发现可以做 dp。对于每个节点 $u$ 记录一个 $a_u$，里面存两个数，分别是到达 $u$ 的最快的选手和他所用的时间。转移是平凡的。

考虑没有一个固定的根怎么办。对于一个无根树，我们就可以做换根 dp。考虑如和 $O(1)$ 换根。我们只用在 $a_u$ 里多记录几个值。分别是：第一个到达的与他的时间，第二个到达的与他的时间，第一个从哪里来。如何换根呢？我们考虑从 $u$ 转移 $v$（$v \in son_u$）。我们发现：如果最快的不来自 $v$，我们就直接拿他来转移 $v$，反之就拿次快的转移 $v$。大力分讨即可。统计答案就离线，然后换根换到 $t$ 的时候把每个 $s$ 对应的得分记录一下就行。

别忘了还原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void dfs2(int u,int fa)
{
    for (auto [s,id] : que[u])
        ans[id] = buc[s];// 桶记录得分
    for (auto [v,w] : g[u])
    {
        if (v == fa)
            continue;
        Klee tu = a[u],tv = a[v];
        buc[a[u].fir.second]--,buc[a[v].fir.second]--;
        if (a[u].from == v)// 如果来自 v 就换成次快的
            a[u].fir = a[u].sec;
        pii tmp = a[u].fir;
        tmp.first += w;
        if (tmp < a[v].fir)// 转移
        {
            a[v].sec = a[v].fir;
            a[v].fir = tmp;
            a[v].from = u;
        }
        else if (tmp < a[v].sec)
            a[v].sec = tmp;
        buc[a[u].fir.second]++,buc[a[v].fir.second]++;
        dfs2(v,u);
        // 别忘了还原
        buc[a[u].fir.second]--,buc[a[v].fir.second]--;
        buc[tu.fir.second]++,buc[tv.fir.second]++;
        a[u] = tu,a[v] = tv;
    }
}