博文

目前显示的是 九月, 2020的博文

二次剩余

BZOJ2654 【tree】题解

HIHO1236 【Scores】题解

对于每个成绩,求出所有满足条件的人的编号,bitset合并即可 由于空间不够,所以要分一下块

HIHO1145 【幻想乡的日常】题解

因为这些点在树上,因此区间数等于点数-边数离线下来按照r排序树状数组维护l即可

BZOJ2143 【飞飞侠】题解

对于这种一个点连出去的每条边权值都相等的图的最短路,我们可以考虑使用并查集优化。

BZOJ3103 【Palindromic Equivalence】题解

BZOJ3707 【圈地】题解

BZOJ2288 【[POJ Challenge]生日礼物】题解

圆的反演

oi-wiki讲的挺好: https://oi-wiki.org/geometry/inverse/

洛谷 P4049 【[JSOI2007]合金】题解

显然第三位是废的根据高一数学,一个向量能被xa+yb表示当且仅当在这个向量在ab的连线上

SP839 【OPTM - Optimal Marks】

异或的各位互不相干,所以分开对每一位数考虑这道题可以转化为两个点集,题中的每条边相当于在点之前连一条流量为1的边,而将所有点分为两个点集也就需要把部分边拆掉,所以跑最小割即可

洛谷 P2569 【[SCOI2010]股票交易】题解

瞎推推状态转移就出来了https://www.luogu.com.cn/blog/Sooke/solution-p2569

洛谷 P3294 【[SCOI2016]背单词】题解

显然情况1灰常不优,3就是2的特殊情况所以只考虑2

洛谷 P2512 【[HAOI2011]防线修建】题解

挺裸的动态凸包离线下来倒着处理把删除变成插入即可

洛谷 P5479 【 [BJOI2015]隐身术】题解

洛谷 P5618 【[SDOI2015]道路修建】题解

洛谷 P3468 【[APIO2014]序列分割】

答案与切的顺序无关显然斜率优化

POJ2411 【Mondriaan's Dream】题解