本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 22:45:00

记录

赛时在上课，听说很多人被 B 卡了，以为特别困难，结果发现是基本题，大失所望。切到 E，但是 E 花了很长时间，后来做 G 的时候也调了很长时间，感觉 F 还是比较困难。（后来发现 F 是难调的板子）

题解

A - A Healthy Breakfast

基本判断题，略过不表。

B - Vertical Reading

暴力枚举所有的 $(w,c)$，然后把每个段中的第 $c$ 个字符拿出来比较即可，所以是基本循环 + 判断题，但是很多人没做出来，怎么回事呢（

C - Move It

发现每个盒子中原有的物品只能留下一个，这里选择留下每个盒子中重量最大的，其余的全部移到其他的空盒子里，显然这样一定最优。

D - Ghost Ants

发现如果方向不同，那么不可能相遇。所以预处理一下向右走的，再用向左走的来询问遇见了多少只。可以设 $l_i$ 表示有多少只的起点在 $i$ 及之前，$r_i$ 表示有多少只的终点在 $i$ 及之前，那么对于 $[x,x-t]$ 询问时答案为 $l_x-r_{x-t-1}$。

话说固定了每只的路程长度 $t$ 的话其实可以简化，这个做法可以做路程长度不同的。

E - Random Swaps of Balls

首先注意到初始状态只有两种：初始黑和初始白。另外求期望需要求出概率，但这个题目中只有这两种状态，所以就可以维护 $f_i,g_i$ 分别表示操作 $i$ 轮后黑球在 $1$ 号的概率以及在 $i\in[2,n]$ 分别的概率，其实这里一定有 $f_i+(n-1)g_i=1$，但是我赛时没注意到。

所以分别计算一下每种情况在 $n^2$ 种情况中出现的次数即可，有以下转移：

• $f_i=\frac{n^2-2n+2}{n^2}f_{i-1}+\frac{2n-2}{n^2}g_{i-1}$
• $g_i=\frac{1-f_i}{n-1}$

所以答案为 $f_n+g_n\sum_{k=2}^n$，用等差数列求和即为 $f_n+\frac{(n-1)(n+2)g_n}{2}$。

F - InterSections

发现与区间 $i$ 相交的条件是对 $l,r$ 的共同要求，也即 $l\in[0,l_i-1],r\in[l_i+1,r_i-1]$ 或 $l\in[l_i+1,r_i-1],r\in[r_i+1,10^9]$。考虑把这两个 $l,r$ 的要求放在 $l-r$ 的二维平面上，也就是两个不交的矩形中都可以与第 $i$ 个区间相交。所以扫描线枚举 $l$ 维，求 $r$ 维上的最大值即可。（但是截止到写这段话我还没有调出来）

G - Suitable Edit for LIS

首先原有的最长长度以及不含两端的最长长度 $+1$ 是显然能达到的。考虑让第 $i$ 个数修改后从前面和后面各连上一段，所以先用树状数组跑出以 $i$ 结尾和以 $i$ 开头的最长上升子序列长度 $f_i,g_i$。

所以要求的就是 $\max^{n-1}_{x=2} f_i+g_j+1$，其中 $i<x,j>x,a_j-a_i\ge 2$，那么变为枚举 $j$，把 $f_i$ 以 $a_i$ 为下标扔到树状数组上维护即可，为了保持不小于 $2$ 的性质需要把 $a_i+1$ 也进行离散化。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-03 14:26:22

一题多解，写一下。

Update：25.09.28 LCA 讲课后，补充了栈做法的正确性证明。

Sol.1 DP 优化

朴素地设 $f_i$ 表示以 $i$ 为结尾的合法子串数，则有 $f_i=f_{g_i}+1$，其中 $g_i$ 表示 $[g_i,i]$ 合法的最大下标。可以想到初始化 $g_i=i$，然后不断让 $g_i=g_{g_i-1}$ 直到 $a_{g_i}=a_i$，但是这种做法最劣是 $O(n^2)$ 的，会被卡。

所以考虑快速求出 $g_i$ 这个位置，话说这里题解强得离谱导致我对着题解看了好久。考虑再设 $to_i$ 表示 $[to_i+1,i]$ 合法的最小下标，$mx_{i,j}$ 表示 $[i+1,mx_{i,j}]$ 合法且 $a_{mx_{i,j}}=j$ 的最大下标。

初值 $to_i=i$，还是先找到 $k=to_{i-1}$，然后找到 $x=mx_{k,s_i}$，所以现在保证了 $[k+1,x],[k+1,i-1]$ 均合法且 $s_x=s_i$，所以 $[x+1,i-1]$ 合法，从而两端加上 $s_x=s_i$ 后 $[x,i]$ 仍然合法。此时转移 $to_i=to_{x-1},f_x=f_{x-1}+1$，然后维护 $mx_{to_i,s_i}=i$。

