test20200116
闲扯我怎么又被卡常了呀！ $map$ 常数是真的垃圾。。。
$T1$Solution我们将所有点按照 $x$ 为第一关键字， $y$ 为第二关键字的顺序排序，然后我们可以发现一个奥妙重重的事：若 $a,b$ 匹配， $p,q$ 匹配，且满足 $aq$ 。
我们枚举第一对匹配的点为 $a,b$ ，显然
...
test20200115
发表于
闲扯终于有一道考试能想出做法而且不会打炸的题了泪目。
$T1$Solution由于要使得距离最大，我们考虑贪心的进行匹配。
假设对边 $(u,v)$ 来说，它的一边有 $j$ 个男生，有 $k$ 个女生，那么我们一定有 $\min(j,m-k)$ 个男生和另外一边的女生配对，有 $\min(k,m-
...
Atcoder Beginner Contest 150
发表于
$A,B,C$签到题，随便做做。
$D$将每一个数里面的 $2$ 全部提出来，其个数即为 $w_i$ ，如果 $w$ 不是所有数都相等，那么无解。
否则求出所有数的 $lcm$ ，再乘上 $2^{w_i-1}$ ，剩下的一个 $2$ 放入 $(p+0.5)$ 中，可以看出这一定是个奇数。
答案就是
...
「SHOI2017」组合数问题
发表于
闲扯矩阵乘法练习题。
题面「SHOI2017」组合数问题
Solution问题是求 $\sum_{i=0}^{\infty}\binom{nk}{ik+r}$ 。
可以发现 $ik+r\equiv r\ (mod\ k)$ ，所以问题等价于求从 $nk$ 个物品中选择 $m$ 个物品的方案数，其中
...
2020WC集训训练赛day5
发表于
闲扯暴力场 $+\ FST$ 场。
题面2020WC集训训练赛day5
$T1$结论题，可以证明答案一定在最大的 $\log_2 x+2$ 个之间取到，然后直接暴力即可。
证明参考 $JKLover$ 的 博客。
code
$T2$我们考虑当代价为 $\prod_{i=1}^N\binom{x_i}
...
P4342 [IOI1998]Polygon
发表于
闲扯这算是区间 $dp$ 的经典题？
题面P4342 [IOI1998]Polygon
Solution简单的想法是每次枚举拆掉那条边，然后做一次区间 $dp$ ，时间复杂度为 $O(n^4)$ ，没法通过本题。
这类环形的，我们有一个经典的处理方式：将数组复制一遍放在后面，然后按照一般的做。
我们
...
5105 Cookies
发表于
闲扯学到了， $dp$ 原来还有这种骚操作，是我以前太菜了。。
题面5105 Cookies
Solution我们设 $dp_{i,j}$ 表示考虑前 $i$ 个人，分出去了 $j$ 个饼干时的最小怨气总和。
首先，我们明确一个事实：贪婪度大的孩子应该拿到更多的糖果。这很容易通过邻项交换证明。
但是
...