更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525009

前置知识

前言

既然没人讲与概率有关的知识的话，那就让我来简单介绍一下概率的相关知识吧，这个如果不知道的话这道题还是很难写的。

概率相关

定理 $1$：互补法则

定义：若事件 $A$ 发生的概率为 $P(A)$，则其不发生概率为 $1 - P(A)$。

举例：早上起来有两种选择，吃饭和不吃饭，若吃饭的概率为 $\displaystyle\frac{3}{10}$，则有不吃饭的概率为 $1 - \displaystyle\frac{3}{10} = \displaystyle\frac{7}{10}$。

定理 $2$：加法法则（互斥事件）

定义：若事件 $A_1 \sim A_n \in S$ 且 $A_i \cap A_j=\emptyset \quad \forall i, j\in\{1,2,\dots,n\},\quad i \neq j$。

那么集合中所有事件发生的概率 $P = \sum_{i=1}^n P(A_i)$。

举例：掷一次骰子时，点数大于 $4$ 的概率 $P = P(5) + P(6) = \displaystyle\frac{1}{6} + \displaystyle\frac{1}{6} = \displaystyle\frac{1}{3}$。

定理 $3$：乘法法则（无关事件）

定义：若事件 $A$ 与 $B$ 互相独立，不受影响，那么$ P(A \cap B) = P(A) \times P(B)$。

举例：早上吃饭的概率为 $\displaystyle\frac{3}{10}$，吃完饭写作业的概率为 $\displaystyle\frac{5}{6}$，那么早上吃完饭后去写作业的概率为 $\displaystyle\frac{3}{10} \times \displaystyle\frac{5}{6} = \displaystyle\frac{1}{4}$。

题目

题目大意

牛牛需要在 $n$ 个时间段内完成 $2n$ 节课程，每时间段有两节课程分别安排在教室 $c_i$ 和 $d_i$。牛牛可以申请更换教室，申请通过的概率为 $k_i$，最多申请 $m$ 次。更换教室后，牛牛需要在教室间移动，移动的体力消耗为最短路径的体力值。求最小的体力消耗期望值。

题目类型

我们发现对于每一个时间段 $i$ 的课程，都有选 $c_i$ 和 $d_i$ 两种，我们可以很快想到用动态规划来解决期望概率的问题，而最短路径的话可以用弗洛伊德算法求解，因为本题 $1 \le v \le 300$，那么我们的状态如何设计呢？

状态设计

首先，对于每个时间段是一定要在状态里面的。其次，牛牛对于换教室这个事情其实是不感冒的，可以换或者不换，因此换了多少个教室是一定要在条件里面的。最后，因为我们按时间段向后 dp 的话，当前的 $i$ 时间段是由 $i - 1$ 推出的，但是无法记录上一个时间段到底换没换教室，如果要开个别的东西记录一下就太麻烦，因此就需记录上一个时间段是否换了教室。

所以我们可以这样记录状态，用 $dp_{i,j,k}$ 来表示，在第 $i$ 个时间段内，已经选了 $j$ 间教室更换，$k$ 表示当前的为这个时间段是否更换，$k \in \{0,1\}$。

转移方程（分类讨论）

一：选择不更换当前的教室，再次分类讨论。

由互补法则可知，当前成功更换的概率为 $v_i$，失败的概率即为 $1 - v_i$，而下文的 $2$ 与 $3$ 属于互斥事件，因此用加法法则，将两者的概率加到一起。

1. 前一个教室不做更改，当前期望值即为 $f_{c_{i-1},c_i}$。

2. 前一个教室做更改，且更改成功，当前期望值即为 $v_{i-1} \times f_{d_{i-1},c_i}$。

3. 前一个教室做更改，且更改失败，当前期望值即为 $(1 - v_{i-1}) \times f_{c_{i-1},c_i}$。

总结第一大类的情况，为了求最小值，所以取小，即可得出选择不更换当前教室的转移方程：

