游戏地址

起因

去年五月份参加了一次自强内部的HackDay，有幸跟cc酱组了个小队伍。
当时提出了一个很早就有过的想法————通过命令行的方式来进行游戏。

于是乎我们就开心地做起来了，很快便碰到了问题：游戏通信如何进行？

题目来源：POJ2435

分析

题目大意：

给一张各种字符组成的图，

S,E分别为起点终点

+是十字路口

-,|是横的竖的街道

.不能走

1
2
3
4
5
6
7
8
9

+-+-+.+-+-+

|...|.....|

+-+.+-+-+-+ 

..|.......|

S-+-+-+.E-+

比如这张图

题目来源：POJ2229

分析

题目大意为：

给出一个正整数N(<=10^6)，可知N可分解为多个2^K(>=0)的数相加

如:
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1;

= 1 + 1 + 1 + 1 + 1 + 2;

= 1 + 1 + 1 + 2 + 2;

= 1 + 1 + 1 + 4;

= 1 + 2 + 2 + 2;

= 1 + 2 + 4;

共6种；

求种数。

刚拿到题目的时候，我联想到了整数的划分。

题目来源：POJ3670

分析

题目大意为：

给定一个长度为N（N<=30000）的仅包含1,2,3的串

求最长不下降子序列（正反均可）

题目来源：POJ3040

分析

题目大意：

给定N(<=20)种钞票,第i种面值为a[i],数量为b[i]

每周要给奶牛C(<=10^8)元的工资，求最多可以给几周。

注意：

1）给的工资每周不少于C元。

2）任意i,j 若a[i]<a[j] 则 a[j]为a[i]的倍数

肯定是贪心，但问题是怎么贪

题目来源：POJ3280

分析

题目大意为：

给定一个长度为M（M<=2000）的小写字母串

给定串中出现的N种字母的添加和删除代价

可以在任意位置加入或删除任意字母，代价如给定

求使原串变形为回文串的最小代价

解法

刚开始的思路非常复杂，储存两个代价，并且递归处理

(left,right)之外的回文串(之间的已为回文)，然后分各种情况讨论。这又犯了想当然的毛病，而且每次都是打到一半才发现算法不完善，情况考虑未完整，影响很致命。

其实这题的解法很简单。

题目：Roadblocks

题目来源：POJ3255

分析

题目大意为：

给一个双向路径联通图，求节点1到节点N的第二短路(路程严格大于最短路)

解法

刚开始想到的是直接做最短路，用一个dist存最短路，用一个dist2存第二短路，即每次更新dist[i]时，把dist[i]的原有值给dist2[i]

但是发现这样很蛋疼。。

题目：Corn Fields

题目来源：POJ3254

分析

题目大意为：

1. 给定一个12*12的矩形，每个格子为0或1，0为不能放东西，1可以

2. 现在放东西进格子里，一个格子可以放的条件：

   • 这个格子可以放（值为1）
   • 相邻的四个格子没有放

3. 求有几种放法