LOJ #6077「2017 山东一轮集训 Day7」逆序对

题目链接

还是反序表那套理论,弱化版有 $O(nK)$ 的做法

根据 $\sum x_i=K$ 的容斥计数,需要求得是 $f_{i,j}$ 表示从 $1\sim n$ 中选出 $i$ 个数,和为 $j$ 的方案数

其中 $i$ 的上界 是$O(\sqrt K)$,旋转体积背包 $O(K\sqrt K)$

注意背包时,数字互不相同,且最大的数不能超过 $n$,需要减去一项。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namesp[......]

Read more

OI生涯主要游记搬运

我已经不是一个OIer了,也许即将成为一个ACMer,但是这些记忆会永远记在心中。

我是manchery,曾经是一个OI选手。

从原博客整理搬运了OI主要写过的游记,还是有很多比赛自己懒或者打的不好就没写了,不过写出来的这些已经够珍贵了。

THUSC 2016 游记

  • 从前的从前

    在老叶的号召下,把pkusc thusc都报了 但是pku不要我 学校其他人都被祝学习进步了

    又可以逃课啦 心里小小的自豪

  • day0

    和老叶坐了几乎整个白天的火车

    早上看了Po姐的JOI的题 质量不错 都是可做的 但是电脑是在电池弱 就没在火车上码 //其实是懒

    下午和老叶看了pku的题 暴力搜索那[……]

Read more