Zarxdy34-CSDN博客

原创 SRM 635 DIV2

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

2015-06-30 21:56:30 702

原创 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 1140

原创 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 648

原创 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 693

原创 POJ3020 Antenna Placement

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

2015-05-16 13:46:05 488

原创 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 660

原创 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 495

原创 BZOJ1004【HNOI2008】Cards

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

2015-05-06 19:14:36 546

原创 BZOJ1059【ZJOI2007】矩阵游戏

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

2015-05-02 01:15:43 523

原创 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 548

原创 BZOJ4010【HNOI2005】菜肴制作

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

2015-05-01 23:06:42 804

原创 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 1833 1

原创 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 927

原创 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 791

原创 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 645

原创 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 671

原创 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 625

原创 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 556

原创 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 840

原创 BZOJ1052【HAOI2007】覆盖问题

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

2015-04-11 09:56:29 771

原创 BZOJ1028【JSOI2007】麻将

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1028【分析】枚举加上的那张等待牌。统计出每个序数相同的牌的数量，然后按序数从小到大分牌。对于序数相同的牌，先考虑刻子（3个相同），然后剩下的牌按顺子分掉，分不掉就说明当前牌不是听牌。简略的证明：3个顺子即3个刻子，所以优先考虑刻子；如果前面的牌都分完了，当前要分的同

2015-04-11 09:36:44 713

原创 BZOJ1007【HNOI2008】水平可见直线

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1007【分析】先按直线的斜率排好序。斜率相同的直线只有截距最大的那个可见。然后记录一个栈，以及一个数组D[i]记录位于栈中的第i条直线与栈中第i-1条直线交点的横坐标。（以斜率从小到大排序为例，那么栈中第i条直线可见部分仅在x>D[i]处）如果当前加入的直线与栈顶直线的交点横

2015-03-26 19:27:12 597

原创 BZOJ1503【NOI2004】郁闷的出纳员

郁闷的出纳员【问题描述】OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很

2015-03-21 11:01:54 632 1

Zarxdy34