ACM模拟专题

1.1227-XTUOJ

题目描述

假设在一个XOY坐标的平面上，机器人一开始位于原点，面向Y轴正方向。 机器人可以执行向左转，向右转，向后转，前进四个指令。 指令为

LEFT:向左转RIGHT:向右转BACK:向后转FORWORD n:向前走n(1≤n≤100)个单位现在给你一个指令序列，求机器人最终的位置。

输入

样例的第一行是一个整数T(T≤20)，表示样例的个数。 每个样例的第一行是一个整数N(1≤N≤1,000)，表示指令的条数。 以后的N行，每行一条指令。

输出

每个样例输出两个整数，为坐标(x,y)，之间用空格隔开。

样例输入

2 4 LEFT FORWORD 1 RIGHT FORWORD 1 2 BACK FORWORD 1

样例输出

-1 1 0 -1

考点：动作过程的模拟实现，找规律。

易错：字符读取数字，必须注意两位以及两位以上的数字

思路：审题，由题意得知是在坐标轴分析，题目的关键在于我们怎么求得机器人的朝向。根据三角函数很容易得出机器人转向的规律，由该规律直接模拟即可得出最终代码。

代码如下：

#include<bits/stdc++.h> using namespace std; #define MAX 100 typedef char SString[MAX]; int main() { int T,N; SString str; scanf("%d",&T); while(T--) { int flag=0; int step; int x,y; x=y=0; scanf("%d",&N); getchar(); while(N--) { gets(str); if(str[0]=='L') flag--; if(str[0]=='R') flag++; if(str[0]=='B') flag+=2; if(str[0]=='F') { int length=strlen(str); if(length==9) step=str[8]-'0'; else if(length==10) step=(str[8]-'0')*10+str[9]-'0'; else step=100; if(flag%4==0) y+=step; if((flag-1)%4==0) x+=step; if((flag-2)%4==0) y-=step; if((flag-3)%4==0) x-=step; } } printf("%d %d\n",x,y); } return 0; }

2.1248-XTUOJ

Alice和Bob在玩骰子游戏，他们用三颗六面的骰子，游戏规则如下：

点数的优先级是1点最大，其次是6,5,4,3,2。三个骰子点数相同，称为"豹子"，豹子之间按点数优先级比较大小。如果只有两个骰子点数相同，称为"对子"，对子之间按点数优先级比较大小。其他情况称为"点子"，点子按点数和比较大小。豹子比对子、点子大，对子比点子大，如果对子的点数优先级相同，就看剩余那个骰子的点数优先级。

现在给你Alice和Bob投掷骰子的情况，判断一下胜负情况。

输入

第一行输入一个整数K，表示游戏的次数。 以后每两行表示一个样例，第一行是Alice骰子的点数。第二行是Bob骰子的点数。

输出

如果是Alice赢，输出"Alice",如果是Bob赢，输出"Bob",否则输出"Draw"。

样例输入

3 1 1 1 6 6 6 2 1 2 4 5 4 4 5 6 6 5 4

样例输出

Alice Bob Draw

考点：过程的模拟实现。

易错：题意的理解--点数的优先级。

解题思路：

      理解题目，题目要求我们去实现这个过程。要模拟这个过程，必须弄清楚这个过程有哪些步骤，然后用函数分别实现这些步骤，这样也方便调试。由题可知，我们要实现下列这些函数功能。

（1）点数优先级的比较。

（2）豹子对子点子的判断。

（3）豹子同豹子，点子同点子以及对子同对子之间的比较。其中，对子同对子的比较比较容易出错。

      想好这些逻辑以后，我们开始实现这个过程即可。注意，两个对子最多要比较两次数字优先级，如果在敲代码之前没有注意到这点，就会让整个程序出错。

代码如下：

