高度由习惯堆积

2019年4月

ZJOI2017 树状数组

题目loj题目链接思路研究代码发现,她的树状数组实际上询问的是$[l-1,r-1]$的抑或和,所以题目的询问实际上就可以转化为$l-1$上的元素与$r$上的元素相同的概率。一开始想的是,线段树维护每一个元素是$1$的概率是多少,然后进行数学运算,得到答案,然后发现,两点之间的概率不是相互独立的。比如说修改了$[l,r]$的区间,那么如果这次修改的结果是$l$,那么$r$在此次收到的影响就必然...
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]\ ...