牛客界面越来越好看了唉（＃－.－）

..对于刚学dp的萌新十分不友好..题目描述:你一个数组R,包含N个元素,求有多少满足条件的序列A使得0≤A[i]≤R[i].A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模.首先知道等式成立的条件是对于每一位分配的A[i],不可能存在2个1,也就是说最多分配一个1.然后就是介绍dp的含义了.dp需要开两维dp[k][i],第一维是分配到了第k位,第二维是这些A[]前k-1位是不是与R[]相同,然后直接dfs即可.冷静分析复杂度是60*(1<<10).代码如下: #include <bits/stdc++.h...

1.DP2.网络流3.线段树

这题貌似写过= - =...我们考虑取每个的价值,假设说我们取了第i个,其他个没有取.取第i个,其他不选,对于在取i的时间内是一种什么情况呢?假设我们有两种选择,第一个时间是ti.另外一个时间是tj.第一个每分钟减少w[i],另外一个减少w[j].第一个完成的价值是val[i],另外一个完成的价值是val[j].考虑取这两个的先后顺序,似乎很简单分析,因为我们所用时间相同,那么其他产生的代价是一样的,我们可以不予考虑.假如说我先取i再取j,那么我获得的价值是val[i]+val[j]-(ti+tj)w[j]-tiw[i].同理考虑先取j再取i就是val[j]+val[i]-(tj+ti)w[i...

https://blog.nowcoder.net/n/82f28d6e3af24c7f97dab5f9d5e8afd6

题意:牛牛喜欢整数序列，他认为一个序列美丽的定义是1：每个数都在0到40之间2：每个数都小于等于之前的数的平均值具体地说：for each i, 1 <= i < N, A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.3：没有三个连续的递减的数现在给你一个序列，每个元素是-1到40，你可以将序列中的-1修改成任意的数，求你可以得到多少个美丽序列，答案对1e9+7取模.对于题目我们很容易想到第一维是到了第几个数.对于第二个条件,我们就得想到前面的总和是多少,到了第三个条件我们就得设当前是递减序列的第几个,为了方便转移我们还需要另设一个就是当前的...

当初因为菜,dp学了一会就没学了,最近重学.

是个树状数组好题,但是我对建立多个树状数组并不是太了解写法,所以自己手写一下.题目给定n个点,以及他们代表的数,然后给你m条边,然后支持两种操作,1是修改,2是查询.修改是把u节点的值改成x.查询是查询与u节点相邻点的mex.思路:思路很清晰,考虑每个节点连接sqrt(m)的数量不可能超过sqrt(m)个,我们将点分为重点,轻点.重点就是超过sqrt(m)个的点,轻点就是没超过sqrt(m)的点.然后对于重点我们二分树状数组解决,对于轻点我们直接暴力求解,此外对于修改操作,对于其连接点是重点,我们要对其连接点的树状数组进行单点修改,且改变它本身的权值,对于轻点来说直接改变自己的权值即可. #i...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+9; const ll N=1e5+5; ll A=691504013ll;//1+sqrt(5)/2 ll B=308495997ll;//1-sqrt(5)/2 ll D=276601605ll;//1/sqrt(5) ll f[N],ivf[N]; inline ll pow(ll a,ll b) { b%=mod-1; ll res=1; while(b) { if(b&1) res=res*a%m...

难点在于计数.  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+100; struct vv{ int id,w; }a[N]; bool cmp(vv b,vv c) { return b.w>c.w;//把权值大的排前面. } int fa[N],vis[N],fcnt[N];//某个点的祖先,标记数组 inline int F(int x)//寻找x的祖先. { if(fa[x]==x) return fa[x]; else return fa[x]...

http://acm.hdu.edu.cn/showproblem.php?pid=6759题意:是说给你很多个初始位置和加速度的机器人.然后问你有多少个机器人曾经拿过rk1,并列不算.怎么写呢?首先我们应该知道,假如两条线重合.那么显然是不能作为答案的,我们要标记一下.对于每个机器人来说他们的运动轨迹都可以看成是一条一次函数.然后我们就可以发现很多性质了,解方程的性质.画个图:我们很容易发现,假如我们先拿起始坐标按p排序,维护一个栈,就可以作为答案,首先我们把第一条线的信息放入栈,然后假如a小于栈顶里面的a那么显然不可能成为rk1,因为你起点低,后劲少怎么可能当rk1(好像说的就是我.)假如...

重点是bfs,分块只是优化bfs. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+6e4; const ll M=500;//块的大小 struct vv{ ll d,p,r,m;//距离 磁力 半径 质量 }a[N]; ll L[M],R[M],D[M];//每个块的左边和右边.每个块最右边的质量 bool vis[N]; queue<ll>q;//队列 bool cnp(vv x,vv y) { return x.d<y.d;//距离排序 }...

不对自己狠点就永远不知道自己多菜,鸽了很久的cf,今天打一场觉得也还行,挺锻炼思维的.多校咕了那么多场.确实是自己太菜了不敢打了.其实训练和比赛并不矛盾吧?一直都是自己太畏惧了..下次争取每场比赛不咕!要对自己狠一点..做最好的自己.

嗯,今天也是我第一次学分块,所以更下题解和分块.辛格大佬说这个题就是莫队的板子分块一般是将一个区间分成sqrt(n)块,然后对于进行处理,比如说今天我们这个题目求区间众数.我们处理出两个数组,一个f[i][j]表示第i块到第j块的众数是多少,另外一个s[i][j]表示前i块中j出现次数.处理完这两个数组,我们就很容易知道假如给定一个区间l-r要我们求这个区间的众数,怎么求呢?假设l-r不跨一个区间.那么直接暴力求就好了,假如跨的区间＞1,那么众数产生会是哪些地方呢?我们画个图.emm,有点丑...不过并不影响什么,显然众数只可能是f[2][4]和l-2/4-r里面的一个数,如此这个题就做完了....