## hdu 3967 Zero’s Number (不允许前导0（新写法）的数位dp)

dp[i][j][k][p]表示第i位，前半部分%k的结果，后半部分%k的结果，是否有前导0.

## codeforces 145 E. Lucky Queries (线段树lazy标记)

c4和c7倒是没什么疑问。。。。

left.c4+right.c47,left.c4+right.c7,left.c47+right.c7…

c47最大是5.。。但是left.c4 + right.c7=6，比正确答案大。

## hdu 5904 LCIS (dp)

dp[a[i]]表示以a[i]结尾的最大长度。
dp[a[i]] = dp[a[i-1]] + 1

## codeforces 455 E. Function (斜率优化，线段树套凸包)

f[i][j] = min (f[i-1][j],f[i-1][j-1])

Function is calculated as follows: , ki — how many times we visited the i th element of the array a.

sum[y] - sum[l] + a[l]·(x - (y - l))

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[l]·l + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[l]·l - sum[l])

You may notice that in brackets something like the equation of the line — K·X + B. That’s very similar to the equation of the line:a[l]·(x - y) + a[ll - sum[l], where K = a[l], X = (x - y), B = a[ll - sum[l].

Now we must find minimum for all l and fixed X = (x - y).

We have n lines, i. e. for every element in array a one line (Ki, Bi).

, where (Ki, Bi)i-th line. Ki = a[i], Bi = a[ii - sum[i].

For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires space, because each line lies in vertices. And we can answer query in operations. Because we visit vertices and each vertex need in operations. You can learn the theory about Convex

Remainder: convex hull trick lets us maintain k linear functions of the form fi(x) = aix + bi and answer efficiently (in time proportional to number of functions) to the queries Q(x) = min1 ≤ i ≤ k fi(x) (given x).

Now we will be able to solve the problem if we can answer a bit more general kind of queries: we consider only lines with indices from given L and R; formally, Q(x, L, R) = minL ≤ i ≤ R fi(x).

How can we do it? Let’s make a segment tree! Let’s say we have such m that 2m ≥ n. Then the root contains the convex hull of lines having indices [0, 2m - 1], its left child contains [0, 2m - 1 - 1], right child [2m - 1, 2m - 1]and so on. We can costruct all these hulls one by one; without any optimizations it gives us time .

Now let’s say we have to answer the query Q(x, L, R). Then we just “break” the interval [L, R] into base intervals (in the same way a segment tree does) and for each of such base intervals we find its minimum at x. Now we see that the answer is the smallest of these minima. It doesn’t matter that we consider some groups of lines from interval [L, R] separately — still, we can just take the smallest of the results.

What’s the time? We have base intervals, for each of them we can compute the answer in , so total time is . There are some ways which let us compute all answers off-line in , but it’s not the subject 😛

wjmzbmr关于斜率优化的讲解

## hdu 3507 Print Article (斜率优化dp)

dp[i] 表示处理完前面i个数的最小代价。

dp[0] = 0 ;

dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。

1，用一个单调队列来维护解集。

2，假设队列中从头到尾已经有元素a b c。那么当d要入队的时候，我们维护队列的上凸性质，即如果g[d,c]<g[c,b]，那么就将c点删除。直到找到g[d,x]>=g[x,y]为止，并将d点加入在该位置中。

## codeforces 380 C. Sereja and Brackets (线段树区间合并)

（说“因此”是因为。。。只要左边有没匹配的左括号。。。右边有没匹配的右括号。。。因为他们中间有的都是匹配好的括号，会被删除。。。所以两边的括号总能匹配在一起）

query的时候要合并左右两个区间。。。不过可能某一区间中为空。。。这里合理得初始化为node(0,0,0)，就不用分情况讨论了。。。

## 【施工中】回文自动机学习笔记

20171115 update:

emmmm，这篇是学习笔记是１６年９月写的。。。。一转眼13个月过去了啊。。

len表示某个状态所表示的回文串的长度

cnt表示某个状态所表示的回文串的数量

## codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.

poj 2886 题目链接

## 1053: [HAOI2007]反素数ant

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2750  Solved: 1559
[Submit][Status][Discuss]

## Description

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x
，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么

## Input

一个数N（1<=N<=2,000,000,000）。

不超过N的最大的反质数。

1000

840

## Source

（oi赛制不可以带纸质材料，所以打表大概算是恶习…不过acm不一样啊orz。。。反素数表1..1E18也才167个。。。。