高度由习惯堆积

分类 OI题解 下的文章

April 19, 2019

HNOI2014 江南乐

题目LOJ链接思路首先认识到:对于好几堆石子来说,它们总的SG值等于每一个石子的SG值的亦或和。证明:参见: 浅谈算法——博弈论(从零开始的博弈论)对于每一个需要求SG值的$x$首先考虑70分的暴力写法:可以直接暴力求SGvoid GetSG(int n,int f){ for(int i=f;i<=n;i++){ memset(mark,0,sizeof(ma...

NOI2014 购票

各位dalao的解法都好神啊。。。这里给一种点分治的解法。题目链接思路首先斜率部分。转移方程:$ans[x]=min(-dis[u]*p[x]+ans[u])+dis[x]*p[x]+q[x]$发现结果只与$min()$框内的部分有关,观察这个形式,发现是个一次函数,也就是说可以斜率优化。dalao们对于推斜率式子这部分表示很不屑,但是我太菜了,所以还是写一下吧。令$p=p[x]$,当$u$...

BZOJ2759 一个动态树好题

题目有$N$个未知数$x[1..n]$和$N$个等式组成的同余方程组:$x[i]=k[i]*x[p[i]]+b[i] mod 10007$其中,$k[i],b[i],x[i]∈[0,10007)∩Z$你要应付$Q$个事务,每个是两种情况之一:一.询问当前$x[a]$的解$A\ a$无解输出-1$x[a]$有多解输出-2否则输出$x[a]$二.修改一个等式$C\ a\ k[a]\ p[a]\ ...

JOISC2014 历史研究

题目IOI 国历史研究的大牛——JOI 教授,最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活,开始着手调查日记中记载的事件。日记中记录了连续 $N$ 天发生的事件,每天发生一件事件。事件有种类之分。第$i$天发生的事件的种类用一个整数$X_i$表示,$X_i​$​越大,事件的规模就越大。JOI 教授决定用如下的方法分析这些日记...

LOJ2710 election

题目有一个长度为$N$的字符串$S[1…N]$,它仅由C和T两种字母组成。现在有$Q$个查询,每个查询包含两个整数$L$和$R$,表示:设新字符串 $S'=S[L…R]$,至少在$S'$中要删除多少个字符,才能保证:对于$S'$的每一个前缀与每一个后缀,其C的数量都不小于T的数量。思路28pts有一个显然的贪心,对于一段区间,先扫描前缀,遇到不合法的点就删掉,再扫描后缀,把不合法的点删掉,这...