题解 P1724 【东风谷早苗】

RKcer21 · 2018-08-19 18:35:37 · 题解

这题是一道不错的题目 首先，让我们来晒一下0分WA代码

#include<bits/stdc++.h>
using namespace std;
int a[10001];
char c[5001];
int i,j,k,n,m,t,x,y;
  int main()
{
  gets(c);
  cin>>n;
  m=strlen(c);
  for (i=0; i<n; i++)
    {
      if (c[i%m]=='E') x+=1;
        else if (c[i%m]=='S') y-=1;
          else if (c[i%m]=='W') x-=1;
            else y+=1;
    }
cout<<x<<' '<<y;
return 0;
}

乍一眼看，没毛病，模拟大法啊，可是，luogu评测机似乎是用linux的，gets会出问题（注：noip也是用linux评测的） 具体怎么解决呢？请看下集（走开）

如果你坚持要用，你可以选择度娘（玄学啊）

现在让我们来看改了gets的程序

#include<bits/stdc++.h>
using namespace std;
int a[10001];
string c;
int i,j,k,n,m,t,x,y;
  int main()
{
  cin>>c;
  cin>>n;
  m=c.length();
  for (i=0; i<n; i++)
    {
      if (c[i%m]=='E') x+=1;
        else if (c[i%m]=='S') y-=1;
          else if (c[i%m]=='W') x-=1;
            else y+=1;//按题意模拟即可
    }
cout<<x<<' '<<y;
return 0;
}

怎么只有60分啊，我们可以看一下数据。

对于60%的数据：T <= 500,000且命令串长度 <= 5,000

对于100%的数据：T <= 2,000,000,000且命令串长度<= 5,000

哦，原来是那40%的大数据惹的祸。

再看一下题目与程序，你会发现，有很多个步骤是在重复运行的 于是乎，我们可以将每一轮的运动方式给记录下来（记录每一轮x与y的变化），再将剩余的步骤直接暴力即可（不要说的这么难听，模拟好不好）

#include<bits/stdc++.h>
using namespace std;
int a[10001],xx,yy;//xx与yy记录每一轮的运动方式，即每一轮x与y的变化
string c;
int i,j,k,n,m,t,x,y;
  int main()
{
  cin>>c;
  cin>>n;
  m=c.length();
  for (i=0; i<m; i++)
    if (c[i%m]=='E') xx+=1;
        else if (c[i%m]=='S') yy-=1;
          else if (c[i%m]=='W') xx-=1;
            else yy+=1;//记录每一轮的运动方式
for (i=0; i<n%m; i++)
     if (c[i%m]=='E') x+=1;
        else if (c[i%m]=='S') y-=1;
          else if (c[i%m]=='W') x-=1;
            else y+=1; //将剩余进行模拟
cout<<x+n/m*xx<<' '<<y+n/m*yy;
return 0;
}