- 博客(39)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #375 (Div. 2) F. st-Spanning Tree
题目链接：点击打开链接题意：给出无向图n个点，m条边 (2 ≤ n ≤ 200 000, 1 ≤ m ≤ min(400 000, n·(n - 1) / 2)) 找出一个生成树，使得s点的度不超过ds，t点的度不超过dt;解：数据分别是20w和40w,又是找生成树，显然是kurskal。首先，我们先不管s和t点，把其他点弄成生成树再说。然后，我们再考虑s点和t点与其他点的
2016-11-04 15:47:46
251
原创 Codeforces Round #375 (Div. 2) E
题目链接：点击打开链接题意：给出一个无向图，然后，要求变成一个有向图，使得出度==入度的点最多。输出一种方案。解：根据欧拉回路的一些推论；显然，原图为无向图，度为偶数的点都是可以的，度为奇数的点不能。那么，要找一个方案，我们可以把奇数度的点变成偶数度，即添加一个点s和所有的奇数度的点连边。然后，对于这个构成的“无向图”，找欧拉回路，肯定所有的点都能被包含。（自己看欧拉回路推论）
2016-11-04 15:36:24
365
原创 HDU3911 Black And White（黑白子）
题意：给一行棋子（只有黑色和白色，1为黑，0为白），长度为100000。有m个操作，x,l,r 若x==0，查询(l,r)区间内连续的黑棋最大数量，若x==1，翻转（l,r）区间。#include #includeusing namespace std;#define maxn 500001int n,m,a[maxn];int max(int x,int y,int z){
2015-11-06 14:40:53
387
原创 HDU 1078 FatMouse and Cheese(记忆化搜索)
题意：老鼠从（0,0）点走，每次最多可以走k步（只能水平或垂直地走），且下一个点的价值比当前点的价值大。求他得到的价值最大为多少。#include #include #include #include #include #include #include #include #include #include using namespace std;#define maxn
2015-10-05 21:49:25
297
原创 CodeForces 579C A Problem about Polyline[数学]
题意： 一条过点(0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....的折线，再给出点(a,b)，问经过点(a,b)的折线中，x最小是多少？如果没有折线经过(a, b)则输出-1。答案精确到小数点后9位。思路：‘/’ 方程式：y=x-2*k*x0 '\'方程式：y=
2015-09-22 09:46:27
466
原创 杨辉三角求二项式分布
预处理杨辉三角，保存到C[][]数组中，c[n][m]就表示随机地从n个数中选M个。 1193: 教师节的礼物Time Limit:1000MS Memory Limit:65536KBTotal Submit:38 Accepted:6 Page View:19Submit Status DiscussDescription又到了一年一度的
2015-09-15 09:01:52
766
原创 华哥倒酒（二分答案）
今天华哥请吃饭，待会儿打完比赛不要跑了。 华哥现在已经去饭店了，他在桌子上整齐地摆放了n个空酒杯，编号为i酒杯的容量为ri。他有m条理（jie）由（kou）要往某写杯子里加酒。第j条理由是往编号为sj到编号为tj的杯子中倒入dj的酒。但是华哥并被注意到，在他祭出他的某条理由后，有些杯子中的酒就会漫出来！（已经倒入的酒的量大于了杯子的容量）然而，猥（ji）琐（zhi）的上决╇ф早已经看穿了这一
2015-09-14 13:06:27
2768
原创 UVA 11324 The Largest Clique （拆点+KM）
题意：有n个盒子，围城一个环，每个盒子里可能有糖果或无糖果，总糖果不超过N，要求，把盒子中糖果数超过1的移到无糖果的盒子中，问最少几步。分析：把有糖果数为val的盒子，拆成val个装一个糖果的盒子，编号num1从1开始累加，但他们在同一点。然后就是与每个盒子匹配，用km，这里要求最少几步，就拿距离来建图。w[i][j] 表示第i个糖果的盒子，到第j个盒子的距离，由于是求最少，那么w[i][
2015-09-09 20:56:34
290
原创 UVA 11324 The Largest Clique(tarjan有向图强连通+缩点)
题意：给出一个有向图，问最多能有多少点能构成一个集合，这个集合性质是任意两点能相互到达，即u->v or v->y.分析：任意两点能互相到达，而且是有向图，很容易想到是强连通。要使这个集合中的点最多，仅一个强连通分量肯定不行，可由多个强连通分量构成. 那么求出各个强连通分量后，缩点，然后深搜一次，找出最大点集。#include #include #include #include
2015-09-08 20:53:48
335
原创 HDU 3394 Railway
题意：给一个无向图。如果至少有两个环共用了一些边，那么这些边被认为是“冲突边”。如果一些边不在任何一个环中，这些边被认为是“多余边”。你要找出这个图中有多少“多余边”和“冲突边”然后输出条数。另外这图不一定是连通的，无重边和自环。分析：冲突边：就是找一个点双连通分量，如果此连通分量边数>点数 ，则边数为ans。多余边：桥。#include #include #include #inc
2015-09-07 19:14:21
482
原创 HDU 4587 TWO NODES(割点，连通块，枚举)
题意：给出一个无向图，删除两个点让剩余的图的连通分量的数量最大。思路：先枚举删哪个点，删了后会分成1个或多个连通块。在这些连通块中，考虑再次要删的点，当然是删割点最优啊。删除一个点后，跑cut_bri()的时候记录连通块个数，同时记录其中割点，注意重边#include #include #include #include #include #include #include #i
2015-08-27 20:19:57
365
原创 Gym 100712H Bridges(桥+缩点+树的直径)
题意：给一个连通图，无重边，求增加一条边的最少桥的数量分析：先把桥的总数算出，并标记哪些边是桥，然后通过缩点，生成一个只有桥的图。要想使得更多的桥变成非桥，那么在桥的图中就把最长的跳路径首尾相连就可以了。我们可以算出桥的图的直径，所以最后结果为桥的总数-直径。树的直径求法：以任意点开始bfs找到最长的点，这个点必为直径的一个端点，然后以这个点作为起点再次bfs，找到的最远的点的距离就是直径
2015-08-17 20:56:27
420
原创 hdu 5360 Hiking 多校6 优先队列
题意：给定n个人，现在要邀请这些人去远足，但每个人同意邀请的条件是当前已经同意去远足的人数c必须满足c>=l[i]&&ci，问你邀请的顺序是什么才能使尽可能多的人去远足，若有多个最优解，输出任意的一个。 思路：很容易想到，在左值满足的情况下找最小的右值。但是N#include #include #include #include #include #include #inclu
2015-08-12 11:38:38
257
原创 CodeForces 527C Glass Carving(multiset)
题意：给你一个w*h 的玻璃，有n个操作，在第几行画线或者在第几列划线分层小块，每次操作后问小块中的最大面积分析：multiset H,v,a1,a2; H是存的划线的高度的id，v的每次画竖线的id。a1存H的差值，a2存v的差值#include #include #include #include #include #include #include #include
2015-08-10 09:57:47
480
原创 HDU 5316 Magician（线段树 区间合并）
题意：给你n（n分析：最初没读懂题意。。。。 一看数据范围和查询方式，肯定和线段树相关，问题的要求又有点像DP。分析知道，其实就是求线段树的区间合并问题，取出的序列只可能是以奇数开头奇数结尾，奇数开头偶数结尾，偶数开头偶数结尾，偶数开头奇数结尾。用jj,jo,oo,oj表示。当合并的适合考虑这四种情况就是可以了。jj=max(l.jj ，r.jj, l.jj+r.oj, l.jo+r
2015-08-08 08:14:11
365
原创 CodeForces 195B After Training（STL）
题意：有n个球，m个篮子， 要把这n个球放进这些篮子，首先放篮子中求最少的篮子，若数量相同再放距离中间篮子最近的，若距离相同放篮子编号小的。分析：这道题可以用线段树，set，优先队列 都可以搞 #include #include #include #include #include #include #include #include #include #includ
2015-08-07 15:39:08
382
原创 codeforce 567c Geometric Progression（map）
题意：给 n(2*10^5)个数，取出三个数Ni,Nj,Nq,(1分析：枚举中值，用map暴力，之前用map用的少，现在写一发。#include #include #include #include #include #include #include #include #include #include #include using names
2015-08-06 09:31:29
510
原创 hdu1150 Machine Schedule(最小点覆盖)
#include #include #include #include #include #include #include #include #include #include #include using namespace std;/* 题意：有2台机器加工零件，第一台有n种工作模式（n0,n1,n2...），第二台有m种工作模式（M0,M1,M2...）初始状
2015-08-01 10:31:20
417
原创 Segment set（普通并查集+计算几何两线段相交与否）
hdu1558 判断两线段相不相交贴的模板，暂时没搞懂#include #include #include #include #include #include #include #include #include #include #include using namespace std;int f[1001];typedef struct point{
2015-07-31 16:56:15
291
原创 A Bug's Life（带权并查集）
hdu1829 这是一道比较简单 好理解的并查集#include #include #include #include #include #include #include #include #include #include #include using namespace std;int f[2001],r[2001];int n,k;int findfa(in
2015-07-31 16:52:25
349
原创 食物链（带权并查集）
Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。 此人对N个动物，用
2015-07-31 16:45:43
282
原创 HDU1828 Picture 周长并 线扫描
题意：给出n个矩形，求他们的轮廓的周长. 以这个图为例 我们只看红色的（横线）不看竖线，他讲的是只扫描一次的做法。 第一次求出的部分是第一次覆盖的长度。 第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的 长度,插入第二条横线后，得到的总的长度-之前总的长度 第三次因为是矩形的上边,是出边，该线段的标记c
2015-07-29 09:46:38
305
原创 HUD 1255 面积覆盖 线扫描
求面积交#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define maxn 11005struct line{ double x1,x2,h; int c;
2015-07-29 09:18:26
237
原创 HDU1542 Atlantis(面积并)
题意：给出n个矩形的 左下角和右上角坐标，计算他们覆盖的面积。#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define maxn 11005struct line{
2015-07-29 08:59:24
309
原创 HDU3746 Cyclic Nacklace(KMP_Next的应用)
题意：给一个字符串，求再在后面添加几个字符串可以使得整个字符串循环。#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define maxn 200000+5int Next[ma
2015-07-27 21:11:28
271
原创 HGU3336 Count the string (KMP Next数组的应用)
题意：给出一个字符串，求它所有前缀在此字符串中出现的次数。分析：一看，肯定是kmp中 next[i] 求以下标i-1结尾的字符串，使得最长的（前缀==后缀）的长度。很好想到，当next非零时，肯定和前缀有匹配，自然ans+1。当一个前缀出现多次，当next[j]!=0,ans+1,j=next[j],一直往前跳，直到next[j]为0，如果不为0，ans+1。这里比较难理解，next[i]表示
2015-07-27 11:01:07
320
原创 Simpsons’ Hidden Talents（KMPnext[]的应用）
题意：给两个字符串，求最大的第一字符串的前缀等于第二个字符串的后缀分析：先把两个字符串连接起来，再求出Next[]。这样next[]数组的最后一位存的就是ans.但是要考虑两个字符串求前后缀发生越界的情况，如图，假如这种情况，两个字符串发生了越界,。此时l1~r1==l2~r2,l1~z1==l2~z2,l2~z2==z3~r2。同时，z2~r1肯定等于z3~r2。=>l1~z1==z3~
2015-07-25 09:26:51
255
原创 KMP模板
#include #include#includeusing namespace std;char s[1000001];int next[10005];//next[i] 0-i字符串最大匹配数/** next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1]* next[i]为满足x[i-z...i-1]=x[0...z-1]的
2015-07-25 09:20:56
231
原创 UVA11997 K Smallest Sums（并归，优先队列）
题意：有k行数，每行k个数，从每行中抽出一个数，相加得到sum, 求这样的sum的前k小数，并输出。分析：大白书（刘汝佳 著）优先队列章节，假设现在有两行A,B（从小到大排序），求前k小,则：A1+B1A2+B1A3+B1........... 用一个优先队列来维护前k小的值，先把（A1+B1），（A2+B1），（A3+B1）...放入队列，但这k个数不一定是前k
2015-07-23 23:07:54
366
原创 SPOJ GCPC11J Time to live（求一棵树的直径（两个BFS））
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83468#problem/D题意：给出一棵树，让你找出一个节点，使得所有点到这个节点的最大距离最小分析：可以想到，若是找到这棵树的最大深度length，再除2,即是结果,若是length是奇数，ans+1; 也可以 (length+1)/2,不管奇数偶数。#include #
2015-07-21 23:04:51
513
转载 POJ 1185 炮兵阵地（状态压缩dp）
1. 为何状态压缩： 棋盘规模为n*m，且m≤10，如果用一个int表示一行上棋子的状态，足以表示m≤10所要求的范围。故想到用int s[num]。至于开多大的数组，可以自己用DFS搜索试试看；也可以遍历0~2^m-1，对每个数值的二进制表示进行检查；也可以用数学方法（？） 2. 如何构造状态： 当然，在此之前首先要想到用DP（？）。之后，才考虑去构造
2015-07-21 20:39:51
325
原创 HDU 1281 棋盘游戏（二分匹配，关键点）
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=69427#problem/EDescription小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能
2015-07-21 15:47:43
411
原创 HDU 3530 Subsequence（单调队列维护）
题意：给n个数的序列，子序列（连续的，题意描述得不是很清楚），要求它的子序列 m分析：和这道题类似POJ 2823Sliding Window分析题意可知，其实就是求一个区间它的最值满足该条件，且该区间最长，则用两个单调队列维护此时序列的最大值q1和最小值q2。现态假设 m加入下列一个点：①该点加入两个队列后会不会存在 q1-q2q1
2015-07-21 10:14:58
451
原创 基因匹配Match(最长公共子序列) NlongN
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82285#problem/F题意：两个串，求最长公共子序列，有n个数，每个数都出现5次。设为a串和b串 分析：首先n。 我们可以把a串作为模式串，b串作为查找串。由于这里每个数只有5次，我们可以先存下a串中的每个数在b串中的5个数的位置,用f[a[i]][j]
2015-07-18 21:19:29
1359
原创 A==B?（java大数做高精度）
import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;public class MyMain { public static void main(String args[]) { Scanner sc=new Scanner(System.in); wh
2015-07-18 10:20:56
372
原创 UVA 10635 Prince and Princess(最长上升子序列)
题意：有n*n的格子用1-n*n不同的数表示，第一个人输入p+1长度的数，第二个人输入q+1个不同的数，问他们最长公共子序列最长是多长。 分析：由于(0那么怎么求这个最长上升子序列呢？假设求1,4,6,3,5,7，最长上升子序列dp[i]:表示长度为i,最小的那个数①加入1，dp[1]=1;②加入4，dp[2]=4;③加入6，dp[3]=6;④加入3，dp[2]=3;⑤加入5，dp
2015-07-17 22:43:38
416
原创 志愿者选拔（单调队列）
Description世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。 参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。 面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等） 作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个
2015-07-16 20:40:03
435
原创 简单BFS ZOJ 1649 Rescue
题意：r->a用时最少，经过'x'需2s,经过'.'1s.思路：用BFS，但是，显然，走的步数少并不代表用的时间少。因此，标记走到每个点用的最少时间，若下次要走到该点，必须比该点用时更少（同时更新该点）。#include #include #include #include #include #include #include #include #include #inclu
2015-07-15 17:06:32
376
原创 二进制暴力
CF:550B题意：输入n,l,r,x,再输入n个数，在这n个数中任意选其中某些数相加和为sum,要求sum>=l&&sum=x#include #include#include#include#include#includeusing namespace std;#define inff 1000000000int main(){ int c
2015-06-07 09:51:22
415
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人