ARC101F Robots and Exits
AtCoder 分析 我们先把所有只有只会从一个出口出去的机器人删掉，这些机器人不影响答案。 对于剩下的机器人，记它到左边第一个出口的距离为 $a$ ，到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$。 设 $x$ 为所有机器人往左移动的最远点到初始位置的距离，$y$ 为所有机器人往右移动的最远点到初始位置的距离。那么每次相当于把 $(x,y)$ 变成 $(x...
分类 题解 下的文章
- 首页
- 题解
ARC101E Ribbons on Tree
AtCoder 分析 设 $F(E)$ 表示 $E$ 中的边全部未被覆盖的方案数。 根据容斥原理可以得到 考虑怎么求 $F(E)$。可以这么考虑：把所有 $E$ 中的边去掉，那么每次选择的点对都要在同一个连通块内。假设剩下的连通块的大小为 $n_1,n_2,...,n_k$。 设 $G(n)$ 表示 $n$ 个点中两两一组的方案数。显然当 $n$ 为奇数时 $G(n)=0$，否则有 $G(...
洛谷5382 [THUPC2019]改善生活
Luogu LOJ 分析 首先有一个结论：存在一个最优解，满足小 Z 只引出了一个话题。 感性理解的话就是如果再引出一个话题的话相当于两个话题取了平均值，答案不会变得更优。 那么直接枚举引出了哪个话题，再直接计算就好了。 注意到题目中要传递闭包，$\mathcal{O}(n^3)$ 做法不够优秀，可以用 bitset 做到 $\mathcal{O}(\frac{n^3}{\omega})$ ...
洛谷5176 公约数
Luogu 分析 首先要知道一个性质 即可。可以发现就是 这个题 $k=2$ 时的版本，直接复制过来即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #incl...
CF1130E Wrong Answer
Codeforces 分析 我们直接令 $n = 2000$，并在前面放 $1998$ 个 $0$，然后设 $1999$ 项为 $-d$ ，$2000$ 项为 $x+d$ 。 那么正确答案是 $2000x$ ，Alice 算出来的答案是 $x+d$ ，两者的差为 $1999x-d$ 。 那么 $1999x-d=k\Rightarrow x=\frac{k+d}{1999}$ 。随便找一组满足...
洛谷4221 [WC2018]州区划分
Luogu LOJ 分析 每个集合是否合法很容易判，先把这个东西预处理出来，记为 $chk_S$ 。 设 $f_S$ 表示集合 $S$ 的答案，那么有： 子集卷积即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========...
洛谷5279 [ZJOI2019]麻将
Luogu LOJ 分析 首先我们并不需要整副牌，我们只需要每种牌的出现次数，也就是说只需要一个长度为 $n$ 的串。 考虑怎么判一副牌能不能和。可以去做一下这道题。 我们把第一维去掉，强制 $f$ 值不超过 $4$ 、雀头数不超过 $7$ ，这样子就会有大量重复状态。爆搜可以搜出本质不同的状态只有 $2091$ 种。 那么我们把所有状态预处理出来，然后预处理出对于每个状态追加 $x\...
洛谷5288 [HNOI2019]多边形
Luogu LOJ 分析 首先有一个结论：最终状态一定满足所有边都连向 $n$ 。那么步数就等于初始状态下不与 $n$ 相连的边数。 把所有初始与 $n$ 相连的边按另一个端点排序。那么对于排序后相邻的两个点 $l,r(l+1\neq r)$ ，一定会存在一条边 $(l,r)$ 。那么图中一定会存在一个点 $mid$ ，使得初始状态下存在两条边 $(l,mid)$ 和 $(mid,r)$ 。...
洛谷3348 [ZJOI2016]大森林
Luogu 分析 假设现在有一个 1 l r x 的操作。我们考虑一下第 $l-1$ 棵树和第 $l$ 棵树、第 $r$ 棵树和第 $r+1$ 棵树的区别。这里假设只有一个这 1 操作。 我们可以这么认为：第 $l$ 棵树是把第 $l-1$ 棵树上生长节点的子树移到第 $l$ 棵树的生长节点上得到的；第 $r+1$ 棵树是把第 $r$ 棵树上生长节点的子树移回去得到的。 那么如果我们可以快速...
洛谷3175 [HAOI2015]按位或
Luogu 分析 我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。 考虑 min-max 容斥 那么只需要求子集和，可以 FMT。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==...