ACM

题目链接 题意：给出l,r,k，定义f(n,k)为将数n分成左右两个非空的部分，再求和之后能被k整除的方案数。 现在问区间[l,r]中所有f(i,k)的和。 思路：数位dp…

题目链接 题意：统计区间[a,b]里数字1出现的次数。 思路：数位dp。 收获是，dfs传递的参数可能是为了判断符合条件的答案（比如不要62中的preis6等） 但是也可能是在统计答案信息。。。pos等于0的时候返回值未必是1和0.。。

题目链接 题意：给出一串只由数字'4’和'7’组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的每个数反转，反转的定义为，4变成7,7变成4.

题目链接 题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。 思路：区间更新+区间询问的模板题…. 注意体会pushdown以及update的时候。。。

题目链接 题意： 给定两个序列，求它们的最长公共递增子序列的长度， 并且这个子序列的值是连续的 思路：以值为连续做入手点。 很显然个鬼咯 dp[a[i]]表示以a[i]结尾的最大长度。 dp[a[i]] = dp[a[i-1]] + 1 对于b序列一样。

题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5 个数（a[i] ai≤1E4)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。 参考题解：茶姐的回答（下标好像搞错了，领会意思即可 官方题解 以及前置技能点是：斜率优化+线段树

题目链接 题意：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]的前缀和。

参考博客 这个东西英文好像叫做：convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解：斜率优化是一种数形结合的思想。。。 对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。

题意：一串电话号码，每个数字+8取各位后，把每个数字写成对应的大写英文，从"ZERO"和“NINE”，然后打乱字母的顺序。现在给出打乱的字母顺序，问可能的字典序最小的电话号码是是多少（可能有前导0）

题目链接 题意：给出一个由‘(’和‘）’组成的字符串。。。然后给出若干查询。。。每个查询一个区间，问区间中能匹配的括号数。。。 思路：考虑某一个区间中的括号匹配。。。其实是一个不断寻找’()‘然后删去的过程。。。

题目链接 题意：给出 n 个数，q 个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数对 1e9+7 取模的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n) 是欧拉函数，意义为小于等于 n 并且与 n 互质的数的个数。

poj 2886 题目链接 题意：n 个人围成一圈，每个人身上有一个数，可正可负。从第 k 个人开始出圈，如果第 k 个人身上的数是 X，X>0，就左边第 x 个没有出圈的人出圈，否则右边第 -X 个人出圈。第 k 个人出圈得到的糖果数目为 f(k)，f(x) 表示 x 的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。

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的最大的反质数么？

题目链接 题意：求约数个数恰好为n个的最小的x 思路：这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上，这道题应该和反素数没有关系。 如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数…打表就行了。。。

题目链接 题意：求区间 [a,b] 中约数最多的那个数，如果有多个，输出最小的。 思路：看起来好像和反素数没什么关系……只是打个约数个数的表。 但是实际上，所有的答案恰好都是反素数。 我们回顾反素数的定义：设 f(x) 为 x 的约数个数，那么如果 f(n)>f(i)（0<i<n），n 就被称为反素数。

acdreamer的博客 wiki上的反素数是什么鬼orz…完全不是一个东西吧。。。。 反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数（？随便口胡的…

题目链接 题意：n 只青蛙，第 i 只位于 x[i]，舌头长度为 t[i]。m 只蚊子，第 i 只蚊子所在位置为 p[i]，蚊子的大小为 b[i]。 蚊子按照出现顺序输入。 一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换 n 次以后得到的数列中，逆序对的个数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let’s find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。 思路：二分中位数。 一开始还觉得由于中位数在整数意义上不连续不能二分。。。。

题目链接 题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。 思路：二分距离check合法性。 大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。