by hl666:

奇思妙想题

首先考虑如果区间内存在某个质数P，则对于两个数x,y，除非w(x)=w(LCM(x,y))（即x对应的质因子集合为y对应的质因子集合的子集），否则不如用w(x)+1的代价直接把x和P连起来

因此现在的做法就很显然了，先把所有质因子集合有包含关系的点连起来，最后把每个连通块和P

连起来即可

有一种比较好的处理方法是，对于某个数x，我们令g(x)为它的质因数集合中所有数的乘积（由于有去重，因此g(12)=2×3=6;g(27)=3）

此时x对应的质因子集合为y对应的质因子集合的子集等价于g(x)是g(y)的约数，那么直接在上面跑一个调和级数的枚举即可

令M=∑ri，总复杂度O(MlogM)

但如果区间内没有质数怎么办呢，不难发现这样的区间长度一定不会很长，我们可以直接暴力跑生成树

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<utility>

#define RI register int

#define CI const int&

using namespace std;

typedef pair <int,int> pi;

const int N=1e6+5;

struct edge

{

int x,y,w;

inline edge(CI X=0,CI Y=0,CI W=0)

{

x=X; y=Y; w=W;

}

friend inline bool operator < (const edge& A,const edge& B)

{

return A.w<B.w;

}

}; int t,l,r,w[N],g[N],vis[N],sz[N],is_prime[N],fa[N];

inline void init(CI n)

{

RI i,j; for (i=1;i<=n;++i) g[i]=1;

for (i=2;i<=n;++i) if (!w[i])

{

is_prime[i]=1; g[i]=i; w[i]=1;

for (j=i*2;j<=n;j+=i) ++w[j],g[j]=g[j]*i;

}

}

inline int getfa(CI x)

{

return fa[x]!=x?fa[x]=getfa(fa[x]):x;

}

int main()

{

for (scanf("%d",&t),init(1e6);t;--t)

{

RI i,j; scanf("%d%d",&l,&r); int ans=0;

if (l==1)

{

for (i=2;i<=r;++i) ans+=w[i];

printf("%d\n",ans); continue;

}

bool has_prime=0;

for (i=l;i<=r;++i) if (is_prime[i]) has_prime=1;

if (has_prime)

{

for (i=1;i<=r;++i) sz[i]=vis[i]=0;

for (i=l;i<=r;++i) ++sz[g[i]];

for (i=2;i<=r;++i) if (!vis[i]&&sz[i])

{

ans+=w[i]*(sz[i]-1)+(w[i]+1); vis[i]=1;

for (j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])

vis[j]=1,ans+=w[j]*sz[j];

}

printf("%d\n",ans-2);

} else

{

vector <edge> E; for (i=l;i<=r;++i) fa[i]=i;

for (i=l;i<=r;++i) for (j=l;j<=r;++j)

E.push_back(edge(i,j,w[i]+w[j]-w[__gcd(i,j)]));

sort(E.begin(),E.end());

for (auto [x,y,w]:E)

{

if (getfa(x)==getfa(y)) continue;

ans+=w; fa[getfa(x)]=getfa(y);

}

printf("%d\n",ans);

}

}

return 0;

}

出征

P16689 出征 - 洛谷

给出一个序列 $a_i$，和常数 $p$，你可以进行若干次操作，每次操作可以选择一个 $j$，使得 $i \in [j, n]$ 的后缀中，统一增加或减少 $\binom{i - j + p}{p}$。问至少多少次操作之后才能将序列全化为 $k$。

$1 \le n \le 10 ^ 5, 0 \le p \le 80, 0 \le k, a_i \le 10 ^ 6$。

对于这个题，还是很神奇的，实际上不是计数题。

我们可以先观察特殊性质，发现 $p = 0$ 的时候，就是选一个后缀，使得这个后缀统一增加或者减少 $1$，那这个我们是怎么做的呢，我们显然是可以从前往后判断，逐个满足每一个的要求，我们写暴力的时候发现，其实如果你在 $j$ 点进行了一次操作，其实不是很影响这个序列，不需要修改，只需要打上一个标记，后面的标记推下去计算即可。

于是我们就想到，是否操作只和单点有关，我们发现对于 $p = 0$ 的时候，我们将这个增加的贡献表达出来就是 $f(j) = [0, 0, 0, \dots, 1 ,1 ,1 , \dots]$，对于这个增加的贡献，我们可以对其做一次差分，得到的差分序列 $\Delta ^1 f(j) = [0, 0 ,0 ,\dots 1, 0, 0, \dots]$，发现进行一次差分之后，就变成与 $j$ 点相关的单点修改操作了。

