ACM算法笔记(一)模拟算法【详细解析】

  • Post author:
  • Post category:其他


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



版权声明:本文为Colicsin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。