2017-02-06阅读(4542)评论(0)

Codeforces 25E Test  出题：众所周知，程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错，出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。 4.7华丽地处理字符串  字...

2017-02-05阅读(4904)评论(0)

Codeforces 86C Genetic engineering  基因工程：给定m个子串，求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。 4.7华丽地处理字符串  动态规划算法  用AC自动...

2017-02-04阅读(2941)评论(0)

AOJ 2212 Stolen Jewel  夺宝奇兵：某国国宝失窃，你千辛万苦追回珍宝，正准备上交给国家时，却被怀疑是赝品。为了鉴别真伪，需要将宝石放到迷宫的魔法阵中。但迷宫中有特殊机关，不允许特定的移动模式。如下图的移动方式是...

2017-02-03阅读(2862)评论(0)

SPOJ QTREE5 Query on a tree V  染色：给定一颗黑白树，请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。 4.6划分、解决、合并：分治法  树上的分治法  重心分解后...

2017-02-02阅读(2949)评论(4)

UVa 12161 Ironman Race in Treeland  赛车：给定一颗树及各边长度及花费，请计算花费在m以内的最长路径。 4.6划分、解决、合并：分治法  树上的分治法  不断根据重心分割子树，...

2017-01-31阅读(2878)评论(0)

POJ 2114 Boatherds  漂流：给定一颗树及各边长度，请快速查询是否有距离为k的顶点对。 4.6划分、解决、合并：分治法  树上的分治法  与POJ1741类似 只需将“不超过k”改为“不超过k减...

2017-01-29阅读(2980)评论(0)

Codeforces 97B Superset  点集：给定n个点，请添加一些点，使任意两点满足①在同一条水平线或竖直线上②或构成一个矩形框住其他点。 4.6划分、解决、合并：分治法  平面上的分治法  从子问...

2017-01-28阅读(3554)评论(1)

GCJ 2009 World Finals B : Min Perimeter  极小三角：从n个点中找出3个，使其形成的三角形周长最小。 4.6划分、解决、合并：分治法  平面上的分治法  不断地用垂直分割线...

2017-01-27阅读(3538)评论(0)

POJ 1854 Evil Straw Warts Live  文字游戏：求通过交换相邻字符使某字符串成为回文的最小步数。 一个回文字符串被定义为等同于自己本身的反转。  给定一个字串，其不一定是个回文，计算最少的swa...

2017-01-26阅读(4885)评论(0)

UVa 10181 15-Puzzle Problem  滑动拼图：给定拼图，求解决方案。 4.5开动脑筋智慧搜索  A*与IDA*  滑块拼图问题是否有解的判断方法是，先将表格平铺： 然后计算N=逆序数对之和...