#include<bits/stdc++.h> using namespace std; int flag; int Scan(int a[]) { if(a[0]==a[1]&&a[1]==a[2]) return 3; else if((a[0]==a[1])||(a[0]==a[2])||(a[1]==a[2]))return 2; else return 1; } void num_judge(int a,int b) { if(a==1||b==1) { if(a==1&&b==1) flag=3; else if(a==1) flag=1; else flag=2; } else if(a>b) flag=1; else if(a<b) flag=2; else flag=3; } void Left(int a[],int b[])//对子之间的比较 { sort(a,a+3); sort(b,b+3); if(a[1]==b[1]) { int t1,t2; if(a[1]==a[0]) t1=a[2]; else t1=a[0]; if(b[1]==b[0]) t2=b[2]; else t2=b[0]; num_judge(t1,t2); } else { if(a[1]==1) flag=1; else if(b[1]==1) flag=2; else if(a[1]>b[1]) flag=1; else flag=2; } } int main() { int a[5],b[5]; int K; scanf("%d",&K); while(K--) { int judge_1,judge_2; for(int i=0; i<3; i++) scanf("%d",&a[i]); for(int i=0; i<3; i++) scanf("%d",&b[i]); judge_1=Scan(a); judge_2=Scan(b); if(judge_1>judge_2) printf("Alice\n"); else if(judge_1<judge_2) printf("Bob\n"); else { if(judge_1==3) num_judge(a[0],b[0]); else if(judge_1==1) { int sum1=a[0]+a[1]+a[2]; int sum2=b[0]+b[1]+b[2]; if(sum1>sum2) flag=1; else if(sum1<sum2) flag=2; else flag=3; } else Left(a,b); if(flag==1) printf("Alice\n"); if(flag==2) printf("Bob\n"); if(flag==3) printf("Draw\n"); } } return 0; }

3.1253-XTUOJ

有N 个任务需要Robot去完成，这个N个任务的地点在一个数轴上，坐标为1 到n 。每个任务需要先完成a i  个任务才能开始去做。Robot可以在直线上左右移动，初始位置位于任务1 的地点，方向朝向数轴正方向。请问Robot最少转换多少次方向可以完成所有的任务。

输入

存在多个样例。 每个样例的第一行是一个整数n(1≤n≤1000) ,第二行是一个n 个整数a 1 ,a 2 ,⋯,a n (0≤a i <n) 。 输入数据保证一定能完成任务。

输出

每行输出一个样例的结果

样例输入

3 0 2 0 7 0 3 1 0 5 2 6

样例输出

1 2

考点：模拟过程的实现。易错：时间复杂度。

思路：

审题后，我们可以把题目翻译一遍。题目要求我们遍历数轴，当数据到达数轴点对应的数字要求后，该点才能被访问，求最小的掉头次数，我们自然想到，每次遍历的都到达末尾，那么转身次数不就是最少的了吗？至此，我们的出第一种思路：

     设置数组存数，模拟数轴，设置布尔数组，用来模拟访问。这里必须注意，题中的输入要求是存在多个样例，也就是说，当按下ctrl+Z的时候，程序结束。我们先来回顾一下当字符串存在多个输入时是如何书写的，如下：

while(gets(str)){..}，按下ctrl+Z，程序结束。

     为什么会这样呢？首先我们明确，EOF是END OF FILE的缩写，而gets函数：

1）当程序正常输入字符串时：返回读入字符串的地址，也就是字符串存放的数组的首地址;

2）当程序出现错误或者遇到文件结尾时：返回空指针NULL，注意不要弄混空指针和空字符

由此我们可知，按下ctrl+Z后，gets返回NULL，程序结束。

 对于scanf函数：

scanf()函数返回成功赋值的数据项数，出错时则返回EOF。

所以对于用scanf读取的整数来说，当scanf返回EOF时，程序可以结束了，我们自然可以写出下面的判断代码：

  while(scanf("%d",&num)!=EOF)。

      再次回到题目本身，我们继续分析。其实可以发现，我们转身过来，转身过去分析的坐标中有重复分析过的。尽管有布尔数组让我们判断是否处理过，但是他不能避免重复访问的毛病。那么接下来的问题就是如何避免重复访问。思考过后，我们可以借用两个数组分别存储还未访问的坐标，一个数组存储向右遍历后，还未访问的坐标，另一个数组中存储向左访问时还未访问的坐标。

扩展：

      此题让很多朋友都大呼：怎么不用STL解呢？博主首次STL-Vector的使用送给了此题，但是让楼主体会到了“初恋失败”的感觉- -||。因为它超时了！！不管是上述哪一种方法，它都是超时的，所以还是提醒各位，如果不是非用Vector不可，尽量用数组代替。

       还有，对于此题的AC还是一波三折的（大牛误批），花了20分钟已经把答案AC出来了，但是博主的输入判断没有写对，导致提交的时候一直显示超时，当时的心情可以用呵呵呵呵来形容。幸好，最后发现这个错误，但是这个AC时间真的伤不起啊！！！最后还是送上超时的Vector源码。

      

