Edit Step Ladders

PC/UVa IDs: 110905/10029 题目描述

分析:按字典序排列的n个单词构成了一个隐式的有向无环图:每个单词单词都有一条出边指向在它字典序之后的每一个单词。要在这张图里找出符合条件的最长路径包含的顶点数。简单的想法就是“暴力”回溯了:对每个顶点进行一次回溯,找出以该点开始的最长的edit step ladder——这个时间复杂度高得能上了火星!思考一下就会发现,回溯包含了大量的重复计算:假设以单词w开始的最长ladder长度为l,那么对于字典中排在w之前的每一个单词(实际上是edit step为1的那些单词),在回溯经过w时都要做同样的重复计算,浪费了大量时间。如果我们计算好了以w开始的最长ladder的长度l,那么对于w的每一个one edit step前驱顶点,其最长ladder长度即为l+1。 继续阅读

The Tourist Guide

PC/UVa IDs: 110903/10099 题目描述

分析:假设从起点s到终点d的路径是a1->a2->..->an,这条路径上容量(权值)最小的边的权值为p,则p即为这条路径的最大容量。在所有s到d的路径中,我们要找出容量最大的一条,设其容量为P。则往返次数n可由
n * P >= T + n
得到
n = ceil(T / (n – 1))
关键是怎样找出P。简单的想法是用回溯法枚举出从s到d的所有路径、找出容量最大的一条,但这样会TLE! 继续阅读

Little Bishops

PC/UVa IDs: 110801/861 题目描述

分析:考虑两点:
第一,国际象棋棋盘的格子由黑白两色交替填充,黑色格子里的象吃不到白色格子里的象,反之亦然。
第二,把棋盘顺时针旋转45度,象就变成了车!虽然棋盘也从正方形变成了菱形,但其边界不难确定。
由此形成解法:首先把棋盘拆为黑、白两部分,然后旋转棋盘,接着把k个象分为两组,一组i个,一组k-i个,分别放在黑、白棋盘里,各有mb(n, i)和mw(n, k – i)种放置方法,则总的方法数为 继续阅读