CF24D Broken robot
CodeForces Luogu 分析 设 $f_{i, j}$ 表示 $(i,j)$ 到最后一排的移动步数的期望。显然有转移 对于每行，列与列之间的转移有后效性，高斯消元即可。但是这是一个 band-matrix，所以可以 $\mathcal{O}(m)$ 消元。 注意特判$m=1$的情况。 代码 #include <bits/stdc++.h> #define re reg...
CodeForces Luogu 分析 设 $f_{i, j}$ 表示 $(i,j)$ 到最后一排的移动步数的期望。显然有转移 对于每行，列与列之间的转移有后效性，高斯消元即可。但是这是一个 band-matrix，所以可以 $\mathcal{O}(m)$ 消元。 注意特判$m=1$的情况。 代码 #include <bits/stdc++.h> #define re reg...
Luogu 分析 可以发现，在一个点双联通分量中，设割点的数目为 $s_1$，非割点的数目为 $s_2$，那么： 若 $s_1=0$，即没有割点，那么要有两个出口才能保证能出去。此时出口可以放在任意两个非割点上。 若 $s_1=1$，即只有一个割点，那么如果割点坍塌就都出不去了，所以要放一个出口。此时出口可以放在任意一个非割点上。注意到这里若非割点坍塌，其它点可以通过割点离开到其它分量去。...
Luogu 分析 题意即维护一个数列，支持区间开平方（取下整）和区间求和。 容易发现，对于最大的数据 $10^{12}$，开 $6$ 次方即可得到 $1$，之后再开方就不会变。 那么对于线段树的每个节点维护一个标记，表示该节点对应的区间是否全为 $1$ 或 $0$。 修改时如果修改到一个满足条件的区间，则不用修改；否则往下递归修改直到到达叶节点或者满足条件的节点。这样子复杂度是对的。 注意可...
Luogu 分析 由熟知结论，邻接矩阵的 $k$ 次幂中 $(u, v)$ 上的数表示 $u\to v$ 恰好走 $k$ 步的方案数。 然而本题有一个不动和自爆的问题。 不动的话，相当于走自环；自爆的话，减一个 $0$ 号节点，$0 \sim n$ 都向 $0$ 连一条边即可。这样子保证了自爆后就没有后继了。 代码 #include <bits/stdc++.h> #define...
Luogu 分析 将方程左边通分 代码 #include <bits/stdc++.h> #define re register typedef int mainint; #define int long long using namespace std; const int MOD=1e9+7; inline int read() { int X=0,w=1; c...
Luogu 分析 设 $f_{i, j}$ 表示还剩 $i$ 个人时第 $j$ 个人的获胜概率。 考虑转移。首先枚举庄家抽到的卡牌 $k$，从而得到这一轮被淘汰的人的位置 $c$。 如果 $c \neq j$，则无法转移。否则第 $c$ 个人被淘汰之后，剩下的 $i-1$ 个人要组成一个新的环，庄家为第 $c$ 个人的下一个。容易算出，当 $c > j$ 时，第 $j$ 个人是新的环里...
Luogu 分析 首先我们是没有必要每次给所有蚯蚓加 $q$ 的，只需要维护一个变量 add 表示所有蚯蚓长了多少即可。 那么一个显然的想法是用一个大根堆维护所有蚯蚓，然后直接模拟一下就好了。这样子就有 $85$ 分了。 注意到每次分出去的蚯蚓一定会成为最短的两条蚯蚓（想一想，为什么？），那么只需要开三个队列维护就好了。 注意一下输入进来的长度没有排好序，自己要排一下。 代码 #inclu...