这种找可行解的问题套路还是比较多的。 Description A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $...
ZJOI 2019 Day2 游不动记
Day 1 在余姚中学待了一周多,还没去看过五楼报告厅。报告厅还是比较宽敞的,还有 LED 屏幕。 上午是 zzy 讲《树上分治算法》,分别讲了边分、点分和全局平衡二叉树。讲的很快,例题引入比较跳跃于是成功在开场...
2019.4 余姚中学 被吊打记
$\TeX$ 版游记 (不好意思标题有点不恰当别人貌似不屑于吊打我) Day -1 第一次坐软卧,感觉空间宽敞,设施也比较新。当然是多交钱了的 Day 0 早上 8 点到了余姚站,坐了十几分钟公交车到宾馆。误判了地图的...
bzoj 4176 Lucas的数论 题解【莫比乌斯反演】【杜教筛】
怎么又有我不知道的东西啊..自闭了 Description 去年的 Lucas 非常喜欢数论题,但是一年以后的 Lucas 却不那么喜欢了。 在整理以前的试题时,发现了这样一道题目“求 $\sum f(i)$,其中 $1\le i\le ...
洛谷 P3327 [SDOI2015]约数个数和 题解【莫比乌斯反演】【前缀和】【质因数分解】
有个引理。希望以后这种东西还是能自己推出来 题目描述 设 $d(x)$ 表示 $x$ 的约数个数,给定 $N,M$,求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$。 输入输出格式 输入格式: 输入文件包含多组...
杜教筛瞎推 学习笔记【杜教筛】【数学】
〇、前言 对于 bzoj3944 来说,和莫比乌斯反演等其他知识关系不大,但是 $\mu$ 函数在自变量较大情况下的前缀和在反演题中也是会被用到的。 接下来通过 bzoj3944 Sum 一题引入杜教筛的思想。 参考资料 铃悬...
HBTS(HBOI) 2019 真实退役记
Day 0 早上迷迷糊糊醒了不知道多久,反正差不多的时间被叫醒了,然后走去了火车站。 这次终于取到了蓝色的车票,以前去武汉的车票都取的红色不知道为什么…… 在火车上看了《悲伤逆流成河》,稍微有点悲情,还...
洛谷 P3825 [NOI2017] 游戏 题解【2-SAT】【枚举】
复习一下 2-SAT,感觉核心还是记住了的。 题目背景 狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是,小 L 在玩游戏之余,还精于研究游戏的设计,因此他有着与众不同的游戏策略。 题目描述 ...
洛谷 P3181 [HAOI2016]找相同字符 题解【SAM】【前缀和】
SAM 挺神奇的,就是不会.. 题目描述 给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。 输入格式 两行,两个...
bzoj 1597 [Usaco2008 Mar] 土地购买 题解【斜率优化】【DP】【贪心】
比较考思维的一道斜率优化。 Description 农夫 John 准备扩大他的农场,他正在考虑 $N (1\le N\le 50\ 000)$ 块长方形的土地。每块土地的长宽满足 $(1\le$ 宽 $\le 1\ 000\ 000, 1\le$ 长 $\le 1\ 000\ ...