高度由习惯堆积

分类 OJ:HDU 下的文章

March 26, 2019

HDU1890 Robotic Sort

题目题目大意是让你找在一个区间内找一个最小权值的点,让它通过旋转的方式换到最前面。思路注意Splay的性质:中序遍历不变。所以这里就可以把Splay看作一个超级数组,而不是通常定义的二叉查找树(左边的子树权值都小于它,右边的子树权值都大于它)。然后它就可以通过打标记的方式实现区间的翻转操作。具体方法是:如果要对一段区间进行操作的话,只要:int L=find(l-1),R=find(r+1)...

HDU6061 RXD and functions

题目题目链接思路显然可以发现,那些a其实和最终的结果没有关系,我们关心的仅仅是所有a的总和,设这个和为$a$。也就是说$g(x)=f(x-a)$通过二项式定理展开得:$\sum_{i=0}^{n}c_i \sum_{j=0}^{i} \binom{i}{j} (-a)^{i-j}x^{j}$因为要求的是$x^j$的系数,所以整理一下,把$j$写在前面。$$ \sum_{j=0}^{n}\su...

HDU6155 Subsequence Count

题目给出一个长度为n的01串S,有Q个操作:1.翻转区间[l,r](0变1,1变0)2.求区间[l,r]有多少不同的子串思路这是一道好题,首先考虑没有修改操作的dp状态,则$dp[i][j]$表示到了第$i$个位置,结尾为$j$的串的方案数则我们可以得到以下递推关系:$$ dp[i][j]=dp[i-1][0]+dp[i-1][1]+1,j==S[i]\\ dp[i][!j]=dp[i-1]...