A. 乘方

算法：直接暴力做即可，但要注意a = 1 的情况会 TLE ，特判一下即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    LL res = 1;
    while (a > 1 && b -- )
    {
        res *= a;
        if (res > 1e9)
        {
            res = -1;
            break;
        }
    }

    printf("%lld\n", res);
    return 0;
}

B. 乒乓球

算法 (字符串处理,模拟) O(n)

先将整个比赛情况读取进来，然后依次枚举在11分制和21分制下的比赛结果即可。

• 在11分制下，一局比赛结束的条件是：某一方达到11分，且分差达到2；
• 在21分制下，一局比赛结束的条件是：某一方达到21分，且分差达到2；

注意最后如果比分是0:0，也要输出。

时间复杂度 每个字符处理一遍，因此时间复杂度是 O(n)。

#include <bits/stdc++.h>
using namespace std;

void work(string str, int score)
{
    int a = 0, b = 0;
    for (int i = 0; i < str.size() && str[i] != 'E'; i ++ )
    {
        if (str[i] == 'W') a ++ ;
        else b ++ ;

        if (max(a, b) >= score && abs(a - b) >= 2)
        {
            printf("%d:%d\n", a, b);
            a = b = 0;
        }
    }
    printf("%d:%d\n", a, b);
}


int main()
{
    string str, s;
    while (cin >> s) str += s;

    work(str, 11);
    puts("");
    work(str, 21);

    return 0;
}

C. 扫雷游戏

算法 (枚举) O(n2)

依次枚举每个空格，然后统计八个方向上的相邻格子有没有地雷即可。

时间复杂度 每个格子枚举一遍，因此时间复杂度是 O(n2)。

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;
char g[N][N];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            if (g[i][j] == '*') cout << '*';
            else
            {
                int cnt = 0;
                for (int k = 0; k < 8; k ++ )
                {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '*')
                        cnt ++ ;
                }
                cout << cnt;
            }
        }
        cout << endl;
    }
    return 0;
}

D. 插入排序

算法：先将所给数组按插入排序（稳定）排好序，然后有若干次操作，第一种操作把一个数变成另一个数，第二种操作求 x 的排名，注意排序后原数组不变，且为稳定排序，需要写 cmp 作双关键字排序。

a 存原数组，b 存排好序后在 a 里的下标（存映射关系，最小数、次小数。。。），c 存反向映射（a 里面第一个数在 b 里的下标）

复杂度：每次操作 O(n)，m 次操作，O(nm)

#include <bits/stdc++.h>
using namespace std;

const int N = 8010;

int n, m;
int a[N], b[N], c[N];

bool cmp(int x, int y)
{
    if (a[x] != a[y]) return a[x] < a[y];
    return x < y;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        b[i] = i;
    }

    sort(b + 1, b + n + 1, cmp);
    for (int i = 1; i <= n; i ++ )
        c[b[i]] = i;

    while (m -- )
    {
        int t, x, v;
        scanf("%d%d", &t, &x);
        if (t == 1)
        {
            scanf("%d", &v);
            a[x] = v;
            int k = c[x];

            while (k > 1 && (a[b[k - 1]] > a[b[k]] || a[b[k - 1]] == a[b[k]] && b[k - 1] > b[k]))
            {
                swap(b[k - 1], b[k]);
                swap(c[b[k - 1]], c[b[k]]);
                k -- ;
            }
            while (k < n && (a[b[k + 1]] < a[b[k]] || a[b[k + 1]] == a[b[k]] && b[k + 1] < b[k]))
            {
                swap(b[k + 1], b[k]);
                swap(c[b[k + 1]], c[b[k]]);
                k ++ ;
            }
        }
        else printf("%d\n", c[x]);
    }

    return 0;
}