-
[综合] POJ1012 打表约瑟夫问题详解
题意: 约瑟夫问题的变形,总共k个好人和k个坏人,好人先排在坏人前面,寻找一个最小的m,使每次杀的都是坏人,保证坏人比好人先死 要点: 先打表把1-14的所有情况都赋值给一个数组,然后直接对应输出就行 约瑟夫问题: 维基百科:点击打开链接 百度百科:点击打开链接 设拿走k个的位置为ans[k],an...
90
热度 -
[综合] POJ1008 Maya Calendar(模拟)整除和取余的边界问题
题意: 玛雅有两种计年方式,输入一种年月日,输出对应的另一种年月日 要点: 1.注意题目要求,第一种还有第19月,一开始没看见,然后输出是一起输出,不是一个一个输出 2.这题主要的一个难点是有关/和%的边界: 例如:26/13=2,26%2=0,如果我想使整除26/13=1,即向下取整,并且想使26...
91
热度 -
[综合] POJ1013 Counterfeit Dollar(技巧)
题意: 有十二枚硬币,其中有一枚假币与其他真币重量不同,但不知道是轻是重,通过称量三次确定这枚硬币的字母代号 要点: 题目中没有说每次称量几枚硬币,所以用模拟非常复杂,这里有一个比较特别的技巧: 先如果天平是平衡的,那么对于的所以硬币肯定是真的,用一个数组存储将这些硬币剔除,后面计算时就不用考虑了。...
18
热度 -
[综合] POJ1363 Rails(数据结构栈)
题意: 一列火车从A站进入,B站开出,中间有一个站台,可以改变车厢顺序,原本是1~n,看输入的序列能否达到 要点: 就是模拟栈的压入弹出,如果栈顶元素对应的编号与输入的顺序一致就弹出,如果不一致就继续压入。最后如果栈是空的就说明顺序是合法的,否则不合法 15114206 Seasonal 1...
98
热度 -
[综合] POJ1664 放苹果(递归)
题意: 中文题,把m个苹果放入n个相同的盘子,盘子中可以不放苹果,问有几种方法 要点: 一开始我还以为是数学题,这不是组合概率问题吗?后来看网上的解释原来是递归: 用f(m)(n)记录有几种方法: 1.m=1||n=1时都只有一种,f(m)(n)=1 2.m<n时,就相当于m个苹果放m个盘子,...
87
热度 -
[综合] 例题6-7 UVa122 Trees on the level(树队列BFSsscanf字符串转整数)
题意: 看白书 要点: 这题还真难,有很多不知道的特殊函数知识不说,还有很多C++的容器。结点最多256个,要考虑最差的情况就是排成一条链,这样深度是256,如果用数组会爆炸,所以用动态分配。 sscanf()的这种读取字符串转换为整数的方法比较特殊,适用面比较窄:sscanf(&s[0],...
85
热度 -
[综合] POJ1046 Color Me Less(水)
题意: 颜色由(R,G,B)组成,先输入16组颜色制成表,再输入一些颜色,寻找与表中最接近的颜色 要点: 水题,简单的不得了,春节期间练练手,这几天学习效率非常低下,节日的气氛还是有些影响 15147087 Seasonal 1046 Accepted 400K 16MS G++ 618B...
20
热度 -
[综合] 例题6-8 UVa548 Tree(树的遍历转换)
题意: 分别用中序和后序输入一颗有权二叉树的权值,找出叶子满足到根权值和最小,如果一样大选自身权值最小的叶子 要点: 后序的最后一个结点一定是根结点,再在中序中找对应权值相同的结点的位置,这样左边就是左子树,右边是右子树,再递归一个个把分别的根结点放上去,这就是后序如何变成中序。 #include...
49
热度 -
[综合] 例题6-9 UVa839 Not so Mobile(树)
题意: 看白书 要点: 书上的代码倒是简洁,自己写是写不出这么简洁的,递归还是差点 #include<stdio.h> #include<stdlib.h>boolbuild(int&w)//这里传递地址改变w的值 {intw1,w2,d1,d2;boolb1=t...
41
热度 -
[综合] 例题6-11 UVa297 Quadtrees(四分树)
题意: 看白书 要点: 非二叉树,因为四分树比较特殊(有中间结点这种东西),所以给出先序遍历就可以确定整棵树(因为如果要向下必须要用中间结点,而且中间结点本身没有值),所以只要模拟一个方块的分割就行 #include<stdio.h> #include<stdlib.h>...
79
热度 -
[综合] 例题6-12 UVa572 Oil Deposits(DFS)
题意: 就是看有几个可以搜索完的块,求连通块,有个专门的算法名:种子填充 要点: 标准深搜,有上下左右和斜对角的可以用二重循环来表示 #include<stdio.h> #include<string.h> #include<stdlib.h> boolidx...
43
热度 -
[综合] POJ1564 Sum It Up(DFS)
题意: 输入一组数,要求输出总数为t的所有组合 要点: 因为数最多只有12个,直接暴力搜索就可以了,还有要判断重复,就是与前一个比较,但是其实只是剪枝提升速度,4,3,2,1,2,1这种还是会输出两个4,2,1这种 15167723 Seasonal 1564 Accepted 164K 1...
20
热度 -
[综合] 例题6-15 UVa10305 Ordering Tasks(拓扑排序)
题意: 看白书 要点: 1.拓扑排序:将一个图上的所有结点排序,使得每一条有向边(u,v)对应的u都排在v后面。注意只有有向无环图(DAG)才有拓扑排序 2.利用dfs先将最深的赋值给数组中最后一个位置,相同深度的就随便排了,因为只输出一种,所以答案跟题目中给的可以不一样 3.注意其中的c[n]数组...
4
热度 -
[综合] POJ2367 Genealogical tree(拓扑排序)
题意: 就是最简单的拓扑排序,裸题 要点: 裸题,直接模板一套就行 15174030 Seasonal 2367 Accepted 188K 0MS C++ 734B 2016-02-1817:08:31 #include<stdio.h> #include<str...
16
热度 -
[综合] 例题6-16 UVa10129 Play on Words(欧拉回路)
题意: 输入一些单词,看是否能将这些单词首尾分别对应相同的排成一个序列 要点: 欧拉道路,也即是从无向图的一个结点出发走出一条道路,每条边恰好经过一次,俗称一笔画, 对于无向图来说:如果一个无向图是连通的(任意一个点出发,通过dfs遍历可得到所以顶点),且最多只有两个度数为奇数的顶点,则一定存在欧拉...
91
热度 -
[综合] 例题6-17 UVa10562 Undraw the Trees(树)
题意: 将一棵多叉树转换成括号表示法 要点: 用先序遍历直接在二维数组内递归,主要是字符的输入判断比较麻烦,还有如果同时用scanf和gets的话,要把scanf后的换行符除去 #include<stdio.h> #include<string.h> #include&l...
55
热度 -
[综合] POJ2251 Dungeon Master(BFS)
题意: 要逃出地牢,地牢是三维的,有上下层之分 要点: 就是将原本二维的BFS转换为三维的就可以了,求最短距离,这种BFS我还是可以做的 15188937 Seasonal 2251 Accepted 304K 32MS C++ 1469B 2016-02-2222:10:22 #i...
10
热度 -
[综合] POJ3083 Children of the Candy Corn(BFS+DFS)
题意: 普通的迷宫求路径,但这题需要输出三个解:1.沿着左边查找,2.沿着右边查找,3.最短路径 要点: 最短的简单,直接BFS搞定。沿着左边查找和沿着右边查找其实是一个问题,也即是DFS中先遍历左边还是右边,沿着左边查找就把顺时针查找,如果不成功就向右查找,向右查找一次其实是向前,两次向右,三次向...
89
热度 -
[综合] POJ3009 Curling 2.0(DFS)
题意: 冰壶比赛,球会沿着直线一直运动下去,碰到阻碍会停下,同时阻碍消失,求最小步数 要点: DFS的变种,原本的DFS是一步一步的,现在是沿着直线一直下去,其实差不多,就是把直线看成一步就行。因为可以交错,所以不用设visit数组,同时要用回溯法。因为题目上说超过10步就失败,大大减少了时间复杂度...
2
热度 -
[综合] 例题6-20 UVa1599 Ideal Path(两次BFS)
题意: 看白书 要点: 因为这次需要找字典序最小的边,所以以前随机打印的方法是不行的,这道题用了一个很巧妙的方法:先从终点倒着BFS,将所有结点到终点的最短步数储存起来,然后直接从起点开始走,再一次BFS,到达每一个新结点时要保证d值恰好-1,选择颜色字典序最小的走,如果有多个最小,就存入队列,下一...
37
热度