$dp_{i,j,0} \gets \min(dp_{i-1,j,0} + f_{c_{i-1},c_i},dp_{i-1,j,1} + v_{i-1} \times f_{d_{i-1},c{i}} + (1 - v_{i-1}) \times f_{c_{i-1},c_i})$

二：选择更换当前教室，再次分类讨论

下文的 $1$ 和 $2$ 属于互斥事件，而 $3,4,5,6$ 也属于互斥事件，因此用加法法则，将两者的概率加到一起。而对于 $3,4,5,6$，由乘法法则，则将两次概率相乘。

1. 前一个教室不做更改，且当前教室更改成功，当前期望值即为 $v_i \times f_{c_{i-1},d_i}$

2. 前一个教室不做更改，且当前教室更改失败，当前期望值即为 $(1 - v_i) \times f_{c_{i-1},c_i}$

3. 前一个教室做更改，且前一个更改成功，当前教室更改成功，当前期望值即为 $v_{i-1} \times v_i \times f_{d_{i-1},d_i}$

4. 前一个教室做更改，且前一个更改成功，当前教室更改失败，当前期望值即为 $v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i}$

5. 前一个教室做更改，且前一个更改失败，当前教室更改成功，当前期望值即为 $(1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i}$

6. 前一个教室做更改，且前一个更改失败，当前教室更改失败，当前期望值即为 $(1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i}$

总结第二大类的情况，这里的 $j$ 不要忘记 $-1$，即可得出选择更换当前教室的转移方程：

$dp_{i,j,1} \gets \min(dp_{i-1,j-1,0} + v_i \times f_{c_{i-1},d_i} + (1 - v_i) \times f_{c_{i-1},c_i},dp_{i-1,j-1,1} + v_{i-1} \times v_i \times f_{d_{i-1},d_i} + v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i} + (1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i} + (1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i})$

代码

#include<iostream>
#include<algorithm>
#include<iomanip>
//#define int long long
using namespace std;

const int MAXN = 2005;
const int MAXV = 305;
double f[MAXV][MAXV];
int n,m,e,v;
int c[MAXN],d[MAXN];
double k[MAXN];
double dp[MAXN][MAXN][2];

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> m >> v >> e;
	for(int i = 1;i <= n;i ++) cin >> c[i];
	for(int i = 1;i <= n;i ++) cin >> d[i];
	for(int i = 1;i <= n;i ++) cin >> k[i];
	for(int i = 1;i <= v;i ++){
		for(int j = 1;j <= v;j ++){
			f[i][j] = 1e18;
		}
		f[i][i] = 0;
	}
	for(int u,v,w,i = 1;i <= e;i ++){
		cin >> u >> v >> w;
		f[v][u] = f[u][v] = min(f[u][v],w * 1.0);
	}
	for(int t = 1;t <= v;t ++){
		for(int i = 1;i <= v;i ++){
			for(int j = 1;j <= v;j ++){
				if(f[i][t] + f[t][j] < f[i][j]){
					f[i][j] = f[i][t] + f[t][j];
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][1] = dp[i][j][0] = 1e18;
		}
	}
	dp[1][0][0] = 0;
	dp[1][1][1] = 0;
	for(int i = 2;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],dp[i - 1][j][1] + k[i - 1] * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * f[c[i - 1]][c[i]]);
			if(j > 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * k[i] + f[c[i - 1]][c[i]] * (1 - k[i]),dp[i - 1][j - 1][1] + k[i - 1] * k[i] * f[d[i - 1]][d[i]] + k[i - 1] * (1 - k[i]) * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * k[i] * f[c[i - 1]][d[i]] + (1 - k[i - 1]) * (1 - k[i]) * f[c[i - 1]][c[i]]);
		}
	}
	double ans = 1e18;
	for(int i = 0;i <= m;i ++){
		ans = min(ans,min(dp[n][i][1],dp[n][i][0]));
	}
	cout << fixed << setprecision(2) << ans << '\n';
	return 0;
}

