s哒c-CSDN博客

原创 HDOJ 1254 推箱子 (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1254题意：推箱子游戏，在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置，求最少的推箱子的次数，如果不能完成则输出-1。思路：带嵌套的BFS~第一层BFS箱子，箱子每次移动前要再BFS一下人，看人能不能走到推动箱子的位置。注意：//因为人的位置不同时箱子可能

2013-04-25 10:35:34 1262

原创 HDOJ 1728 逃离迷宫 (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1728不得不说我还好水……原来觉得迷宫这类的搜索我已经做得不错了，但是这道题让我重新认识了现实……题意：在一个M*N的迷宫里，gloria要从一个地方走到另一个地方，判断是否可以在K次转弯内到达目的地。思路：BFS时先从一个点朝一个方向一直搜下去，直到不能搜了为止，然后再搜另一个方向。这样可以保证转弯

2013-04-20 17:38:09 1657

原创【更新】XMU 1308 单词联想（双向BFS）

http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1308题意：用给出的n(你思路：双向BFS搜索。搜索时用map查重，用string的replace对单词进行转换。具体过程详见代码注释部分。另外，这道题转换规则存在一对多映射的情况……【注意】双向BFS每次扩展结点后总是选择结点较少的一边进行下次搜索，而不是机械的两遍交替

2013-03-23 14:09:14 1137

原创【更新】HDOJ 1195 Open the Lock (双向BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1195题意：要从一个4位数，变成另一个4位数。有3种变换方法：1、选择一位加1（9+1变成1）；2、选择一位减1（1-1变成9）；3、选择相邻的两位交换其数值（第一位与第四位不相邻）。求最少的步数。思路：这是我第一次写出双向BFS~用两个队列分别记录正向的bfs和反向的back_bfs，用map进行查重，

2013-03-07 09:16:14 1008

原创 ZOJ 3675 Trim the Nails (状态压缩+BFS)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3675题意：Robert用一个指甲刀剪指甲，但是他的指甲刀上有一些豁口，现在假设他的指甲刀宽Nmm（指甲刀的具体情况用“*”和“.”表示：“*”表示是好的地方，“.”表示是坏的地方，每个符号表示1mm），指甲宽Mmm。求Robert最少要剪多少下才可以把指甲剪完。PS：指

2012-11-26 22:47:32 1106

原创快速读取的数字函数

int getval(){ int ret(0); char c; while((c=getchar())==''||c=='\n'||c=='\r'); ret=c-'0'; while((c=getchar())!=''&&c!='\n'&&c!='\r')

2012-11-17 21:16:53 753

原创 HDOJ 2102 A计划 (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=2102这个题断断续续的做了好久，好无语……各种小细节的错，终于A掉了……题意：从骑士从（0,0,0）点开始要在规定的T时间内到达P点（公主的位置）。每走一步要花一个单位的时间。‘.’是可走的路；‘*’是墙，不能走；‘#’是时空传输机，如果走上去就会被传送到另一层的相同位置（传送不耗费时间）。求其实能否

2012-10-20 09:28:17 1149

原创 HDOJ 1712 ACboy needs your help (分组背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1712题意：ACboy要在m天内学完n门课程，他花j天学第i门课程将获得A[i][j]的收益，求ACboy学完这n门课程可获得的最大收益。思路：每一门课程有m种情况可选，但是学每门课只能选一种情况，所以可以把每一门课分别看成一个组，然后用分组背包求解。#include#includeint va

2012-10-01 18:40:36 773

原创 HDOJ 2159 FATE (二维完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=2159题意：通过啥k种怪，杀掉每种怪（每个）会产生要取得a经验并消耗b忍耐度，现求杀不超过s个怪，能否取得n经验，如果能求出保留的最大忍耐度是多少？思路：二维完全背包求出最优解的情况，然后看>=n的里面剩下忍耐度最多的是多少。#include#includeusing namespace

2012-09-30 23:39:44 991

原创 HDOJ 1004 Let the Balloon Rise (map)

http://acm.hdu.edu.cn/showproblem.php?pid=1004题意：求出现次数最多的颜色。思路：用map存储颜色和出现次数，然后遍历一遍查找出现次数最多的即可。#include#include#includeusing namespace std;int main(){ int n; map color; while

2012-09-07 23:00:59 669

原创 ZOJ 3633 Alice's present

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3633这个应该算是ZOJ的水题了吧！只可惜比赛的时候虽然想到了用STL里的map，但是因为对map不熟悉所以没用map搞，于是比赛的时候没有A掉这道题。有时间要学习整理一下STL一些常用的东西了。题意：Alice将她的娃娃排成了一排，她要选一段（连续的）娃娃作为礼物送

2012-08-28 14:21:23 1231

原创 HDOJ 1242 Rescue (BFS+优先队列)

http://acm.hdu.edu.cn/showproblem.php?pid=1242题意：天使被关入了恶魔的监狱，他的朋友们要救他出去，根据给出的“地图“求他的朋友们到达他的位置的最短时间，路途中每走一个格子花费1个单位的时间，遇到守卫者需要再花1个单位的时间把他打倒……思路：因为朋友不止一个，要从每个朋友出发既要储存每个朋友的初始位置，又要进行多次BFS，极其浪费时间。所以，应该

2012-08-17 09:39:28 1744

原创 HDOJ 1312 Red and Black (DFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1312原来这道题这么水……题意：一个人站在一块黑色瓷砖上，他只能前后左右的走，切不可以走到红色瓷砖上。求它可到达的瓷砖数。思路：DFS，每次标记后都不清空标记。#include#include#includeint map[22][22];int w,h,max=INT_MIN;int

2012-08-16 16:03:12 971

原创 HDOJ 2717 Catch That Cow (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=2717题意：从N到K有3中走法：坐标加1、减1、乘2。求从N到K的最短步数。思路：BFS#include#include#includeusing namespace std;int n,k,cnt[111111];void bfs(){ queue q; q.push(n);

2012-08-16 10:53:32 817

原创 HDOJ 4255 A Famous Grid (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=4255题意：在一个螺旋网格当中求从一个数到另一个数的最短距离（格子中数字为素数地方不可以走）。思路：打出一个螺旋网格来，然后在其中进行BFS迷宫求解。由图可发现每层的左上角的数字都等于该层的行、列数的平方，所以打表时起始点的值就知道了。#include#include#include

2012-08-14 17:23:52 729

原创 HDOJ 3732 Ahui Writes Word (多重背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3732这是一道很坑爹的题呀！！！一打眼看看以为是简单的01背包，然后就华丽的超时了……后来才发现被迷惑了！这是一道多重背包的问题。这道题足以给做惯了经典多重背包，已经出定势思维的我们敲响警钟了！这题一个特点：物品个数很大，背包的体积很大，但是物品的价值和花费都很小！题意：有N个单词，总复杂度为C，

2012-08-13 10:43:04 1013

原创 CSUOJ 1093 Caps Lock (CSU Monthly 2012 Aug. C)

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1093o(︶︿︶)o唉！被一个简单的判断两个字母是否同为大写或小写坑苦了……题意：有N篇文章，每篇文章只有大写或小写字母，打文章的顺序可以是任意的，但对于任意一篇文章必须完整打完才可以打下一篇文章。求全部打完至少要按几次“Caps Lock键”。思路：总次数分两部分讨论：一部分是每篇文章

2012-08-12 19:35:22 2287 2

原创 HDOJ 1171 Big Event in HDU (多重背包) / (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=1171题意：已知有N种价值的物品，每种价值为v，有m件，现将物品分为两部分，使每部分价值尽量相等（如果不等则使第一部分大于第二部分）。多重背包：思路：背包体积为总价值的一半，然后用多重背包求最大值。#include#includeint bag[333333];int main(

2012-08-12 10:51:23 1248

原创 HDOJ 1059 Dividing (多重背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1059题意：有一些被划分为1-6价值的石头，并一直每个价值有多少块，求可否将石头分成两份且价值相等。思路：求出总价值，除2。转化为大小为（总价值/2）的背包可否恰好装满的问题。#include#include#define maxn 444444//(1+2+3+4+5+6)*20000=420

2012-08-10 10:48:47 1254

原创 HDOJ 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 (多重背包)

http://acm.hdu.edu.cn/showproblem.php?pid=2191题意：现有m种大米，每种价格为p，重量为h，有c袋。求用n元钱最多可买多重的大米？思路：典型的多重背包。为节约时间，将c拆分成2的n次方相加的形式（可以表示出所有情况！）。#include#includeint main(){ int t,v,m,bag[111],val[4444

2012-08-10 10:39:42 1814

原创 HDOJ 4342 History repeat itself

http://acm.hdu.edu.cn/showproblem.php?pid=4342题意：给定一个数N，求第N个素数M以及公式的结果。思路：1、先打表将部分公式值求出。2、第N的非平方数即N+N之前的平方数个数：add(计算add时加了一个偏移量：sqrt((double)n)，否则会出错)。3、计算M的公式结果时先求出M开方取证的结果：tmp，tmp*tmp-1的公式结果已存在表

2012-08-09 12:59:37 571

原创 HDOJ 1114 Piggy-Bank (完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1114题意：已知空罐重量、当前重量、每种硬币的重量和面值，要求根据给定的储钱罐重量求出储钱罐内至少含有多少钱。思路：要求恰好装满的完全背包（求最小值）----------------------------------------------------------------------------

2012-08-09 09:36:54 1517

原创 HDOJ 1284 钱币兑换问题

http://acm.hdu.edu.cn/showproblem.php?pid=1284题意：求用1，2，3组合成N有多少种情况。思路：一共有3种面值——因为有1分的存在，不管2分和3分的怎么拼都能凑成恰好的钱数，所以可以不考虑1分的（只要2分和5分组合小于等于钱数即可）；有几个2分的一共有（钱数/2+1）种情况，所以现在讨论用几个3分的就可以了；3分的情况用一个for循环从0到钱数/

2012-08-06 16:04:37 690

原创 HDOJ 1248 寒冰王座 (完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1248题意：用面额为N的钞票能买到商品，因为店铺不找零，所以求“浪费”的最小金额。思路：这道题是一道典型的完全背包题（也可以用别的方法解），将150，200，350作为物体体积，N做为背包容积。#include#include#define N 11111int type[4]={0

2012-08-06 12:06:58 1292

原创 HDOJ 1203 I NEED A OFFER! (01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1203题意：Speakless现在有n万美元，他想申请出国，每个学校都有不同的申请费用a，Speakless得到这个学校offer的可能性b。求Speakless至少收到一份offer的可能性最大是多少。思路：至少收到一份offer的可能性最大是多少不好求，可以转化为求一分都收不到的可能性最小是多少。这样

2012-07-26 10:00:14 1110

原创 POJ 3624 Charm Bracelet (01背包)

http://poj.org/problem?id=3624题意：求可能的最大值。思路：典型的01背包。#include#includeint f[22222];int main(){ int m,n,w[4444],v[4444]; while(scanf("%d %d",&n,&m)==2) { int i,j; for(i=1;i<=n;i++)

2012-07-25 17:58:24 1203 1

原创 HDOJ 2955 Robberies (01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=2955题意：一个抢到要抢银行，已知每个银行的现金数量和抢该银行被抓的概率。求在被抓概率小于P时能抢到的最大金额。思路：这道题比较特别，不能将概率作为物品的价值。需要将银行的总钱数看成背包，将银行的现金看成物品进行01背包。最后求比逃跑概率大的最大金额。#include#include#defin

2012-07-24 19:13:39 871

原创 HDOJ 2546 饭卡 (01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=2546题意：卡内有m元钱，有n种菜可以买（每种菜只可以买一次），只要卡内金额大于等于5元就可以买任何菜（刷到负也可以）。求最少可使卡上的余额为多少。思路：最贵的一个菜一定是最后买，然后用01背包求（m-5）元钱可买的菜的最大金额，然后（m-最大金额-最贵的菜的价钱）即为所求。#include#inc

2012-07-24 14:49:37 881 1

原创 HDOJ 2602 Bone Collector (01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=2602题意：求最大价值思路：典型的01背包#include#include#define N 1111int main(){ int t,n,v,val[N],vol[N],dp[N],i,j; while(scanf("%d",&t)==1) { wh

2012-07-24 14:42:00 590

原创 HDOJ 4300 Clairewd’s message

http://acm.hdu.edu.cn/showproblem.php?pid=4300第一次搞KMP，比赛的时候现学现卖，代码写的不怎么好，仅供参考……不足之处，还望高人指点！题意：截获了一段电文，电文至少含有密文（和明文），密文完整，明文可能不全甚至完全没有。现要求根据给出的匹配规则输出完整的电文（要求使电文最短）。思路：使电文最短，即找到电文后半部分与前半部分的最大匹配。用扩

2012-07-21 18:47:52 1320 2

原创 HDOJ 1233 还是畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1233题意：求最小的公路总长度。思路：克鲁斯卡尔#include#include#include#define maxn 111struct ln{ int a,b,dis;}path[maxn*maxn];int set[maxn];int cmp(const void

2012-07-20 10:46:55 598

原创 HDOJ 1874 畅通工程续 (Floyd)

http://acm.hdu.edu.cn/showproblem.php?pid=1874题意：求两村之间最短距离。思路：赤裸裸的Floyd。#include#define maxn 222#define INF 2139062143int map[maxn][maxn],n;void floyd(){ int i,j,k; for(k=0;k<n

2012-07-19 16:06:24 571

原创 HDOJ 1863 畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1863题意：求最小生成树。思路：克鲁斯卡尔算法。代码是自己根据对克鲁斯卡尔的理解写的，可能不够精简，所以仅供参考，不足为训，还望高人指点。#include#include#includestruct ln{ int a,b,c;}con[10000];int set[1

2012-07-19 10:27:12 745

原创 HDOJ 1232 畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1232题意：求最少还需要建设的道路数目。思路：简单并查集，看还剩几个集合。#includeint set[1500];int find(int x){ while(set[x]!=x) x=set [x]; return x;}void merge(

2012-07-19 10:10:44 1256

原创 HDOJ 1181 变形课 (DFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1181题意：判断是否可以用给出的单词首尾相连（连接处字母相同）构成一个从b到m的串。例如：big-got-them。实际上就是判断有向图中从b到m是否可达。思路：构建临街链表，DFS搜索。开始时忘记将已经用过的点标记……然后就华丽的爆栈了……#include#includeint alp

2012-07-19 09:54:55 899

原创 HDOJ 1272 小希的迷宫

http://acm.hdu.edu.cn/showproblem.php?pid=1272题意：判断是否所有点都连通且不存在回路。#include#include int set[100000+10]; int find(int x) { while(set[x]!=x) x=set[x]; return x; } voi

2012-07-16 20:33:31 1249

原创 HDOJ 1548 A strange lift (BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1548题意：一个电梯，在第 i 层只能选择上或下k [ i ] 层（任何时候都不超过顶楼且不低于1楼），求从A到B层最少要按几下电梯按钮？思路：BFS#include#define maxn 222typedef struct{ int floor,go,cnt;//floor为当先在

2012-07-16 14:01:34 1205

原创 HDOJ 1394 Minimum Inversion Number

http://acm.hdu.edu.cn/showproblem.php?pid=1394线段树解法：题意：（每次将一个排列的第一个元素移到这个排列尾部）求最小的逆序数是多少。注：逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。思路：先求出初始排列的逆序数Sum，然后循环每次将原

2012-07-16 10:16:13 783

原创 HDOJ 1556 Color the ball

http://acm.hdu.edu.cn/showproblem.php?pid=1556树状数组解法：题意：给N段连续的球上色，求上色后每个球被涂色的次数。思路：假设有一个数组d，令其的初值为0。若涂色 [ L,R ] 的区间，则令d [ L ] +=1；d [R] - =1;C [ i ] 为对应数组d的前i项和，这样C是 [ L,R ] 的区间就记录了球的涂色次数。因为实际操作

2012-07-15 23:40:07 948

原创 POJ 2528 Mayor's posters

http://poj.org/problem?id=2528题意：在一面墙上贴海报（与均墙等高），求最后露在外面的海报有几张。将每个单位线段看成一个点，然后按照更新区间内点的方法来updata。思路：首先通过把读入的段信息转化成点信息（即线段的两个端点），然后离散化，这样可以避免胡浩博客中的第二种情况。比如：线段（1-10）（1-4）（6-10），转化成段点：1-11 1-

2012-07-15 09:43:00 1046

空空如也

空空如也