2010 East Central Regional Contest

     摘要: 2010  East Central Regional Contest声明:本博菜,只做水,未给出程序的题目待补充。 题目网址:http://acm.ashland.edu/ 【Problem A】 Cut It Out!【Problem B】 Flip It     简单的模拟题。    把一个卡片矩阵通过四种操作翻成一叠...  阅读全文

posted @ 2010-11-15 23:55 IronOxide 阅读(390) | 评论 (0)编辑 收藏

The 2010 ACM-ICPC Asia Chengdu Regional Contest 的几个题目

     摘要: 声明:本博菜,只做水。题目网址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3416比赛网址:http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=319【Problem C】 水题,直接按题目意思写即可。 Code highli...  阅读全文

posted @ 2010-11-14 00:25 IronOxide 阅读(947) | 评论 (0)编辑 收藏

练习一下2-SAT问题

     摘要: 【练习一】http://acm.hdu.edu.cn/showproblem.php?pid=3622这题是2010天津网络赛试题。二分答案,将圆看做一个点,当两个圆a,b的距离小于给定距离d时,说明a,b互斥,连边<a , ~b> ,<~b , a> 。二分+ 2_SAT 。  这确实是个好思路。  Code highlighting pr...  阅读全文

posted @ 2010-11-11 16:14 IronOxide 阅读(334) | 评论 (0)编辑 收藏

Southeastern European Regional Programming Contest 2009 部分解题报告

     摘要:                         Southeastern European Regional Programming Co...  阅读全文

posted @ 2010-10-29 02:04 IronOxide 阅读(757) | 评论 (0)编辑 收藏

<王晓东 算法分析与设计 > 线性规划与网络流24习题

     摘要:   其实早有Beyond The Void 大牛做了解题报告,非常犀利,Orz !网址:http://www.byvoid.com/blog/lpf24-solution/ 我从头做了一遍, 感觉受益匪浅。贴出自己代码,仅供参考。思路可参考Beyond牛。好不容易找到了两个可提交的网站:南开大学<可惜只有几个题>http://acm.nankai.edu.cn/p...  阅读全文

posted @ 2010-10-26 00:14 IronOxide 阅读(826) | 评论 (0)编辑 收藏

基础算法之搜索

     摘要: POJ 1950  Dessert     比较简单,但是要细心。    这道题关键注意运算一个给定的表达式。我的是用两个栈实现,一个数字栈,一个操作符栈。    其次,题目规模<=15,所以可以全体打表。也可以将结果个数打表,表达式搜索,当搜出结果超过20时,马上退出。 参考程序: Co...  阅读全文

posted @ 2010-10-10 21:34 IronOxide 阅读(281) | 评论 (0)编辑 收藏

HDOJ 3647 (2010ACM 杭州网络预选) Tetris 深搜 + 剪枝

     摘要: 题目描述:        一个规模为 W*H 的长方形 , 其中 W*H=40;      然后游戏依次随机生成10个块,这10个块为以下之一:         题目特别限制:不能使后面方块的某个格子在前面方块...  阅读全文

posted @ 2010-10-04 19:09 IronOxide 阅读(365) | 评论 (0)编辑 收藏

POJ 2411 Mondriaan's Dream 状态压缩 动态规划

题目描述:
给出一个 h*w 的空棋盘,1<=h,w<=11,若用1*2或2*1的骨牌去完全覆盖这个棋盘,问有多少种方法?

题目分析:
      规模很小,棋盘的每个格子有覆盖和未覆盖两种,正好对应二进制中的 1 和 0 。所以可以用一个二进制数表示一行棋盘的状态,这称之为状态压缩,然后对其进行相应的位运算,表示相应的操作。

     首先,我们明确一下状态的在该题的意义: 若当前格被一个1*2的骨牌盖住,或者被一个2*1的骨牌下面格盖住,则为 1 ;否则为0 。
     有了状态,我们就可以得出一些结论:
     1.当前行的状态只与上一行有关;
     2.若上行某个为0,则下行相应格必须为1;若上行某格为1,则下行相应格可为 0 或1;
     这样我们就可以有上一行的状态,递推出下一行的状态了。我们可以先求出所有的用1*2骨牌填一列的状态集M。然后,用每一个状态A去与上行状态判断,若有矛盾,则证明当前行不能为A;否则,A状态的方法数可由上行得出。
      用一个方程表示: F[ row  , i ] = sum ( f[row - 1 , j ] )  , j表示上行状态,i表示与j无矛盾的状态。
参考程序:

 

posted @ 2010-08-19 17:21 IronOxide 阅读(723) | 评论 (0)编辑 收藏

POJ 1198 Solitaire 广搜

     摘要: 题目描述:在一个 8 * 8 的棋盘上,有四个棋子,每颗棋子可在上,下,左,右,四个方向进行四种操作,四种操作是一下的某一种:     1. 若相邻格有棋子,则可像跳棋一样,跳过去,到达对称的一格。     2.若相邻格为空,则可直接移过去。 问能否从一种状态在8步之内变成另一种状态?题目分析: &...  阅读全文

posted @ 2010-08-19 10:00 IronOxide 阅读(852) | 评论 (0)编辑 收藏

POJ 2186

POJ 2186

题目描述:给定一个有向图,求满足下列条件的点V的个数:其他点均能沿着有向边到达V。

首先,将图的极大强联通分量缩成一个点,这是因为只要该联通分量某一点满足上述条件,则整个联通分量满足条件。

然后,明确的一点是,缩点后的图必无环,否则,可将环上所有点也缩成一个点,与极大强联通分量矛盾。

最后,只要找到缩点后的图中无出度的点的个数,设为cnt, 若 cnt > 1 , 则必无满足条件的点,因为一个出度为

零的点无法到达另一个出度为零的点;若cnt = 1 , 则该点所对应的强联通分量的点的个数即为答案。

参考程序:

posted @ 2010-08-16 19:46 IronOxide 阅读(854) | 评论 (1)编辑 收藏

仅列出标题
共2页: 1 2 
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔分类

随笔档案

ACMer

方向

搜索

最新评论

阅读排行榜

评论排行榜