第一次屯题，听说屯题比较有压迫感→_→，月赛题我也做了百来道了，如果再屯50道差不多就没了（可以交差了），君嘘刚完结，为了不忘记它带给我的感动，好好做题吧

现在做了几道：

50

p2373: 转移方程:f[i]=min(f[j])+1 (i-2*b<=j<=i-2*a) 然后单调队列优化一下即可

p2374:先预处理出每个栅栏尽头往下是哪个栅栏，然后就是一个简单DP，预处理可以用线段树实现。。。我看到一群线段树跑的比我的链表慢23333

p2378:预处理粗每棵子树的size，然后遍历即可→_→，做完发现标算是树形DP←_←，真的不是dfs吗。。

p1984:用并查集记录每个节点的父亲节点，再开两数组记录从该点到父亲节点的横纵距离，离线做，把读进来的询问按time从小到大排序，然后依次构造求解

p1985:= =|||打脸了，我还以为剩下的题质量应该会高（其实是我小号过了），裸题，求树的最长链

p1986:预处理出每个点到根的距离，比如用F[i]表示节点i到根的距离，然后两点间的距离便是f[x]+f[y]-2*f[LCA(x,y)]，LCA用倍增算法

p2008: ...这题不等式可以化为Ahi+Bwi-C<=Ah+Bw。。按这个排序然后有n³的做法。。题解上说用堆优化→_→表示不明白怎么优化，网上的n²方法实在屌，不敢看，然后优化n³的暴力，优化掉重复计算的数据，然后可以卡过

p2010:二分平均值然后拿比平均值小的N/2个Bi较小的，比平均值大的也一样，注意要开long long

p1991:区间Dp,f[i][j][0..1]表示区间i~j的作业还没收过的最小时间，0表示在i教室，1表示在j教室→_→代码写的很胖

p3167:KMP,两个串相同的条件是串上的每个数字，比它大的数字个数，与它相等的数字个数，比它小的数字个数都相等，这样裸的用KMP已经可以过了，如果嫌慢可以用线段树/树状数组优化

p3168:刚开始看错题目吓傻了，以为两个矩阵会重叠要用线段树，然后坐标范围那么大。。铁定TLE啊，然后发现是不会重叠，那么只要按x排序，y排序，判一下有没有碰到就好了→_→我的代码精简能力就那么差吗。。居然打了1.3k+

p2454:先排序，把前2*k个大的找出来→_→，然后就可以随机调整= =|||，然后。。就过了= =|||

p2228:普通的DP很好想，f[i][j][0..1]表示到第i个数，取了j个数，i这个数取或不取，0表示不取，1表示取，方程:f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i]);然后这样不加优化的内存是将近120M，所以需要用滚动数组优化空间

p2227:可以用优先队列做，把边框压入队列，然后每次找一个最小的扩展，如果扩展到一个比它低的，说明有积水，然后更新这个位置的high再压入队列，如果高，也压入队列，直到队列为空

p2393:贪心，每次维护最大值即可→_→题解里讲的什么乱七八糟的

p3042:f[i][j][0..1]表示i~j区间里的点已经取了的最小时间，0表示在i，1表示在j，转移:略长+o+|||

p3046:f[i][j]表示用到第i个数，集合大小为j的方案数，方程:f[i][j]=∑(f[i-1][j-k])，可以用滚动数组+前缀和优化

p3037:开始还以为是DP，后来发现从（1，1）出去了后速度是确定的！。。然后就是求最短路了- =spfa，dij都可以

p3039:枚举分母，然后可以二分找分子，也可以暴力找分子

p3257:方程:f[a[i].x+a[i].w][j+a[i].c]=max(f[a[i].x+a[i].w][j+a[i].c],f[i][j]+a[i].f)+o+|||好吧我不小心喵到了题解

p3192:有一种做法叫暴力

p3189:二分排名上下界，每次跑一遍匈牙利，网上一堆网络流解法→_→

p3190:贪心，按左端点排序，然后维护一个优先队列，如果有重复，新开一组

p3622:贪心，按Ci排序然后每次取满足的最大的Bi，数据量有点大，可以用set实现

p3276:暴力+枚举就能过我会乱说？

p3666:DP很好想，但是数据范围略大，裸的应该会跪，离散化一下就好了→_→题解里说肯定存在一种最优解，b中的元素都是A中的元素，不知道有什么用意+o+

