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

A. 计算机内存

题目链接：A. 计算机内存

基本的算术运算题：

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

// 我们可以看到题目描述的上方有一个空间限制 32M, 在计算机中一个整数占据 4 个字节的内存, 
// 1MB 等于 1024KB, 1KB 等于 1024B, 1B 就代表 1 字节, 那么请问 n MB 的内存可以使用多少个整数呢?

void solve()
{
    int n;
    cin >> n;
    cout << n * 1024 * 1024 / 4 << endl;
}

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

值得注意的是，本题要求输出整数，故应先算乘再算除，以保证整数性；例如 n / 4 * 1024 * 1024 在本题就是错误的。 除此之外，将 / 4 写成 * 0.25 也是错误的，本质上相当于先进行了除法。

当一个算术表达式中同时有乘除运算时，先乘再除可以更好地保证精度，先除再乘可以更好地防止溢出。

B. 浮点除法

题目链接：B. 浮点除法

printf

使用格式控制符 %.3f 即可保留三位小数：

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

// 输入两个整数 a, b, 输出 a 除以 b 的值，保留三位小数

void solve()
{
    int a, b;
    cin >> a >> b;
    printf("%.3f\n", (double)a / b);
}

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

cout

使用 fixed 和 setprecision(3) 即可保留三位小数：

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

// 输入两个整数 a, b, 输出 a 除以 b 的值，保留三位小数

void solve()
{
    int a, b;
    cin >> a >> b;
    cout << fixed << setprecision(3) << (double)a / b << endl;
}

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

需要注意的是，如果不使用 fixed，则 setprecision 设置的是有效数字的位数，而不是小数点后的位数。 并且，fixed 和 setprecision 的作用域是全局的，即一旦使用，后续的所有输出都会受到影响。

C. 排队领水

题目链接：C. 排队领水

简单思维题：

1. 不少于 a 个人在他前面，即他必然在最后 n - a 个人中；
2. 不多于 b 个人在他后面，即他必然在最后 b + 1 个人中。

综上，懒羊羊可能的位置个数应为 min(n - a, b + 1)。

其实题目有 bug，羊村村民排队打水，不应该有人

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

// 羊村的供水系统搞砸了，隔壁牛村捐赠的的矿泉水刚刚送达，村长让喜羊羊们排队领水，
// 已知有 n 个羊村村民正在排队取水，懒羊羊不知道他在队伍的具体哪个位置，
// 但他知道有不少于 a 个人在他前面，有不多于 b 个人在他后面，
// 你能帮忙计算一下懒羊羊有多少个可能的位置吗？

void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n - a, b + 1) << endl;
}

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

D. 最大公约数

题目链接：D. 最大公约数

简单数学题，辗转相除法求最大公约数：

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }  // 递归形式
// int gcd(int a, int b) { while (b) { int t = a % b; a = b; b = t; } return a; } // 迭代形式

void solve()
{
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
}

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

如果你不想自己定义 gcd 函数，也可以使用 <algorithm> 头文件中的 __gcd 函数。

除了最大公约数，还有最小公倍数，可以使用 a * b / gcd(a, b) 求得。

E. 打印质数表

题目链接：E. 打印质数表

考察大家对于质数的判断：

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

bool isPrime(int x)
{
    if (x == 1)
        return false;  // 1 既不是质数也不是合数
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;  // 有除了 1 和自身以外的因子的数不是质数
    return true;  // 其余的数都是质数
}

void solve()
{
    int n;
    cin >> n;
    bool flag = false;
    for (int i = 2; i <= n; i++)
    {
        if (isPrime(i))
        {
            if (flag)
                cout << " ";
            cout << i;
            flag = true;
        }
    }
    cout << endl;
}

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

F. 数位之和

题目链接：F. 数位之和

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

// 求一个整数的所有数位之和

void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    while (n)
    {
        ans += n % 10;  // 取个位值
        n /= 10;        // 整体右移一位
    }
    cout << ans << endl;
}

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

你也可以使用 to_string 将整数转换为字符串，然后遍历字符串求和。

G. 字符框

题目链接：G. 字符框

判断含有 face 四个字符的 2*2 字符框的个数，判断方法不止一种。 n*m 的区域中，有 (n - 1) * (m - 1) 个 2*2 的字符框，遍历时应注意范围，不要越界。

4 次 if

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

// 给你 n∗m 的二维网格，求 2∗2 的方格的个数，方框里面的字符可以构成 'face'

void solve()
{
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++)
        {
            if (a[i][j] != 'f' && a[i][j + 1] != 'f' && a[i + 1][j] != 'f' && a[i + 1][j + 1] != 'f')
                continue;
            if (a[i][j] != 'a' && a[i][j + 1] != 'a' && a[i + 1][j] != 'a' && a[i + 1][j + 1] != 'a')
                continue;
            if (a[i][j] != 'c' && a[i][j + 1] != 'c' && a[i + 1][j] != 'c' && a[i + 1][j + 1] != 'c')
                continue;
            if (a[i][j] != 'e' && a[i][j + 1] != 'e' && a[i + 1][j] != 'e' && a[i + 1][j + 1] != 'e')
                continue;
            ans++;
        }
    cout << ans << endl;
}

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

set 集合

学过 STL 的同学可以使用 set 集合来判断：

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

// 给你 n∗m 的二维网格，求 2∗2 的方格的个数，方框里面的字符可以构成 'face'

