- 博客(108)
- 收藏
- 关注
RSS订阅原创 HDU 5360 Hiking (贪心+优先队列)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5360题意：要去旅游有n个人，第i个人接受邀请最少要Li个人已接受邀请，且不能超过Ri个人已接受，问最优邀请方案使得最多人去思路：很容易想到贪心，从满足Li条件的人中选取Ri最小的人邀请，可以每次将满足条件的人进入优先队列，每次去队首就可以了#include
2016-06-02 12:29:05
392
原创 Codeforces 622C Not Equal on a Segment
题目链接：http://codeforces.com/problemset/problem/622/C题意：给出一个大小为n的序列，给出一个区间[l,r]和c要求找出一个该区间内和c不一样的数，没有则输出-1思路：将序列中相邻的数合并，因为是找不同的数，所以时间一下就得到了优化……#include #include #include #include u
2016-06-02 12:18:19
325
原创 HDU 5363 Key Set
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5363题意：给出一个大小为n集合，问有多少子集合里数的和等于一个偶数思路：有n/2个偶数，n/2个奇数(设n是偶数)，可以选取的偶数一共有：C(n/2,0)+C(n/2,1)+……+C(n/2,2)=2^(n/2)种情况，而可以选取的奇数有:C(n/2,0)+C(n/2,2)+…
2016-05-31 20:16:52
307
原创 HDU 5344 MZL's xor
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5344题意：给出大小为n数组a，ai=(aj*m+z)%l （j=i-1，a0=0），数组b为所有的(ai+aj)，问b1^b2^b3……是多少思路：假设n=3，b1=(a1+a1),b2=(a1+a2),b3=(a1+a3),b4=(a2+a1),b5=(a2+a2),b6=(
2016-05-30 09:53:30
321
原创 Codeforces 609C Load Balancing
题目链接：http://codeforces.com/problemset/problem/609/C题意：将一个大小为n序列重新分配，将ai-1同时aj+1算一次操作，问要多少次操作后序列中min和max的差不大于1思路：一开始想了个很蠢的方法，各种wa，其实就只有2种情况，设平均值为x，要么把所有小于x的数变成x，要么把大于x+1的数变成x+1，分别计算这2中情况的操作
2016-05-29 21:07:18
337
原创 Codeforces 616D Longest k-Good Segment
题目链接：http://codeforces.com/problemset/problem/616/D题意： 给出一个序列，要求找出一个最大连续的子序列，要求子序列中不同的数不可以超过k思路：因为是连续的序列，所以可以用"移尺法"(听别人说的名字)，类似于维护一个符合题目要求的队列，这个方法似乎经常用到的，详细看代码#include #include #in
2016-05-29 20:48:16
402
原创 Codeforces 612C Replace To Make Regular Bracket Sequence
题目链接：http://codeforces.com/problemset/problem/612/C题意：有4对类型的括号，可以将左括号变成另一类型的左括号，可以将右括号变成另一类型的右括号，问最少变多少次可以括号可以匹配，不可以输出-1思路：利用栈做括号匹配就可以了，失配的时候将一个右括号转换下类型res++，最后栈清空了就匹配完成#include #include
2016-05-25 20:13:22
324
原创 Codeforces 610C Harmony Analysis(构造)
题目链接：http://codeforces.com/problemset/problem/610/C题意：‘+’代表1，‘*’代表-1，要求构造2^k个两两正交的串思路：k=1时，s[1][1]=‘+’ k=2时，s[2][1]., =s[2][2]=s[1][1]=‘+’
2016-05-24 21:24:02
557
原创 Codeforces 616C The Labyrinth
题目链接：http://codeforces.com/problemset/problem/616/C题意：给出n*m的矩阵，问和每一个‘*’连通的'.'有多少个(包括自己)思路：每一个'.'连通块分配一个编号并求出连通块大小，每一个'*'号加上四周的连通块就好，注意去重#include #include #include #inc
2016-05-24 20:26:02
417
原创 Codeforces 618C Constellation
题目链接：http://codeforces.com/problemset/problem/618/C题意：给出n个点，要求以这些点构造一个三角形，三角形的边不能有其他点，三角形内也不可以有其他点思路：用点的x坐标或者y坐标排序，以第一个和第二个点为三角形2个点，寻找第三个点，排序过后就排除了有其他点还在边上的情况了#include #in
2016-05-24 20:19:52
326
原创 Codeforces 620C Pearls in a Row(贪心)
题目链接：http://codeforces.com/problemset/problem/620/C题意：给出一个n大小的序列，截取一段，如果这一段有2个相同的数字，那么就是好的子序列，问最多有几个好子序列思路：从头开始遍历，碰到第一个出现2次的数字就把这段数字截取，我感觉第3个样例输出1 3，5 7应该也符合题意，但是wa了……注意的是LL要用map进行
2016-05-22 19:33:14
677
2
原创 Codeforces 623A Graph and String (构造)
题目链接：http://codeforces.com/problemset/problem/623/A题意：一个仅包含abc这3个字母的字符串，a与b和自身相连，b与ac和自身相连，c与b与自身相连，给出字符串每一位的相连情况，要求构造出这样一个字符串思路：b与ac和自己都相连，所以连有n-1个点的位置必定是b，其他的点我们找一点和与该点相连的点设为a，其他设为c，最后n^
2016-05-22 19:21:34
587
原创 HDU 5336 XYZ and Drops
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5336题意：有一个n*m的平面，平面上有若干个大小为1~4的水滴，当一个水滴碰到一个水珠后大小加1并且水珠消失，一旦水滴大小超过4之后会变成4个水珠向四个方向炸开，现在(x,y)有一个炸开的水滴，水珠1s移动一格且互不干扰，问t秒之后平面上的水滴状态思路：蛮简单的bfs，
2016-05-21 20:54:26
309
原创 HDU 5328 Problem Killer
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5328题意：给出一个序列，要求截取一段最长的等比或者等差数列思路：暴力预处理相邻的数的ap和gp，注意gp要用小数，遍历取最大就可以#include #include #include #include using namespace std;double
2016-05-21 20:43:55
530
原创 HDU 5327 Olympiad
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5327题意：一个数所有位的数字没有重复即是"漂亮的数"，问[L,R]里有几个这样的数思路：数据不大，暴力打表，比较无脑#include #include #include #include using namespace std;int num[1
2016-05-21 20:40:14
245
原创 HDU 5335 Walk Out
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5335题意：给出一个n*m的矩阵，都是由0和1组成，从(1,1)走到(n,m)，每一步的数字组成一个二进制数，问要如何走才可以使得这个数最小思路：前导0可以被省略，所以一开始可以向4个方向走，直到走到第一个1，走到第一个1后向左和向上走都会使得这个二进制数位数加一，这样一
2016-05-19 20:51:38
403
原创 HDU 5326 Work
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5326题意：有n个人，给出n-1个关系a b，表示a是b的直属上司，如果c是a的直属上司，我们可以认为c管理a和b共2人，问有多少人可以不多不少管理k个人思路：数据范围很少，没有环，直接建立一个邻接链表搜索每一个点即可#include #include
2016-05-17 12:20:52
249
原创 HDU 5319 Painter
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5319题意：给出一个n*m个格子，有2种刷子，红刷子只能画'\'，蓝刷子只能画‘/’，红和蓝涂在同一个格子会变成绿色，问最少要刷几次思路：暴力每一个格子，如果s[i][j]是红色的，如果s[i-1][j-1]也是红色或者绿色的那么这2个格子可以由一笔画成，否则无法一笔画出，res
2016-05-17 12:15:03
250
原创 Codeforces 165E Compatible Numbers
题目链接：http://codeforces.com/problemset/problem/165/E题意：给出n大小的数列，为数列中的每一个数找到一个与其进行&操作后等于0的数，并且该数也在该数列中思路：假设一个数的二进制为10101，将其0位取反得到一些数：11101,10111,11111，与变化后的数进&操作得到0的数同样&1010等于0，那么将数列
2016-05-16 20:24:23
505
原创 HDU 5316 Magician (区结合并)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5316题意：给出一个大小为n的区间，2种操作，更新某一个点的值，或者查询[l,r]区间的“最大值序列”(要求该序列的下标奇偶相间)思路：线段树的单点更新和区间合并可以实现题目要求，我们维护4个数据就好，查询的比较特殊(1).区间里最大的以奇数开头和以奇数结尾的序列
2016-05-10 20:51:35
708
原创 HDU 5317 RGCDQ
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5317题意：一个数n可以分解成若干个质数相乘的等式(如12=2*2*3有2个不同的质数，10=2*5有2个不同的质数)，那么我们认为f(12)=2,f(10)=2，求gcd(f[L],f[R])思路：11000000，因此最多有7种质数，f[x]#include #
2016-05-10 20:38:33
306
原创 HDU 5303 Delicious Apples (类似背包)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5303题意：有一个长为len(0~len-1)的环，环上一些位置上有苹果树，每棵数上有若干个苹果，有一个大小为k的箩筐，当箩筐满了之后可以回到出发点0处把苹果卸下，问最少走多少距离才可以把所有苹果运回0点呢？思路：由于是一个环，我们将其分成左右2边处理出取第i个苹果时的最短距离，
2016-05-05 12:13:26
306
原创 Codeforces 607A Chain Reaction (dp+二分)
题目链接：http://codeforces.com/problemset/problem/607/A题意：有n个灯塔，点亮一个灯塔会摧毁该灯塔左边距离x以内的灯塔，现在可以在最右边放置一个位置和摧毁距离任意的灯塔，问最少可以摧毁多少个灯塔思路：dp[i]表示i为最右边的灯塔时剩下的灯塔数，利用二分查询找到离灯塔i最近存活的灯塔j，dp[i]=dp[j]+1，n减去存活最多
2016-04-29 17:06:23
348
原创 hdu 1688 Sightseeing
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1688题意：给出一个有重边的有向图，求给出的2个点间有多少条最短路以及和最短路的路程差1的次短路思路：dijstra算法魔改一下，用队列进行操作，dist[i][0]记录到i点最短路，再用dist[i][1]记录次短路，cnt[i][0]和cnt[i][1]数组则记录最短路和次短
2016-04-29 16:18:35
1234
原创 POJ Brackets (区间dp)
题目链接：http://poj.org/problem?id=2955题意：给出一串括号，‘（’与‘）’匹配‘ [ ’与‘ ] ’匹配，问最多有几个匹配得括号思路：区间dp，刚做的时候想到了之前某道题的思路：如果s[i]与s[k]匹配dp=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1])然后特判k=j以及k=i+1的情况。后来看了下这道题很久之
2016-04-29 12:45:13
245
原创 Codeforces 607B Zuma (区间dp)
题目链接：http://codeforces.com/problemset/problem/607/B题意：给出一个大小为n的序列，可以一次消除一个数字或者一串回文，问最小消除多少次可以消除完所有数字思路：如果s[i]==s[k]，可以认为这2个数子最后一起消去，因为i与k之间的数字必定会消去剩下一个数字或者一串回文，与s[i]与s[k]组成新的回文,dp[i][j]表示从
2016-04-27 14:12:56
279
原创 CSU 1542 Flipping Parentheses
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1542题意：给出一串匹配的括号，改变其中一个括号的方向，要求改变最左边的一个括号方向使得该串括号重新匹配思路：((()))这样一个串括号，我们每遇到‘(’便加1，遇到’)‘便建1这样可以得到序列：1 2 3 2 1 0，可以发现如果一串括号是匹配的，那么该序列的末尾
2016-04-27 12:26:41
220
原创 LightOJ 1422 Halloween Costumes (区间dp)
题目链接：http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1422题意：有n天，每一天要求穿一种衣服，一件衣服可以穿在别的衣服的外面，也可以脱掉，但是脱掉之后不可以再穿，问最小需要多少件衣服思路：dp[i][j]代表i到j天最少需要多少件衣服。一开始先初始化为i-j+1，如果第i天和第
2016-04-21 20:14:34
248
原创 FZU 1914 Funny Positive Sequence
题目链接：http://acm.fzu.edu.cn/problem.php?pid=1914题意：给出大小为N的序列a，A(0)=a1,a2,a3……an;A(1)=a2,a3……an,a1;A(n-1)=an,a1,a2……an-1。B(0)则等于A(0)中的每个数加和，比如:B(n-1)=an+a1+a2+……+an-1，要求每一步都大于0，问这样的A有几个思路：序列
2016-04-19 19:59:32
359
原创 HDU 1719 Friend
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1719题意：1和2是friend num a和b是friend num的话，a+b+a*b也是friend num 思路：a+b+a*b=(a+1)*(b+1)-1 a=c+d+c*d=(c+1)*(d+
2016-04-18 20:11:30
277
原创 FZU 2093 寻找兔子 (状压dp)
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2093题意：有n个点和m条相连的边，兔子可能藏在任一点钟，1秒可以询问2个点是否有兔子，兔子每1秒必须向相邻的点移动，问至少要多少秒才可以确定兔子的位置思路：完全没想到是dp…当通向一个点的所有点都被确保没有兔子的话，即可确认该点没有兔子，01串来表示需要确认该点没有兔子的话需哪几个点被
2016-04-15 17:07:05
239
原创 FZU 2087 统计树边
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2087题意：给出一个有n个点m条边的图，没有重边和自环，问有多少条边可以是最少生成树上的边思路：对Kruscal不熟悉……没有想出来，图上只有2种边，一种是最少生成树上的边，一种不是最少生成树上的边，每次贪心的时候有权值相同且不在同一个集合的边res++，之后将这些边全放进生成树的集合里
2016-04-14 11:33:22
321
原创 POJ 1651 Multiplication Puzzle(区间dp)
题目链接：http://poj.org/problem?id=1651题意：给出n个数，出了第1个数和第n个数都可以进行一种操作：将该数从序列中去掉，得到s[x-1]*s[x]*s[x+1]的分数，问最终得到的最高分数是多少思路：区间dp，dp[i][j]表示从i到j可以得到的最多分数，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[
2016-04-13 12:40:45
163
原创 Codeforces 599C Day at the Beach
题目链接：http://codeforces.com/problemset/problem/599/C题意：给出大小为n的序列，要求将该序列分成连续的若干个部分，每个部分各自升序排序后组成的序列与原序列升序排序后一样，问最多分成几个部分思路： 一开始可以想到要满足max(h1,h2,h3……,hx)max(h1,h2,h3……,hx)，所以max[1,x]必定小于max[x
2016-03-10 17:46:28
576
原创 Hdu 2896 病毒侵袭
#include #include #include #include using namespace std;struct Tree{ Tree *Next[100]; Tree *fail; int ed;}*que[1030];Tree *tree;int top=-1;int stk[1030];ch
2016-03-09 19:09:34
240
原创 Codeforces 593A 2Char
#include #include #include #include using namespace std;int num[30][30],vis[30];char s[100030];int main(){ int n; while (scanf("%d",&n)!=EOF) { int cnt=0,ch
2016-03-09 18:54:57
205
原创 POJ 3616 Milking Time
题目链接：http://poj.org/problem?id=3616题意：n项作业，分别开始和截止的日期和完成需要时间，每迟完成一天扣一分，问最小扣了几分思路：还是最长递增子序列那一套，先按照结束时间排序，先结束的放前面先处理，dp[i]表示最后处理i项作业所需要的时间，当j(0#include #include #include #include u
2016-01-28 21:47:13
204
原创 POJ 2533 Longest Ordered Subsequence
题目链接：http://poj.org/problem?id=2533题意：给出大小n的序列，最长递增子序列思路：做过很多遍了……dp[i]代表以s[i]为尾的子序列最大长度，若s[i]>s[j](0#include #include #include #include using namespace std;int dp[1030],s[1030]
2016-01-28 20:32:59
200
原创 POJ 3166 Treats for the Cows
题目链接：http://poj.org/problem?id=3186题意：给出大小为n的数字序列，每次操作从左边或者右边去掉一个数si，总分数等于si乘于操作数i思路：每次仅可以从左边或者右边出一个数，dp[i][j](i是左边出的数的个数，j是右边出的数的个数)就只能由dp[i-1][j]以及dp[i][j-1]得出，一直递归就可以了#include
2016-01-28 20:18:56
270
原创 POJ 1661 Help Jimmy
题目链接：http://poj.org/problem?id=1661联动：http://blog.csdn.net/csdn364988181/article/details/48208349题意：场景中有n个平台，角色从某个地方下落，到达地面结束，从一个平台到另一个平台不可以超过max，不然摔死，在平台上移动速度是1m/s，下落的速度也是1m/s，问最快到达地面要多少
2016-01-23 21:14:11
299
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人