• 未优化：时间 $O(n^2)$，空间 $O(n)$。
• 优化后：时间 $O(n)$，空间 $O(nS)$，$S$ 为 $s_i$ 的值域。

栈做法

判断区间是否合法只需要像括号序列一样用栈维护还没有匹配的字符，如果最终空了就合法。如果枚举所有区间再依次判断，复杂度为 $O(n^3)$。如果枚举左端点 $l$，从 $l$ 开始每空一次便是一个合法区间，复杂度为 $O(n^2)$。

最终版本是维护整个区间的栈序列，只要 $x,y$ 分别放进去后栈中元素相同，那么 $[x+1,y]$ 就是一段合法区间。所以问题变成了判断栈序列相同，以下是复杂度正确的优化做法。

正确性证明：

区间合法显然是可加的，即 $A,B$ 均合法一定有 $AB$ 合法。另外显然操作顺序是任意的，即任意消除可消的元素都能消完合法区间，因此若 $AB$ 合法且 $A$ 合法则一定有 $B$ 也合法。那么若前缀 $S$ 和更长的前缀 $T$ 消完的栈序列均为 $R$，将 $R$ 倒过来接在前面，有 $RS$ 和 $RT$ 均合法，这两者相减即可得到该区间合法。同样该区间合法也能反推出 $S$ 和 $T$ 一定相同，因此该结论正确。

Sol.2 矩阵乘法（群论思想）+ 哈希

考虑如果能用运算消掉两个元素的话，就相当于群论中 $aa^{-1}=e$。所以每种元素第偶数个赋上 $a$，第奇数个赋上 $a^{-1}$。但问题是如果群中满足交换律，会把 $aba^{-1}b^{-1}$ 这种串判定为合法，所以必须使用不满足交换律的群。

可以使用矩阵乘法群，手算构造出互逆矩阵并放到序列里。对整个序列做前缀乘法，判断相同矩阵的出现次数即可，需要用哈希判断。所以我感觉不如 Sol.3 直接哈希，复杂度时间 $O(nx^3)$，空间 $O(nx^2)$，其中 $x$ 为矩阵大小。

Sol.3 栈 + 哈希

维护前 $i$ 个时栈序列的哈希值 $h_i$，弹栈时就跳到栈顶的前一个位置的哈希值，否则就把新的值加入 $h_{i-1}$，开个 map 维护一下每个哈希值出现的次数就行了。

但是 $10^9$ 级别模数很可能出现哈希冲突，需要用双模哈希或者用自然溢出扩大到 $10^{18}$ 级别才能比较稳定地通过，但我用哈希冲突也试了俩数才全过。

复杂度：时间 $O(n\log n)$，空间 $O(n)$。

Sol.4 栈 + Trie

用 Trie 维护每次出现的栈序列，发现每次栈序列只会变化 $1$，也就是要么删一个数，要么加一个数，对应到 Trie 上也就是向父亲或儿子跳一下。每次都给对应的节点计数即可，最终答案即为 $\sum\frac{k(k-1)}2$，$k$ 是每个节点对应的栈序列出现次数。

复杂度上由于一共只会修改 $n$ 次，Trie 中至多有 $n$ 个节点。如果用数组存子节点则时间 $O(n)$，空间 $O(nS)$，用 map 的话时间 $O(n\log n)$，空间 $O(n)$。后者可以无视值域，而且其实时间常数也比较小。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-04 15:14:59

A. Gift

容易发现如果只有一种权值，就是最小瓶颈生成树，可以直接跑最小生成树解决。但是有两个权值 $s_i,g_i$，考虑枚举一个权值的最大值 $s$，只用 $s_i<s$ 的边跑关于 $g_i$ 的最小生成树，求出答案 $sS+gG$。

显然跑的轮数是 $m$，如果每次都直接用所有边进行 Kruskal，还有 $O(m\log m)$ 的复杂度，整体变为 $O(m^2\log m)$。但是发现每次不一定要用所有边去跑，因为若边在先前的处理中没有进入最小生成树，那么一定不会由于加边而加入。

所以每加入一条边时用上一轮最小生成树中的边加上新边跑即可，边数至多为 $n$，复杂度降为 $O(mn\log n)$。另外 $O(n\log n)$ 的瓶颈在于对边排序，但是每次只有一条新边，插入边集即可，复杂度为 $O(nm)$。

B. Mice

Sol.1 贪心