具体的来说，我们每一次对选择的 $j$，后缀的增加或减少都是呈现 $f(j) = [0, 0, 0, \dots, \binom{p}{p}, \binom{p + 1}{p} , \binom{p + 2}{p} , \dots]$，这样的增加贡献，我们再考虑刚刚的差分操作，也就是，第一个位置不变，为 $\binom{p}{p}$，第二个位置是 $\binom{p + 1}{p} - \binom{p}{p} = p = \binom{p}{p - 1}$。这个部分实际上还可以用帕斯卡三角直接转化，因为 $\binom{p + 1}{p} = \binom{p}{p} + \binom{p}{p - 1}$，因此，移项就能得到。后面的同理，我们发现实际上一次差分会使得上下指标减 $1$，对于第一项，我们就可以把 $\binom{p}{p}$ 写成 $\binom{p - 1}{p - 1}$。我们可以写出通用式子的一阶差分 $\Delta^1 f(j) = [0, 0, 0, \dots, \binom{p - 1}{p - 1}, \binom{p}{p - 1}, \binom{p + 1}{p - 1}, \dots]$。很明显这个式子还能继续做差分，我们想要的是把这个变成单点的修改操作，这样就和 $p = 0$ 做一阶差分时的统计方式是一样的。

我们考虑只有经过 $p$ 轮，这样组合数选的就是 $0$，也就是又变回了我们的最初的 $p = 0$ 的情况，我们只需要再做一轮差分，就能得到最终我们想要的单点的修改贡献，即：

$$ \Delta ^ {p + 1} f(j) = [0, 0, 0, \dots, 1, 0, 0, \dots] $$

这样的式子，我们就可以清晰的看到具体哪个地方进行了操作。

因此我们的最终做法是，先把原数组 $a_i \gets k - a_i$，这样只需要判断到 $0$ 即可，对 $a_i$ 做 $p + 1$ 次差分，最后答案就是 $\sum |a_i|$。

为什么要开 int128 ？

我们考虑差分操作，对于 $\Delta ^ 1 a_i = 1\times a_i - 1\times a_{i - 1}$，对于 $\Delta ^ 2 a_i = 1 \times a_i - 1 \times a_{i - 1} - (1 \times a_{i - 1} - 1 \times a_{i - 2}) = 1 \times a_i - 2\times a_{i - 1} + 1\times a_{i - 2}$。

重复这个过程，我们发现其形态类似于二叉结构，每一个 $a_i$ 在做贡献时，都会在自己和前面的位置做一次贡献，这实际上就是帕斯卡三角的系数问题。

因此对于连续的 $p + 1$ 次，我们 $a_{i - j}$ 的贡献系数就是 $(-1) ^ j \binom{p + 1}{j}$，对于最坏的情况，我们把所有绝对值加起来，即 $\sum \binom{p + 1}{j} = 2 ^ {p + 1}$，因此对于 $2 ^ {81}$ 可以证明 int128 是可以存下的。

题目大意

就是说现在有序列 $a_1,a_2,a_3,...,a_n$ ，我们每一次操作可以选择一个位置 $i$ ，将 $i$ 这个后缀加或减一些数（如题）。然后我们要求出将序列变成 $k,k,k,k...$的最小操作数。

解题思路

我们先将给出的数组都减去 $k$ 得到一个“需求数组” $c_1,c_2,c_3,..,c_n$，我们的任务就是通过加减填满所有“需求”。但是我们暴力加的话是 $O(n^2)$ 的。

（我原本试图将 $ C_{i - j + p}^{p} $ 拆成 $i,j$ 独立的式子,但失败了。）

先说一个结论：

有两个序列 $A = a_1,a_2,a_3,...$ 和 $B = b_1,b_2,b_3,...$， $A + B$ 的差分序列 $= A$ 的差分序列 $+ B$ 的差分序列。即 $a_i + b_i - a_{i-1} - b_{i-1} = (a_i - a_{i-1}) + (b_i - b_{i-1})$

就是说我们将 ${c_1,c_2,c_3...}$ 和 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 都差分再用后者将前者全补成 $0$ 等价于原问题。

有

$$C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n - 1}^{m}$$

在 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 中 $C_{p}^{p} = C_{p - 1}^{p - 1} = 1$,$C_{p + i}^{p} - C_{p + i - 1}^{p} = C_{p + i - 1}^{p - 1}$。也就是说对序列的一次差分就是将上下标都减1。

于是我们只要进行 $p$ 次差分就能将原序列变为 $1,1,1,1...$。$p + 1$ 次差分即为 $1,0,0,0,...$

所以我们将 $c$ 数组也进行 $p + 1$ 次差分,随后答案就是 $ans = \sum_{i = 1}^{n} | c_i |$

【PA 2020】Miny

P9100 [PA 2020] Miny - 洛谷

给出每一个炸弹 $i$ 的位置 $a_i$ 和爆炸半径 $r_i$，每次爆炸都会使得 $[a_i - r_i, a_i + r_i]$ 范围内的炸弹爆炸，发生连锁反应。起爆的炸弹集合不定，问你最终的局面的方案数。

$1 \le n \le 3 \times 10 ^ 5, 0 \le a_i, r_i \le 10 ^ {18}$。

我们考虑 dp 的转移。

发现其实我们并不能得到一个很好的没有后效性的东西。

