-
[综合] 习题6-1 UVa673 Parentheses Balance(栈)
题意: 输入一个括号序列,判断是否合法 要点: 栈的水题,注意空行也合法以及每次要清空栈就行了。话说自己写的就是丑,而且中间没有考虑直接失败的例子,每次都得全部读完,时间复杂度不是很好,不过AC也就行了 #include<stdio.h> #include<string.h&g...
88
热度 -
[综合] 习题6-2 S-Trees(树)
题意: 看白书 要点: 题目很简单,就是树的水题,我是直接建树然后模拟,第一次WA主要是最后想输出字符串但没有在末尾加上\0,编译器可以通过但会WA,下次要注意了。这题也可以不建树直接用下标法做,我看了一下网上的代码,确实简单多了 1.建树+模拟 #include<stdio.h> ...
86
热度 -
[综合] 习题6-3 UVa536 Tree Recovery(树的遍历转换)
题意: 给出先序和中序求后序 要点: 递归完成,只要注意一下边界就可以了,水题 #include<stdio.h> #include<string.h> #include<stdlib.h> chars1[30],s2[30]; chartree[30]; i...
62
热度 -
[综合] 例题7-1 UVa725 Division(枚举)
要点: 用0~9编成两个五位数,要求两个数中每个数字只出现一次,第二个数中可以有前导0 要点: 用第二个数直接暴力枚举就可以 #include<stdio.h> #include<string.h> intnum[10];intjudge(inta,intb) {mems...
56
热度 -
[综合] 例题7-6 UVa140 Bandwidth(枚举+剪枝)
题意: 看白书 要点: 就是全排列问题加上一些剪枝,输入存储有些麻烦。注意如果有多个最小的排列,输出字典序最小的那个 #include<iostream> #include<algorithm> #include<cstring> #include<cs...
67
热度 -
[综合] POJ3628 Bookshelf 2(01背包)
题意: 你要很多不同高度的奶牛,想要达到一个高度为b的书架,将奶牛一个个叠起来,要求奶牛的高度和大于b,输出大于b且最小的高度和 要点: 将所有奶牛高度都加起来减去b的值作为背包大小,这样便转化成一个比较普通的01背包问题。现在就是等于向背包里放奶牛,使得高度和最大,这样与b的差值就会越小。这题稍微...
16
热度 -
[综合] POJ1948 Triangular Pastures(01背包)
题意: 输入一些栏杆,可以相互拼接,要求拼成一个面积最大的三角形 要点: 已知三角形三边可以用海伦公式计算三角形面积:S=√[p(p-a)(p-b)(p-c)],p=(a+b+c)/2。因为总长确定,所以确定两条边就可以知道第三条边,用背包的思路,dp[i][j]为1,表示从这些线段中可以组成一个边...
24
热度 -
[综合] ZOJ3861 Valid Pattern Lock(DFS||打表+枚举)
题意: 手机九宫格锁,共9个数,然后给出规定,只能用给定的n个数做密码,求不同的锁屏方法有几种对于一个点可以走向其他相邻8个方向,对于中间有相互隔开的情况,例如1到3,如果2已经访问过,那么方案是可行的,输出所有锁屏方案路径 要点: 可以DFS或直接排列判断,排列的话主要的难点在于判断是否合法,因为...
31
热度 -
[综合] ZOJ3866 Cylinder Candy(数学)
题意: 圆柱给出半径r,高度h,先在往这个圆柱体上涂一层厚度为d的巧克力,求总体积和总表面积 要点: 纯数学积分题,就当复习数学了。 #include<stdio.h> #include<string.h> #include<stdlib.h> #includ...
39
热度 -
[综合] POJ1742 Coins(多重背包可行性)
题意: 给出n硬币的价值和个数,再给一个数值m,求在这些硬币能组成多少种总和(要求小于m) 要点: 与一般背包问题求最值不同,这里是求能有几种组合,应该是叫做背包的可行性问题,看了网上的代码,大体是用两个数组,一个储存总和是否出现过,一个储存当前硬币使用的数量。 15278156 Seas...
40
热度 -
[综合] HDU4135 Co-prime(容斥原理)
题意: 寻找(a,b)中与n互质的数的个数 要点: 参考博客点击打开链接,求互质一般都是用容斥原理。 16614828 2016-03-2011:03:58 Accepted 4135 0MS 1780K 872B C++ seasonal #include<stdio.h>...
5
热度 -
[综合] POJ1426 Find The Multiple(DFS||BFS||同余模定理)
题意: 给出一个数,寻找这个数的倍数,要求只能由0和1组成 要点: 可以用BFS和DFS做,用BFS做只能用G++过,C++会超时。用DFS可以避免这些问题,但深度要自己猜一个数,来过oj的数据,有点投机取巧。最好是用同余模定理,但是别人的博客我有点看不懂。 参考博客:同余模定理做法 DFS: ...
29
热度 -
[综合] POJ1905 Expanding Rods(二分)
题意: 给一个长度为L的钢条,加热后长度改变并且弯曲成一个弧,算出之间的距离 要点: 基础思想是二分,但其实里面包含了很多证明 参考博客:点击打开链接 15301383 Seasonal 1905 Accepted 196K 0MS C++ 510B 2016-03-2220:56:20 ...
20
热度 -
[综合] POJ3984 迷宫问题(BFS+记录路径)
题意: 迷宫找出口问题,要求输出最短路径 要点: 普通迷宫找出口问题我倒是会做,但这题要记录路径,所以抓瞎了。看了一下,主要是要用一个队列数组来实现队列,用front指向当前pop出的结点,用rear指向当前入队的结点,通过记录前驱来记录通过的路径,并且通过递归倒序输出数组也就是正序输出路径,注意起...
90
热度 -
[综合] POJ3414 Pots(BFS)
题意: 给两个不同容量的杯子,要求经过最少的操作使其中一个杯子中有cL水 要点: 也就是BFS题,只不过这题每个节点有6种方向 15304559 Seasonal 3414 Accepted 212K 0MS C++ 2024B 2016-03-2319:34:10 #include...
71
热度 -
[综合] POJ2524 Ubiquitous Religions(并查集)
题意: 学校中每个人都有宗教信仰,现在只能知道某些人的宗教信仰相同,求总共有几种宗教 要点: 水题,跟HDU1213一毛一样,都是求最后集合个数,早知道不做了 15315712 Seasonal 2524 Accepted 504K 313MS C++ 691B 2016-03-2612:...
95
热度 -
[综合] POJ1703 Find them, Catch them(并查集)
题意: 两个两个输入一些数,D代表这两个数不同,A代表查询这两个数是否相同 要点: 与食物链那一题类似,都是开多倍数组,储存每种情况 15321734 Seasonal 1703 Accepted 1680K 375MS C++ 973B 2016-03-2718:34:06 #in...
4
热度 -
[综合] HDU1856 More is better(并查集)
题意: 王老师要找一些男生帮助他完成一项工程。要求最后挑选出的男生之间都是朋友关系,可以说直接的,也可以是间接地。问最多可以挑选出几个男生(最少挑一个)。 要点: 并查集水题,只要求那个集合中个数最大即可,就是数据比较大,所以rank数组就不开了。 16698903 2016-03-281...
58
热度 -
[综合] HDU1272POJ1308 小希的迷宫Is It A Tree?(并查集)
题意: 中文题不解释 要点: 两题一毛一样,判断是否合并后的结构是一棵树,即结构中应该没有环路,所以合并时如果发现两个根结点是相同的,就说明存在环路了。并且还要满足顶点数=边数+1。这题比较恶心的地方在于,如果一开始输入0,0要输出Yes,输入部分比较难写,而且HDU改题的时候还没提这事,POJ上倒...
31
热度 -
[综合] POJ2229 Sumsets(DP)
题意: 输入一个数n,要求分解为2的幂的和,求有几种组合方法 要点: dp方程很难想到啊,先是考虑如果n为奇数,那么组合中肯定有1,那么f[n]=f[n-1];如果n为偶数的话,先考虑如果有1,那么肯定有两个1合并而来,如果没有1,则全为2,4,6这种,这样我们把分解式中所有数除2,最后得到f[n]...
52
热度