2017第八屆藍橋杯C/C++ A組題解

第一題

标題：迷宮

X星球的一處迷宮遊樂場建在某個小山坡上。

它是由10x10互相連通的小房間組成的。

房間的地闆上寫着一個很大的字母。

我們假設玩家是面朝上坡的方向站立，則：

L表示走到左邊的房間，

R表示走到右邊的房間，

U表示走到上坡方向的房間，

D表示走到下坡方向的房間。

X星球的居民有點懶，不願意費力思考。

他們更喜歡玩運氣類的遊戲。這個遊戲也是如此！

開始的時候，直升機把100名玩家放入一個個小房間内。

玩家一定要按照地上的字母移動。

迷宮地圖如下：

------------

UDDLUULRUL

UURLLLRRRU

RRUURLDLRD

RUDDDDUUUU

URUDLLRRUU

DURLRLDLRL

ULLURLLRDU

RDLULLRDDD

UUDDUDUDLL

ULRDLUURRR

------------

請你計算一下，最後，有多少玩家會走出迷宮?

而不是在裡邊兜圈子。

#include<iostream>
using namespace std;
bool geted[10][10]={false};
char maze[10][10];
int cnt=0;
int dfs(int x,int y)
{
    if(x<0||x>=10||y<0||y>=10)
    {
        cnt++;
        return 0;
    }
    if(geted[x][y]==true)
        return 0;
    geted[x][y]=true;
    switch(maze[x][y])
    {
        case 'U':
            dfs(x-1,y);
            break;
        case 'D':
            dfs(x+1,y);
            break;
        case 'L':
            dfs(x,y-1);
            break;
        case 'R':
            dfs(x,y+1);
            break;
    }
    geted[x][y]=false;
    return 0;
}
int main()
{
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            cin>>maze[i][j];
        }
    }
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            dfs(i,j);
        }
    }
    cout<<cnt<<endl;
    return 0;
}

第二題

标題：跳蚱蜢

如圖 p1.png 所示：

有9隻盤子，排成1個圓圈。

其中8隻盤子内裝着8隻蚱蜢，有一個是空盤。

我們把這些蚱蜢順時針編号為 1~8

每隻蚱蜢都可以跳到相鄰的空盤中，

也可以再用點力，越過一個相鄰的蚱蜢跳到空盤中。

請你計算一下，如果要使得蚱蜢們的隊形改為按照逆時針排列，

并且保持空盤的位置不變（也就是1-8換位，2-7換位,...），至少要經過多少次跳躍？

20 用bfs去做

#include<iostream>
#include<queue>
using namespace std;
struct node
{
    long long int value;//每跳一次的結果
    int empty_pos;
    int cnt;
};
bool geted[987654329];
int thestart=123456789;//123456789 用9代替0 避免在下面計算位數的時候出錯
int theend=876543219;//876543219
int X[4]={-2,-1,1,2};
long long int change(long long int value,int jump_pos,int empty_pos)
{
    int number[9];
    for(int i=8;i>=0;i--)
    {
        number[i]=value%10;
        value/=10;
    }
    swap(number[jump_pos], number[empty_pos]);
    long long int num=0;
    for(int i=0;i<9;i++)
    {
        num=num*10+number[i];
    }
    return num;
}

int bfs()
{
    queue<node> q;
    q.push(node{thestart,8,0});
    geted[thestart]=true;
    do{
        node top=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int jump_pos=(top.empty_pos+X[i]+9)%9;
            long long int s=change(top.value,jump_pos,top.empty_pos);
            if(geted[s]!=true)
            {
                geted[s]=true;
                q.push(node{s,jump_pos,top.cnt+1});
                if(s==theend)
                {
                    cout<<top.cnt+1<<endl;
                    return 0;
                }
            }
        }
    }while(!q.empty());
    return 0;
}

int main()
{
    bfs();
    return 0;
}

第三題

标題：魔方狀态

二階魔方就是隻有2層的魔方，隻由8個小塊組成。

如圖p1.png所示。

小明很淘氣，他隻喜歡3種顔色，所有把家裡的二階魔方重新塗了顔色，如下：

前面：橙色

右面：綠色

上面：黃色

左面：綠色