记 $c_i=\gcd(i,a_i)$，操作二实际上就是给定初始的 $x$，每次令 $x\to c_x+x$，问跳出序列的路径上所有 $a_x$ 之和。

这个形式非常像 [HNOI 2010] 弹飞绵羊 这道题，实际上可以直接照搬分块做法，先将序列分块。

设 $f_i$ 表示从 $i$ 出发跳出快后到达那个位置，$g_i$ 表示从 $i$ 跳到 $f_i$ 的路径权值和。

假设 $i$ 所在的块的右边界为 $r$，则分情况。

1. 若 $i+c_i>r$：$f_i=i+c_i,g_i=a_i+w_i$。

2. 若 $i+c_i\le r$：$f_i=f_{i+c_i},g_i=a_i+g_{i+c_i}$。

注意单点修改整个块都要重构，所以单点修改的复杂度为 $O(B)$。

回到本题，查询的复杂度是显然的 $O\left(\frac{n}{B}\right)$，考虑如何修改。

不难发现，$c_i$ 在修改过程中只会不断增大趋近于 $i$，每次增大都会乘上一个数，均摊分析可以知道所有 $c_i$ 的变化次数不超过 $1\sim n$ 的质因子个数之和，即 $n\log n$。

所以每次要找到哪个数要单点修改后，直接暴力重构块即可，然后用分块维护区间 $a_i\gets a_i\times c$ 的操作。这一部分的复杂度为 $O(nB\log n)$。

问题在于，如何快速找到哪个数要单点修改，记 $b_i=\frac{i}{c_i}$。我最初的做法是每个块记录这个块 $u$ 所有 $b_i$ 每个具体质因子 $x$ 的和记为 $p_{u,x}$，修改时，先将 $c$ 拆成 $\log n$ 个区间乘质因子的操作，对于第 $i$ 个块乘质因子 $x$，则判断 $p_{i,x}$ 取值，若大于 $0$，则暴力修改块，反之则跳过。

最终的时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}\log V\right)$，空间复杂度为 $O(nB)$，大概取 $B=500$ 左右最快，只能在 LOJ 通过，常数太大了。

其实有一种更简单的区间找数操作，对于质数 $x$ 单独开一个 set，若 $b_i$ 有 $x$ 为质因子，则在 set 中插入 $i$。每次修改 $[l,r]$，直接暴力找 $[l,r]$ 里所有的数，每个数只修改 $c_i,b_i$，最后将有单点修改操作的块重构，注意维护此时的 set。

这样此时找数的时间复杂度也是可以均摊的，时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}+n\log^2n\right)$，此时 $B=\sqrt{\frac{n}{\log n}}$ 最优，大概在 $n=200\sim 300$ 的时候跑的比较快，且空间复杂度为 $O(n)$。已经可以通过 COGS 的测试了。

这个题，真简单吧。

大概是整张图的边集被划分成若干个边集，我们要选出最小若干个集合，使得剩下的边集组成的图中 $1,n$ 不联通。

显然是最小割，对于集合 $i$ 的边 $(u,v)$，我们连一条 $u\to i\to v$ 的边，表明若选择点 $i$ 割掉，则这条边就走不通了（实际上就是选择集合 $i$）。

显然割不掉点，所以把点拆成入点和出点，然后连 $S\to 1,n\to T$ 的边，除了入点出点边权设为 $1$，其他均设置成 $\infty$。

时间复杂度为 $O(m\sqrt{m})$，复杂度原理参考二分图最大匹配的网络流建模方法。

多想了很多东西。

不难发现分差不是很大，可以设 $f_{i,j}$ 表示当前进行了 $i$ 局，$s_A-s_B=j$ 的方案数。

可以从前往后转移，不难发现确定了 $i,j$ 就能确定两个人的得分，不让不合法的状态转移到别的状态即可。

时间复杂度 $O(Tn)$。

讲个笑话：交当年自己写的题解的代码，结果忘了自己当年习惯在题解代码里加反作弊了。