发现只有最近奶酪有两块的老鼠需要决策，如果左边那块还没有被占用或能与前面的老鼠共用就往左，否则就往右。如果离所选奶酪 $x$ 的距离与记录的最小距离 $mn_x$ 相等，或所选奶酪还没有被选就记录答案。否则要么抢不到，要么抢了另一只老鼠原来有的，答案均不会改变。

Sol.2 DP

发现一只老鼠至多对应两块奶酪，设第 $i$ 只老鼠能前往的奶酪区间为 $[l_i,r_i]$，一定有 $0\le r_i-l_i\le 1$。而且相邻两只老鼠对应的奶酪只会有一块重复，也就是 $r_{i-1}\le l_i$。那么 DP 状态设计就要考虑到重复奶酪的分配。

设 $f_{i,0/1}$ 表示前 $i$ 只老鼠中第 $i$ 只老鼠是 / 否选 $r_i$ 这个奶酪，能吃到奶酪的最多老鼠数。边界 $f_{0,0}=0$，有如下转移：

设 $k=\max(f_{i-1,0}+1,f_{i-1,1}+[r_{i-1}\ne l_i\wedge dis(i,l_i)=dis(i-1,r_{i-1})])$，也就是选 $l_i$ 的答案。

• $l_i=r_i$ 时，$f_{i,0}=-\infty,f_{i,1}=k$。
• $l_i\ne r_i$ 时，$f_{i,0}=k,f_{i,1}=\max(f_{i-1,0},f_{i-1,1})+1$。

最终答案即为 $n-\max(f_{n,0},f_{n,1})。$

C. Mutation

求方案数，总方案数有 $2^k\le4,194,304$ 种，每种都要求出总代价，显然不能硬求，可能要做到 $O(1)$ 查询。

考虑拆字符串中每对字符对所有方案的贡献，对于 $(l,r),l<r$，如果要在最终的字符串中相邻，就一定需要删掉 $[l+1,r-1]$ 中的全部字符，并且保留 $a_l,a_r$。那么就有 $\forall i\in[l+1,r-1],a_i\ne a_l$ 且 $a_i\ne a_r$。

也就是说，对于 $r=i$ 的区间，只有每个字符最后一次出现的位置 $x$ 作为 $l$ 合法，否则就有 $a_i=a_l$。同时 $x$ 还要在 $a_r$ 上一次出现之后，否则就有 $a_i=a_r$。所以能贡献的区间就只剩至多 $nk$ 个了，维护一个 $last_i$ 就能处理出这些区间。

然后考虑分别处理这些 $(l,r)$ 的贡献，状压地用 $S$ 表示 $[l+1,r-1]$ 中存在的所有字符种类，这里用 $last_j>l$ 来判断是否存在即可。那么所有包含 $S$ 的方案均有 $d_{a_l,a_r}$ 的代价，先给 $t_S$ 加上。同时 $a_l,a_r$ 不能删，所以给 $S+a_l,S+a_r$ 分别减去 $d_{a_l,a_r}$，$S+a_l+a_r$ 容斥地加上 $d_{a_l,a_r}$。这样以后做高维前缀和即可。

另外，删字母的代价可以放到 $S=2^i$ 上，在做高维前缀和时也能统计出来。时间复杂度 $O(nk+2^k)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 11:12:30

记录

B 吃一发不应该，D 调很久不应该，F 不知道怎么回事挂一个点。E 是板子，切得比较快。G 太困难了（好像也不是那么困难）。

题解

A - Insert

基本循环题，略过不表。

B - Intersection of Cuboids

有体积交等价于每一维上都有交的区间，对每一维分别判断即可。

C - Make Them Narrow

先排序，显然取的一定是连续的 $n-k$ 个数，所以枚举起点 $i$，答案为 $\min_{i=1}^{k+1}a_{i+n-k-1}-a_i$。

D - Go Stone Puzzle

状压 + BFS，需要记录的状态为每一位上是黑还是白的 $S$ 串，以及目前空着的位置 $x$，状态数 $(n+2)2^{n+2}$，BFS 转移时枚举哪两位移到 $x,x+1$ 即可。只要保证空着的两个位置均为 $0$，就可以直接用相等判断是否是结果串。

E - Tree and Hamilton Path 2

发现一定要走每一条边以到达每一个点，同时走到最后一个没走的点 $x$ 时不用走回来，也就是从 $x$ 回到 $st$ 的路不用走。所以记树的边权和 $tot$，最长链长度 $dis$，答案为 $2tot-dis$。也就是从最长链一端开始走，最后走到另一端，这条链上的边只会经过一次。求 $dis$ 用 DFS 求树的直径即可。

F - x = a^b

发现 $10^{18}$ 内最多只有 $2^{59}$，所以没有次数高于 $59$ 的数。考虑设 $f_i$ 表示 $x^i\le n$ 的 $x$ 个数，那么 $f_i=\lfloor\sqrt[i]{n}\rfloor$。

