思路： dp[][]代表前i个小朋友发j个饼干的最小怒气值，由于排序不等式的证明，所有怒气值最高的小孩应该发的饼干是最大值，依次递减，我们先排序，然后记录在数组中原来的值，但是状态转移很难想啊，是类似整数划分，最后有几个饼干是等于1的，如果有k，K>0那么就可以由f[i][j]=min(f[i][j],f[i-k][j-k]+(i-k)*(sum[i]-sum[i-k]));，如果等于0的时候呢，由于这个怒气值取决于这个图形的形状，那么直接把整体往下-1就行了，最后比较ex的是要输出方案？？啊这，那就老老实实求吧，记录一个h，如果由第二个转移过来那就等价于把前i个小朋友发的饼干的抬高1。...

一开始我和大佬想的是二分再套线段树，然后tle了，想不到优化然后就查网了，如果左子树满足条件就不要递归右子树了可以优化一下，然后如果整段区间的最大值也不满足那就没必要往下递归了。 int query(int m,int l,int r,int val){ if(tree[m].l==tree[m].r) { if(tree[m].val>=val) return tree[m].l; return -1; } if(tree[m].l>=l && tree...

vj 题意：给你一个数一年有k天，选择最少的人使得他们满足他们生日概率大于等于0.5。 思路：这就是很简单的概率论的生日概率模型，然而我没想出来，看了思路以后还写复杂了，二分模拟来求然后tle了，结果直接递推算就能过了。 tle代码： #include<bits/stdc++.h> using namespace std; int n; const double eps=1e-3; bool check(int mid) { double res=1.0; for(int i=0;i<mid;i++) res=res*(n-i)/n; return res...

复杂度o n^2m 思路：bfs出分层图，不断dfs，用当前弧优化。 #include<bits/stdc++.h> using namespace std; const int N=10010; const int M=200010; int h[N],e[M],ne[M],f[M]; int cur[N],d[N]; int q[N],idx; int n,m,S,T; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++; ne[idx]=h[b],f[idx]=0,e[i...

链接 题意：r,n代表一个r * r的矩阵，n代表有n个金币，初始时间是0，现在你站在(1,1)位置，然后给出n个金币出现的位置(x,y)和出现的时间t，这个金币只在t这一分钟出现，过了t就消失，然后保证给出的t是严格递增的，求你能获得的最大收益。每分钟你能向四周移动一个单位。 思路：dp[i]以第i个结尾的最大值，只想到on^2的做法，但后来发现因为r很小，t又是递增的，第二层循环只要枚举(i-4r~i-1）就行了，为什么呢，因为i-5r一定能更新i-3*r，那么如果枚举所有点，这样就多余了。复杂度O(nr) #include<bits/stdc++.h> using name...

题意：n个人，m个怪物，k瓶药水，每个人可以打死对应的集合里面的一个怪物，一碰药水可以让一个人多打死一个怪物，每个人最多只能用一瓶药水，问最多能打死多少个怪物 思路：想到了匹配，然后用最大流做，一开始想的建图是从超级原点连一条容量是n+k的边到虚拟节点，然后虚拟节点与所有勇士连一条容量是2的边，然后勇士与对应的怪物连1的边，怪物与汇点连1的边跑最大流，然后wa了，错误在于我们这样做默认勇士可以用药了，然后k等于0的时候，答案就不对了，所以正解是超级源点和所有勇士连1的边，药水节点与勇士连1的边，超级源点与药水连k的边，勇士和对应怪物连1的边，怪物与汇点连1的边，跑最大流 ac代码： #inc...

const int MAXN = 1000005 ; int64_t mulEx(int64_t a , int64_t b , int64_t Mod) { ///logn快速乘 if(!a) return 0 ; int64_t ans(0) ; while(b) { if(b & 1) ans = (ans + a) % Mod; a <<= 1 ; a %= Mod ; b >>= 1 ; } return ans ; } int64_t powEx(int64_t b...

__int128 read(){ __int128 x=0,f=1; char ch=getchar(); while(!isdigit(ch)&&ch!=’-’)ch=getchar(); if(ch==’-’)f=-1; while(isdigit(ch))x=x10+ch-‘0’,ch=getchar(); return fx; } void print(__int128 x){ if(x<0)putchar(’-’),x=-x; if(x>9)print(x/10);//注意这里是x>9不是x>10 (2019.10 wa哭了回来标记一下...

给定长度为n的正方形，每操作一次可以将一块正方形切为4部分，问操作k次能得到多少不同的图形样式，每次只能切中间，所以偶数肯定不能继续切了。 思路： 我们发现每操作一次n就会变成(n-1)/2dp？dp[][]代表前i层操作j次的方案数，如何转移呢？看了博客有个朴素的转移法就是枚举上一次的四块操作数，那复杂度是不能接受的，我们可以上下两块分为两组，先用ans数组预处理出来，由于组内是有序的所以两层循环都从0开始，这样就将复杂度变成了（30*n^2）是可以接受的。 代码： #include<bits/stdc++.h> using namespace std; const int N...

题意： 题目大意：给出一个长度为 n 的序列，现在有 m 个位置被锁定，也就是无法进行操作，每次操作可以选择一个没有被锁定的位置，将其更改为任意数值，现在问最少进行多少次操作，可以使得整个序列变得严格递增 思路： 有个小技巧，看了大佬的博客才明白的，就是每一位都减去它的下标，这样判断起来，只需要判断锁住的元素是单调不下降的，就合法了，然后该题就转换成求k段操作数最少，由于每一段是独立的，那么考虑一段，有个结论最少操作数就是len-最长不下降子序列长度,那就分别求每一段就行了，加两个哨兵可以更有效的做题，然后在分别求每一段的时候也是不一样的，len=1的时候的数组是不能动的，最后一定要以a[r]...

题意：从1~m中选一个数插入到a中，然后把这n+1个数，分成（n+1）/2组，每一组权值和最小。 思路：先将a数组排个序，然后枚举要放的数，二分找到大于等于b的位置，如果该位置是奇数就选择该位置，如果是偶数，–pos，然后加上这个点的权值差加上不算该点的前缀和 加 后缀和。更新一下答案就可以了。简单的贪心都做不出，凭什么拿铜牌啊。。 代码： #include<bits/stdc++.h> using namespace std; const int N=200010; #define int long long int n,m; typedef long long ll; ll...

题意： 每次可以将前缀减1或者后缀减1，问是否存在一种方法使得全部构成0. 思路： 构建差分序列，然后操作就可以变成将d[1]-1 d[X],X ϵ \epsilon ϵ(2,n+1)加上1 另外一种操作就是将d[X],X ϵ \epsilon ϵ(1,n)减去1 将 n+1 + 1 然后我们将题目所给的差分数组算出来，关于正数的我们可以不管，因为有操作2，最后操作完满足1~n的差分值都是0，关于负数的只有操作1可以，我们只需要讨论 ∑ \sum ∑|负数之和|<=d[1]就行了。 AC代码： #include<bits/stdc++.h> using namespace ...

思路：找出必败态 打出sg函数的表 硬找规律！ #include<bits/stdc++.h> using namespace std; #define x first #define y second typedef long long ll; int qsm(int a,int b,int c) { int res=1; while(b) { if(b&1) res=res*a%c; b>>=1; a=a*a%c; } return res; } int sg(int a,int b,int c,int d) { ...

#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<windows.h> using namespace std; int main() { int ok=0; int n=1000; for(int i=1; i<=n; ++i) { system("make.exe > make.txt"); system("ab.e...