在此之前，我们要先知道异或运算是个什么东西：就是将两个二进制数的最低位对其，依次比较两个二进制数的每一位，如果相同，则得到的结果为 $0$，不同则为 $1$。

从定义可以推导出来的结论：对于任意 $x$，都有 $x\oplus x=0$，应为两个相同的数二进制上每一位都相同，所以结果一定为 $0$，同理可以推出 $x\oplus 0=x$。这里不多做叙述。（$\oplus$ 为异或的运算符号）

我们定义 $s_i=a_1\oplus a_2\oplus\dots\oplus a_i $。显然 $a_l\oplus a_{l+1}\oplus\dots\oplus a_r=s_r\oplus s_{l-1}$。基于的原理便是 $x\oplus x=0$。应为 $s_r,s_{l-1}$ 都包含 $s_{l-1}$ 这个部分，所以相抵消，只剩下 $[l,r]$ 这部分的异或和。

根据异或的定义，我们可以很方便的推出：如果 $a\oplus b=k$，那么 $a\oplus k=b,b\oplus k=a$。

结论部分讲解完毕，让我们回到题面，注意到是区间静态问题，不要求强制在线，显然可以用莫队乱搞。

我们在上文提到 $s_r\oplus s_{l-1}$ 即为 $[l,r]$ 区间的异或和。可以将问题转化为：每次给出区间 $[L,R]$，求出 $\sum\limits_{L-1\le i,j\le R}[s_i\oplus s_j=k]$。我们可以开一个桶 $cnt$，$cnt_{s_i}$ 为当前区间中，$s_i$ 的个数。当前区间异或和为 $k$ 的子区间数量为 $ans$。

如果有 $s_i\oplus s_j=k$，那么必然 $s_i\oplus k=s_j$。如果当前区间左右边界移动时，区间内多了一个 $s_i$，那么该区间内所有的 $s_j$ 与其的异或和是 $k$，区间内 $s_j$ 的数量为 $cnt_{s_j}$，所以对当前区间答案的贡献为 $cnt_{s_j}$。在将 $cnt_{s_i}+1$。我们就完成了区间的扩张。

已知 $s_i,k$，如何快速找到 $s_j$ 使得 $s_i\oplus s_j=k$。根据异或运算的性质 $s_j=s_i\oplus k$。

坑点大全：

1. 因为询问是区间 $[L,R]$，而处理时会将 $L-1$。所以会出现左边界为 $0$ 的情况。因此莫队中两个指针的初始位置都是 $0$.

2. 初始情况下，区间包含 $s_0=0$，所以 $cnt_0$ 初值为 $1$。

3. 当 $k=0$ 时，对于任何 $a$ 都有 $a\oplus 0=a$。因此在删除时，应当先对 $cnt$ 操作，再对答案 $ans$ 操作（我 WA 了好几次）。

4. 虽然 $a_i$ 小于 $10^5$，但如果 $a_1=100000,a_2=31071$，$s_2$ 有最大值为 $ 131071$。所以 $cnt$ 的大小一定要把控好（好像数据不卡这个）。

看到这个题的第一眼就气笑了，都 2026 年了，出题人企图让我在代码里用小数运算。

这给了我一个提示：说不定这个与众不同题其实就是要用一些与众不同的算法。

注意到分配最多摊位的社团与分配最少摊位的社团的摊位差不超过 $30$，因为对于任意 $i,j$，都有 $u_i\times 2^{30}>u_j$。

好的，我们先执行这样的操作若干轮：每次都给一个社团一个摊位，但需要保证 $m-n\ge 30n$。

什么，暴力模拟会 TLE，没事，我们模拟倍增的过程分配。

此时 $m$ 被缩小到 $31n$ 这个级别了，直接用堆模拟即可，时间复杂度 $O(n\log^2 V)$。

注意到 COGS 机子太垃圾被卡常了，只能把 $m$ 缩小到 $30n$ 这个级别了。

最劣解喜加一。