-
86
热度 -
[综合] POJ1321 DFS
一个简单的搜索问题,但我还是搞半天搞不出来,递归实在是用不好 这题比八皇后难一些,k==n时,就是八皇后问题,但k<n的情况还是要考虑,原本k==n,每行都应该放一个,现在k<n,有的行不能放,所以每行搜索中,如果每一列都不符合,就需要搜寻下一行 代码如下: #include<s...
77
热度 -
[综合] UVa 524 素数环(DFS)
比较简单的搜索题,我自己也可以写出来,主要是最后输出的时候不知道怎么写,后来因为输出形式一直WA,UVa的题就是这点不好,输出形式要求太高,而且一律都是WA,不是PE,最后输出形式改了但还是WA,后来发现自己数组开小了,16刚刚好是不够的,下次一定注意数组开的要稍微大一点 代码如下: #inclu...
38
热度 -
[综合] UVa129 相邻重复子串
题意: 输入正整数n,l,输出由前l个字符组成的,字典序第k小的没有两个相邻重复子串的串。 要点: 判断ABCABA是否包含重复子串的方法是这样的:运用回溯法,只要比较当前串后缀,因为回溯法的特性,我们只要考虑当前的情况即可,前面的不用管,这样递归可以保证从头到尾都是成立的,当然后缀要从一个比较到n...
81
热度 -
[综合] POJ1014 DFS
题意: 一组价值从1到6的弹珠,每个价值对应输入相应的个数,判断能否平均分为两组 要点: 简单DFS,一开始我直接套用模板超时了,主要原因是我又重新设了一个数组想储存这些对应的价值,这肯定就慢了,其实不需要,对应的i就是价值,所以直接dfs就可以 PS:看网上一般都是用背包问题做的,下次研究一下换种...
15
热度 -
[综合] POJ3176 DP水题
题意: 三角形从上到下求最大值,只能向下或向右下 要点: 好简单的DP题,看了一下白书DP的介绍,3分钟就过了,DP白书上有很详细的解释,可以好好看看 代码如下: #include<stdio.h> #include<string.h> intmax(inta,intb) ...
15
热度 -
[综合] POJ1050与最大连续子段和,最大子矩阵问题
最大连续子段和: 一组连续的数:-4215-29,这组数据的最大的连续子段和解无疑是15,但怎么求出它呢?这里就有DP的思想 首先,用0作为分界点,不难想到如果用一个dp[k]数组储存当前子段和 如果dp[k]>=0,dp[k]=dp[k-1]+a[k] 但如果dp<0,无论后面a[...
17
热度 -
[综合] POJ1083 水题
题意: 两排房间搬桌子但只要一个走廊,输入一组房间号,求最短搬完的时间 要点: 就是一个区间求交集的问题,输入的两个房间号作为前区间和后区间,有交集说明不能同时搬,交集最大值即为至少需要的时间。注意看图,前区间如果是偶数要-1,后区间如果为奇数要+1,例如:2,3实际对应的区间是1,4,看图可以知道...
87
热度 -
[综合] POJ2192 Zipper(DP||DFS)
题意: 输入三个字符串,看前两个字符串能否组成第三个字符串,要求前两个字符串各自的字母顺序在第三个字符串中保持不变 要点: 可以用dp或dfs做,下面是dp的思路: 首先用定义一个数组dp[i][j],i代表了第一个字符串的第i个字母,j代表第二个字符串中第j个字母,那么可以通过dp[i][j]=1...
19
热度 -
[综合] POJ2385 经典DP
题意: 站在树下接苹果,总共两棵树,每一分钟有一根树掉下一颗苹果,从一棵树移动到另一棵树下为动一次,先站在第一棵树下,问经过t分钟,动w次,最多能接到几个苹果 要点: 经典dp题,状态分为动与不动两种,所以状态转移方程可以写为dp[i][j]=max(dp[i-1][j]+(a[i]==j%2+1)...
27
热度 -
[综合] POJ1157 花店问题经典DP
题意: 花店摆花,不同的花放进不同的花瓶美观度不同,排在后面的花不能放在排名前的花放入的花瓶的前面的花瓶 要点: 首先注意题意,加入花1放入第2个花瓶,花2就只能放在第3个花瓶或更后面,这样就简单多了,否则估计要用搜索。 这样问题就近似于数字三角形,首先设一个数组dp[i][j]记录当前最大美观度,...
62
热度 -
[综合] POJ1160 邮局问题
题意: m个村庄排在同一直线上,在之中建立n个邮局,要求这些村庄到最近的邮局之和最小 要点: 这道题挺难的,思路比较难想到不说还比较难理清 首先:在第a个和第b个村庄中建1个邮局的邮费最小方案应该是建在第(a+b)/2个村庄里,说实在的这个我一开始都不知道。 然后问题就可以拆成DP问题:在前k个村庄...
5
热度 -
[综合] POJ1163 DP水题
水题,数字三角形,最近dp做的真不怎么样,找点信心 代码如下: #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> usingnamespacestd;intm...
78
热度 -
[综合] 弄清size_t以及有符号数与无符号数的比较
一:size_t的具体概念 size_t一般在sizeof()中出现,常用于内存分配,sizeof运算符以字节为单位返回其操作数的大小,而C规定sizeof返回size_t类型的值,这是一个无符号整数类型,一般也就是unsignedint。但它对应的字节大小跟操作系统有关,size_t的真实类型与...
2
热度 -
[综合] 习题4-10 UVa815 Flooded!
快半个月没刷题了,一直在准备期末考试,终于考完了可以刷题了!思路很清晰的一道题,没有什么特别难的地方,但花的时间长了点。 要点: 先将海拔高度从小到大排列,如果要淹没一个格子,需要比它小的所有格子的雨水的海拔高度都达到这个格子的海拔高度,count=a[i]*(i-1)-sum{a[1],a[2]…...
97
热度 -
[综合] POJ3122 二分与误差
题意: n个派f+1个人分(包括自己),同一个派可以分成多块,但每个人只能拿一块,并且不能拼接比如一块6派,如果拿5,剩下的1就得丢弃 要点: 1.比较普通的二分,将每块派大小除mid,累加得到分给的人数。要注意mid也就是每个人分到的派可以是浮点数。 2.要求精度问题,因为left和right都是...
4
热度 -
[综合] POJ3750 循环链表解决约瑟夫问题
题意: 就是约瑟夫斯问题,首先从一个人开始,越过k-2个人(因为第一个人已经被越过),第k个人出列。接着,再越过k-1个人,第k个人出列。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下。依次输出每个出列的人 要点: 利用循环链表来实现,每次删除结点并输出这个结点的值。实际上最好用双向循环链表,但...
12
热度 -
[综合] POJ2503 二分结构体字典序排序sscanf函数
题意: 就是模拟一个查字典的过程,先输入互相对应的英语和外国语作为参照,再输入一些外国语,要求输出对应的英语 要点: 1.结构体的字符串排序 structNode {intdata;charstr[100]; }s[100]; //按照结构体中字符串str的字典序排序 intComp(constv...
81
热度 -
[综合] 例题6-4 UVa11988 静态链表
题意: 输入一串字符串,将其中[]中的字符放到字符串最开头,再输入得到的字符串 要点: 使用静态链表,也就是利用两个数组,还挺难的,主要是一个插入操作以及要设一个last来表示当前的最后字符。 代码如下: #include<stdio.h> #include<string.h&...
1
热度 -
[综合] 例题6-5 UVa12657 双向链表
题意: 看白书吧,介绍的很清楚,P144 要点: 好难啊,用两个数组表示双向链表,里面还有很多小技巧,真难,讲不清楚,看书 代码如下: #include<stdio.h> #definemaxn100050 intleft[maxn],right[maxn];voidlink(int...
66
热度