NOIP-C++大神培養計劃Step1.1.1基礎算法——模拟算法1

模拟算法，可以說是最基礎的算法了。

它的基本定義沒太多意思：就是去模拟題目的要求。題意要你怎麼做，你就怎麼做，看懂了題目，基本上就會做了。

舉一個大家耳熟能詳的栗子。

A+B Problem

給定兩個整數A和B，輸出他們的和。

這是學習C++的最簡單的例題之一。

代碼如下：

#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b<<endl;
    return 0;
}           

那為什麼要舉這麼簡單的栗子呢？

不知你有沒有注意，其實這就是一個模拟。

題目要你算A+B，你就算，這就是模拟。

我們在學習C++語言時做的題很多都有模拟的氣息，是以，這一個算法大家應該會比較熟悉了。

有些簡單的模拟題呢，很快就能做出來，當然個别難題還是要絞盡腦汁來想了。

下面，我們就來講解一下往年NOIP中，考到的一些模拟。

栗1.1.1-1 洛谷1003 鋪地毯

https://www.luogu.org/problemnew/show/P1003

題目描述

為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區域（可看做是平面直角坐标系的第一象限）鋪上一些矩形地毯。一共有 n 張地毯，編号從 1。到n。現在将這些地毯按照編号從小到大的順序平行于坐标軸先後鋪設，後鋪的地毯覆寫在前面已經鋪好的地毯之上。

地毯鋪設完成後，組織者想知道覆寫地面某個點的最上面的那張地毯的編号。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆寫。

輸入輸出格式

輸入格式：

輸入共n+2行

第一行，一個整數n，表示總共有n張地毯

接下來的n行中，第 i+1行表示編号i的地毯的資訊，包含四個正整數

a,b,g,k ，每兩個整數之間用一個空格隔開，分别表示鋪設地毯的左下角的坐标(a,b)以及地毯在x軸和y軸方向的長度第n+2行包含兩個正整數x和y，表示所求的地面的點的坐标(x,y)

輸出格式：

輸出共1行，一個整數，表示所求的地毯的編号；若此處沒有被地毯覆寫則輸出−1

輸入輸出樣例

輸入樣例#1：

3

1 0 2 3

0 2 3 3

2 1 3 3

2 2

輸出樣例#1：

輸入樣例#2：

4 5

輸出樣例#2：

-1

說明

【樣例解釋1】

如下圖，

1 号地毯用實線表示，

2 号地毯用虛線表示，

3 号用雙實線表示，覆寫點(2,2)的最上面一張地毯是 3 号地毯。

【資料範圍】

對于30% 的資料，有

n≤2 ；

對于50% 的資料，

0≤a,b,g,k≤100；

對于100%的資料，有

0≤n≤10,000 ，

0≤a,b,g,k≤100,000。

noip2011提高組day1第1題

一般來說，Day1T1總是最簡單的。那麼，我們就來分析一下，這題該怎麼去模拟。

解題思路：

首先，我們看到了題目，第一眼就想到了用二維數組，枚舉每一個地毯，再給數組指派便好！

來看一看代碼：

#include<iostream>
using namespace std;
int s[10001][10001],n;//二維數組用于存每一點的覆寫情況 
int x,y,a,b;//地毯的大小 
int X,Y;//詢問坐标 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y>>a>>b;
        for(int j=x;j<=x+a;j++)//枚舉X軸 
        {
            for(int t=y;t<=y+b;t++)//枚舉Y軸 
            {
                s[j][t]=i;//二維數組指派 
            }
        }
    }
    cin>>X>>Y;
    if(s[X][Y])
        cout<<s[X][Y]<<endl;
    else
        cout<<"-1"<<endl;
    return 0; 
}           

但是，注意：

資料範圍是阻止我們AC的重要敵人，你要是開一個像

s 100001

的數組，空間會爆啊啊啊！

那怎麼辦呢？我們來想一想辦法吧。

