Hihocode 1492 Parentheses Sequence(dp)

题意:$给定一个长度为N\le 10^3的括号串,可以插入括号$$问变成合法的括号串的最短插入次数,和方法数$     Read more
TaoSama's avatar
TaoSama Apr 05, 2017

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

HDU 5787 K-wolf Number(数位dp)

题意: $求1\le L\le R\le 10^{18}范围内,每2\le K\le 5个数字都不同的数字有多少$     Read more
TaoSama's avatar
TaoSama Aug 05, 2016

HDU 5781 ATM Mechine(期望dp)

题意: $给定1\le K\le 2000的钱的上界,即钱x\in[0, K],1\le W\le 2000次警告次数$$>会被警告,\le 可以直接取走钱,警告次数超过W会被警察带走$$人采取最优策略的情况下,问取完所有钱的期望次数$     Read more
TaoSama's avatar
TaoSama Aug 03, 2016

Codeforces 85C Petya and Tree(树形dp)

题意: $N\le 10^5的一棵满二叉搜索树,点权1\le A_i\le 10^9$$满二叉搜索树:每个节点的儿子个数为0或者2$$给定Q\le 10^5询问,每次查询一个值1\le q\le 10^9,保证值没有在BST中出现过$$并且查询过程中一定会出错有且仅有一次,即本该去左子树去了右子树,反之亦然$$求在BST中查询这个值的期望$     Read more
TaoSama's avatar
TaoSama Aug 01, 2016

HDU 5735 Born Slippy(dp、分块、可持久化)

题意: $N\le 2^{16}个节点的一棵树,点权w_i < 2^{16},现从树上抓出来一条链序列$$对于起点s\in [1, N],找出1个序列,v_1=s, v_2, \cdots, v_m$$使得f(s)=w_{v_1}+\sum\limits_{i=2}^{m}w_{v_i} \text{ opt } w_{v_{i-1}}最大,opt可以是AND,OR,XOR$$求每个f(i)$     Read more
TaoSama's avatar
TaoSama Jul 25, 2016

51nod 1532 带可选字符的多字符串匹配(dp、bitset优化)

题意: $N\le 2\times 10^6的母串,M\le 500的模式串$$模式串的每个字符c_i有cnt_i\le 62个可选字符$$求母串哪些位置可以匹配模式串$     Read more
TaoSama's avatar
TaoSama Jul 24, 2016

HDU 5745 La Vie en rose(dp、bitset优化)

题意: $N\le 10^5的母串,M\le 5000的模式串$$对于模式串,不相邻的2个字符可以和相邻的交换$$即abcd,ab换和cd也可以换,但bc换了cd就不能换了$$求每个位置是否能匹配模式串$     Read more
TaoSama's avatar
TaoSama Jul 24, 2016

HDU 5726 GCD(dp、倍增)

题意: $给定一个N\le 10^5个数,|A_i| \le 10^9,Q\le 10^5次询问$$定义gcd(l, r)=gcd(a_l, a_{l+1}, \cdots, a_r)$$每次询问给定一个[l, r],查询\forall_{1\le l’\le r’\le N},gcd(l’, r’)=gcd(l, r)的(l’, r’)个数$     Read more
TaoSama's avatar
TaoSama Jul 24, 2016