主要是记一个结论

这样，维护区间修改 $\gcd$ 查询就非常方便

注意 $\gcd$ 的写法

1
2
3
4
5

ll gcd(ll x, ll y){
    return x && y
        ? gcd(y, x%y)
        : std::max(std::abs(x),std::abs(y));
}

给定长为 $n\le 2\times 10^5$ 的序列，你需要将其中 $k$ 个节点染色，满足 $m\le 10^5$ 组条件：$[l_i, r_i]$ 中有且仅有一个节点被染色。

最大化 $k$

题面，数据

「Link」

令左边房子为 $l_i, r_i$ ，正在考虑右边 $L,R$ 房子的答案

求出第一个 $i$ 满足 $r_i > L$

求出第一个 $j$ 满足 $l_j > R$

$j-i$ 即为贡献

因为不能向上走，所以可以一行一行考虑

$f_{i,j}$　表示从 $(i,j)$ 走到最后一行的期望步数，$f_{n,j}=0$

矩阵大概是这样的，需要优化求解

「Link」

首先观察炮的攻击范围，左右上下完全对称

也就是说，A 打不到 B 和 B 打不到 A 是等价的，于是就考虑左边和上面

一行一行地考虑，正在考虑第 $i$ 行

一行内部炮冲突的问题是容易解决的

「Link」

一道 trivial 的 DP

$w\times h$ 的纸张，每次能沿横或纵切一刀，最先切出 $1\times1$ 的人赢

$2\le w,h\le 200$

一行棋盘，若干个棋子，初始状态给出，每次可将棋子移到右侧第一个空格（棋子与空格不一定相邻 如：1101->1011/0111），不能移者输。

• 局面 $(x,y)~~~ x,y>0$
• 操作 $(x,y)\rightarrow(a,b)~~~a+b=x$ 或 $a+b=y$

$x,y\le 2\times 10^9$

先手必败还是必胜？

• 局面 $(x,y)~~~x,y\geq0$
• 操作 $(x,y)\rightarrow(x-\lambda y, y)~~(x-\lambda y,y\geq0)$
• $(x,0)$ 是败

给出 $(x,y)$ 求是否为先手必胜