高度由习惯堆积

分类 OJ:LOJ 下的文章

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

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有一个显然的贪心,对于一段区间,先扫描前缀,遇到不合法的点就删掉,再扫描后缀,把不合法的点删掉,这...