5月20号洛谷题单刷题总结（模拟算法和高精度）

本文主要是介绍5月20号洛谷题单刷题总结（模拟算法和高精度），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

模拟算法和高精度

• • P1042 [NOIP2003 普及组] 乒乓球
  • P2670 [NOIP2015 普及组] 扫雷游戏
  • • • 第一种做法
      • 第二种做法
  • P1518 [USACO2.4]两只塔姆沃斯牛

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;
} 

这篇关于5月20号洛谷题单刷题总结（模拟算法和高精度）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！