#include<bits/stdc++.h> using namespace std; int main() { vector<int> p,q; int n; while(scanf("%d",&n)!=EOF) { p.clear(); q.clear(); int flag=0; int turnover=0; for(int i=0; i<n; i++) { int num_rec; scanf("%d",&num_rec); p.push_back(num_rec); } while(flag!=n) { for(int i=0; i<p.size(); i++) { if((flag>p[i]||flag==p[i])) flag++; else q.push_back(p[i]); } if(flag==n) break; turnover++; p.clear(); for(int i=q.size()-1; i>=0; i--) { if((flag>q[i]||flag==q[i])) flag++; else p.push_back(q[i]); } if(flag==n) break; turnover++; q.clear(); } printf("%d\n",turnover); } return 0; }

正解代码如下：

方法一：

#include<bits/stdc++.h> using namespace std; #define MAX 1010 void num_change(int p[],int n) { int length=n-1; if(length==0) return; for(int i=length;i>=n/2;i--) { int t=p[i]; p[i]=p[length-i]; p[length-i]=t; } } int main() { int p[MAX],q[MAX]; int n; while(scanf("%d",&n)!=EOF) { int num_p,num_q; num_p=num_q=0; memset(p,0,sizeof(p)); memset(q,0,sizeof(p)); int flag=0; int turnover=0; for(int i=0; i<n; i++) scanf("%d",&p[i]); num_p=n; while(flag!=n) { for(int i=0; i<num_p; i++) { if(flag>=p[i]) flag++; else { q[num_q]=p[i]; num_q++; } } if(flag==n) break; turnover++; num_p=0; for(int i=num_q-1; i>=0; i--) { if(flag>=q[i]) flag++; else { p[num_p]=q[i]; num_p++; } } if(flag==n) break; turnover++; num_q=0; num_change(p,num_p); } printf("%d\n",turnover); } return 0; }

方法二：

#include<bits/stdc++.h> using namespace std; //vector<int>p; #define MAX 1010 int main() { int n; int a[MAX]; bool ans[MAX]; while(scanf("%d",&n)!=EOF) { int flag=0; int turnover=0; memset(ans,false,sizeof(ans)); for(int i=0; i<n; i++) scanf("%d",&a[i]); while(flag!=n) { for(int i=0; i<n; i++) { if((flag>=a[i])&&!ans[i]) { flag++; ans[i]=true; } } if(flag==n) break; turnover++; for(int i=n-1; i>=0; i--) { if((flag>=a[i])&&!ans[i]) { flag++; ans[i]=true; } } if(flag==n) break; turnover++; } printf("%d\n",turnover); } return 0; }

4.1258-XTUOJ

编写一个程序，将1 ~ n 2  按行依次填入n×n 的矩阵，执行若干条行或者列的循环移动的指令，再将数字按行依次取出。

指令如下：

指令含义L x yx行循环左移y次R x yx行循环右移y次U x yx列循环上移y次D x yx列循环下移y次

输入

第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10) 和m(1≤m≤1000) ，分别表示矩阵的大小和指令的条数。 以后的m行是m条指令，矩阵的行列按1开始计数，指令满足1≤x≤n,1≤y≤n−1 。

输出

每行输出一个样例的结果，数字之间用一个空格隔开，行末无空格。

样例输入

4 3 1 L 1 1 3 1 R 1 1 3 1 U 1 1 3 1 D 1 1

样例输出

2 3 1 4 5 6 7 8 9 3 1 2 4 5 6 7 8 9 4 2 3 7 5 6 1 8 9 7 2 3 1 5 6 4 8 9

考点：过程模拟，数据的循环移动。

易错：循环移动规律。

思路：

      理清题意。题目的实质是，找出数据循环移动n位后所在的位置，我们就依次我出发点，找出一定规律。先来看向右移动。我们取题目中一个样例分析可知，如果数据a在数据中的初位置为flag，那么向右移动b位后的位置为（flag+b）%n，其中，n为行数目。经分析可知，向下移动和此规律是一致的。那么我们再来分析向左移动。同样是由特殊到一般的规律，取题中样例分析：初始flag=0,n=3;

flag      b      实际位置

-1          1            2

-2          1            1

-3          1            0

       分析到这里，实际上我们可以得出结论了，但是还有一种更好的思路，我们可以假设，在flag=0的位置前面，仍旧有三个位置，检验一下，flag=0，左移一位，刚好到2，继续左移，到1，继续左移，到0，和我们已知的规律是一致的，由此，我们得出左移的规律:

b=b%n;//左移4位实质上和左移一位是相同的，所以才有了这个式子。

