AGC035C Skolem XOR Tree
AtCoder Luogu 分析 可以发现 $(2i)\oplus (2i+1)=1$，因此可以想到大致的构造方法：连 $(1,2i)$、$(1,2i+1)$、$(2i+1+n,2i)$、$(2i+n,2i+1)$。这样子就满足了 $2i$ 和 $2i+1$。 然而有一些问题。一个问题是 $1$ 如何处理。可以仿照样例，使 $2$ 和 $3$ 不按上面的方式连边，而是连 $(1,2)$、$(...
分类 题解 下的文章
- 首页
- 题解
ARC103D Robot Arms
AtCoder Luogu 分析 首先，如果存在 $i,j$ 满足 $|x_i+y_i|$ 与 $|x_j+y_j|$ 的奇偶性不同，则无解。因为走到 $(x,y)$ 的步数一定与 $|x_i+y_i|$ 的奇偶性相同。 先考虑 $|x_i+y_i|$ 全部为奇数的情况。 先考虑步长的问题。可以利用二进制进行构造，即令步长为 $2^0,2^1,\cdots$。容易发现最大只需要到 $2^{3...
51nod1850 抽卡大赛
51nod 分析 首先考虑一个暴力做法。 假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。 枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移 这...
BZOJ3218 a + b Problem
BZOJ 分析 容易看出最小割。考虑连边： 对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。 对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。 考虑正确性...
CF505E Mr. Kitayuta vs. Bamboos
Codeforces Luogu 分析 二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。 由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。 考虑贪心，...
51nod1667 概率好题
51nod 分析 甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。 设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当 则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。 考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^...
CF115E Linear Kingdom Races
Codeforces Luogu 分析 考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移 这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。 考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i...
CF547E Mike and Friends
Codeforces Luogu 分析 考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。 将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。 代码 // =================================== /...
洛谷4518 [JSOI2018]绝地反击
Luogu LOJ 分析 设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。 考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。 这样子可能过不了，考虑一些优化。我们预...
洛谷4631 [APIO2018]Circle selection 选圆圈
Luogu LOJ 分析 暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。 考虑用 KD-Tree 优化模拟过程。 我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。 然后建树时按方差选维度就可以过了。 代码 // =================================== // ...