p1990:先按v值排序，然后只考虑每只只和前面的交流，维护两个树状数组，一个记录所有坐标个数，一个记录所有坐标和然后随便搞搞

p3169:差分约束，spfa搞搞

p3038:能上则上，上不了了，踢掉最远的，用优先队列很方便→_→话说题解里写的是什么。。线段树模拟。。吓傻

p2433:贪心是很明显的，每次切最小的山峰，我记得这题以前gang过，没gang出来，那个时候就是被判山峰恶心到了，还脑洞特别大想到用一颗倒着的树来做，其实只要每次扫描就可以了

p2432:宽搜，注意判重，可以用hash，也可以直接set搞

p3177:→_→有一种东西叫做双联通缩点，可以用tarjan算法，我会说我不会吗，我会说我用暴力0ms过了吗233，看着一堆人代码2000b3000b的笑死了，缩完点的图就变成一颗树了，答案就是（叶子节点个数+1）>>1

p3179:发现我真的是越来越懒了，这题一般都是离散化一下，然后二分+线段树。。然后因为我懒，，就抽风想了个DP，代码大大缩短+o+看着别人2000b+再看我900b+，虽然说DP，也是建立在离散化和二分基础上的，毕竟跑的比别人慢是事实，而且写dp数组开了好多=_+|||

p3659:感觉树形DP写的好虚，对树还不熟练，f[i][0]表示自己控制自己，f[i][1]表示被父亲控制，f[i][2]表示被儿子控制

p1273:裸的最大流

p3281:添一个源点向食品连一条容量为1的边，添一个汇点，饮料向汇点同样连边，把每头牛拆成两个点比如x，y，x向y连边，如果z是牛喜欢的食物，z向x连边，k是它喜欢的饮料，y向k连边，如果不把牛拆成两个点要WA

p2455:二分最大的最小长度，再网络流，朴素的要T，还有数组要开大

p2112:先floyd求出每头奶牛到机器的最短路，然后二分最大的最小长度，网络流验证，与p2455类似

p2135:最小费用最大流裸题，流两遍就好了，我是代码打的太丑了吗。。warning一直去不掉

p3280:f[i][j]=min(f[i+1][j]+w[s[i]],f[i][j-1]+w[s[j]],f[i+1][j-1](s[i]==s[j]))

p3613:求经过k条边的最短路吗。。不就是做k次floyd→_→不过这样要超时，用矩乘加速，矩乘写成floyd的形式

p3612:朴素的动归应该比较好想f[i][j]=min(f[i-1][k]+abs(j-k)*c+(j-a[i])^2)，转移的时候记录最优值就可以了

p3272:真是太感动了，把一个y打成x能过7个点然后调了半天，先跑出（递推？）到每个点的方案数，然后将边反向再跑一遍，用x→y表示一条边的话，答案就是max(f1[x]*f2[y])

p3274:先将数字全部转换为二进制，然后累加再减去第一列然后求距离最远的两个hash值相同的串，答案为距离

p3266:设m[d]=(t[d+1]+t[d+2]+...+t[n])/(p[d+1]+p[d+2]+...+p[n])则(t[d+1]-m[d]*p[d+1])+(t[d+2]-m[d]*p[d+2])+...+(t[n]-m[d]*p[n])=0设V[i]=t[i]-m[d]*p[i]那么如果sumV>0那么是可以改进的，于是这样能有个n²的做法。。看看数据范围，感觉加一点猥琐的技巧性优化就能过的样子，不过设y=m[d]x-p[i]*m[d]+t[i]，再设-p[i]*m[d]+t[i]=Max，则y=m[d]x+Max，是一条直线解析式，定穿过p[i],t[i]，于是在直线下面的点d就不用考虑了，于是只要维护一个上凸壳进行斜率优化就可以了

p3270:找出环然后分两种，一种是环里最小的数来交换还有一种就是别的环的数来交换

p3269:不明白了，这么水的题通过的人那么少，只要找中位数然后再找一下它周围的4个点就可以了

p3621:spfa+二分

p3255:次短路。。spfa删边再跑。。

p3182:两次BFS，第一次往左，第二次往右

第一次屯题结束了（感觉还不错），君嘘在我做题的时候不断激励我，我不会忘了那感动

截图留念：

loading...