1 ZLucker

尚未进行身份认证

暂无相关描述

等级
TA的排名 40w+

cf708D incorrect flow(上下界费用流)

题目先上个链接:http://www.cnblogs.com/mjtcn/p/8469349.html#4016492这个链接对模型啊,推导过程都很详细易懂~对于本题的建图:先将下限上限设为f;即对u->v,流量为f,则,m[u]+=f,m[v]-=f;对于c<f:1)扩容,ans+=f-c,将答案增加到最后的答案里2)同时增加流量和容量:u->v连c...

2018-10-31 17:48:12

hdu5889 Barricade(最小割+spfa)

最小割;转载:https://blog.csdn.net/a519781181/article/details/51908303?utm_source=blogxgwz0这篇文章把最小割介绍的很清楚。题目1、先求从1到n的最短路,用spfa,注意是无向图。2、将求得的最短路放入最大流模板,跑最小割,权值是花费,此时应将图视为有向图,因为不可能反向走回去。代码不贴了。...

2018-10-28 23:04:50

POJ2391 Ombrophobic Bovines+POJ2455

题目网络流+二分答案+floyed最短路径+分点题意好理解。1、由于答案是是要最短的避雨时间,因此需要猜测并验证可能的避雨时间-->二分法求答案2、由于需要建图,而一个农场上既有牛又有避雨点,牛又可以自行选择避雨点,为了建图方便,选择分点,将i号地分为i号只有牛的地和i+f号只有大棚的地,这样,图的层次可以这样分,源点连所有有牛的地,流量为每块地的牛数量,只有牛的地若满足条件...

2018-10-14 18:12:19

2018CCPC Tree and Permutation

题目题意见其他博客(滑稽)首先,推公式,有N!种全排列,每种排列有N-1条路,总共有N!*(N-1)条路,自己在纸上写一下,可以发现,每种路径(x-y)出现两次,(x-y和y-x是一样的长度),N个点,有N*(N-1)/2不同的种组合,计算出每种组合出现2*(N-1)!次。本题即树上搜索和DP,计算每两点之间的距离之和,再乘以出现的次数即可。注意点:注意取模操作,千万小心爆long...

2018-09-23 23:31:59

CCPC 2018 Buy and Resell HDU - 6438

题目题意见其他博客;关键词:贪心,优先队列,map;将每天的价格放入元素大小从小到大递增的优先队列中,分两种情况1、当前元素小于队首元素或者队列为空,直接加入队列2、当前元素大于队头元素,说明当前元素可以买入队头元素(不一定是最优解,先记着,后面又更优情况时可以更新),那么,将队首元素弹出,加入两次当前元素,第一次加入说明把原来的元素更新到当前这个元素的值(即后面若有更好的元素...

2018-09-22 23:58:20

2018 icpc 南京网络赛 SUM

SUM不难分析出将整数n分解成质因数相乘 n=p1^a1+p2^a2+.....=pn^an*x依据题目要求,可知,an直可取1或者2,当an为1时,一个素数有两种拆分方式,所以贡献为2,当an为2时,只有将一个pn分配到x里去,且x本身不可整除an时,才能满足条件,因此贡献为1。f(n)=2*f(x) (an=1)  f(n)=f(x) (an=2)  f(n)=0 ...

2018-09-11 00:02:36

落谷P1020 导弹拦截(线性DP+树状数组+Dilworth)

第一问,求最长不递增序列,普通DP复杂度为n*n,考虑用树状数组降低复杂度为n*log(n)普通DP:for(inti=1;i<=n;i++)f[i]=1;//以i结尾的最长不上升序列长度for(inti=1;i<=n;i++){for(intj=i+1;j<=n;j++){if(a[j]<=a...

2018-09-02 22:13:03

hdu 5115 Dire Wolf (区间DP)

作为第一道自己写出的区间DP,写个水博标记一下。题意见其他博客(hhh)这题和lightoj1422很像,思路也很像。对于一个区间,达到最优状态有两种可能,第一种是每次打死边界那只,第二种是区间中打死一只,最优解就是两种方案中选择一个伤害小的。从左往右递推,那么初始情况默认为打死新进来的作为边界的那只:dp[j][i]=dp[j][i-1]+wolves'attack[i]+...

2018-08-30 15:02:34

Can you answer these queries? 线段树从下向上的板子

被自己的破板子气哭,TLE一下午+晚上感谢:https://blog.csdn.net/qq_41061455/article/details/81321449#include<bits/stdc++.h>usingnamespacestd;#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1co...

2018-08-24 21:24:10

HDU 6319 Ascending Rating(单调队列)

转载:https://blog.csdn.net/qq_36258516/article/details/81290393反向使用单调队列

2018-08-21 22:56:22

二维树状数组

转载:https://blog.csdn.net/cggwz/article/details/78420102鸣谢!

2018-08-21 16:12:47

常用模板

1、双端队列/单调队列O(n)intn,k,a[maxn],b[maxn],deq[maxn];//a[]保存读入的数组;b[]保存一段区间的答案;deq[]双端队列,保存数组下标voidupper()//值按照升序存放在队列中{ ints=0,t=0;//s:首;t:尾 for(inti=0;i<n;i++) { while(s<t&&am...

2018-08-20 17:09:37

set、pair

set:http://www.360doc.com/content/17/0526/22/10408243_657567440.shtmlpair:https://blog.csdn.net/sinat_35121480/article/details/54728594

2018-08-20 10:19:26

动态规划

入门总概:https://www.sohu.com/a/153858619_466939          https://blog.csdn.net/feizaosyuacm/article/details/53846323          http://www.360doc.com/content/16/0906/13/30724179_5887965...

2018-08-17 11:37:26

单调队列

滑动窗口:https://blog.csdn.net/legend050709/article/details/36417347单调队列:https://www.cnblogs.com/tham/p/8038828.html 时间复杂度O(n)

2018-08-14 10:39:35

优先队列以及sort

优先队列转载:https://blog.csdn.net/c20182030/article/details/70757660      https://blog.csdn.net/zzycsx/article/details/47851737sort:https://www.cnblogs.com/AlvinZH/p/6784862.html?utm_source=itdada...

2018-08-10 11:17:27

图论

1、并查集:经典食物链:https://blog.csdn.net/freezhanacmore/article/details/87674132、强联通分图,tarjan,割点:tarjan求lca(最近公共祖先):https://blog.csdn.net/lw277232240/article/details/77017517 TarjanAlgorithm的时间复杂度为O(E+...

2018-08-09 11:46:15

简单数论

欧拉函数:https://blog.csdn.net/sentimental_dog/article/details/52002608(素数幂=素数的幂次方)数分解因数:https://blog.csdn.net/lianai911/article/details/44598155(打表+公式+素数幂)首先分解素因数,得到一个分解公式;然后搞清楚有几种不同的素因数,每种素因数出现了几次...

2018-08-03 17:32:43

取石子博弈论

博客搬运工_(:______转载注明:https://blog.csdn.net/acmlzq/article/details/51212297斐波那契博弈:转载注明:https://blog.csdn.net/acm_cxlove/article/details/7835016nim博弈状态转换:转载注明:https://www.cnblogs.com/clliff/p/42568...

2018-08-02 15:56:15

树的直径

vector<int>vec[100002];intmaxx,maxp1,maxp2,d[100002],pre,mem[100002];boolvis[100002];voiddfs(ints){ vis[s]=true; for(inti=0;i<vec[s].size();i++) { if(!vis[vec[s][i]]) { d...

2018-08-01 23:53:20

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!