C++ GESP 2024年3月 七级真题

1

单项选择

2

判断题

3

编程题

交流问题

题目分析

染色法判定二分图，可能是非连通图，所以每一个结点都要进入深搜，将染色较少的部分和较多的部分分别进行累加。

参考程序

#include<bits/stdc++.h>
usingnamespacestd;


constint N = 1e6 + 10;


int n, m;


structEdge{
    int to, next;
}e[N];


int h[N], cnt = 0;


voidadd(int a, int b)
{
    e[cnt].to = b;
    e[cnt].next = h[a];
    h[a] = cnt++;
}


int a = 0, b = 0;
int s1 = 0, s2 = 0;
int color[N];


booldfs(int u, int c){
    color[u] = c;


    if(c == 1) a++;
    else b++;
    
    for(int i = h[u]; ~i; i = e[i].next){
        int v = e[i].to;
        if(!color[v]){
            if(!dfs(v, 3 - c)) 
                returnfalse;
        }
        elseif(color[v] == c){
            returnfalse;
        }
    }
    returntrue;
}


intmain()
{
    memset(h, -1, sizeof h);


    cin >> n >> m;


    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    
    for(int i = 1; i <= n; i++){
        if(!color[i]){
            a = 0, b = 0;
            dfs(i, 1);
            s1 += min(a, b);
            s2 += max(a, b);
        }
    }
    
    cout << s1 << " " << s2 << endl;
    
    return0;
}

俄罗斯方块

题目分析

1. Flood Fill 联通块问题
2. 将转弯用 0 1 2 3 拼成的字符串表示
3. 如果没有路回溯用空格进行分隔。

参考程序

#include<bits/stdc++.h>
usingnamespacestd;


typedeflonglong ll;
constint N = 510;


int n, m;
int a[N][N];           // 网格颜色矩阵
int book[N][N];        // 标记是否访问
unordered_map<string, int> mp; // 存储形状序列化字符串




int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


// DFS 遍历连通块并记录路径形状
voiddfs(int x, int y, string &s){
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];


// 边界与同色判断
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
if (book[nx][ny] || a[nx][ny] != a[x][y]) continue;


            s += char(i + '0');   // 记录方向
            book[nx][ny] = 1;     // 标记访问
            dfs(nx, ny, s);
        }
    }
    s += ' '; // 分隔回溯结构，避免形状混淆
}


intmain(){
scanf("%d %d", &n, &m);


// 读入颜色矩阵
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);


int ans = 0;


// 遍历所有点
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!book[i][j]) {
                book[i][j] = 1;
string s = "";
// printf("(%d,%d)\n", i, j);
                dfs(i, j, s);
// cout << s << endl;
// 若未出现过该形状，计入种类
if (!mp[s]) ans++;
                mp[s] = 1;
            }
        }
    }


printf("%d\n", ans);
return0;
}