AIM Tech Round 3 (Div. 1) C. Centroids(树形dp)

题意: $给定N\le 4\times 10^5的一棵树,询问每个点是否能通过删掉1条边再添加1条边成为重心$$重心:删除这个点,所有连通分量的最大大小\le n/2$     Read more
TaoSama's avatar
TaoSama Aug 26, 2016

HDU 5801 Up Sky,Mr.Zhu(可持久化Trie)

题意: $给定N\le 10^5的字符串S,字符集大小为5,其中的回文子串长度<20$$定义回文子串str[0\ldots n-1]的特征串为str[\lfloor n/ 2\rfloor\ldots n-1]$$给定询问区间s[L\ldots R]里,特征串前缀为T的回文串有多少个,|T|\le 10$     Read more
TaoSama's avatar
TaoSama Aug 13, 2016

HDU 5829 Rikka with Subset (NTT)

题意: $给定N\le 10^5个数,对于一个给定的1\le K\le N,设数集全集为U$$\forall S\in U,val(S):=S中前min(K, |S|)大数的和$$val(U)_{k}=\sum_{S\in U} val(S)$$输出每个val(U)_{k}$     Read more
TaoSama's avatar
TaoSama Aug 12, 2016

HDU 5756 Boss Bo(主席树、标记永久化)

题意: $给定N\le 5\times 10^4个点的一棵树,Q\le 10^5$$定义一个点是好点,当且仅当他所有祖先都不是坏点$$每次询问指定K个点为坏点,查询1个点P到所有好点的$$op=1:距离和$$op=2:最小距离$$op=3:最大距离$     Read more
TaoSama's avatar
TaoSama Aug 11, 2016

HDU 5820 Lights(主席树)

题意: $给定N\times N的网格图,N= 5\times 10^5,选中其中K\le 5\times 10^5个交叉点$$现判断对于任意2个交叉点之间,是否至少存在一条路径,使得这个路径的每个转弯都是交叉点$     Read more
TaoSama's avatar
TaoSama Aug 10, 2016

HDU 5812 Distance(数学、约数枚举)

题意: $维护1个集合S,d(x, y):=x经过多少次 乘/除素数 变成y$$给定Q\le 10^5个操作,有三种类型$$1 x:插入x,若x存在则无视$$2 x:删除x,若x不存在则无视$$3 x:求min_{y\in S} \{ d(x, y) \}$     Read more
TaoSama's avatar
TaoSama Aug 10, 2016

HDU 5811 Colosseo(拓扑排序、LIS)

题意: $给定N\le 10^3个人,给定拓扑关系,现将他们分为两个集合T1和T2$$问各自是否存在合法拓扑序,且在保证拓扑序的情况下,T2最多能添加多少人到T1中$     Read more
TaoSama's avatar
TaoSama Aug 10, 2016

HDU 4348 To the moon (主席树、标记永久化)

题意: $给定N\le 10^5个数,Q\le 10^5询问,初始时间戳Timestamp=0$$C l r v:Timestamp+1,将[l, r]区间的数都+v$$Q l r:查询当前Timestamp的[l, r]区间和$$H l r t:查询历史Timestamp=t的[l, r]区间和,保证合法$$B t:回到历史Timestamp=t的时刻,保证合法,保证不会回到将来$     Read more
TaoSama's avatar
TaoSama Aug 09, 2016

CodeForces 231E Cactus(边双缩点、LCA)

题意: $给定一颗N\le 10^5个点的仙人掌,M\le 10^5条边$$仙人掌定义为:任意一个点至多属于一个简单环$$Q\le 10^5询问,(u, v)有多少条简单路径可达$     Read more
TaoSama's avatar
TaoSama Aug 09, 2016

HDU 5803 Zhu’s Math Problem(数位dp)

题意: $给定A,B,C,D\in[1, 10^{18} ]$$求满足a+c>b+d \cup a+d\ge b+c且a\in[0, A], b\in [0, B], c\in[0, C], d\in[0, D]$$的不同的四元组(a, b, c, d)个数$     Read more
TaoSama's avatar
TaoSama Aug 08, 2016