5 Zarxdy34

尚未进行身份认证

暂无相关简介

等级
TA的排名 22w+

SRM 635 DIV2

准备了很长时间期末考结果还是萎掉了......技术考了年级400名......【250 IdentifyingWood】一遍找过去就好了...#include #include #include #include #include #include #include #include #include #include #include #include

2015-06-30 21:56:30

POJ1836【Romania OI 2002】Alignment

题目链接:http://poj.org/problem?id=1836【分析】    两次LIS,中间允许相等。可以nlogn但我懒得写了。【代码】#include #include #include using namespace std;const int maxn=1010;const double eps=1e-8;double h[maxn]

2015-05-23 14:06:24

POJ1789【CTU Open 2003】Truck History

题目链接:http://poj.org/problem?id=1789【分析】    最小生成树不解释。【代码】#include #include using namespace std;const int maxn=2010,inf=~0U>>1;char s[maxn][10];int dist[maxn][maxn],d[maxn],vis[max

2015-05-23 13:14:58

POJ2274【CEOI2003】The Race

题目链接:http://poj.org/problem?id=2274【分析】    第一问逆序对,树状数组或者归并排序随便过...    第二问堆维护。考虑到如果有三辆车a,b,c,a在b的前面,b在c的前面,后来a超过了c,那么之前要么b先超过了c,要么a先超过了b。也就是说只有位置相邻的车才有可能发生较早的超车。然后堆维护一下就好了。    PS:拍了三个晚上的第二问

2015-05-23 10:47:56

POJ3020 Antenna Placement

题目链接:http://poj.org/problem?id=3020【分析】    这道题可以用很多算法搞过去。    可以写二分图或者轮廓线DP,蒟蒻表示太弱写不来二分图就去写轮廓线DP了。    裸的二分图、裸的轮廓线也就没什么好说的了......注意数组的初始化(前几篇博文提到遇多组数据初始化死,果然这次又WA在这了)。【代码】#include #

2015-05-16 13:46:05

POJ1416 Shredding Company

题目链接:http://poj.org/problem?id=1416【分析】    水题不多说......直接暴力。【代码】#include #include #include using namespace std;int a[8],v[8][8];int n,target,num;int d[8],fnd[8],fp;int ans,ansti

2015-05-16 13:43:50

BZOJ2301【HAOI2011】Problem b

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2301【分析】    这题用的是莫比乌斯反演,于是乎蒟蒻去看PoPoQQQ大神的PPT学了一下莫比乌斯反演。    将问题转化为1    设f(i)表示gcd(x,y)=i的数对个数,F(i)表示i|gcd(x,y)的数对个数,则有    然后就可以得到   

2015-05-14 21:07:21

BZOJ1004【HNOI2008】Cards

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1004【分析】    首先这是个置换群。由于之前没学过置换群于是去补了一下。主要是Burnside引理与Polya定理,由于太弱看了很久。    然后就可以开始应用了,但是由于有颜色数量限制不能直接使用Polya定理,需要用Burnside引理并且有比较深刻的理解。大概就

2015-05-06 19:14:36

BZOJ1059【ZJOI2007】矩阵游戏

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1059【分析】    格子是可以随意变换的,但是原来同行或同列的格子无论怎么变换还是同行同列的。    那么就分行和列做一个二分图匹配,完美匹配时关卡有解。    每次做这种题目都会忘了把图重新初始化...【代码】#include #include

2015-05-02 01:15:43

BZOJ3207 花神的嘲讽计划Ⅰ

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3207【分析】    如果不是看标签做的真以为要用什么高贵的数据结构...    就是随便哈希一下,然后再找一下就好了。【代码】#include #include using namespace std;typedef long long LL;c

2015-05-02 00:35:44

BZOJ4010【HNOI2005】菜肴制作

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4010【分析】    这应该比较明显是个拓扑排序。    序号小的要放前面,但是会受到后面很多菜的限制。其实序号小的优先考虑和序号大的最后考虑应该是差不多的。(不知道科不科学,求大神指正)    把图中的边全部反向,拓扑+堆维护剩下的节点中度为0且序号最大的。把得到的

2015-05-01 23:06:42

BZOJ3144【HNOI2013】切糕

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3144【分析】    所有人都说这是个经典的最小割模型......蒟蒻泪流满面......    建一个r+1层的,每层都是p*q的图,从源出发向第一层连inf的边,从第r+1层上每个点出发向汇连inf的边,对i,j,k与i,j,k+1之间连v(i,j,k)的边。 

2015-04-25 17:45:55

UOJ#14【UER#1】DZY Loves Graph

题目链接:http://uoj.ac/problem/14【分析】    先请允许我诚意地orz DZY神犇...    UOJ的题解真的很良心...http://vfleaking.blog.uoj.ac/blog/15    主要内容就是一个按秩合并的并查集,支持删边加边。在没有Return操作的情况下,这么做是nlogn的,已经足够了,但是有Return操作,在删完大

2015-04-25 14:15:01

STL 自定义比较函数

以priority_queue为例。    如果我要写一个元素类型为整型的大根堆,那么直接用STL的优先队列就可以了。#include #include using namespace std;priority_queue Q;int main(){ Q.push(1); printf("%d\n",Q.top()); Q.pop(); return 0;}

2015-04-25 10:46:06

UOJ#13【UER#1】跳蚤OS

题目链接:http://uoj.ac/problem/13【分析】    建一棵Trie树,然后基本上就是一个裸的Trie了,记录一下父亲节点和是否是快捷方式即可。【代码】#include #include using namespace std;const int maxn=500010,inf=~0U>>1;struct Trie{ int ch[

2015-04-25 09:56:09

UOJ#12【UER#1】猜数

题目链接:http://uoj.ac/problem/12【分析】    良心题。显然a+b的最大值是g+l。由于n是完全平方数,最小值就是2√n。    据说double精度不够直接开根会爆掉...long double就可以了...【代码】#include #include using namespace std;typedef long long L

2015-04-25 09:26:10

BZOJ1207【HNOI2004】打地鼠

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1207【分析】    显然的动规...不要害怕10000的数据范围,n^2还是可以很轻松地过掉的。    三个小优化:1.决策从i-1到1枚举 2.状态转移时先判断f[j]>=f[i] 3.记录前i个f的最大值mx[i],如果f[i]>mx[j]那么决策1..j就不需要考

2015-04-18 15:18:00

BZOJ1492【NOI2007】货币兑换

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1492【分析】首先要利用一个贪心的思想,就是在同一天要么把钱全部换成金劵,要么把金劵全部换成钱。因为如果当天换钱或换金劵有利润,那么就全换掉,没有利润就不换。于是设f[i]为第i天能得到的最多的钱,x[i]与y[i]分别表示用第i天换来的钱全部换取A、B劵的数量,那么有f

2015-04-18 13:47:17

BZOJ3856 Monster

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3856【分析】大水题...但是如果做的时候不思考仔细一点会贡献大量的AC率...人能打死喵的三个条件:1.OTK 2.第k回合打死 3.第k+1回合喵回血后的血量低于初始血量【代码】#include using namespace std;typede

2015-04-17 09:52:25

BZOJ1052【HAOI2007】覆盖问题

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1052【分析】先扫出覆盖所有点的最小矩形,那么放置的正方形的顶点与该矩形的顶点重合时最优。剩下的两个正方形也用同样的办法放,枚举重合的四个顶点。二分正方形的边长,检查是否可行即可。【代码】#include #include using namesp

2015-04-11 09:56:29

查看更多

勋章 我的勋章
    暂无奖章