但是直接加会算重很多 $x$，考虑每个 $x$ 都在最大的使得 $k_i\le n$ 的 $i$ 处计算，那么考虑到 $i$ 时就需要将 $f_i$ 减去 $\sum_{j=2i}^{P}f_j,i\mid j$，也就是把在 $i$ 的倍数处考虑过的减掉。

但是，用枚举和 pow 函数求 $f_i$ 都挂了几个点，目前不知道原因，是因为前者中我用来求 $f_2$ 的 sqrt 函数以及 pow 函数均有精度问题，导致挂了，需要注意。

G - Go Territory

考虑如果直接 BFS 找出所有与 $(-1,-1)$ 相连的点，复杂度会到 $O(XY)$，大约 $4\times10^{10}$ 级别。考虑减少点数，发现如果分行考虑，每行每一段连续的白点为一个连通块，那么连通块总数为 $X+n$，可以接受。相邻两行连边时用双指针可以做到总共 $O(n)$，总时间复杂度 $O(n\log n)$，瓶颈在排序。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 10:27:00

思路

发现从剩余的 $45$ 张牌里选两张的方案数为 $\frac{45\times44}{2}=990$，每个人从七张牌中选五张的方案数为 $\frac{7\times 6}2=28$，总共需要处理的牌型有 $990\times28\times2=55440$ 种，所以直接暴力搜出每一种即可。

另外还有一些处理牌型时能注意到的点：

• 每张牌是什么花色不重要，只需要知道五张牌是否同花色即可。
• 任意两种有区别的牌型均能分出大小。
• 所有比较均是先比较类型，再以某些牌的大小为关键字比较。

因此想到如果能把每种牌型都压成一个数，会更方便比较。所以代码中把牌的类型作为高位，其他关键字依次作为低位压成了一个数。而且这里只需要保证同种类型的牌型处理时位置对齐即可，不同类型之间已经由于最高位不同分出大小了。

一共才 $55440$ 种牌型，且时限 $20$ 秒，处理常数大点也能过，但我的代码大概用了 $200$ 毫秒。

具体还是看代码吧，里面还写了几个函数来简化。

代码

