第一题:太鼓达人:BZOJ3033 题意:给出k,求一个最长的M位01串,使其从每一个位置向后走k个得到 的M个k位01串互不相同(最后一个和第一个相邻,即是一个环).输出 字典序最小的答案. 2 ≤ k ≤ 11. 结论+爆搜: 第二问我们将每个k二进制数看成一个点,在它后面加上0/1就能得 到两个新数,我们从这个数向两个新数连边,于是这就变成了求一个欧 拉回路的问题.显然此题是存在欧拉回路的第一问答案为2的k次方 ,第二问暴力求欧拉回路即可. 发现sjh的注释很详细,所以贿赂搞来了一个满满注

题意:       给你一个集合,然后有如下输入,a ,b ,c表示在范围[a,b]里面有至少有c个元素,最后问你整个集合最少多少个元素. 思路:       和HDU1384一模一样,首先这个题目可以用差分约束来解决,是大于等于所以跑最长路(如果非要跑最短路建-权也可以),说下建图,首先我们把每个区间抽象出来,区间的两个端点之间的元素个数 [a ,b] = c 可以抽象成 点a,和点(b + 1)之间的距离 大于等于c,那么这样就可以把输入建进去了,还有个关键的地方就是题目的隐含条件,一般的查

转自:http://blog.csdn.net/shahdza/article/details/7779273 最短路 [HDU] 1548 A strange lift基础最短路(或bfs)★2544 最短路 基础最短路★3790 最短路径问题基础最短路★2066 一个人的旅行基础最短路(多源多汇,可以建立超级源点和终点)★2112 HDU Today基础最短路★1874 畅通工程续基础最短路★1217 Arbitrage 货币交换 Floyd (或者 Bellman-Ford 判环)★124

先更新第一个做法:差分约束 转化成最长路,求出的每一个解是满足差分方程的最小值 spfa求最短路 对于边(x->y) 有: if(dis[y] > dis[x] + a[i].d) dis[y]=dis[x]+a[i].d; dis[y]的初始值为INF,dis[y]会是满足所有约束条件之中所有可能的值之中最大的(更新到最大的就不会再更新了). 贴一个简略的证明: 同理,最长路求出来的是所有可能解之中最大的. 这题是字典序最小,那么我们要转化成最长路来求,求到的每个s[i]都是可能的值中最小的

出处:http://blog.csdn.net/shahdza/article/details/7779273 最短路 [HDU] 1548    A strange lift基础最短路(或bfs)★ 2544    最短路  基础最短路★ 3790    最短路径问题基础最短路★ 2066    一个人的旅行基础最短路(多源多汇,可以建立超级源点和终点)★ 2112    HDU Today基础最短路★ 1874    畅通工程续基础最短路★ 1217    Arbitrage   货币交换

题目链接:http://poj.org/problem?id=3159 题意:有n个小孩,m个关系格式是A B C 表示小孩 B 的糖果数最多比小孩A多C个,相当于B-A<=C; 有m个这样的关系最后求小孩n比小孩1最多多几个糖果: 差分约束: 比如给出三个不等式,b-a<=k1,c-b<=k2,c-a<=k3,求出c-a的最大值, 我们可以把a,b,c转换成三个点,k1,k2,k3是边上的权,如图   由题我们可以得知,这个有向图中,由题b-a<=k1,c-b<=k2

题意(真坑):傻国王只会求和,以及比较大小.阴谋家们想推翻他,于是想坑他,上交了一串长度为n的序列a[1],a[2]...a[n],国王作出m条形如(a[si]+a[si+1]+...+a[si+ni])>k(或<k)的批示,结果发现批错了,问是否存在一个满足不等式组的序列a[1]...a[n],好让国王借口自己看错了. 因为是求是否存在,即判环,没有要求最大还是最小,所以最长路.最短路都可以解决. 注意: 1.总点数,若不加源点而采用把所有点入队,总点数==n+1:否则,总点数==n+2.这

做的第一道差分约束的题目,思考了一天,终于把差分约束弄懂了O(∩_∩)O哈哈~ 题意(略坑):三元组{ai,bi,ci},表示区间[ai,bi]上至少要有ci个数字相同,其实就是说,在区间[0,50000]上,每一个三元组表示[ai,bi]之间至少要标记ci个数字,问至少要标记多少个数字. 在学习差分约束的童鞋,建议看一下:09年姜碧野的<SPFA算法的优化及应用>,06年冯威的<浅析差分约束系统>,不过后者看起来较难搞懂,也可以看http://ycool.com/post/m2u

对于一个有向带权图,进行一种操作(v,d),对以点v为终点的边的权值-d,对以点v为起点的边的权值+d.现在给出一个有向带权图,为能否经过一系列的(v,d)操作使图上的每一条边的权值为正,若能,求最小边权的最大值. 不得不说,图论与动态规划的产物实在是神奇!! 1.既然是“最小值最大”问题,容易想到二分答案. 2.抽象出数学模型.这个在<训练指南>里写得已经很详细,鄙人还是以自己的理解表达一下. 这里有两处特别值得学习的地方.一.叠加:假设每个点都对应着一个(v,d)操作,那么对于边u->