我们不妨发挥人类智慧，设计一个好的的 dp 状态。

我们设 $dp_i$ 表示，前 $i$ 个炸弹，以 $i$ 结尾，且钦定 $i$ 不爆炸的方案数。那么我们枚举 $j < i$ 进行转移，当且仅当 $[j + 1, i -1]$ 这部分的炸弹爆炸不会波及到 $i$ 和 $j$ 这样才能满足我们设定的不爆炸的钦定。 为了更好的判断是否波及，我们设 $L_i$ 表示左边能引爆 $i$ 的最大的炸弹，$R_i$ 表示右边能引爆 $i$ 的最小的炸弹。换言之就是最近且能引爆 $i$ 的。 这个过程我们可以用单调栈维护，我们可以通过单调栈，扫描两次，第一次求 $L$，第二次求 $R$，那么由于随着下标的增长，$a_i$ 是不断增加的，我们要想知道 $i$ 左边的第一个能引爆 $i$ 的，我们需要在单调栈中维护能覆盖 $a_i$ 的，最大的下标。若是当前的栈顶无法满足，就弹出，找前面的是否有能满足的。 对于这样的操作，我们再从后往前扫一次即可得到 $R$。

那么我们的 dp 可以转化为：

$$ dp_i = \min_{j < i \text{ and } (L_i \le j) \text{ and } (R_j \ge i)}(dp_i = dp_j + dp_i) $$

对于这个操作实际上是 $n ^ 2$ 的，我们考虑优化。

我们不难发现，满足条件 $L_i \le j$ 的序列，实际上下标直接就可以从 $L_i$ 开始一直到 $i$。

换言之，我们答案就是 $j \in [L_i, i - 1] \text{ and } R_j \ge i$ 的 $\sum dp_j$。

对于这样的询问，我们难免会想到在处理完当前的 $i$ 之后，把 $dp_i$ 插入到树状数组中，然后问 $[L_i, i - 1]$ 的时候，直接用树状数组做前缀和差分即可。

但是问题就在于，我们在询问 $L$ 的时候，插入的 $dp_i$ 实际上是只有 $[0, L]$ 的部分的 $R_j \ge i$ 的部分，可是留到最后算是会出问题的。

这个时候就可以用两种方式解决这个问题。

第一种方式是主席树，我们考虑把不同版本存下来，问 dp 的时候，只需要找到 $L_i - 1$ 的版本和 $i - 1$ 的版本即可。

第二种方式，我们把需要用到的询问离线下来，每次做完当前 $i$ 的操作之后，把挂在 $i$ 上的询问的答案都计算出来。

时间复杂度 $\mathcal{O}(n \log n)$。

【JOI 2017 Final】足球 / Soccer

P5100 [JOI 2017 Final] 足球 / Soccer - 洛谷

在二维网格球场上有 $N$ 名球员，求通过球员移动/运球（每步疲劳度为 $C$）以及踢球（踢出距离 $p$ 疲劳度为 $A \times p + B$）相互配合，将足球从 $1$ 号球员处转移到 $N$ 号球员初始位置所需的最小总疲劳度。

$1 \le W, H \le 505, 1 \le A, B, C \le 10 ^ 9, 1\le n \le 10 ^ 5$。

我们考虑到球的状态，球要么是被人带着，要么是在被踢的状态。

考虑拆点做分层图或者拆状态。

我采用的方式是拆状态。

我们设 $d_{x, y, st}$ 表示在 $(x, y)$ 这个位置，状态是 $st$ 的最小花费。

这里我们设 $5$ 种状态，由于被踢的状态是特殊的，我们单独处理。因为被踢的时候只能沿着本方向一直走。我们定义 $\{ 0, 1, 2, 3, 4\}$ 分别表示被踢的时候，上下左右，和被带的时候，分别在最短路的时候转移。

但是被踢转换到被带的时候，需要找到最近的球员进行接球，这个过程需要预处理每一个格子最近的球员，可以用多源的 BFS 完成这个预处理。

时间复杂度 $\mathcal{O}(HW \log (HW))$。

【ARC215A】Zombie

AT_arc215_a [ARC215A] Zombie - 洛谷

给出 $n$ 个僵尸的位置，在一个长为 $L$ 的数轴上，你需要放 $k$ 块脑子，每个僵尸每秒都会向脑子方向移动 $1$，问脑子存在的最长时间和。

$1 \le n \le 2 \times 10 ^ 5, 1 \le k \le 10 ^ 9, 1 \le a_i \le 10 ^ 9, 1\le L \le 10 ^ 9$。

其中，所有僵尸的位置均为偶数。

我们考虑贪心的策略，其中，对于贪心策略来讲，无非就是选择中间或者两边。

我们将中间的区间按大小排序，枚举选多少个区间，直接预处理前缀和，或者枚举的时候累计，最后 $\mathcal{O}(1)$ 计算剩余的脑子放在两边的方案数。

时间复杂度 $\mathcal{O}(n \log n)$。