By Xiejiadong 一月 21, 2020 No Comment 动态规划区间dp多项式数学树形dp模拟 Codeforces Round #614 ConneR and the A.R.C. Markland-N 【题意】 禁用一些位置,找没有被禁用的最近的 Read more
By Xiejiadong 五月 12, 2019 No Comment 后缀自动机字符串树形dp 【AHOI2013】差异 题意 求 \(\sum_{1\le i < j \le n} len(T_i)+len(T_j)-2\t Read more
By Xiejiadong 五月 10, 2019 No Comment 动态规划后缀自动机字符串 【Hihocoder1465】后缀自动机五·重复旋律8 题意 求若干串\(T\)在另一个长串\(S\)中各自作为子串出现的次数,匹配的方式为“循环同构”。 分析 循环 Read more
By Xiejiadong 四月 18, 2019 No Comment Manacher动态规划字符串 【Nowcoder17062】回文 题意 每次可以删除头部或者尾部的一个字母\(x\),代价为\(a_x\); 每次可以在头部或者尾部新增一个字母 Read more
By Xiejiadong 四月 15, 2019 No Comment AC自动机动态规划字符串 【JSOI2007】文本生成器 题意 求包含集合\(S\)中任意个字符串为子串,且长度为\(m\)的字符串个数。 分析 考虑在AC自动机上dp Read more
By Xiejiadong 四月 15, 2019 No Comment AC自动机动态规划字符串数位dp 【SDOI2014】数数 题意 求满足\(\le n\)且不包含集合\(S\)中任意字符串作为子串的个数。 分析 多子串问题,考虑在AC Read more
By Xiejiadong 三月 25, 2019 No Comment dfsstl二分答案二进制相关算法位运算动态规划启发式合并字符串数位dp数学构造树形dp模拟比赛记录素数贪心 埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 A Wasserstein Distance 显然,有跨越的移动是没有意义的。因为相邻的移动和跨越的移动代价相 Read more