模拟算法和高精度
不多说了，进入正题
P1042 [NOIP2003 普及组] 乒乓球
华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在1111分制和2121分制下，双方的比赛结果（截至记录末尾）。
比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：
WWWWWWWWWWWWWWWWWWWWWWLW
在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。直到分差大于或者等于22，才一局结束。
你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。
输入格式
每个输入文件包含若干行字符串，字符串有大写的W、L和E组成。其中EE表示比赛信息结束，程序应该忽略E之后的所有内容。
输出格式
输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。
输入:
WWWWWWWWWWWWWWWWWWWW
WWLWE
输出：
11:0
11:0
1:1
21:0
2:1
分析：
这是某一次我们的考试题。
注意输入的时候，碰到E就停止。
11分制和21分制的要分开写。
所以也要分开输出。
并且还要注意11分制写完之后，把计数器清零！！！！！
#include<bits/stdc++.h>
using namespace std;
char s;
string a;
long long w,l,i;
int main()
{
while(cin>>s && s !='E'){
if(s=='\n'){
continue;
}
i++;
if(s == 'W'){
w++;
a += s;
}
if(s == 'L'){
l++;
a += s;
}
if((w >= 11 || l >= 11)&&(w-l>=2||l-w>=2)){
cout<<w<<':'<<l<<endl;
w=0,l=0;
}
}
cout<<w<<':'<<l<<endl<<endl;
w=0,l=0;
for(int j=0;j<i;j++){
if(a[j] == 'W'){
w++;
}
if(a[j] == 'L'){
l++;
}
if((w >= 21 || l >= 21)&&(w-l>=2||l-w>=2)){
cout<<w<<':'<<l<<endl;
w=0,l=0;
}
}
cout<<w<<':'<<l<<endl；
return 0;
}
P2670 [NOIP2015 普及组] 扫雷游戏
扫雷游戏是一款十分经典的单机小游戏。在nn行mm列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。
现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。
注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
输入格式
第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。
接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符’’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。
输出格式
输出文件包含n行，每行m个字符，描述整个雷区。用’’表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。
输入样例：
3 3
*??
???
?*?
输出样例：
*10
221
1*1
第一种做法
分析：（1）这个题可以用动态数组来做。开一个bool flag[maxn][maxn]，然后遍历这个二维数组，扫到雷就把flag[i][j]更新为1。那么没雷的只能是0。那么每个问号格子里的就把八个方向的的雷数累加，最后输出。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;
bool flag[maxn][maxn];
int main(){
memset(flag,0,sizeof(flag));
ios::sync_with_stdio(false);
int m,n;
char ch;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='*') flag[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(flag[i][j]==1) cout<<'*';
else cout<<a[i+1][j+1]+a[i+1][j-1]+a[i+1][j]+a[i][j+1]+a[i][j-1]+a[i-1][j+1]+a[i-1][j]+a[i-1][j-1];
//这就是那八个方向的和
}
cout<<endl;
}
return 0;
}
第二种做法
(2)DFS做法：搜索，找到地雷就把周围的数加起来
开两个二维数组，一个存场上的情况，一个存答案。
dfs函数主要是把八方向的数累加。注意最后要判断数组不要越界了。要不然会RE。
最后判断是不是地雷就行了，是就输出地雷，不是就把上面算过的数输出就行了。
#include<bits/stdc++.h>
using namespace std;
char a[101][101];
int ans[101][101]={0};
int n,m,i,j;
int dx[8]={1,0,-1,0,-1,1,1,-1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
void dfs(int x,int y)
{
int nx,ny,k;
for (k=0;k<8;k++){
nx=x+dx[k];
ny=y+dy[k];
if (nx>=1&&nx<=n&&ny>=1&&ny<=m) ans[nx][ny]++;
}
}
int main(){
cin>>n>>m;//输入
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
cin>>a[i][j];
if (a[i][j]=='*') dfs(i,j);
}
for (i=1;i<=n;i++){
for (j=1;j<=m;j++)
if (a[i][j]=='*') cout<<a[i][j];
else cout<<ans[i][j];
cout<<endl;
}
return 0;
}
P1518 [USACO2.4]两只塔姆沃斯牛
两只牛逃跑到了森林里。F J 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和 John）。
追击在 10×10 的平面网格内进行。一个格子可以是：一个障碍物，两头牛（它们总在一起），或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内（当他们相遇时），但是他们都不能进入有障碍的格子。
一个格子可以是：
. 空地；
* 障碍物；
C 两头牛；
F Farmer John。
这里有一个地图的例子：
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍（地图边沿也是障碍），它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时，它们不会离开地图。
Farmer John 深知牛的移动方法，他也这么移动。
每次（每分钟）Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。
读入十行表示地图。每行都只包含 10 个字符，表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 C。F 和 C 一开始不会处于同一个格子中。
计算 Farmer John 需要多少分钟来抓住他的牛，假设牛和 Farmer John 一开始的行动方向都是正北（即上）。 如果 John 和牛永远不会相遇，输出 0。
输入格式
输入共十行，每行 10 个字符，表示如上文描述的地图。
输出格式
输出一个数字，表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛，则输出 0。
输入：
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
输出：49
分析：这个题实在太经典了。
我直接搬老刘总结的了;)
这个地图上只有100个点，FJ和牛只会面对4个方向，所以FJ只会有400个不同状态，牛也有400个不同状态，一共有160000个状态，如果超过160000分钟，如果还不相遇，就不会相遇了。因为如果某个状态已经出现过了，第二次出现后，肯定陷入一种死循环中。
#include<bits/stdc++.h>
using namespace std;
const int toocircle=1919810;//循环周期，这个周期必须大于160000
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};//上右下左 顺时针
int fx,fy,cx,cy;
int dfj=0,dcs=0,ans; //FJ的方向，牛的方向，最初都是面向被，下标都是0
char mapp[12][12];
inline void nextstep(int &x,int &y,int &d){
x=x+dx[d],y=y+dy[d];//移动
if(mapp[x][y]=='*'){ //回撤转弯
x=x-dx[d];
y=y-dy[d];
d=(d+1)%4;//转弯90°
}
}
void init(){
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
cin>>mapp[i][j];
if(mapp[i][j]=='C') cx=i,cy=j;//如果找到了牛，记录牛的位置
if(mapp[i][j]=='F') fx=i,fy=j;//如果找到了Fj,记录Fj的位置
}
}
for(int i=0;i<=11;i++){ //自动加一圈障碍，这样不用判断是否到边
mapp[i][0]=mapp[0][i]=mapp[11][i]=mapp[i][11]='*';
//注意看这个是矩形边界。这个一般不容易想到
}
}
void work(){
ans=0;
for(;(fx!=cx || fy!=cy) && ans<toocircle;ans++){
nextstep(fx,fy,dfj);//FJ走一步
nextstep(cx,cy,dcs);//牛走一步
}
if(ans<toocircle) cout<<ans<<endl;//如果这个答案在范围以内，直接输出就好了
else cout<<0<<endl;//找不到
}
int main(){
init();
work();
return 0;
}