题目链接 题意：一段数字串，如果一个数字k满足，将该串分成若干个长度为K的子串，这些子串两两满足每个字符出现的次数一样多，那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。 思路： * 首先我们发现，所有的阿贝尔周期一定是数字串长度（设为n)的因数。 * 然后我们还发现。。。如果某个因子是阿贝尔周期，那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期，类似筛法。 * 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。 然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。 还是太保守了。。。 不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜 /* …

题目链接 题意：给出l,r,k，定义f(n,k)为将数n分成左右两个非空的部分，再求和之后能被k整除的方案数。 现在问区间[l,r]中所有f(i,k)的和。 思路：数位dp... 枚举一下分点即可。。想到这个这题就A了。。。 然后相当于做分点个数个数位dp...求和即可。 dp[i][j][k][p]表示第i位，前半部分%k的结果，后半部分%k的结果，是否有前导0. 然后关于前导0这个。。。换了一种写法。。。加了一个状态在dp数组里。。。 不然每次都要一个if。。。感觉有点丑。。。。这样写简介了一点。。。 以及。。因为每次k是不同的。。。我dp状态记录的时候又没有记录k...所以记得每次初始化成-1。。。 因为忘记这个结果第二个样例 …

题目链接 题意：统计区间[a,b]里数字1出现的次数。 思路：数位dp。 收获是，dfs传递的参数可能是为了判断符合条件的答案（比如不要62中的preis6等） 但是也可能是在统计答案信息。。。pos等于0的时候返回值未必是1和0.。。 然后傻逼fzu。。。long long 必须交 I64d..因为这个wa到死。 傻逼fzu，毁我青春。 /* *********************************************** Author :111qqz Created Time :Thu 29 Sep 2016 02:20:09 AM CST File Name :code/fzu/2113.cpp …

题目链接 题意：给出一串只由数字'4'和'7'组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的没个数反转，反转的定义为，4变成7,7变成4. 思路：线段树lazy标记。 线段树的域记录5个信息，c4,c7,c47,c74，flip,a分别表示4的个数,7的个数，非下降子序列的个数，非上升的子序列的个数，以及该区间是否被翻转。 纠结了很久PushUp操作。。。。 c4和c7倒是没什么疑问。。。。 一开始觉得c47是由三部分的最大值更新得到的。。。 left.c4+right.c47,left.c4+right.c7,left.c47+right.c7... 但是样例过不了。。。 纠结了 …

题目链接 题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。 思路：区间更新+区间询问的模板题.... 注意体会pushdown以及update的时候。。。 要同时更新tree数组和lazy数组。。。 读入的时候可以用sscanf判断操作类型。。。 /* *********************************************** Author :111qqz Created Time :Mon 26 Sep 2016 05:30:21 AM CST File Name :code/cf/problem/52C.cpp …

我学不会dp不是因为我智商低，而是因为没有足够好的资料。 ** 我学不会dp不是因为我智商低，而是因为没有足够好的资料。** ** 我学不会dp不是因为我智商低，而是因为没有足够好的资料。**

题目链接 题意： 给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的 思路：以值为连续做入手点。 很显然个鬼咯 dp[a[i]]表示以a[i]结尾的最大长度。 dp[a[i]] = dp[a[i-1]] + 1 对于b序列一样。 答案为 MAX(min(dp[i],dp2[i])) ( 1=<i <= 1E6) /* *********************************************** Author :111qqz Created Time :Mon 26 Sep 2016 04:02:24 AM CST File Name :code/hdu/5904.cpp …

题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5​​ 个数（a[i] a​i​​≤1E4​​)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。 参考题解：茶姐的回答（下标好像搞错了，领会意思即可 官方题解 以及前置技能点是：斜率优化+线段树 思路：考虑一排数a[1]到a[n]，原问题可以转化成从a[y]走x-1步，每一步原地不动或者向左移动一个格子后的总的代价。 Function is calculated as follows: , k__i — how many times we …

题目链接 题意：n个数，分成若干段，每段的代价为 ，求最小代价。 思路：dp。 状态方程很显然个鬼。。。 dp[i] 表示处理完前面i个数的最小代价。 dp[0] = 0 ; dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。 这复杂度是n^2的。。。然而n最大5E5.....boom.... 斜率优化登场！ 这篇博客讲得非常好 我们假设k两边移项一下，得到：(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我们把dp[j]-num[j]^2看做是yj， …

浅谈数形结合思想在信息学竞赛中的应用 参考博客 这个东西英文好像叫做：convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解：斜率优化是一种数形结合的思想。。。 对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。 简单地说。。。如果把状态的下标和状态对应成二维平面的点。。。 凸起来的点一定不会影响答案。。。 具体证明参考论文。。。。。 也就是维护一个"下凸折线" 具体维护的办法是用单调队列来维护。。。 感觉还是挺简单的。。。。