flag'=(n+flag-b)%n;

至此，这个问题也解决一半了。那么对于该题所用的存储结构，自然想到用二维数组。

拓展：

       在这个题目中，楼主又发现了“新大陆”。楼主刚接触STL不就，想试试这个STL的“威力”，最后才让楼主明白，这是在作死。

（1）Vector的初始化必须用Push_back(）,不可以调用scanf函数直接存储。

（2）Vector一维数组不可以直接赋值给二维的Vector。但是可以用整型数组赋值。

如：

vector<int>P[MAX]

vector<int>p;

for(int i=0;i<n;i++)P[2][i]=p[i];//编译器禁止这样赋值，不会报错，但是运行时会中断。

这就是本次使用Vector的全部体会，悲伤~在代码测试方面，楼主还是有新的体会的，当你实在找不到逻辑错误的时候，疯狂地测试样例是真的有助于你发现代码中隐藏的不足，当然，楼主还是希望朋友们能一次就AC掉这道题目，测试样例的过程也是十分难受的--。

代码如下：

#include<bits/stdc++.h> using namespace std; #define MAX 100 vector<int> P[MAX]; typedef char String[MAX]; void InitVector(int n) { int n_count=1; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { P[i].push_back(n_count); n_count++; } } void Left(int a,int b) { int temp[MAX]; int length=P[a].size(); b=b%length; for(int i=0; i<length; i++) { int flag=i; flag=(flag+length-b)%length; temp[flag]=P[a][i]; } for(int i=0; i<length; i++) P[a][i]=temp[i]; } void Right(int a,int b) { int temp[MAX]; int length=P[a].size(); for(int i=0; i<length; i++) { int flag=i; flag=flag+b; flag=flag%length; temp[flag]=P[a][i]; } for(int i=0; i<length; i++) P[a][i]=temp[i]; } void Up(int a,int b,int n)//上减下加 { int temp[MAX]; b=b%n; for(int i=0; i<n; i++) { int flag=i; flag=(flag+n-b)%n; temp[flag]=P[i][a]; } for(int i=0; i<n; i++) P[i][a]=temp[i]; } void Down(int a,int b,int n)//上减下加 { int temp[MAX]; for(int i=0; i<n; i++) { int flag=i; flag=flag+b; flag=flag%n; temp[flag]=P[i][a]; } for(int i=0; i<n; i++) P[i][a]=temp[i]; } int main() { int K; scanf("%d",&K); String Str; while(K--) { for(int i=0; i<MAX; i++) P[i].clear(); int n,m; scanf("%d%d",&n,&m); InitVector(n);//初始化 getchar(); while(m--) { int num1,num2; char str_rec; gets(Str); sscanf(Str,"%c %d %d",&str_rec,&num1,&num2); if(str_rec=='L') Left(num1-1,num2); if(str_rec=='R') Right(num1-1,num2); if(str_rec=='U') Up(num1-1,num2,n); if(str_rec=='D') Down(num1-1,num2,n); } for(int i=0; i<n; i++) for(int j=0; j<n; j++) { if(i!=n-1) printf("%d ",P[i][j]); else printf(j==n-1?"%d":"%d ",P[i][j]); } printf("\n"); } return 0; }

5.1239-XTUOJ

2048是大家非常喜欢的一款小游戏，给定一个2048的局面，和下一步的指令，请计算出变化后的局面。 2048的游戏规则如下：

游戏是一个4×4 的格子玩家可以使用上、下、左、右控制数字方格滑动，每滑动一次，所有的数字方块都会往滑动的方向靠拢，相同数字的方块在靠拢、相撞时会相加。不断的叠加最终拼凑出2048这个数字就算成功每次滑动后，会在某个空白格子中出现随机的2或者4，如果不存在空白格子，则游戏结束。

输入

第一行是一个整数K，表示样例的个数。 每个样例的前4行，每行4个整数，如果整数为0表示空白格子，其他为数字。 每个样例的第5行，是指令，指令为"LEFT","DOWN","RIGHT","UP",依次表示滑动的方向。

输出

输出每个样例的结果,每个样例后输出一个空行。

样例输入

3 2 2 0 0 2 0 2 0 2 0 0 2 0 0 2 2 LEFT 2 0 2 0 2 2 2 2 0 2 0 2 4 2 2 0 LEFT 2 4 2 2 0 2 2 0 0 4 4 4 0 0 0 2 LEFT

样例输出

4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 4 0 0 4 0 0 0 4 4 0 0 2 4 4 0 4 0 0 0 8 4 0 0 2 0 0 0

考点：过程模拟。

易错：题意的理解。

思路：

       2048小游戏，对于玩过的朋友来说，这是一道送分题，对于没玩过的楼主来说，这简直就是一道送命题。先从题意入手，我们可以注意到几个细节。第一，相同的数字在靠拢相撞时会相加。第二，空白格出现随机的2或4。第一遍看的时候对于第一点好像有点不理解，没关系，我们先来看看第二点是怎么做到的，那么从哪里找到答案呢？当然是样例。透过样例，我们发现，样例中好像并没有实现“出现随机2或4的功能”，那么我们暂且先假设这道题目没有要求实现这个功能。回到第一个细节。相同数字在靠拢相撞时会相加，这是一个怎样的过程呢？我们还是由特殊到一般的思路分析。

通过样例，我们可以有两种理解方法：

（1）数字是一个个移动的。

（2）数字是同时移动的。

为什么这么说呢，大家看下面这个样例：

0 4 2 2

0 0 0 0

0 0 0 0

0 0 0 0

RIGHT

对于第一种思路得到的结果：

0 0 0 8

0 0 0 0

0 0 0 0

0 0 0 0

对于第二种思路得到的结果：

0 0 4 4

0 0 0 0

0 0 0 0

0 0 0 0

      正是由于这样的原因，楼主才说，对于玩过的朋友，这道题目是很好选择，对于没玩过的楼主也只能碰碰运气--||。不过，这道题目也提醒了楼主，正确理解题意是非常重要的，希望大家别像傻傻的楼主一样，踩同样的坑。

接下来就是一一实现每一个模拟功能了。

代码如下：

#include<bits/stdc++.h> using namespace std; #define MAX 50 int num[MAX][MAX]; bool flag[MAX][MAX]; void InitMaxtrix() { for(int i=0;i<4;i++) for(int j=0;j<4;j++) scanf("%d",&num[i][j]); } void Left() { for(int i=0;i<4;i++) for(int j=1;j<4;j++) { int t=j; while(t!=0&&num[i][t]!=0) { if(num[i][t-1]==0) { num[i][t-1]=num[i][t]; num[i][t]=0; t--; } else if(num[i][t-1]==num[i][t]&&!flag[i][t-1])//记住这里有错误样例2 2 4 0,题意没有理解清楚 { //0 0 0 0 num[i][t-1]+=num[i][t]; num[i][t]=0; flag[i][t-1]=true; break; } else break; } } } void Right() { for(int i=0;i<4;i++) for(int j=2;j>=0;j--) { int t=j; while(t!=3&&num[i][t]!=0) { if(num[i][t+1]==0) { num[i][t+1]=num[i][t]; num[i][t]=0; t++; } else if(num[i][t+1]==num[i][t]&&!flag[i][t+1]) { num[i][t+1]+=num[i][t]; num[i][t]=0; flag[i][t+1]=true; break; } else break; } } } void Up() { for(int j=0;j<4;j++) for(int i=1;i<4;i++) { int t=i; while(t!=0&&num[t][j]!=0) { if(num[t-1][j]==num[t][j]&&!flag[t-1][j]) { num[t-1][j]+=num[t][j]; num[t][j]=0; flag[t-1][j]=true; break; } else if(num[t-1][j]==0) { num[t-1][j]=num[t][j]; num[t][j]=0; t--; } else break; } } } void Down() { for(int j=0;j<4;j++) for(int i=2;i>=0;i--) { int t=i; while(t!=3&&num[t][j]!=0) { if(num[t+1][j]==num[t][j]&&!flag[t+1][j]) { num[t+1][j]+=num[t][j]; num[t][j]=0; flag[t+1][j]=true; break; } else if(num[t+1][j]==0) { num[t+1][j]=num[t][j]; num[t][j]=0; t++; } else break; } } } int main() { int K; scanf("%d",&K); while(K--) { memset(flag,false,sizeof(flag)); char str_rec[MAX]; for(int i=0;i<4;i++) for(int j=0;j<4;j++) num[i][j]=0; InitMaxtrix(); getchar(); gets(str_rec); if(str_rec[0]=='L') Left(); if(str_rec[0]=='R') Right(); if(str_rec[0]=='U') Up(); if(str_rec[0]=='D') Down(); for(int i=0;i<4;i++) printf("%d %d %d %d\n",num[i][0],num[i][1],num[i][2],num[i][3]); printf("\n"); } return 0; }