Posts

题目链接 题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。

题目链接 题意：给出一个n个数的排列，每次可以把一个数放到最前面或者最后面的位置，问至少要进行多少次操作才能使得数列升序。 思路：考虑不被移动的那些数，当把所有一定的数去掉以后，这些剩下的数一定是一段数值连续，位置递增的数。如果想要移动的数最少，俺么这串递增的数就尽可能长。

题目链接 题意：给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。 思路：一开始想的是用一个left数组维护每次删除后某一列左边是哪一列，目的是为了下次的判断。

题目链接 题意：n堆石子，每堆a[i]个，k种颜色。给每个石子涂色，要求对于每种颜色，任意两堆中该颜色石子的个数最多差一个。问是否有解，有解输出一组方案。 思路：我们发现有解与否只和最大值最小值有关。

题目链接 题意：nm个格子，有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个nm的图保证至少有k个湖。问填多少个.成，才能使得恰好有k个湖。

题目链接 题意：给出n,m，n个数，对其中的一些数进行修改，要求1..m中出现次数最少的数最大，输出这个最少的数最大是多少，以及修改的次数。 思路：最小的数最多出现n/m次。

题目链接 ……sad… 果然没睡够，起来就写题，脑子完全就是不清醒的状态。 这个不清醒主要体现在，10+ 次忘记删条件编译。 改着改着就忘记这件事了，好烦啊。本来早就 A 了，结果又接着去改。

题目链接 题意：给出n，有1..n n个数，可以选择两个数进行加，减，乘，三种操作，操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。 思路：我们发现。。。两个数相减可以为1.。那么只要找到4个数的方案和5个数的方案就好了。。。

题目链接 题意：存在一个[2..100]之间的数，每次可以询问一个数是否是该数的因子，返回yes或者no，最多询问20次。每次要输出询问的数，以及最后要输出这个数是否是质数。

题目链接 题意：一段数字串，如果一个数字k满足，将该串分成若干个长度为K的子串，这些子串两两满足每个字符出现的次数一样多，那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。

题目链接 题意：给出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）

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