#include<iostream>
#include<vector>
#include<cstdio> 
#include<algorithm>
#define pb push_back
#define int long long 
#define double long double
using namespace std;
const int P=1e17;
char tc[3];
struct card {int cl,rk;} my[3],op[3],pu[6];
bool eq(card x,card y) {return x.cl==y.cl&&x.rk==y.rk;} \/\/判断两张牌是否相同 
bool chkgl(card x,card y) {return x.rk==y.rk?x.cl<y.cl:x.rk<y.rk;} \/\/给每两张不同牌唯一的大小关系 
vector <card> temp,tem;
vector <int> rk,tk; \/\/rk 为牌型，tk 为比较时的关键字 
int cnt,tcl,p[6];
int ccl(char ch)
{
	if(ch=='S') return 0;
	if(ch=='H') return 1;
	if(ch=='D') return 2;
	return 3;
} \/\/转换花色 
int crk(char ch)
{
	if(ch>='2'&&ch<='9') return ch-'0';
	if(ch=='A') return 14;
	if(ch=='T') return 10;
	if(ch=='K') return 13;
	if(ch=='Q') return 12;
	return 11;
} \/\/转换点数 
bool eqlr(int l,int r)
{
	for(int i=l+1;i<=r;i++) if(rk[i]!=rk[i-1]) return false;
	return true;
} \/\/判断 rk 中 [l,r] 是否相等 
int flus()
{
	if(rk[4]==14)
	{
		bool tf=true;
		for(int i=0;i<4;i++) if(rk[i]!=i+2) tf=false;
		if(tf) return 1;
	}
	for(int i=1;i<5;i++) if(rk[i]!=rk[i-1]+1) return 0;
	return rk[0];
} \/\/判断 rk 中的五张牌是不是顺子，若是，返回其最小值作为权值 
int so()
{
	int res=0,len=tk.size();
	for(int i=0;i<len;i++) res+=tk[i]*p[len-i-1];
	return res;
} \/\/把 tk 中的比较关键字压缩成一个数字 
void ins(int x) {tk.pb(x);}
int sol()
{
	sort(rk.begin(),rk.end()); \/\/先升序排序 
	if(tcl!=-2&&flus()) return P*9+flus(); \/\/同花顺 
	if(eqlr(0,3)) {ins(rk[0]),ins(rk[4]); return P*8+so();}
	if(eqlr(1,4)) {ins(rk[1]),ins(rk[0]); return P*8+so();} \/\/四张 
	if(eqlr(0,2)&&eqlr(3,4)) {ins(rk[0]),ins(rk[3]); return P*7+so();}
	if(eqlr(0,1)&&eqlr(2,4)) {ins(rk[2]),ins(rk[0]); return P*7+so();} \/\/三带二 
	if(tcl!=-2) {for(int i=4;i>=0;i--) ins(rk[i]); return P*6+so();} \/\/同花色 
	if(flus()) return P*5+flus(); \/\/顺子 
	if(eqlr(0,2)) {ins(rk[0]),ins(rk[4]),ins(rk[3]); return P*4+so();}
	if(eqlr(1,3)) {ins(rk[1]),ins(rk[4]),ins(rk[0]); return P*4+so();}
	if(eqlr(2,4)) {ins(rk[2]),ins(rk[1]),ins(rk[0]); return P*4+so();} \/\/三张 
	if(eqlr(1,2)&&eqlr(3,4)) {ins(rk[3]),ins(rk[1]),ins(rk[0]); return P*3+so();}
	if(eqlr(0,1)&&eqlr(3,4)) {ins(rk[3]),ins(rk[0]),ins(rk[2]); return P*3+so();}
	if(eqlr(0,1)&&eqlr(2,3)) {ins(rk[2]),ins(rk[0]),ins(rk[4]); return P*3+so();} \/\/两对 
	for(int i=0;i<4;i++) if(rk[i]==rk[i+1])
	{
		ins(rk[i]);
		for(int j=4;j>=0;j--) if(j!=i&&j!=i+1) ins(rk[j]);
		return P*2+so();
	} \/\/一对 
	for(int i=4;i>=0;i--) ins(rk[i]);
	return P+so(); \/\/单牌 
}
int solv()
{
	tcl=-1,rk.clear(),tk.clear();
	for(card k:tem) rk.pb(k.rk),tcl=((tcl==-1||tcl==k.cl)?k.cl:-2);
	return sol();
} \/\/判断 tem 中五张牌是否同花色，不同则 tcl=-2，同时把点数传到 rk 中 
int solve()
{
	int res=-1;
	for(int i=0;i<7;i++) for(int j=i+1;j<7;j++)
	{
		tem.clear();
		for(int k=0;k<7;k++) if(k!=i&&k!=j) tem.pb(temp[k]);
		res=max(res,solv());
	}
	return res;
} \/\/枚举 temp 中七张牌选五张（不选两张）的方案，并传到 tem 计算最大值 
void check()
{
	if(eq(pu[4],pu[5])||chkgl(pu[4],pu[5])) return;
	for(int i=4;i<=5;i++)
	{
		for(int j=1;j<=2;j++) if(eq(pu[i],my[j])||eq(pu[i],op[j])) return;
		for(int j=1;j<=3;j++) if(eq(pu[i],pu[j])) return;
	} \/\/判断没有牌重复 
	int mysc,opsc; temp.clear();
	for(int i=1;i<=5;i++) temp.pb(pu[i]);
	temp.pb(my[1]),temp.pb(my[2]),mysc=solve(),temp.pop_back();
	temp.pop_back(),temp.pb(op[1]),temp.pb(op[2]),opsc=solve(); \/\/分别把各自的七张牌传到 temp 中计算 
	cnt+=(mysc>opsc);
} \/\/对于每种 pu[4],pu[5] 的情况计算是否获胜 
signed main()
{
	p[0]=1;  for(int i=1;i<=5;i++) p[i]=p[i-1]*1000;
	while(cin>>tc)
	{
		if(tc[0]=='#') break;
		cnt=0,my[1]={ccl(tc[0]),crk(tc[1])};
		cin>>tc,my[2]={ccl(tc[0]),crk(tc[1])};
		for(int i=1;i<=2;i++) cin>>tc,op[i]={ccl(tc[0]),crk(tc[1])};
		for(int i=1;i<=3;i++) cin>>tc,pu[i]={ccl(tc[0]),crk(tc[1])}; \/\/存储牌 
		for(pu[4].cl=0;pu[4].cl<4;pu[4].cl++) for(pu[4].rk=2;pu[4].rk<=14;pu[4].rk++)
		for(pu[5].cl=0;pu[5].cl<4;pu[5].cl++) for(pu[5].rk=2;pu[5].rk<=14;pu[5].rk++) check(); \/\/枚举 
		printf("%.8Lf\n",(double)cnt\/990);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 14:46:31

记录

ABCD 都切了，但是 CD 出现了低级错误，已经记录了。

题解

A. Array Divisibility

考虑直接赋 $a_i=i$，这样下标为 $k$ 的倍数的数同样为 $k$ 的倍数，符合题意。

B. Corner Twist

先处理出 $r_{i,j}=b_{i,j}-a_{i,j}$，考虑由上到下，由左到右将 $r_{i,j}$ 归零，每次只用其下面和右面最近的三个格子。每行这样处理到 $(i,m-1)$，如果 $r_{i,m}\ne0$ 即无解。处理完 $n-1$ 行后若最后一行不全为 $0$ 则无解。

正确是因为每种大于 $2\times 2$ 的操作都可以转化成若干个 $2\times 2$ 的操作，所以只用这一种操作推平即可。

C. Have Your Cake and Eat It Too

考虑若区间在中间的人选择 $[l,r]$，那么另外两个人分别选 $[1,l-1],[r+1,n]$ 一定最优。所以分别以三个人为中间，枚举 $l$ 二分最小的合法 $r$，再判断另外两个人能否填进去即可。预处理一下前缀和即可实现，时间复杂度 $O(n\log n)$。

D. Swap Dilemma

首先是特殊情况，若两个数组元素不同则无解，否则若同时有两个或以上相同元素则有解，因为可以在一者中交换相同元素来随意改变另一个数组。

接着可以转化，发现任意交换操作均能通过若干次交换相邻两个元素来达成，所以就转化为两个数组分别做若干次交换相邻元素。另外发现如果合法，就可以把数组交换成任意形态，所以转化为使其单调递增。

那么就有一个性质，每次交换可以消掉一个逆序对。那么求出逆序对数就是需要的最少交换次数。求出两个数组需要的次数 $x,y$，若 $x,y$ 同奇偶则有解，否则无解。因为多的偶数次可以通过两次相同的操作消除掉。

E. I Love Balls

考虑把球按最终取出的顺序排成一个序列。先只考虑非特殊球，发现奇数位上是先手，偶数位上是后手，那么就能算出先手所占的比例，每个球都有同等的概率被先手取到，所以用这个比例乘上所有非特殊球的权值和就能求出先手这一部分的期望。

对于特殊球，考虑把它们插入非特殊球形成的空中，共有 $(n-k+1)$ 个空，同样奇数位是先手，偶数位是后手。那么同样计算即可。可以算出先后手中一者的期望，用总和减去就是另一者的。

F. array-value

考虑二分答案，变为检验所有区间中权值不超过 $mid$ 的数量是否达到 $k$。考虑枚举 $r=j$，找合法的 $(l,r)$ 个数。首先找到最后一个 $a_k\oplus a_j$ 的 $k$，那么所有 $l\in[1,k]$ 均有 $k,r$ 合法。保留下所有 $r<j$ 的 $r$ 对应的 $k$，那么这些 $k$ 前面都合法，取最大值即为最靠右的合法位置 $l$ 使 $l,j$ 合法。

依次枚举 $r=j$ 统计答案总和即可。那么问题变成了求出编号最大的 $l$ 使 $a_l\oplus a_r\le mid$ 的 $l$。考虑用 01Trie 维护目前所有的数，如果 $mid$ 该位为 $1$ 就跳到与 $a_r$ 不同的子树，并记录另一子树的答案。否则直接跳到与 $a_r$ 相同的子树。只要在 Trie 上维护目前子树内的编号最大值即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-10 22:54:13

记录

是目前打得最好的一场了，切得比较顺利，数据结构竟然没调一遍写对了，G 题太难了没补。

题解

A - Sanitize Hands

基本题，略过不表。

B - Uppercase and Lowercase

基本题，略过不表。

C - Sierpinski carpet

递归下去分别填即可，略过不表。

D - 88888888

有两种思路，一种是等比数列求和，没想出来。考虑类似快速幂的计算方式，在函数中同时记录已经计算了 $t$ 个 $n$，若 $n$ 长度为 $k$，下次乘的时候要乘上 $10^{kt}$

E - Reachability in Functional Graph

基环树基本题，发现所有环上的点互相可达，环外的点可达的点有对应环上的所有点和该点到环路径上的所有点，拓扑排序跑出环来，建反边从环上 dfs 统计答案即可。

F - Two Sequence Queries

考虑用线段树维护，发现区间 $a+x$ 相当于区间和增加 $x\sum b$，$b+x$ 相当于区间和增加 $x\sum a$，因此维护区间 $a,b,ab$ 的和，进行区间操作和懒标记下传即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-11 15:20:48

记录

只切到 C，D 数论和 E 计数没做出来，后来补了。

题解

A. Shovels and Swords

贪心，假设有 $a>b$，先把 $a-b$ 的差值用 $2$ 个 $a$ 和 $1$ 个 $b$ 消耗掉，若 $b$ 不够直接结束，否则已有 $a=b$，先用两者各 $3$ 个做，最后若余下 $2$ 个还能再做一个。

B. Shuffle

发现 $1$ 最终的可能位置永远是一段连续区间，因此维护该区间左右端点，每次操作若与目前的区间有交，则答案与操作区间取并集即可。

C. Palindromic Paths

显然要走 $x=n+m-2$ 步，发现要求即为对于 $i\in[0,\frac{x}{2})$ 的所有 $i$，要求所有第 $i$ 步的格子和第 $x-i$ 步的格子全部颜色相同，所以开桶记录每一步的格子颜色情况，取黑白中较少的一种修改即可。

D. Two Divisors

发现无解情况只有 $x=p^k$ 时，选出的数相加与 $x$ 一定有公因数 $p$。因此考虑把 $x=p^kq$ 的最小质因子 $p$ 拿出来，除掉所有 $p$ 后剩下 $q$，$p,q$ 即为一组可行解。

考虑证明，$\gcd(p+q,a)=\gcd(p+q,p^kq)$，由于 $p$ 是质数且 $p\neq q$，因此 $p+q$ 一定不为 $q$ 的倍数，且 $q$ 中无 $p$ 这一质因子，因此 $p+q$ 一定不为 $p$ 的倍数，所以 gcd 一定为 $1$

E. Two Arrays

发现 $b_i$ 单增，考虑把 $a$ 变为单增序列，设 $c$ 为 $a$ 后缀最小值，则对于每个 $b_{i}$，分界处必然要选在所有 $c_k=b_{i}$ 的位置之前，才能保证该区间最小值等于 $b_i$。

因此每个 $b_i$ 分界的选择方案数有 $c$ 中 $b_i$ 的出现次数个。特别地，若 $b_1\ne c_1$ 则无解，乘法原理统计答案即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-11 22:11:26

记录

D 前边切得挺顺的，E 模拟二分调整场，F 模拟赛后调半天，GH 倒是比较板，虽然我看了也不一定能做出来就是了。

题解

A - When?

判断基本题，略过不表。

B - Number Box

枚举位置和方向，模拟即可。

C - Rotation

发现若把整个段看成环，每操作一次都会使序列开头的编号 $-1$，记录总共操作次数，取模得到目前的 $x$ 在原序列的位置即可。

D - Trophy

显然最优方式一定是每关只打一遍直到解锁 $x$，之后重复打 $x$ 直到满足次数要求。因此枚举 $x$，计算前缀 $a_i+b_i$ 的和再加上 $b_i$ 乘上剩余次数，更新最小值即可。

E - Packing Potatoes

首先发现每次取到的土豆都是一个连续段，所以先预处理出土豆重量的前缀和 $s_i$。这时会发现若 $x\ge s_n$，那么每次不管从哪开始取都会先把 $n$ 个土豆全取一遍，所以可以把这部分单独拿出来，取模使得 $x<s_n$

再发现从同一个 $i$ 开始取，每次都会取到固定的 $x_i$ 个土豆，所以用二分计算出从 $i$ 取到的土豆个数 $x_i$。接着发现最多 $n+1$ 次取后就一定会出现循环节，所以找到这个循环节，便可以实现 $O(1)$ 查询，要注意还要把 $s_n$ 的整数倍这一部分加到答案中。

F - Main Street

结论显然，要么直接走，要么从四个方向中选择一个走到主干道上，再沿主干道走到终点周围的某个方向，再走到终点，共 $16$ 种方案。这里关键在于处理走的路线长度，考虑走到主干道上后可能两点在同一行或列的主干道块上，就不能使用差的绝对值作为距离，此时还要分讨两点同时从哪边走，总之比较麻烦。

G - Triangle

很显然可以枚举 $a_{i,j}=1$ 的 $i,j$，统计 $a_{i,k}=1$ 且 $a_{k,j}=1$ 的 $k$ 个数，用 bitset 优化，时间复杂度 $O(\frac{n^3}{w})$

Ex - Odd Steps

考虑朴素的转移，设 $f_i$ 为总和为 $i$ 的划分方案，则 $f_i=\sum_{j=2-i\mod2}^{i-2}$，这里设 $g_i=\sum_{j=2-i\mod2}^{i}$，转移就变成了 $f_i=g_{i-2}$，若遇到被限制的数字直接取 $f_{a_i}=0$ 即可，时间复杂度 $O(S)$

发现 $S$ 范围比较大，考虑矩阵优化，把 $f_i,s_{i-1},s_{i-2}$ 放入矩阵中，按照 $a_i$ 把整个过程分成 $n+1$ 段进行转移，每次转完以后把 $f_{a_i}$ 赋为 $0$ 再转下一段即可，时间复杂度 $O(n\log S)$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-12 12:43:06

记录

ABC 切了，D 进行了大分讨，讨到一半去吃饭了，回来打完又改了小错误过了，EFG 没看。

题解

A. LCM Problem

发现要求即为两不等的数 $x,y$ 以及它们的 lcm 在同一区间 $[l,r]$ 内，考虑让这三个数之间的差尽可能小，且让大的尽可能大。所以发现让 lcm 与较大的数 $y$ 相等一定最优，考虑怎么让 $x$ 尽量大，发现 $y$ 为偶数时 $\frac{y}{2}$ 最大，所以取最大的偶数作为 $y$，看 $x=\frac{y}{2}$ 是否不小于 $l$ 即可。

B. Array Walk

发现向左回退的操作一定会在同一个位置操作完，不然肯定不优，因此枚举所有可能的位置作为向左回退的位置，取可能的最大答案即可。预处理前缀和可以实现每次 $O(1)$ 查询结果。

C. Good String

发现好串定义可以转化为 $t_i=t_{i-2}$，这里 $t_0=t_n,t_{-1}=t_{n-1}$，所以分奇偶讨论，若长度为奇数则所有位必须相同，若为偶数则必为两位数循环出现，分别枚举 $10$ 个数和 $90$ 种两位数的情况，暴力判断需要删掉多少即可。

D. Segment Intersections

对所有贡献到最终答案中的部分分类，可以分成本来就有的交集，本来在 $a,b$ 中其中一个有的部分，代价为 $1$。这两中一定是会先贡献的，分讨一下贡献到哪一部分时满足条件。

这两部分用完后，每组区间一定会相等或无交集，相等的话每次都需要 $2$ 的代价使答案增加 $1$。无交集的话需要扩展至两个区间有共同端点，之后会有一部分代价为 $1$ 的直到两区间相同，剩下的同样代价为 $2$。可以枚举处理的区间数量 $x$，取最小代价即可。

E. Calendar Ambiguity

数学题，直接写出式子，即为找 $x,y$ 的组数使得：

• $x<y\le \min(m,d)$
• $(x-1)d+y\equiv(y-1)d+x\mod w$

第一个式子很简单，为了方便先设 $\min(m,d)=c$，需要化简的是第二个式子。首先移项合并得到 $(y-x)(d-1)\equiv 0 \mod w$，即 $w | (y-x)(d-1)$，考虑将 $w$ 和 $(d-1)$ 约掉公因数 $g$，得到 $w' | (y-x)d'$，由于 $w'$ 与 $d'$ 互质，问题转化为求 $x,y$ 数量使得 $y-x$ 是 $w'$ 的倍数。

直接设 $y-x=kw'$，如果直接枚举 $k$ 复杂度不对，考虑 $k$ 的最大范围，由于 $y\le c,x\ge1$，所以 $k\le\lfloor \frac{c-1}{w'}\rfloor$，设 $z=\lfloor \frac{c-1}{w'}\rfloor$。再考虑 $k=i$ 时的方案数，发现 $y-x=iw'$，又因为 $[x,y]$ 闭区间一定在 $[1,c]$ 闭区间里，所以方案数为 $c-iw'$

综上，答案为 $\sum_{i=1}^z c-iw'$，拆开得 $zc-\sum_{i=1}^ziw'$，等差数列求和得到 $zc-\frac{(z+1)z}{2}w'$，其中 $w'=\frac{w}{\gcd(w,d-1)},c=\min(d,m),z=\lfloor \frac{c-1}{w'}\rfloor$

F. Bicolored Segments

首先区间题能够考虑到每个区间在右端点处处理，最近刚接触到这个思想。

考虑朴素 dp，先把所有端点离散化下来，设 $f_{i,j,k}$ 表示考虑到第 $i$ 个位置，且 $[j+1,i]$ 全为 $k$ 的最大答案。转移如下：

• $f_{i,i,k}=\max(\max_{j=0}^{i-1}f_{i-1,j,0},\max_{j=0}^{i-1}f_{i-1,j,1})$

• $f_{i,j,k}=f_{i-1,j,k}+\sum_{x=1}^n[l_x>j][r_x=i][t_x=k]$

首先 $i$ 维可以滚掉，主要考虑 $j$ 维的处理，把 $j$ 维的 $k=0/1$ 分别拍到两颗线段树上，然后从左到右枚举 $i$，把所有 $r_x=i$ 的区间在 $t_x$ 的线段树上进行 $[0,l_x-1]$ 区间加一，也就是把上述第二个式子中所有的 $r_x=i$ 全部加上了，最后再把两颗线段树的 $i$ 点全部单点修改成两个线段树的最大值即可。