下面：橙色

後面：黃色

請你計算一下，這樣的魔方被打亂後，一共有多少種不同的狀态。

如果兩個狀态經過魔方的整體旋轉後，各個面的顔色都一緻，則認為是同一狀态。

請送出表示狀态數的整數，不要填寫任何多餘内容或說明文字。

不會，看到了一個可能是對的答案，但是代碼不想看。指路大佬的代碼大家加油！

第四題

标題：方格分割

6x6的方格，沿着格子的邊線剪開成兩部分。

要求這兩部分的形狀完全相同。

如圖：p1.png, p2.png, p3.png 就是可行的分割法。

2017第八屆藍橋杯C/C++ A組題解

試計算：

包括這3種分法在内，一共有多少種不同的分割方法。

注意：旋轉對稱的屬于同一種分割法。

請送出該整數，不要填寫任何多餘的内容或說明文字。

分析：考慮頂點，劃分頂點，從中心開始，用dfs去做。

#include<iostream>
using namespace std;
#define len 7
bool geted_v[len][len];//6*6方格 有7*7個頂點
int X[]={-1,0,0,1};
int Y[]={0,-1,1,0};
int cnt=0;
bool test(int x,int y)
{
    if(x<=0||x>=6||y<=0||y>=6)
    {//到達邊緣
        cnt++;
        return false;
    }
    if(geted_v[x][y]==true)
        return false;
    return true;
}
int dfs(int x1,int y1,int x2,int y2)
{//從中心頂點出發的兩個點的坐标，中心對稱
    if(test(x1,y1)==true)
    {
        geted_v[x1][y1]=true;
        geted_v[x2][y2]=true;
        for(int i=0;i<4;i++)
        {
            dfs(x1+X[i],y1+Y[i],x2+X[3-i],y2+Y[3-i]);
        }
        geted_v[x1][y1]=false;
        geted_v[x2][y2]=false;
    }
    return 0;
}
int main()
{
    dfs(len/2,len/2,len/2,len/2);
    cout<<cnt/2/2<<endl;//除以2 因為從中心往四個方向會有重複 向上和向下重複 再除以2是因為旋轉堆成的看作一種
    return 0;
}

第五題

标題：字母組串

由 A,B,C 這3個字母就可以組成許多串。

比如："A","AB","ABC","ABA","AACBB" ....

現在，小明正在思考一個問題：

如果每個字母的個數有限定，能組成多少個已知長度的串呢？

他請好朋友來幫忙，很快得到了代碼，

解決方案超級簡單，然而最重要的部分卻語焉不詳。

請仔細分析源碼，填寫劃線部分缺少的内容。

對于測試資料，小明口算的結果應該是：

#include <stdio.h>

// a個A，b個B，c個C 字母，能組成多少個不同的長度為n的串。

int f(int a, int b, int c, int n)

{

if(a<0 || b<0 || c<0) return 0;

if(n==0) return 1;

return f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(alb,c-1,n-1) ; // 填空

}

int main()

{

printf("%d\n", f(1,1,1,2));

printf("%d\n", f(1,2,3,3));

return 0;

}

第六題

标題：最大公共子串

最大公共子串長度問題就是：

求兩個串的所有子串中能夠比對上的最大長度是多少。

比如："abcdkkk" 和 "baabcdadabc"，

可以找到的最長的公共子串是"abcd",是以最大公共子串長度為4。

下面的程式是采用矩陣法進行求解的，這對串的規模不大的情況還是比較有效的解法。

請分析該解法的思路，并補全劃線部分缺失的代碼。

#include <stdio.h>

#include <string.h>

#define N 256

int f(const char* s1, const char* s2)

