高度由习惯堆积

POI2001 跳舞蝇的教练

题目Byteland一直以奇妙的跳舞蝇而闻名于世。驯养的苍蝇能和着音乐的节奏精确地做每一次飞跃。通常,训练者会在桌上放一排硬币,这些硬币的排列并不按照特定的顺序。每枚硬币上都有一行题字:i→j,i是这枚硬币的编号,j是站在硬币i上的苍蝇下一步应该飞往的硬币编号。训练者在每个硬币上放一只苍蝇,然后开始放音乐。那些苍蝇就跟着音乐的节拍开始跳舞,在每一拍中苍蝇都会直接跳到编号为j的硬币上。在舞蹈中...

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$...