@LittleRewriter
2017-10-08T02:22:38.000000Z
字数 1553
阅读 1034
人生经验
出题可以掌控他人的秘密
这个题是可做的、是不是一眼题（不是裸题）、以合适的难度合适的算法出现
任何的题目都是不可能爆零的
比如今天的O(n)DP，可以放在D2T3
对于30%的数据，n<=5
对于50%的数据，n<=200
对于80%的数据，n<=2000
对于100%的数据，n<=1e8
也就是说，对于NOIP来说，正解搞不动，暴力分很多。
最大子矩阵：
1）改变其中k个数
2）改变其中k个数变为相反数
苦思冥想一个奇怪的东西，找到一个落脚点
1）这个题目是一眼题->继续加强
2）这个题目不可做->放宽条件（缩小数据范围，魔改）
例：由二分思考
有这么一段代码
l=1; r=n; mid=(l+r)/2;
while (l<=r){ if (a[mid]<=m) l=mid+1; else r=mid-1; mid=(l+r)/2;}
是用来二分的，显然当a顺序时，若m在a中出现过，则a[r]=m。
现在a是一个1~n的排列，并且它的顺序被打乱了，求存在多少种排列，使得最终r=k。答案对1e9+7取模。
n,m,k<=10^6。
n,m,k<=10^9。
且x+y=logn
答案为
预处理一下1e6、2e6...1e9的阶乘即可
题目考察什么问题
题目是否与经典问题相关
这个题目的难度（仅限NOIP）
出题人都会做，我为什么不会做
之所以能做，是因为放宽了条件
之所以不能做，是因为加强条件
例 次大公约数
次大公因数=最大公因数/最小公质因数
枚举a[1]的质因数即可
再一次的变式 k大公约数->不可做
树上的命题思路：树套小树，深度为一段区间的点，区间LCA等。
图上的命题思路：每条边以某个概率生成，每次以一定概率走某条边，缩点等。
序列上的命题思路：一段区间，每等差数列位置的区间，a{b{i}}与b{a{i}}构成树套环等。
辅助工具：gcd，max，期望，mex（最小未出现的正整数），sum等。
例：区间开根号向下取整 区间求和
任何一个不超过1e9的数只会经过不超过7次就会到达1，因此最坏7n次
暴力即可
你是出题人！
你是出题人！
你是出题人！
你是出题人！
你是出题人！
你是出题人！
你是出题人！
你是出题人！
当你想到一个好的idea，却不会做，不妨将其简化。
如果是一段序列，不妨将其随机。
如果是一棵树，不妨将其随机。
如果是一个矩阵，不妨将其变成黑白矩阵。
如果是一张图，不妨将其变成二分图。
甚至你可以指定一些特殊条件。（例如树的叶子个数，图的点的度数，每个数的大小等）
例如 叶子个数<=20，没有这个限制出题人都不会做
作一个能回报社会的出题人
有一个容量为m的背包，有n个物品，每个物品有价值和体积。
放若干物品，使得容量之和不超过m的情况下价值和在模p意义下最大。
n,p<=1000。
dp[i][j]->价值为j，体积最小为多少
那么dp[i+1][(j+v[i])%p]=min(dp[i+1][(j+v[i])%p],dp[i][j]+w[i]);
队列首插入、队列尾插入、队列首删除、查询队列元素最大值
劈成两半，左边维护单调队列，右边维护一个栈，然后维护一个后缀最大值
当且仅当栈为空时从队列中删除