http://www.cnblogs.com/wangfang20/p/3196858.html 题意: 求集合Z中至少要包含多少个元素才能是每个区间[ai,bi]中的元素与Z中的元素重合个数为ci. 思路:对于dis[b]-dis[a]>=c的形式,我们建一条a到b的边,权值为c,最后求最长路就是要得到的最小值. 可举一例,[1,8]假使有7个不同的数,[1,4]假使有2个不同的数,[4,8]假使有3个不同的数,都满足f[8]-f[1]>=7,f[4]-f[1]>=2,f[8]-f[4

题目:http://poj.org/problem?id=1201 题意:给定n组数据,每组有ai,bi,ci,要求在区间[ai,bi]内至少找ci个数, 并使得找的数字组成的数组Z的长度最小. #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; <<;

分析:设每个人的糖果数量是a[i] 最终就是求a[n]-a[1]的最大值 然后给出m个关系 u,v,c 表示a[u]+c>=a[v] 就是a[v]-a[u]<=c 所以对于这种情况,按照u,v,c建单向边,一条从1到n的路径就是一个关于1和n的推广不等式a[n]-a[1]<=k(k为这条路的权) 所以找到所有不等式中最小k,就是求1到n的最短路,这就是差分约束 然后上代码: #include<cstdio> #include<cstring> #include&l

Layout   Description Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they

http://poj.org/problem?id=1201 题意:给出N个整数区间[ai,bi],并且给出一个约束ci,( 1<= ci <= bi-ai+1),使得数组Z在区间[ai,bj]的个数>= ci个,求出数组Z的最小长度. 思路:建立差分约束系统.因为这里要求数组长度的最小值,要变为 x-y>=k的标准形式. 设数组 s[j] 表示数组 Z 区间[0,j]里包含的元素个数.所以 s[bi+1] - s[ai] >= ci,注意是 j+1, 隐含条件   0 &l

题目大意:给N个小屁孩分糖果,每个小屁孩都有一个期望,比如A最多比B多C个,再多了就不行了,会打架的,求N最多比1多几块糖 分析:就是求一个极小极大值...试试看 这里需要用到一个查分约束的东西 下面是查分约束详解: 一直不知道差分约束是什么类型题目,最近在写最短路问题就顺带看了下,原来就是给出一些形如x-y<=b不等式的约束,问你是否满足有解的问题 好神奇的是这类问题竟然可以转换成图论里的最短路径问题,下面开始详细介绍下 比如给出三个不等式,b-a<=k1,c-b<=k2,c-a<

Problem Description You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.Write a program that:> reads the number of intervals, their endpoints and integers c1, ..., cn from the standard input,> computes the minimal size of a

转载请注明出处: http://www.cnblogs.com/fraud/          ——by fraud 题意:一商店二十四小时营业,但每个时间段需求的出纳员不同,现有n个人申请这份工作,其可以从固定时间t连续工作八个小时,问在满足需求的情况下最小需要多少个出纳 一道十分经典的差分约束题目,在构图上稍有难度 为避免负数,时间计数1-24. 令: r[i]表示i时间需要的人数 (1<=i<=24) num[i]表示i时间应聘的人数 (1<=i<=24) x[i]表示i时间

结题报告合集请戳:http://972169909-qq-com.iteye.com/blog/1185527 /*题意:求符合题意的最小集合的元素个数 题目要求的是求的最短路, 则对于 不等式 f(b)-f(a)>=c,建立 一条 b 到 a 的边 权值为 c,则求的最长路 即为 最小值(集合) 并且有隐含条件:0<=f(a)-f(a-1)<=1 则有边权关系(a,a-1,0)以及(a-1,a,-1); 将源点到各点的距离初始化为INF(无穷大),其中之1为0,最终求出的最短路满足 它

出纳员的雇佣 Tehran的一家每天24小时营业的超市,需要一批出纳员来满足它的需要.超市经理雇佣你来帮他解决问题:超市在每天的不同时段需要不同数目的出纳员(例如:午夜时只需一小批,而下午则需要很多)来为顾客提供优质服务.他希望雇佣最少数目的出纳员.经理已经提供你一天的每一小时需要出纳员的最少数量--R(0), R(1), ..., R(23).R(0)表示从午夜到上午1:00需要出纳员的最少数目,R(1)表示上午1:00到2:00之间需要的,等等.每一天,这些数据都是相同的.有N人申请这项工作

BZOJ_2788_[Poi2012]Festival_差分约束+tarjan+floyed Description 有n个正整数X1,X2,...,Xn,再给出m1+m2个限制条件,限制分为两类: 1. 给出a,b (1<=a,b<=n),要求满足Xa + 1 = Xb 2. 给出c,d (1<=c,d<=n),要求满足Xc <= Xd 在满足所有限制的条件下,求集合{Xi}大小的最大值. Input 第一行三个正整数n, m1, m2 (2<=n<=600,

During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared t