willinglive-CSDN博客

原创【FFT】HDU 4609

给定集合，求任选三个数能构成三角形的概率#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_=(l);i>=

2015-06-10 16:04:24 638

原创 PKU Campus 2015

第一次打ACM现场赛记得那天恰好在下雨，比赛前去看了看未名湖畔至于比赛，我大概乱做了一下下。。。。。。A貌似是读入优化写挂了？不过看了几遍没有啊，把read()改成cin就A了作死A了之后又wa一次，居然还算罚时，而且因为这个没进第一版不开森。。。B看起来是一道模拟题，看不懂样例是什么鬼

2015-05-25 09:40:55 1136

原创【Contest】Problems about probablity

H推导得不太熟练if(i==1) dp[1][1] = ( p1 + p2 ) * dp[1][1] + p4else if(j>1) dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j-1] + p3 * dp[i-1][j-1] + p4 * [j else dp[i][1] = p1 * dp[i][1] + p2 * dp[i][i] + p

2015-05-21 08:36:42 596

原创【LCT】【QTREE5】Query on a tree V

http://www.spoj.com/problems/QTREE5/en/看别人代码理解的LCT。。。想了好久，终于明白up()函数是什么意思了。。。。不明白为什么可以没有flip#include #include #include #include #include #include #include using namespace std;

2015-05-19 09:27:26 885

原创【动态树分治】【bzoj 4012】: [HNOI2015]开店

http://www.lydsy.com/JudgeOnline/problem.php?id=4012一眼的码农题。。。#include #include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(

2015-05-18 12:21:02 1134

原创【LCT】【bzoj 3514】: Codechef MARCH14 GERALD07加强版

http://www.lydsy.com/JudgeOnline/problem.php?id=3514感觉不错，一气呵成=w=#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_

2015-05-16 10:22:16 796

原创【坑坑坑】数据结构 Contest

B矩形面积k次并代码写得很不熟练#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_=(l);i>=_;i--)

2015-05-15 22:03:19 655

原创【poj 2187】Beauty Contest

http://poj.org/problem?id=2187#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_

2015-04-13 11:45:49 439

原创【Pollard Rho模板】【bzoj 3667】: Rabin-Miller算法

http://www.lydsy.com/JudgeOnline/problem.php?id=3667#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define pe

2015-04-13 08:14:03 1074

原创【bzoj 2127】: happiness

http://www.lydsy.com/JudgeOnline/problem.php?id=3894最大权闭合子图比较一般化的问题。。。就是列方程，，，解方程注意的技巧：1.对于一个人选文选理的收益是可以分开计算的。。。2.边权为负数怎么变成正数！只能用于分层图！3.边权*2的技巧。。。被坑了。。。

2015-03-26 16:26:55 518

原创【bzoj 3262】: 陌上花开

http://www.lydsy.com/JudgeOnline/problem.php?id=3262有人说有O(nlogn)的不sort的方法，简直是胡扯。。。中间还不是O(nlogn)的BIT。。。一样的T(n)=2T(n/2)+O(nlogn)自己算算、、、一定要先去重么。。。？jcvb:关键在于等号的处理。按a排序，并把a值相同的三元组

2015-03-20 18:34:43 751

原创【费用流】【bzoj 2245】: [SDOI2011]工作安排

学习zkw费用流之后发现不会写普通的了正好翻代码的时候看到了这个。。。#include #include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)#define per

2015-03-20 16:32:23 530

原创【k短路】【bzoj 1598】: [Usaco2008 Mar]牛跑步

http://www.lydsy.com/JudgeOnline/problem.php?id=1598原来k短路这么简单= =直接看代码就能懂= =#include #include #include #include #include #include #include using namespace std;using namespace __

2015-03-20 15:55:45 824

原创【bzoj 2750】: [HAOI2012]Road

http://www.lydsy.com/JudgeOnline/problem.php?id=2750首先容易想到枚举点对，可以得到一个O(n^2m)的算法，期望得分60分接下来容易想到枚举一个点，再对每一条边算贡献也就是计算从S出发，最短路经过i边的方案数设i连接了u和v首先要满足的是dis[u]+e[i].w==dis[v]那么

2015-03-19 16:39:54 908

原创【bzoj 2749】: [HAOI2012]外星人

http://www.lydsy.com/JudgeOnline/problem.php?id=2749妈蛋官方数据是错的，害我查半天。。。。my thoughts:f(x)=0 (x=1)f(x)=f(phi(x))+1 (else)那么显然是可以O(n)求出来的令k=i*prim[j]f(1)=0f(i)=f(i-1)

2015-03-19 15:26:54 1138

原创【bzoj 3598】: [Scoi2014]方伯伯的商场之旅

http://www.lydsy.com/JudgeOnline/problem.php?id=3598DP啊DP如果枚举mid的话会很麻烦。。。可能还会爆空间改成转移一切都不是问题~#include #include #include #include #include #include using namespace std;///////////

2015-03-19 13:08:20 1210

原创【bzoj 2844】: albus就是要第一个出场

http://www.lydsy.com/JudgeOnline/problem.php?id=2844先求线性基，那么可以得到0的个数cnt0每个数与0异或都会得到2^cnt0这个数。。。。那么从小到大统计答案即可注意最小的可以是0组成的，所以先要加上2^cnt0个0特判一下如果没有0就不加蒟蒻还是太懒了。。。。

2015-03-18 20:56:30 682

原创【bzoj 2115】: [Wc2011] Xor

http://www.lydsy.com/JudgeOnline/problem.php?id=2115dfs找出所有的环，再消元。。。#include #include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int

2015-03-18 20:47:01 493

原创【bzoj 3543】: [ONTAK2010]Garden

http://www.lydsy.com/JudgeOnline/problem.php?id=3543无论是按x排序y排序x+y排序x-y排序，复杂度都是O(n^2)的，，，，貌似有些没卡掉。。。正解当然是O(n^1.5)的辣枚举x，分两类1）扫描线上的点的个数枚举上面的两个点，暴力2）else分界线不超过sqrt(n)个，枚举分界线暴力。

2015-03-18 16:14:05 582

原创【bzoj 2300】: [HAOI2011]防线修建

http://www.lydsy.com/JudgeOnline/problem.php?id=2300离线+set维护凸包第一次码这个，还跑得飞快。。。#include #include #include #include #include #include #include using namespace std;#define rep(i,l,

2015-03-18 10:54:55 588

原创【bzoj 2668】: [cqoi2012]交换棋子

http://www.lydsy.com/JudgeOnline/problem.php?id=2668网络流。注意拆点的技巧开始拆点的时候没有注意点的出入关系，产生了“传递性”，导致混乱理清楚关系：限制的是交换次数交换次数=sum{交换边流量}所以所有的交换边连向一个点来限制次数妈呀还是不对点流量限制不用再拆点，只需要分类讨论一下就可以

2015-03-17 19:59:36 845

原创【bzoj 2666】: [cqoi2012]组装

http://www.lydsy.com/JudgeOnline/problem.php?id=2666这道题，容易想到按x坐标排序，然后扫一遍。。。。。问题是区间内多个颜色相同的情况，到底选哪一个成为问题换种思路。。。加入我们已经确定了哪些车间，可以通过预处理在O(1)内算出代价所以考虑枚举i和last(i)平均值，那么选哪一个就不成问题了，问题在于如何枚

2015-03-17 19:56:13 758

原创【Plan 第九场】

。。。。一场手速赛，，，练练代(yue)码(du)能(li)力(jie)QwQ，我好弱简直是各种错误应有尽有。。。

2015-03-17 11:14:21 461

原创【Plan 第八场】

http://codeforces.com/contest/521随便找了场最近的CF水了水，我果水A送分题#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++

2015-03-16 22:10:43 485

原创【Plan 第七场】

A一类题。。。类似最小乘积生成树。。。。。。。。。。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_

2015-03-14 10:04:33 393

原创【KM模板】HDU 2255 奔小康赚大钱

http://acm.hdu.edu.cn/showproblem.php?pid=2255#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,

2015-03-14 09:08:23 500

原创【bzoj 3052】: [wc2013]糖果公园

http://www.lydsy.com/JudgeOnline/problem.php?id=3052题解啊。。。见vfk的。。。。看了好久才看懂啊。。。。。。。QwQ。。。然后调了好久的参。。。#include #include #include #include #include #include #include using namespa

2015-03-13 20:28:39 580

原创【分治】【bzoj 2458】: [BeiJing2011]最小三角形

http://www.lydsy.com/JudgeOnline/problem.php?id=2458和最近点对一样#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i+

2015-03-13 09:46:35 484

原创【分治】【2015-2】day7 T2

子集和问题，被D得好惨啊QwQ，为甚我没见过。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_=(l);

2015-03-13 09:14:14 433

原创【bzoj 2395】: [Balkan 2011]Timeismoney

http://www.lydsy.com/JudgeOnline/problem.php?id=2395最小乘积生成树、、、？好nb的样纸啊感觉和分数规划的推导差不多。。。。。复杂度是随机数据下期望。。。。#include #include #include #include #include #include using namespace s

2015-03-12 16:57:49 491

原创【Plan 第六场】【后缀数组模板】

题目见2015-1 1.6A后缀数组乱搞，蒟蒻看到uoj有人DA胜过DC3，于是又换了个版。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define pe

2015-03-11 16:55:37 448

原创【poj 1269】Intersecting Lines

http://poj.org/problem?id=1269真是个令人忧桑的故事。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r

2015-03-10 17:41:02 371

原创【计算几何】【poj 3304】Segments

http://poj.org/problem?id=3304QwQ 蒟蒻一直不会计算几何各种版的混搭。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#de

2015-03-10 16:30:07 408

原创【bzoj 2521】: [Shoi2010]最小生成树

http://www.lydsy.com/JudgeOnline/problem.php?id=2521艹艹艹，这么水的题wa了三次原来是饿dinic写错了！！！！！bfs开头三句！！！！！两条枚举边判断两句！！！！！#include #include #include #include #include #include using namespa

2015-03-10 10:06:27 847

原创【2013-5】 day2 一系列生成树问题

QwQ没题解，只能自己瞎bb了Problem 1对边排序，从小到大依次加入1.该边权加完了之后此边仍为割边2.改边权加之前此边为割边3.改边权加之前此边为非割边怎么实现呢、？2、3.直接用并查集即可1.估计要树链剖分才行0.0也可以参见http://blog.csdn.net/willinglive/article/details/4287177

2015-03-10 08:30:40 606

原创【Plan 第五场】

超级大滚粗，不想说了。。。A第一眼：nima这不裸的最大全闭合子图么然后就进坑了。。。。。。。。。。再也没跳出来经vfk认证，此方法转化为了一个NPC问题，因此，如果“最大获利”问题的代价和收益反过来的话就不可做，除非是二分图。。。二分图：http://blog.csdn.net/willinglive/article/details/42234539要是想

2015-03-09 21:39:52 381

原创【Plan 第四场】

题目：见2013-5 day2QAQ大滚粗。。。A对于30%的数据，是bzoj1016的加强版，我太弱了只会这个。。。满分算法待研究。。。#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l)

2015-03-07 12:29:14 418

原创【数位DP】【HDU 4507】吉哥系列故事——恨7不成妻

http://acm.hdu.edu.cn/showproblem.php?pid=4507无聊写个水DP#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#defi

2015-03-06 11:13:05 443

由于第二场太水，故不放上来题目：见2013-5 day1A显然是网络流，如何建图是关键我的想法是S->1->2->T，对所有的1拆点这样是错的，我当场wa掉错误的原因我还没见过——部分流量对整体流量的影响问题，也就是说部分流量是没用的，我们只关心整体的时候maxflow可能是多个部分的感觉这个错误很难发现，只有调试大数据的时候才会发现我说不清楚，看代码就知道，尤其是我最后判断flow==2的时候很明显

2015-03-06 09:48:35 375

原创【EXKMP】【2015-2】day13 T1

一道非常好的DP题！可惜我没背下exkmp的模板#include #include #include #include #include #include using namespace std;#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)#define per(i,r,l) for(int i=(r),_=(l)

2015-03-05 20:02:11 572

迷你C++ 6.0版本

分享100个漂亮的图标图标

空空如也