{

int a[N][N];

int len1 = strlen(s1);

int len2 = strlen(s2);

int i,j;

memset(a,0,sizeof(int)*N*N);

int max = 0;

for(i=1; i<=len1; i++){

for(j=1; j<=len2; j++){

if(s1[i-1]==s2[j-1]) {

a[i][j] = a[i-1][j-1]+1; //填空

if(a[i][j] > max) max = a[i][j];

}

return max;

}

int main()

{

printf("%d\n", f("abcdkkk", "baabcdadabc"));

return 0;

}

第七題

描述：正則問題

考慮一種簡單的正規表達式：

隻由 x ( ) | 組成的正規表達式。

小明想求出這個正規表達式能接受的最長字元串的長度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最長字元串是： xxxxxx，長度是6。

輸入

----

一個由x()|組成的正規表達式。輸入長度不超過100，保證合法。

輸出

----

這個正規表達式能接受的最長字元串的長度。

例如，

輸入：

((xx|xxx)x|(x|xx))xx

程式應該輸出：

#include<iostream>
using namespace std;
string word;
int num=-1;
int dfs()
{
    int len=0;
    int left=0;
    num++;
    if(num==word.size())
    {
        return len;
    }
    while(num<word.size())
    {
        switch(word[num])
        {
            case 'x':
                len++;
                break;
            case '('://将括号内視作一個整體
                len+=dfs();
                break;
            case ')':
                return len;
                break;
            case '|':
                left=len;
                len=dfs();//将|兩邊各自視為整體，得出右邊部分大小
                if(left>len)
                    len=left;
                return len;
                break;
        }
        num++;
    }
    return len;
}
int main()
{
    cin>>word;
    cout<<dfs();
    return 0;
}

第八題

标題：包子湊數

小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個包子。每種蒸籠都有非常多籠，可以認為是無限籠。

每當有顧客想買X個包子，賣包子的大叔就會迅速選出若幹籠包子來，使得這若幹籠中恰好一共有X個包子。比如一共有3種蒸籠，分别能放3、4和5個包子。當顧客想買11個包子時，大叔就會選2籠3個的再加1籠5個的（也可能選出1籠3個的再加2籠4個的）。

當然有時包子大叔無論如何也湊不出顧客想買的數量。比如一共有3種蒸籠，分别能放4、5和6個包子。而顧客想買7個包子時，大叔就湊不出來了。

小明想知道一共有多少種數目是包子大叔湊不出來的。

輸入

----

第一行包含一個整數N。(1 <= N <= 100)

以下N行每行包含一個整數Ai。(1 <= Ai <= 100)

輸出

----

一個整數代表答案。如果湊不出的數目有無限多個，輸出INF。

例如，

輸入：

程式應該輸出：

再例如，

輸入：

程式應該輸出：

INF

樣例解釋：

對于樣例1，湊不出的數目包括：1, 2, 3, 6, 7, 11。

對于樣例2，所有奇數都湊不出來，是以有無限多個。

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 1000ms

最小公約數非1，則INF。用動态規劃做。

#include <iostream>
#include <vector>
using namespace std;
#define Max 100000
bool geted[Max]={false};
int gcd(int a,int b)
{
    int t=0;
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    while(a%b)
    {
        t=a%b;
        a=b;
        b=t;
    }
    return b;
}
int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        geted[a[i]]=true;
    }
    int temp=a[0];
    for(int i=1;i<n;i++)
    {
        temp=gcd(temp,a[i]);
    }
    if(temp!=1)
    {
        cout<<"INF"<<endl;
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=a[i];j<Max;j++)
        {
            if(geted[j-a[i]]==true)
            {
                geted[j]=true;
            }
        }
    }
    int cnt=0;
    for(int i=Max-1;i>0;i--)
    {
        if(geted[i]==false)
        {
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

第九題

标題：分巧克力

兒童節那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。

小明一共有N塊巧克力，其中第i塊是Hi x Wi的方格組成的長方形。

為了公平起見，小明需要從這 N 塊巧克力中切出K塊巧克力分給小朋友們。切出的巧克力需要滿足：

1. 形狀是正方形，邊長是整數

2. 大小相同

例如一塊6x5的巧克力可以切出6塊2x2的巧克力或者2塊3x3的巧克力。

當然小朋友們都希望得到的巧克力盡可能大，你能幫小Hi計算出最大的邊長是多少麼？

輸入

第一行包含兩個整數N和K。(1 <= N, K <= 100000)

以下N行每行包含兩個整數Hi和Wi。(1 <= Hi, Wi <= 100000)

輸入保證每位小朋友至少能獲得一塊1x1的巧克力。

輸出

輸出切出的正方形巧克力最大可能的邊長。

樣例輸入：

2 10

6 5

5 6

樣例輸出：

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 1000ms

#include<iostream>
#include<vector>
using namespace std;
struct node
{
    int x;
    int y;
};
int main()
{
    int n,k;
    cin>>n>>k;
    vector<node> choclate(n);
    for(int i=0;i<n;i++)
    {
        cin>>choclate[i].x>>choclate[i].y;
    }
    int min=1,max=100000;
    while(min<max)
    {
        int len=(min+max+1)/2;
        int num=0;
        for(int i=0;i<n;i++)
        {
            num+=(choclate[i].x/len)*(choclate[i].y/len);
        }
        if(num>=k)
            min=len;
        else
            max=len-1;
    }
    cout<<max<<endl;
    return 0;
}

第十題

标題：油漆面積

X星球的一批考古機器人正在一片廢墟上考古。

該區域的地面堅硬如石、平整如鏡。

管理人員為友善，建立了标準的直角坐标系。

每個機器人都各有特長、身懷絕技。它們感興趣的内容也不相同。

經過各種測量，每個機器人都會報告一個或多個矩形區域，作為優先考古的區域。

矩形的表示格式為(x1,y1,x2,y2)，代表矩形的兩個對角點坐标。

為了醒目，總部要求對所有機器人選中的矩形區域塗黃色油漆。

小明并不需要當油漆工，隻是他需要計算一下，一共要耗費多少油漆。

其實這也不難，隻要算出所有矩形覆寫的區域一共有多大面積就可以了。

注意，各個矩形間可能重疊。

本題的輸入為若幹矩形，要求輸出其覆寫的總面積。

輸入格式：

第一行，一個整數n，表示有多少個矩形(1<=n<10000)

接下來的n行，每行有4個整數x1 y1 x2 y2，空格分開，表示矩形的兩個對角頂點坐标。

(0<= x1,y1,x2,y2 <=10000)

輸出格式：

一行一個整數，表示矩形覆寫的總面積。

例如，

輸入：

1 5 10 10

3 1 20 20

2 7 15 17

程式應該輸出：

340

再例如，

輸入：

5 2 10 6

2 7 12 10

8 1 15 15

程式應該輸出：

128

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 2000ms

參考了這裡，使用一個二維數組記錄坐标系中的點是否被包圍。藍橋杯oj第一個測試點有問題，答案應該是8458。

#include<iostream>
#include<vector>
using namespace std;
struct node
{
    int x1;
    int y1;
    int x2;
    int y2;
};
bool s[10010][10010];
int main()
{
    int n;
    cin>>n;
    vector<node> tangle(n);
    for(int i=0;i<n;i++)
    {//我是假設輸入的是順序的左下角右上角坐标 題目沒有明确說明 可能有測試點是需要判斷的
        cin>>tangle[i].x1>>tangle[i].y1>>tangle[i].x2>>tangle[i].y2;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=tangle[i].x1;j<tangle[i].x2;j++)
        {
            for(int k=tangle[i].y1;k<tangle[i].y2;k++)
            {
                s[j][k]=true;
            }
        }
    }
    int cnt=0;
    for(int i=0;i<10010;i++)
    {
        for(int j=0;j<10010;j++)
        {
            if(s[i][j]==true)
                cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

2017第八屆藍橋杯C/C++ A組題解

第一題

第二題

第三題

第四題

第五題

第六題

第七題

第八題

第九題

第十題

繼續閱讀

IT人求職旅程一周年記

在VC6.0開發環境中添加批量注釋和取消注釋

Compile workrave under windows &ndash; My exprience 在Windows上編譯Workrave

列印unsigned long long int

python算法之二分查找

基礎算法之二分查找

北大考研複試上機——日志排序

[Linux] diff 查找檔案的異同

c++ 比對相鄰元素相等的元素（adjacent_find）

DateTimePicker 控件的格式設定

C++數組引用C++數組引用

[C++學習曆程]基礎部分 C++中的函數學習

使用遞減運算符在循環中按遞減順序列印10到0之間的整數

指針，常量和類型别名

VS C++常見問題集錦1.在Vs中編C出現這兩個錯誤是什麼原因？錯誤1：error LNK2005: _main 已經在 *** 中定義