西南财经大学·奇点工作室·程序设计部 暑期训练营 第三次课后习题题解

A. 递归函数的次数

题目链接：A. 递归函数的次数

考察知识点：递归、滚动数组

递归函数调用次数满足递推式 $a_n=a_{n-1}+a_{n-2}+a_{n-3}+1a\_n\; =\; a\_\{n-1\}\; +\; a\_\{n-2\}\; +\; a\_\{n-3\}\; +\; 1$，其中 $a_1=a_2=a_3=1a\_1\; =\; a\_2\; =\; a\_3\; =\; 1$。 由于 $n\le 100,000,000n\; \backslash leq\; 100,000,000$，所以不能直接递归或者迭代求解，考虑使用滚动数组优化。

时间复杂度：$O(n)O(n)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000

int a[5] = {0, 1, 1, 1};

void solve()
{
    int n;
    cin >> n;
    if (n < 4)
    {
        cout << a[n] << endl;
        return;
    }
    for (int i = 4; i <= n; i++)
    {
        a[4] = (a[1] + a[2] + a[3] + 1) % MOD;
        a[1] = a[2];
        a[2] = a[3];
        a[3] = a[4];
    }
    cout << a[4] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

B. 牛牛的排序

题目链接：B. 牛牛的排序

考察知识点：贪心

由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：

• 当数组本身有序时，不需要排序，输出 0；
• 当最大值或最小值已经就位时，只需要排序 1 次，输出 1；
• 当最大值与最小值都不在头尾时，需要排序 2 次，输出 2；
• 当最大值位于头部，最小值位于尾部时，需要排序 3 次，输出 3。

根据条件判断即可。

时间复杂度：$O(n)O(n)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    for (int &i : a)
        cin >> i;
    int ma = *max_element(a.begin(), a.end());
    int mi = *min_element(a.begin(), a.end());
    bool flag = true;
    for (int i = 1; i < n; i++)
        if (a[i] < a[i - 1])
            flag = false;
    int ans = 2;
    if (flag)
        ans = 0;
    else if (a[0] == mi || a[n - 1] == ma)
        ans = 1;
    else if (a[0] == ma && a[n - 1] == mi)
        ans = 3;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

C. 牛牛的朋友

题目链接：C. 牛牛的朋友

考察知识点：贪心

考虑两头牛时的情况，有以下 4 种移动方式：

1. 两头牛同时向左移动：距离不变
2. 两头牛同时向右移动：距离不变
3. 左边的牛向左移动，右边的牛向右移动：距离增大
4. 左边的牛向右移动，右边的牛向左移动：距离可能减小

其中前两种情况对答案没有影响，第三种情况可以直接忽略，第四种情况需要考虑。

推广到 n 头牛，可以知道最优的情况只会出现在「所有牛都往一个方向移动」或「靠左的牛往右边移动，靠右的牛往左边移动」这两种移动方法中。

因此，用变量 ans 记录初始距离（也即所有牛往同一方向移动的距离），循环枚举牛群的分界点，比较记录最优的距离，即为答案。

时间复杂度：$O(n\log n)O(n\; \backslash log\; n)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n, x;
    cin >> n;
    vl p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    cin >> x;
    sort(p.begin(), p.end());
    ll l = p[0], r = p[n - 1];
    ll ans = r - l;
    for (int i = 0; i < n - 1; i++)
    {
        l = min(p[i + 1] - x, p[0] + x);    // i: 1 ~ n
        r = max(p[i] + x, p[n - 1] - x);    // i: 0 ~ n-1
        ans = min(ans, r - l);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

D. 数圈圈

题目链接：D. 数圈圈

考察知识点：前缀和

使用 $x[i]x[i]$ 记录数字 $ii$ 的圈数，$s[i]s[i]$ 记录 ${\sum }_{j=1}^{i}x[j]\backslash sum\backslash limits\_\{j=1\}^\{i\}\; x[j]$，即前缀和。 则数字 $aa$ 到 $bb$ 的总圈数为 $s[b]-s[a-1]s[b]\; -\; s[a-1]$。

时间复杂度：$O(n\log n)O(n\; \backslash log\; n)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 1000000

ll quan[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
ll x[N+1], s[N+1];

void init()
{
    for (ll i = 1; i <= N; i++)
    {
        ll tmp = i;
        while (tmp)
        {
            x[i] += quan[tmp % 10];
            tmp /= 10;
        }
    }
    for (ll i = 1; i <= N; i++)
        s[i] = s[i - 1] + x[i];
}

void solve()
{
    ll a, b;
    cin >> a >> b;
    ll ans = s[b] - s[a - 1];
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    init();
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. iko和她的糖

题目链接：E. iko和她的糖

考察知识点：递归

递归求解：

• 当补给次数超过 3 次或当前糖果数量小于 0 时，返回。
• 当当前位置超过 n 时，更新答案并返回。

时间复杂度：$O(2^n)O(2^n)$ + 剪枝

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 1005
int a[N], b[N], ans = 0, n;
bool flag = true;

void dfs(int pos, int tang, int k)  // pos: 当前位置，tang: 当前糖果数量，k: 补给次数
{
    if (k > 3)
        return;
    else if (tang < 0)
        return;
    else if (pos > n)
    {
        flag = false;
        ans = max(ans, tang);
        return;
    }
    dfs(pos + 1, tang + a[pos] - b[pos], k + 1);
    dfs(pos + 1, tang - b[pos], k);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
        cin >> b[i];
    dfs(1, 0, 0);
    if (flag)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

F. 大佬的生日大礼包

题目链接：F. 大佬的生日大礼包

考察知识点：二分

不难看出每种礼包的构成：「1 个 U 盘 + 1 个鼠标」 + 1 个「U 盘 / 鼠标 / 键盘」 设 U 盘、鼠标、键盘数量为 $a_0,b_0,ca\_0,\; b\_0,\; c$，分配完每个礼包本身含有的 1 个 U 盘和 1 个鼠标后的 U 盘、鼠标数量为 $a,ba,\; b$，礼包数量为 $mm$，则有以下关系式：

• $a=a_0-ma\; =\; a\_0\; -\; m$
• $b=b_0-mb\; =\; b\_0\; -\; m$
• $a,b,c\ge 0a,\; b,\; c\; \backslash geq\; 0$
• $a+b+c\ge ma\; +\; b\; +\; c\; \backslash geq\; m$

由于相邻两位大佬的礼包不能相同，所以还需要满足：

U 盘 / 鼠标 / 键盘中最少的两种物品不少于礼包总数的一半

基于以上判断条件，使用二分查找 $1\sim a+b+c1\; \backslash sim\; a+b+c$ 范围内满足条件的最大礼包数量即可。

时间复杂度：$O(\log (a+b+c))O(\backslash log\; (a+b+c))$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;


bool check(int a, int b, int c, int m)  // a: U盘数量，b: 鼠标数量，c: 键盘数量，m: 礼包数量
{
    a -= m;
    b -= m;
    if (a < 0 || b < 0 || c < 0 || a + b + c < m)
        return false;
    int t[3] = {a, b, c};
    sort(t, t + 3);
    return t[0] + t[1] >= m / 2;        // 相邻的两位礼包不同，要求最少的两种礼包数量之和大于等于礼包总数量的一半
}

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    int l = 0, r = a + b + c;
    while (l < r)                       // 二分查找礼包数量
    {
        int m = (l + r + 1) >> 1;
        if (check(a, b, c, m))
            l = m;
        else
            r = m - 1;
    }
    cout << l << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. 再编号

题目链接：G. 再编号

考察知识点：前缀和

定义 $sum(a)={\sum }_{i=1}^n{a}_{i}sum(a)=\backslash sum\backslash limits\_\{i=1\}^\{n\}\; a\_i$，考虑计算 $sum(a^{\mathrm{\prime }})sum(a\text{'})$。

定义 $a_t(x)a\_t(x)$ 表示经过 $tt$ 次再编号后第 $xx$ 个人的编号，${sum}_t\{sum\}\_t$ 表示 $tt$ 次再编号的编号和。

当 $t>0t\; >\; 0$ 时，有：

由此递推公式可得 $a_t(x)a\_t(x)$ 的通项：

因为 ${sum}_t=(n-1){sum}_{t-1}\{sum\}\_t=(n-1)\{sum\}\_\{t-1\}$，所以 ${\sum }_{i=0}^{t-1}(-1{)}^i{sum}_{t-1-i}\backslash sum\backslash limits\_\{i=0\}^\{t-1\}\; (-1)^i\; \{sum\}\_\{t-1-i\}$ 事实上是一个等比数列，且有如下关系：

使用前缀和预处理 ${sum}_i\{sum\}\_i$ 和 ${\sum }_{i=0}^{t-1}(-1{)}^i{sum}_{t-1-i}\backslash sum\backslash limits\_\{i=0\}^\{t-1\}\; (-1)^i\; \{sum\}\_\{t-1-i\}$，即为程序中的 s[i] 和 p[i]。

然后根据 t 的奇偶性，计算出 $a_t(x)a\_t(x)$ 的值即可。

时间复杂度：$O(n+m)O(n+m)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007
#define N 100005

void solve()
{
    int n, m;
    cin >> n >> m;
    ll a[N], s[N] = {0}, p[N] = {0};
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[0] = (s[0] + a[i]) % MOD;
    }
    for (int i = 1; i <= 100000; i++)
    {
        s[i] = ((n - 1) * s[i - 1] % MOD) % MOD;
        p[i] = (s[i - 1] - p[i - 1] + MOD) % MOD;
    }
    while (m--)
    {
        int x, t;
        cin >> x >> t;
        if (t == 0)
            cout << a[x] << endl;
        else if (t % 2)
            cout << (p[t] - a[x] + MOD) % MOD << endl;
        else
            cout << (p[t] + a[x]) % MOD << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

H. 牛牛与回文串

题目链接：H. 牛牛与回文串

考察知识点：构造

由题易知，构造的回文串个数与字符串中出现次数为奇数的字符个数有关，所有成对出现的字符都不用单独构造。若所有字符都成对出现，则也至少需要构造 1 个回文串。

因此回文串的个数应为 max(n, 1)，其中 n 为出现次数为奇数的字符个数。

将单独出现的字符作为回文串的中心，其余字符成对出现在中心两侧即可。

时间复杂度：$O(\mathrm{\mid }s\mathrm{\mid })O(|s|)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    string s;
    cin >> s;
    map<char, int> mp;              // 记录每个字符出现的次数
    for (auto c : s)
        mp[c]++;
    int n = 0;
    vector<char> v;                 // 记录出现奇数次的字符
    for (auto p : mp)
    {
        if (p.second % 2)
        {
            n++;
            v.push_back(p.first);
        }
    }
    cout << max(n, 1) << endl;
    string cur;
    for (auto p : mp)
    {
        for (int i = 1; i <= p.second / 2; i++)
            cur += p.first;
    }
    cout << cur;
    if (v.size())
    {
        cout << v.back();
        v.pop_back();
    }
    reverse(cur.begin(), cur.end());
    cout << cur << endl;
    while (v.size())
    {
        cout << v.back() << endl;
        v.pop_back();
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

I. 小红的战争棋盘

题目链接：I. 小红的战争棋盘

考察知识点：模拟

大模拟题，需要考虑的情况比较多，下面的代码提供了一种写法。

时间复杂度：$O(kq)O(kq)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 505

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int board[N][N] = {0};      // 棋盘，记录领土标号
    int cnt = 0;                // 标号计数
    map<string, pii> pos;       // 记录军队位置
    map<string, int> power;     // 记录军队战力（即领土数量）
    map<string, vi> domain;     // 记录军队占领领土的标号
    map<int, string> belong;    // 记录领土归属
    while (k--)
    {
        string name;
        int x, y;
        cin >> name >> x >> y;
        if (board[x][y] == 0)                   // 投放位置为空地
        {
            board[x][y] = ++cnt;
            belong[cnt] = name;
            pos[name] = {x, y};
            power[name] = 1;
            domain[name].push_back(cnt);
        }
        else if (belong[board[x][y]] < name)    // 投放位置有弱于自己的军队
        {
            string old = belong[board[x][y]];
            pos.erase(old);
            power.erase(old);
            domain.erase(old);
            belong[board[x][y]] = name;
            pos[name] = {x, y};
            power[name] = 1;
            domain[name].push_back(board[x][y]);
        }
    }
    map<char, pii> move = {{'W', {-1, 0}}, {'S', {1, 0}}, {'A', {0, -1}}, {'D', {0, 1}}};
    int q;
    cin >> q;
    while (q--)
    {
        string name;
        char op;
        cin >> name >> op;
        // 势力不存在或已消亡
        if (pos.find(name) == pos.end())
        {
            cout << "unexisted empire." << endl;
            continue;
        }
        pii cur = pos[name];
        pii nxt = {cur.first + move[op].first, cur.second + move[op].second};
        // 目标点越界
        if (nxt.first < 1 || nxt.first > n || nxt.second < 1 || nxt.second > m)
        {
            cout << "out of bounds!" << endl;
            continue;
        }
        // 目标点为空地
        if (board[nxt.first][nxt.second] == 0)
        {
            cout << "vanquish!" << endl;
            board[nxt.first][nxt.second] = board[cur.first][cur.second];
            pos[name] = nxt;
            power[name]++;
            domain[name].push_back(board[nxt.first][nxt.second]);
            continue;
        }
        // 目标点为自己的领土
        else if (belong[board[nxt.first][nxt.second]] == name)
        {
            cout << "peaceful." << endl;
            pos[name] = nxt;
            continue;
        }
        // 目标点为敌方领土
        else
        {
            string enemy = belong[board[nxt.first][nxt.second]];
            // 我方战胜敌方
            if (power[name] > power[enemy] || (power[name] == power[enemy] && name > enemy))
            {
                cout << name << " wins!" << endl;
                pos.erase(enemy);
                power[name] += power[enemy];
                power.erase(enemy);
                while (!domain[enemy].empty())  // 敌方领土归我方所有
                {
                    int tmp = domain[enemy].back();
                    domain[enemy].pop_back();
                    belong[tmp] = name;
                    domain[name].push_back(tmp);
                }
                domain.erase(enemy);
                board[nxt.first][nxt.second] = board[cur.first][cur.second];
                pos[name] = nxt;
                continue;
            }
            // 我方战败
            else
            {
                cout << enemy << " wins!" << endl;
                pos.erase(name);
                power[enemy] += power[name];
                power.erase(name);
                while (!domain[name].empty())  // 我方领土归敌方所有
                {
                    int tmp = domain[name].back();
                    domain[name].pop_back();
                    belong[tmp] = enemy;
                    domain[enemy].push_back(tmp);
                }
                domain.erase(name);
                continue;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

在同学们的提交中也有较好的写法，它将游戏与棋盘封装成了类，所有的操作以成员函数的形式实现：

小红的战争棋盘 63289701

本题的代码可以经过一定的修改改成控制台小游戏，具体可以参考以下步骤：

1. 一个势力作为玩家，其余势力作为电脑；
2. 每个势力轮流操作，玩家势力由玩家输入决定，电脑势力可以随机选择或设计简单逻辑；
3. 每步操作完成后，清屏并打印棋盘，直到游戏结束；
4. 游戏结束后，打印胜利势力。

• 棋盘打印上，可以使用单个拉丁字母表示势力，也可以使用不同的颜***分势力；
• 使用拉丁字母表示势力时，可用大写字母表示军队位置，小写字母表示领土范围；使用颜***分势力时，可用背景色表示领土范围，字符表示军队位置；
• Windows 系统下，可以使用 system("cls") 清屏；Linux 系统下，可以使用 system("clear") 清屏。

感兴趣的同学可以尝试实现一下。

typedef

typedef 是 C++ 中的关键字，用于为已有的类型定义一个新的名字，以方便使用。

本文的代码中，都有以下几行代码，这是出于个人习惯，为了编程方便：

typedef long long ll;               // 定义 ll 为 long long 类型
typedef unsigned long long ull;     // 定义 ull 为 unsigned long long 类型
typedef pair<int, int> pii;         // 定义 pii 为 pair<int, int> 类型
typedef pair<ll, ll> pll;           // 定义 pll 为 pair<ll, ll> 类型
typedef vector<int> vi;             // 定义 vi 为 vector<int> 类型
typedef vector<ll> vl;              // 定义 vl 为 vector<ll> 类型
typedef vector<pii> vpii;           // 定义 vpii 为 vector<pii> 类型
typedef vector<pll> vpll;           // 定义 vpll 为 vector<pll> 类型

#define 也可以用于定义类型别名，它们有什么区别呢？

• typedef 是 C++ 中的关键字，#define 是 C 语言中的预处理命令；
• typedef 只能为已有的类型定义别名，#define 可以为任何字符串定义别名；
• typedef 仅在编译器编译时有效，#define 作用于预处理阶段，即编译之前，它是一个简单的字符串替换，因此可能会产生一些意想不到的错误。
• typedef 不能定义宏，#define 可以定义宏。
• typedef 有作用域，#define 没有作用域。

在定义指针时，typedef 与 #define 的区别更加明显：

typedef int *p1;
#define p2 int *

int x;
const int y;

p1 a, b;    // a, b 都是 int* 类型
p2 c, d;    // c, d 分别是 int* 和 int 类型

const p1 e = &x;    // e 是 int* const 类型(指针常量)
const p2 f = &y;    // f 是 const int* 类型(常量指针)

取模

本次习题涉及一些取模运算，下面列出了取模运算的一些性质：

• $(a+b)\mathrm{m}\mathrm{o}\mathrm{d}p=(a\mathrm{m}\mathrm{o}\mathrm{d}p+b\mathrm{m}\mathrm{o}\mathrm{d}p)\mathrm{m}\mathrm{o}\mathrm{d}p(a+b)\; \backslash bmod\; p\; =\; (a\; \backslash bmod\; p\; +\; b\; \backslash bmod\; p)\; \backslash bmod\; p$
• $(a-b)\mathrm{m}\mathrm{o}\mathrm{d}p=(a\mathrm{m}\mathrm{o}\mathrm{d}p-b\mathrm{m}\mathrm{o}\mathrm{d}p+p)\mathrm{m}\mathrm{o}\mathrm{d}p,a>b(a-b)\; \backslash bmod\; p\; =\; (a\; \backslash bmod\; p\; -\; b\; \backslash bmod\; p\; +\; p)\; \backslash bmod\; p,\; a\; >\; b$
• $(a\times b)\mathrm{m}\mathrm{o}\mathrm{d}p=(a\mathrm{m}\mathrm{o}\mathrm{d}p\times b\mathrm{m}\mathrm{o}\mathrm{d}p)\mathrm{m}\mathrm{o}\mathrm{d}p(a\; \backslash times\; b)\; \backslash bmod\; p\; =\; (a\; \backslash bmod\; p\; \backslash times\; b\; \backslash bmod\; p)\; \backslash bmod\; p$
• $(a^b)\mathrm{m}\mathrm{o}\mathrm{d}p=((a\mathrm{m}\mathrm{o}\mathrm{d}p{)}^b)\mathrm{m}\mathrm{o}\mathrm{d}p(a^b)\; \backslash bmod\; p\; =\; ((a\; \backslash bmod\; p)^b)\; \backslash bmod\; p$