CF98E Help Shrek and Donkey
Codeforces 分析 首先可以发现，不到最后是不会选择猜的。 假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。 考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。 考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时，先手的获胜概率。 我们列一个表格，表示在先...
分类 题解 下的文章
- 首页
- 题解
CF468C Hack It!
Codeforces 分析 首先可以发现，当 $x<10^{18}$ 时有这样一个关系式 也就是说，当 $[l,r]$ 从 $[1,10^{18}]$ 变成 $[x+1,x+10^{18}]$ 时，$\sum_{i=l}^rf(i)$ 增加了 $x$ 。 设 $\sum_{i=1}^{10^{18}}f(i)=q$ ，显然一组合法的 $[l,r]$ 为 $[a-q+1,a-q+10^...
洛谷4249 [WC2007]剪刀石头布
Luogu 分析 首先三元环个数不是很好算，考虑用总数减去不是三元环的。 总数显然是 考虑三个点要怎样才不会构成三元环，可以发现有一个点的入度为 $2$ 即可。 进一步发现，如果 $u$ 的入度为 $d$ ，那么整张图会产生 $d\choose 2$ 个不是三元环的三元组。 考虑差分。对于一个点 $u$ ，如果它的入度增加了 $1$ 变成了 $deg$ ，那么整张图会减少 $deg-1$ ...
CF835E The penguin's game
Codeforces 分析 为了方便，下面把为 $y$ 的数称为特殊数。 首先我们可以通过一次询问得到某个集合内的特殊数的个数的奇偶性。 如果询问的集合大小是偶数，且特殊数的个数为偶数，那么返回值为 $0$ 。 如果询问的集合大小是偶数，且特殊数的个数为奇数，那么返回值为 $y$ 。 如果询问的集合大小是奇数，且特殊数的个数为偶数，那么返回值为 $x$ 。 如果询问的集合大小是奇数，且特...
洛谷4389 付公主的背包
Luogu 分析 考虑写出所有物品的生成函数 于是可以调和级数的处理出 $G(x)$，然后多项式 exp 即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #i...
洛谷3297 [SDOI2013]逃考
Luogu 分析 其实就是要求 Voronoi 图的对偶图最短路。 可以通过半平面交求出 Voronoi 图的每个区域，然后对于每条直线连边即可。 然后直接跑 BFS 就好了。 注意特判 $n = 0$。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.c...
洛谷5451 [THUPC2018]密码学第三次小作业
Luogu LOJ 分析 因为 $e_1\perp e_2$ ，所以会存在一对数 $s,t$ ，满足 $e_1s+e_2t=1$ 。 我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形： 于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ，所以可以直接 exgcd 求出 $s$ 和 $t$ 。 然而这里求出的 $s$ 和 $t$ 一正一负，为了方便我...
洛谷3343 [ZJOI2015]地震后的幻想乡
Luogu LOJ 分析 首先看到题目里的提示： 对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\cdots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 。 考虑一个暴力做法：枚举边权的相对大小，然后 Kruskal 求最小生成树并用这个提示算答案。 进一步考虑这样的一个做法：钦定一个边集 $S$ 作为前 $|S|$ 小的边，如果这个...
洛谷4495 [HAOI2018]奇怪的背包
Luogu LOJ 分析 先来考虑 $n=1$ 的情况，可以发现所有能取到的体积为 $k\cdot\gcd(v,P)$ 。于是我们可以直接把体积设成 $\gcd(v,P)$ 。 这样子所有体积都是 $P$ 的约数了。考虑预处理出 $P$ 的所有约数，然后求出每种约数在体积中的出现次数。 注意到一条性质：重复选取相同的体积对答案没有影响。于是假设第 $i$ 个约数有 $s_i$ 个，那么这个约...
CF662C Binary Table
Codeforces 分析 设 $S_i$ 表示第 $i$ 列的状态，$F_i$ 表示 $i$ 状态翻转或不翻转最少能有多少个 $1$ 。 首先考虑一个暴力：枚举翻转哪几行。那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^mF_{S_i\oplus X}\right\}$。 里面考虑枚举 $S_i\oplus X$，那么答案就是 $\displa...