Cplus

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3630

        这题是一个标准的Trie树，也是一个简单题，如果处理好的话用排序也可以过，话说效率还是挺不错的，但这里要讲的是Tire树做法。字符串处理的算法有很多，Trie树和Trie图（也就是AC自动机）都是很高效的数据结构，后缀数组也是，但是由于后缀数组较为复杂，实现起来也比较恼火。Trie树是一棵度 m ≥ 2 的树，它的每一层分支不是靠整

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3126

【分析】如果不是因为看到分类做的话估计拿到这个题目并不能很快反应出来是搜索。其实并不是一个很难的题目，这里把每次变化一位数字后产生的新数字作为一个状态进行搜索，因为用到的是BFS，所以我用到一个结构体来何在每次的状态量。每次搜索一个位变化的数字，如果是素数并且没有被搜索过，那么就把这个数放到队列中。下次扩展时把队列中的队首元素取出进行扩展，直到找到要找的第二个元素为止。不过期间调试的时候一直没有注意到千位的数字循环时会出现只有三位的情况，导致一直没有通过第二个测试数据，最后还是通过单步才查出来~~

做过之后看网上有大牛用dij来做，ORZ~~~

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3468

分析：由于数据量比较大，而且是要动态更新数据区间的数值，所以要用到线段树。但是并不是单纯的区间树，因为要求的是某一区间的和，所以要建成一棵点树。

[Code]

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAXN = 100010;
struct segment
{
        int nLeft, nRight;

        一年一度的学校程序设计比赛终于结束了，从开始准备到现在，大家都在为能举办一次成功的校赛而努力。去年由于地震的原因，校赛取消，今年也是第一次参加并组织校赛，体会到了准备一次比赛的艰辛，不过最终的结果是好的，我们队也成功的获得了第一名，校赛也在大家的努力下成功举办。下面说下我们队比赛的情况。
         和以前的比赛一样，我从后面开始读题，LLX从前面开始读题，王农龙中间。也许最近RP确实不错吧，读到的第一个题就是水题：告诉三角形三个顶点，然后求其面积。估计学过C++的人都能AC，而且C++书上还有这个代码，但我们并没有用海伦公式，而是用了计算几何公式，叉积，1次AC。但此时我们并没有排在前面，排名比较靠后。后面就是

描述 Description
	两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是D。有一个例外，就是一辆车上的人全部都是一个球队的支持者。问要将这N个人全部送至球场，至少要几辆巴士。

输入格式 Input Format

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1979

题目比较水，不多说了，贴上代码：

[Code]

BFS:

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 21;
struct node
{
        int x, y;
};
char cmap[MAXN][MAXN];
int sx, sy, res;

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1101

题意就不说了。

思路：因为可以等价为最少转拐数目，所以很自然会想到BFS，而且效率还是比较高的。首先设计一个结构体来存储到达每一个点的信息，包括这个点的坐信息和转拐信息。本题可以沿四个方面进行扩展：上、下、左、右。并且题目里面有一个比较隐藏的条件，那就是图形的边缘可以走，所以输入的高和宽要加上1之后进行扩展才能得到正确的结果。在记录转向时我用一个二维数组来记录[i, j]点处的方向，如果此刻方向和上一时刻方向相同时，那么此时刻的转拐数目就等于上一时刻的转拐数，否则就要在上一时刻基础上加1。还有一个需要注意的问题：在输入

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1111

题目大意：给定一个矩形框，每个小格子要么一个是"X"，要么是“.”，每个小格子都是单位长度的。要求求出与所指定的位置相邻的 X 所够成的周长；

思路：DFS，但是在DFS过程中要注意记录周长的方法。因为相对于一个小方格来说，如果由 “X” 组成，那么它的周长是由与之相关的八个方向所决定的，但是我们要记录的是与其相邻的左、右、上、下四个位置的方格情况，如果这四个方格中有一个是 “.” ，那么它的周长就可以增加一个单位长，如果是 “X”， 那么递归搜索。别外还要注意的一个细节就是当搜索走出边界时，周长同样要加一个单位。因为最后一点没注意，导致调试很久才通过。

        (队友写的一个，思路是已经明确了，懒得自己写了，直接贴一下~~~)

         描述 Description

闺女求天女，更阑意未阑。
玉庭开粉席，罗袖捧金盘。
向月穿针易，临风整线难。
不知谁得巧，明旦试相看。
——祖咏《七夕》
　　女子乞巧，是七夕的重头戏。古时，女子擅长女红被视为一种重要的德行。所以女孩子们纷纷在七夕这天祈求上天，是自己变得更加灵巧。仰头凝视，以虔诚的心去膜拜桂魄；双手合十，用坚定信念去盼望未来，祈求能有更出众的才能。一根针、一丝线 、一轮月、一束影，组成了一个简单的乞巧仪式。
“年年岁岁花相似，岁岁年年人不同。”千百年后的今天，女孩子们更加看重自己的才华与能力。韵哲君参加了一个新乞巧活动：

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2676

题目技巧性不强，DFS过的，用时16MS。不过写的过程中要注意从后面往前搜。

/************************************************************************/
/*思路：
先从后面开始搜，也就是从第八十个开始搜
1、如果一个小的方格内已经包含了非零的数，则继续向下搜
2、如果一个小的方格内是一个零数，也就是还没有放入相应的数，则对其从零到九开始尝试
3、对每一个数的尝试，检查其合法性：在其所在的3*3方格内是否合适；在此行是否合适：在此列是否合适