高度由习惯堆积

分类 OJ:Codeforces 下的文章

CF1143F U2

题目题目链接大意是:给你若干个点的坐标,点对之间画一条形如$f(x)=x^2+bx+c$的抛物线,问抛物线内最多的点有多少个。思路一道思维好题。首先抛物线上自然没有什么性质可供挖掘,所以考虑转化为直线。注意到$x^2$的系数是$1$,所以原式可化为$y-x^2=bx+c$这样的直线形式,于是点对之间就以直线的形式组合(坐标变为$(y-x^2,x)$)。于是原来的条件就转化为了不在直线上方的点...

CF587C Duff in the Army(树上倍增 树链剖分)

题目有n个城市,由n-1条边连接。两个城市之间的道路是唯一的。 有m个人,住在这n个城市中,现在给出m个人,生活的城市编号。 你需要回答,从一个城市u到另一个城市v的路径中,编号前a小的人的编号是哪些?思路1(树上倍增)树上倍增,可以开一个$num[i][j]$,表示i这个点向前跳$2^j-1$格后到达的点,这样,对于两个点而言,就可以向上跳跃,直到交汇为止,答案则是归并后的ans数组。此题...
February 17, 2019

CF570D Tree Requests

题目一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。思路1(DSU)这应该是比较无脑的一种思路,开一个$cnt[M][i]$记录i这个颜色在某个深度出现了多少次,再开一个tmp记录对于这个深度,cnt是奇数的个数(如果在某个深度,奇数的个数是0或1,那么其就能组成回文串)