Tips:
什么是模拟算法?模拟算法有没有什么严格的定义呢?模拟算法到底用来做什么呢?
笔者:
无论是noip还是icpc又或是各个网站的训练赛、模拟赛,总是脱离不了“模拟题”,所谓的模拟题,运用的“
模拟算法
”,其实并没有什么完全准确的定义。模拟算法,用一句老话说,就是“照着葫芦画瓢”;官方化的诠释则是:根据题目表述进行筛选提取关键要素,按需求书写代码解决实际问题。(还是老话好理解吧哈哈哈哈)
模拟算法一般都是一些很基础的题目,一些神犇眼中,模拟题就是所谓的“水题”,不太需要动脑子,只要按照题目要求来就好。
其实确实也是那么回事
,但是模拟题也分难易,对于一些特困难的模拟题,哪怕是神犇,也很容易做错,所以我们还是不能掉以轻心~
模拟算法需谨慎!!
模拟算法需谨慎!!
模拟算法需谨慎!!
模拟算法需谨慎!!
模拟算法需谨慎!!
模拟算法需谨慎!!
下面给出两例模拟题来解释一下模拟算法。
例题1:
洛谷P1328:https://www.luogu.com.cn/problem/P1328
此题就是模拟猜拳操作,按照题目要求,用数组存储甲乙猜拳结果,然后用for循环来模拟猜拳操作,每一次操作对结果得分进行统计,最后只要输出最终结果即可。思路很清晰,上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int na,nb,ans1=0,ans2=0;
int NA[205],NB[205] ;
int score[6][6]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};
int main()
{
scanf("%d%d%d",&n,&na,&nb);
for(int i=1;i<=na;i++)
scanf("%d",&NA[i]);
for(int i=1;i<=nb;i++)
scanf("%d",&NB[i]);
int j=1,u=1;
for(int i=1;i<=n;i++)
{
ans1+=score[NA[j]][NB[u]];
ans2+=score[NB[u]][NA[j]];
if(j==na) j=1;
else j++;
if(u==nb) u=1;
else u++;
}
printf("%d %d",ans1,ans2);
}
例题2:
洛谷P1067:https://www.luogu.com.cn/problem/P1067
此题相比于例题1来说就难度打了许多,我第一次做也是wa了好几次才a掉此题,为什么呢?仔细看题干发现我们只是进行输出一个多项式而已,但是这个“输出”包含了很多内容,我们需要考虑很多情况:
系数是否为0、系数的正负(影响你代码的输出格式)、常数项的正负、常数项是否为0、系数是否为1、指数是否为1…
先上代码,我写的比较中规中矩的没有压缩的代码:
#include<iostream>
using namespace std;
int main()
{
int n;
int f[101];
cin>>n;
for(int i=n;i>=0;i--)
{
cin>>f[i];
}
for(int i=n;i>=0;i--)
{
if(i!=0)
{
if(i==1)
{
if(f[i]!=0&&f[i]>0&&i!=n)
{
if(f[i]==1||f[i]==-1)
cout<<"+x";
else
cout<<"+"<<f[i]<<"x";
}
else if(f[i]!=0&&f[i]>0&&i==n)
{
if(f[i]==1||f[i]==-1)
cout<<"x";
else
cout<<f[i]<<"x";
}
else if(f[i]!=0&&f[i]<0)
{
if(f[i]==1||f[i]==-1)
cout<<"-x";
else
cout<<f[i]<<"x";
}
}
else
if(f[i]!=0&&f[i]>0&&i!=n)
{
if(f[i]==1||f[i]==-1)
cout<<"+x^"<<i;
else
cout<<"+"<<f[i]<<"x^"<<i;
}
else if(f[i]!=0&&f[i]>0&&i==n)
{
if(f[i]==1||f[i]==-1)
cout<<"x^"<<i;
else
cout<<f[i]<<"x^"<<i;
}
else if(f[i]!=0&&f[i]<0)
{
if(f[i]==1||f[i]==-1)
cout<<"-x^"<<i;
else
cout<<f[i]<<"x^"<<i;
}
}
else if(i==0)
{
if(f[i]>0&&f[i]!=0)
cout<<"+"<<f[i]<<endl;
else if(f[i]<0&&f[i]!=0)
cout<<f[i]<<endl;
else
cout<<endl;
}
}
return 0;
}
不能不承认,我有很多重复代码,但是这样看起来最清楚,每一个“坑”都在什么位置,由此可见,模拟题其实有的时候并没有我们想象中的那么简单,在IOI赛制还好,按照测试点计分,但是ACM赛制则就麻烦大一点,毕竟稍微一不注意,此题A不掉,就悲催了T_T