北京大学程序设计实习2017年期末考试自解

北京大学程序设计实习2017年期末考试自解

1:蜜蜂

一开始想用广搜，结果递归算法爆TLE了，这时候不得不抱dp的大腿，记忆化就是香。

#include<iostream>
#include<cstring> 
using namespace std;
long long int way[51];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        memset(way, 0, sizeof(way));
        way[a + 1] = 1;
        way[a + 2] = 2;
        if (b <= a + 2)
        {
            cout << 1 << endl;
            continue;
        }
        for (int i = a+3; i <= b; i++)
        {
            way[i] = way[i - 2] + way[i - 1];
        }
        cout << way[b] << endl;
    }
    return 0;
}

第一题自解

2:要变多少次

想了半天字符串怎么操作，卡在字符串读取的终点怎么判定上，结果发现有个好东西叫strlen。

看了大佬的代码，两点值得我学习，一是将字符串转为int数组，二是暴力破解的过程，高效直接。

#include<iostream>
#include<cstring>
using namespace std;
char str[1001];
int s[1001];
int l, num;
void oper()
{
    int sum;
    for (int i = 0; i <= l; i++)//i是第一个1出现的地方
    {
        sum = 0;
        for (int j = 0; j < i; j++)
            if (s[j] == 1)sum++;
        for (int j = i; j < l; j++)
            if (s[j] == 0)sum++;
        if (num > sum) num = sum;//暴力破解
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> str;//正序存储在str里面
        l = strlen(str);
        for (int i = 0; i < l; i++) s[i] = str[i] - ‘0‘;
        num = 1000;
        oper();
        cout << num << endl;
    }
    return 0;
}

第二题大佬题解

3:未名冰场

典型的深搜题，刚练过的城堡问题马上就用上了。

#include<iostream>
#include<cstring>
using namespace std;
int visited[101][101];//判定是否已访问过
char map[101][101];//湖面
int icePlaceNum;//结冰区域的数量
int n, m;//map的总行数和列数
void DFS(int x, int y)//对当前冰块进行深搜遍历
{
    if (visited[x][y])return;//之前访问过该冰块
    visited[x][y] = 1;
    if (map[x][y + 1] == ‘@‘)DFS(x, y + 1);
    if (map[x][y - 1] == ‘@‘)DFS(x, y - 1);
    if (map[x + 1][y + 1] == ‘@‘)DFS(x + 1, y + 1);
    if (map[x + 1][y - 1] == ‘@‘)DFS(x + 1, y - 1);
    if (map[x - 1][y + 1] == ‘@‘)DFS(x - 1, y + 1);
    if (map[x - 1][y - 1] == ‘@‘)DFS(x - 1, y - 1);
    if (map[x + 1][y] == ‘@‘)DFS(x + 1, y);
    if (map[x - 1][y] == ‘@‘)DFS(x - 1, y);
}

int main()
{
    int n, m;
    cin >> n >> m;
    while (n != 0 && m != 0)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> map[i][j];
        icePlaceNum = 0;//结冰区域数清零
        memset(visited, 0, sizeof(visited));//visited数组清零
        for(int i=0;i<n;i++)
            for (int j = 0; j < m; j++)
            {
                if (!visited[i][j] && map[i][j]==‘@‘)//冰块没有被访问过
                {
                    icePlaceNum++;
                    DFS(i, j);
                }
            }
        cout << icePlaceNum << endl;
        cin >> n >> m;
    }
    return 0;
}

第三题自解

4:迷阵