-
[综合] poj 3074 Sudoku dlx解数独
分析: dlx是从数据结构角度优化01矩阵精确覆盖和重复覆盖的数据结构,它用十字链表只存贮矩阵中的非0元,而01矩阵精确覆盖dfs过程中矩阵会越来越稀疏而且每次恢复现场会浪费大量时间,dlx恰好能解决这两个问题。本题关键是将数独问题转化为01矩阵精确覆盖。数独转化为精确覆盖问题的方法还是参照Knut...
52
热度 -
[综合] poj 3435 检测数独状态是否合法
题意: 给一个数独的状态,判断它是否合法。 分析: 水,直接判断。 代码: //poj3435 //sep9 #include<iostream> usingnamespacestd; constintmaxN=10; constintMAX=maxN*maxN+10; inta[MA...
20
热度 -
[综合] poj 1084 Square Destroyer dlx解重复覆盖
分析: 将问题转化为重复覆盖问题,DancingLink解决。 代码: //poj1084 //sep9 #include<iostream> usingnamespacestd; constintmaxN=10024; constintmaxL=128; intL[maxN],R[m...
47
热度 -
[综合] poj 2799 IP Networks 模拟
题意: 给一些ip,求包括他们的最小网络(网络号+子网掩码)。 分析: 关键是找到从高位到低位从哪位开始不同。 代码: //poj2799 //sep9 #include<iostream> usingnamespacestd; typedeflonglongll; llvis[40]...
74
热度 -
[综合] poj 1698 Alice's Chance 二分图多重匹配
题意: 一个演员要拍n部电影,每部电影只能在一周的特定几天拍(如周2,周4,周5),第i部电影要拍di天,必须要在wi周拍完,问演员是否可以完成任务。 分析: 建二分图,转化为二分图的多重匹配。 代码: //poj1698 //sep9 #include<iostream> using...
61
热度 -
[综合] poj 1230 Pass-Muraille 贪心
题意: 给一些平行于x轴的墙,求最少去掉多少墙使得x轴上每点穿过不超过k面墙。 分析: 一开始还以为是重复覆盖问题(取最少的行使每列至少一个1),其实这题是可以用贪心解的(类似取最多的行使每列至多k个1)。 代码: //poj1230 //sep9 #include<iostream>...
13
热度 -
[综合] poj 2495 Incomplete chess boards 覆盖问题巧解
题意: 给一个8*8的棋盘,上面有2格被挖掉,判断是否可以用1*2的长方形覆盖棋盘。 分析: poj2446用的二分图匹配是这一类问题的通解。但这题只有恰好2个点被挖,所以有简便做法。可以把整个棋盘黑白染色(就像国际象棋那样),如果挖去的同色,则无法覆盖(这样导致剩余黑色格子数不等于白色格子数,每个...
82
热度 -
[综合] poj 1020 Anniversary Cake dfs的灵活结构
题意: 给一个目标正方形边长和n个小正方形的边长,问是否可以用这n个小正方形填满目标正方形。 分析: dfs不一开始就定好放入顺序,而是用已放入的个数代表深搜维度。 代码: #include<iostream> usingnamespacestd;intbox_size; intn; ...
57
热度 -
[综合] poj 1171 Letter Game 字符串处理或字符串背包
最多只有两个字符串参与构成,可以暴力解: #include<iostream> usingnamespacestd; chars[16]; intcnt[256]; inttot[256]; intm[256]; structDICT {charwords[10];intlen,val;...
84
热度 -
[综合] poj 2110 Mountain Walking 枚举+bfs
题意: 给一个n*n的矩阵,要从左上角走到右下角,使经过数字的最大数与最小数的差最小。 分析: 一开始想到了二分这个差,然后判断是否存在路径,每次只知道差的话深搜每次搜索要记录沿途的最大值和最小值会tle,广搜的话如果节点只记录x,y坐标,搜索中存在要重新访问以前访问过节点的情况,比如一开始(1,1...
97
热度 -
[综合] poj 1077 Eight A*解八数码问题
题意: 经典的八数码问题。 分析: 搜索算法的区别是如何重排open表,关键是如何编码状态和定义状态的值。对搜索过程中任意状态s,A*算法以g(s)+h(s)重排open表,也就是说g(s)+h(s)是排列open中状态的依据,其中g(s)是初始状态到s的消耗,h(s)是s到目标状态的估计。我重排o...
22
热度 -
[综合] poj 1324 Holedox Moving A*算法对bfs的优化
题意: 迷宫里有一条贪食蛇,求它的蛇头到迷宫左上角最少要多少步。 分析: 关键是将蛇的状态压缩编码,然后bfs,超时就改A*,这题有类似最短路径的性质,A*发现节点重复后不需要更新直接舍弃即可。 代码: //poj1324 //sep9 #include<iostream> #incl...
3
热度 -
[综合] poj 2449 Remmarguts' Date A*+spfa求第k短路
题意: 经典的第k短路,A*算法的经典应用之一。 分析: A*,已走的路程g+到终点的最短距离为启发函数,搜索过程中不判重,第k次到t节点时就求出了第k短路。 代码: //poj2449 //sep9 #include<iostream> #include<queue> u...
17
热度 -
[综合] poj 3696 The Luckiest number 欧拉函数在解a^x=1modm的应用
题意: 给一个L,求长度最小的全8数满足该数是L的倍数。 分析: 转化为求方程a^x==1modm。之后就是各种数学论证了。 代码: //poj3696 //sep9 #include<iostream> #include<algorithm> usingnamespace...
15
热度 -
[综合] poj 1166 The Clocks 记录路径的广搜
题意: 给9个时钟的初始状态,和一些对某几个钟的操作,求最少经过几步能到目标状态(全指向12点)。 分析: 明显的广搜,但实现起来的细节要注意:1.因为要记录路径,所以要在整个程序执行过程中扩展出的节点在输出路径前不能销毁,故采用静态内存分配的方法(开node[600000],用get_node()...
28
热度 -
[综合] poj 1270 Following Orders 枚举排列
题意: 给一个字符集和一些字符之间的小于关系,求字符集上的所有可能排列。 分析: 暴力枚举可以分为枚举子集,枚举排列,枚举组合,这题是个简单的枚举排列,枚举过程中用小于关系剪枝即可。 代码: //poj1270 //sep9 #include<iostream> #include<...
62
热度 -
[综合] poj 2079 Triangle 凸包+旋转卡壳
题意: 给平面上n个点,求这n个点组成的最大三角形面积。 分析: 旋转卡壳,但要注意和求平面最远点对的区别,最大三角形的边不一定在凸包上的,也贴出以前写的求平面最远点对的poj2187代码作为对比。 代码: //poj2079 //sep9 #include<iostream> #in...
75
热度 -
[综合] poj 3681 Finding the Rectangle 尺取法解最小矩形覆盖问题
题意: 平面上有n个点,现在要求一个面积最小的矩形能完全覆盖其中的m个点(边界不算)。 分析: 求满足某个性质的最小区间的问题尺取法比二分还要高效,这题可以在x上暴力枚举,在y上用尺取法(在x,y上都用尺取法是不对的)。 代码: //poj3681 //sep9 #include<iostr...
42
热度 -
[综合] poj 3221 Diamond Puzzle 反向bfs
分析: 简单的bfs,但要注意因为输入cases很多,对每个初始状态都搜一遍会超时,其实可以从终止状态反向搜一遍,对搜到的每个状态打表存下即可。 代码: //poj3221 //sep9 #include<iostream> #include<queue> usingnam...
0
热度 -
[综合] poj 2917 Diophantus of Alexandria 因数分解解1/x+1/y=1/n
题意: 给定n,求丢番图方程1/x+1/y=1/n(x<=y)的解数。 分析: 设x=n+a,y=n+b,化简可得n^2=a*b.设n^2的因子个数为p,n^2的所有因子中除n外都是成对出现的,故方程解数为(p+1)/2。 代码: //poj2917 //sep9 #include<i...
55
热度