void solve()
{
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++)
        {
            set<char> s = {a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]};
            if (s.count('f') && s.count('a') && s.count('c') && s.count('e'))
                ans++;
        }
    cout << ans << endl;
}

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

其他判断方法

我们在同学们的代码中还看到了一些其他的判断方法，例如：

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

// 给你 n∗m 的二维网格，求 2∗2 的方格的个数，方框里面的字符可以构成 'face'

void solve()
{
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++)
        {
            int cc = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
            if (cc == 'f' + 'a' + 'c' + 'e')
                ans++;
        }
    cout << ans << endl;
}

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

这个写法在牛客的评测系统中是可以通过的，但是这样的写法是错误的。 事实上我们可以轻松举出反例，例如 dbbg 这四个字符的 ASCII 码和也是和 face 相等的。

a-z 对应 ASCII 码为 97-122。

但这样启发我们想到了一种可能的比较简洁的写法：

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

// 给你 n∗m 的二维网格，求 2∗2 的方格的个数，方框里面的字符可以构成 'face'

int f(char c)
{
    return c * c + 17;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m - 1; j++)
        {
            int cc = f(a[i][j]) + f(a[i][j + 1]) + f(a[i + 1][j]) + f(a[i + 1][j + 1]);
            if (cc == f('f') + f('a') + f('c') + f('e'))
                ans++;
        }
    cout << ans << endl;
}

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

我们只需要找到一个函数 f，使得 f('f') + f('a') + f('c') + f('e') 的值在所有可能的情况中都是唯一的即可。 这里利用了类似于哈希的思想，但上面代码中 f 函数的有效性还有待验证，并不一定真的唯一，只是我们举的一个例子。

H. [NOIP2015]金币

题目链接：H. [NOIP2015]金币

使用循环模拟即可：

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

// 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；
// 之后两天（第二天和第三天），每天收到两枚金币；
// 之后三天（第四、五、六天），每天收到三枚金币；
// 之后四天（第七、八、九、十天），每天收到四枚金币……；
// 这种工资发放模式会一直这样延续下去：
// 当连续 N 天每天收到 N 枚金币后，骑士会在之后的连续 N+1 天里，每天收到 N+1 枚金币。
// 请计算在前 K 天里，骑士一共获得了多少金币。

void solve()
{
    int k;
    cin >> k;
    int ans = 0;
    int i = 1;
    while (k > 0)
    {
        for (int j = 0; j < i && k > 0; j++)
        {
            ans += i;
            k--;
        }
        i++;
    }
    cout << ans << endl;
}

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

I. [NOIP2009]多项式输出

题目链接：I. [NOIP2009]多项式输出

分别对 n+1 项进行判断，需要考虑的情况较多，有：

1. 系数为 0 时，不需要输出该项；
2. 系数为正且该项不是第一个输出项时，需要输出 +；
3. 系数为负时，需要输出 -；
4. 系数绝对值为 1 且不为常数项时，不需要输出系数；
5. 常数项不需要输出 x 和指数。
6. 非常数项指数为 1 时，不需要输出指数。

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

void solve()
{
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 0; i <= n; i++)
        cin >> a[i];
    bool flag = false;
    for (int i = 0; i <= n; i++)
    {
        if (a[i] == 0)
            continue;
        if (a[i] > 0 && flag)
            cout << "+";
        if (a[i] < 0)
            cout << "-";
        if (abs(a[i]) != 1 || i == n)
            cout << abs(a[i]);
        if (i < n - 1)
            cout << "x^" << n - i;
        if (i == n - 1)
            cout << "x";
        flag = true;
    }
    cout << endl;
}

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

std::ios::sync_with_stdio(false);

在默认情况下，cin / cout 是极为迟缓的读入/输出方式，而 scanf / printf 比 cin / cout 快得多。

std::ios::sync_with_stdio(); 是一个「是否兼容 stdio」的开关，C++ 为了兼容 C，保证程序在使用了 printf 和 cout 的时候不发生混乱，将输出流绑到了一起。同步的输出流是线程安全的。

这其实是 C++ 为了兼容而采取的保守措施，也是使 cin / cout 速度较慢的主要原因。我们可以在进行 IO 操作之前将 stdio 解除绑定，但是在这样做之后要注意不能同时使用 cin 和 scanf，也不能同时使用 cout 和 printf，但是可以同时使用 cin 和 printf，也可以同时使用 scanf 和 cout。

bits/stdc++.h

bits/stdc++.h 是一个非标准的头文件，它包含了标准库中常用的头文件。

使用 bits/stdc++.h 有以下几个优点：

1. 大部分竞赛环境都支持 bits/stdc++.h，比赛时使用它可以节省写头文件的时间；
2. 对于大部分的 C++ 标准库函数，我们不再需要去记忆它们所属的头文件，直接使用 bits/stdc++.h 即可；

当然它也有一些缺点：

1. bits/stdc++.h 是非标准的头文件，在某些环境下可能无法使用，可移植性较差，不建议在工程中使用；
2. bits/stdc++.h 包含了标准库中常用的头文件，但我们通常只会用到其中的一小部分，使用 bits/stdc++.h 会增加编译时间。
3. 同时使用 bits/stdc++.h 和 using namespace std; 易导致命名空间污染。

下图展示了笔者设备上 bits/stdc++.h 包含的内容：