有一個真理：NOIP真題一定有标程，也就是答案，是以，我們珂以根據資料範圍來選擇算法或資料類型。

10^6啊，很大，100000*100000是絕對不可能的。

那我們想一想：

如果我們用數組來存x,y,a,b,在倒序枚舉每一塊地闆，判斷（X,Y）是否在地毯所覆寫的區間内。若沒有，則輸出-1

這個可以堪稱完美算法了。我們隻需要開100000*4的數組就可以了，複雜度是O(n)，完虐上一個算法QAQ

接下來我們來證明一下這個算法。

若一個點存在于一塊地毯内（不是最上面的），那麼他一定不存在與比它所在的地毯上層的地毯上，否則就跳出循環了。

這個算法證明很容易。記住，在考場上證明你的算法很重要。

那麼，我們來看代碼：

#include<iostream>
using namespace std;
int s[10001][5],n;//二維數組存x,y,a,b 
int X,Y;//所求坐标 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i][1]>>s[i][2]>>s[i][3]>>s[i][4];
        s[i][3]+=s[i][1];
        s[i][4]+=s[i][2];
    }
    //s數組作用為：s[i][1]:第i張地毯起始點的x軸;s[i][2]：第i張地毯起始點的y軸;s[i][3]：第i張地毯終點的x軸;s[i][4]：第i張地毯終點的x軸
    cin>>X>>Y;
    for(int i=n;i>=1;i--)
    {
        if(s[i][1]<=X&&s[i][2]<=Y&&s[i][3]>=X&&s[i][4]>=Y)
        {
            cout<<i<<endl; 
            return 0;
        }
    }
    cout<<-1<<endl;//沒搜到輸出-1.
    return 0;
}           

這一題就算是完整地講完了。

大家可以好好品味，去洛谷上AC這題吧！

栗1.1.1-2

洛谷P1008 三連擊

https://www.luogu.org/problemnew/show/P1008

将1,2,⋯,9共9個數分成3組，分别組成3個三位數，且使這3個三位數構成1:2:3的比例，試求出所有滿足條件的3個三位數。

木有輸入

若幹行，每行3個數字。按照每行第1個數字升序排列。

輸入樣例#1：

無

輸出樣例#1：

192 384 576

...

（輸出被和諧了）QAQ

這就是一道大模拟題，連輸入都沒有！

怪不得是普及組，來練練水

那麼，這題怎麼來做呢？

我們來思考一下：

讓我們依次枚舉三個三位數的個、十、百位，若遇見滿足a:b:c=1:2:3時就輸出，其實就行了。

我們來看看代碼吧：

#include<cstdio>
#include<cstring>
int i,j,a;
bool v[10];//a[i]表示第i個數已經用過了
int main()
{
    for(i=192;i<=327;i++)//第一個數最小192，最大327。用數學計算的，可以減小複雜度。 
    {
        memset(a,0,sizeof(a));
        a=0;
        v[i%10]=v[i/10%10]=v[i/100]=v[i*2%10]=v[i*2/10%10]=v[i*2/100]=v[i*3%10]=v[i*3/10%10]=v[i*3/100]=1;//統計數字
        for(j=1;j<=9;j++)
            a+=v[j];//a表示1-9這些數字是否全部齊了
        if(a==9) 
            printf("%d %d %d\n",i,i*2,i*3);//如果齊了就輸出
        /*
        算法介紹：
            這裡的i表示第一個數，上面那個很長的語句就是将3個三位數的個、十、百位統計，a來計算用了幾個數，若用了9個，輸出。 
        */
    }
    return 0;
}           

這就是這題的解法。題目本身沒有太大的難度，隻是要求一個思維的缜密，詳解已經在代碼中了，我想這題的了解應該沒什麼問題。

照常，去AC一下吧！

好了，今天的課程就到這裡了，下一次我們将繼續通過例題講解熟悉模拟算法。我們下次見！

如果大家有問題或者想和我讨論，可以加我的QQ：907916611，我很樂意為您解答！