欢迎2025级新生

2025年南昌师范学院第六届计算机程序设计竞赛

2025年南师算法竞赛题解

A题 根本数不清

注意到题目没有输入，没有输出，仅需输出题目描述中所给出的字符串中：i、1、l 的数量，用空格分隔.

解法1

定义字符串，将题目中给出的字符串复制到编译器中。循环遍历字符串，加入判断逻辑即可。

C++解法如下：

#include <bits/stdc++.h>

int main () {
    std::string s = "i11lll1li1lll1ii1i1li1lii1li11li11lili1lliii1i1lii11i11lli1lii1ii11i1li1ll1lli1i11lll1iilli11li11lill1lllilliilii1lliillillillliili11lii1li1lii11l11lli1llil1lllii1l1l1llii11i1lililiii11li1ll111lili11ii11lii11li11ii11llliiii1ll11lii1ili11liii1lll111liili1i11lii1lii1l";
    int ci = 0, c1 = 0, cl = 0;
    for (char ch : s) {
        if (ch == 'i') ci++;
        else if (ch == '1') c1++;
        else cl++;
    }
    
    std::cout << ci << " " << c1 << " " << cl;
}

C解法如下：

#include <stdio.h>

int main () {
    char s[500] = "i11lll1li1lll1ii1i1li1lii1li11li11lili1lliii1i1lii11i11lli1lii1ii11i1li1ll1lli1i11lll1iilli11li11lill1lllilliilii1lliillillillliili11lii1li1lii11l11lli1llil1lllii1l1l1llii11i1lililiii11li1ll111lili11ii11lii11li11ii11llliiii1ll11lii1ili11liii1lll111liili1i11lii1lii1l#";
    int ci = 0, c1 = 0, cl = 0;
    for (int i = 0; s[i] != '#'; i++) {
        char ch = s[i];
        if (ch == 'i') ci++;
        else if (ch == '1') c1++;
        else cl++;
    }
    
	printf("%d %d %d", ci, c1, cl);
}

解法2

使用 ctrl + F ，直接搜索 i、1、l 的数量。

B题 现在开始好好学习

显然地，每过一天，星期都会发生改变。我们可以统一所有的单位（年、月、日）都为日。

显然地，星期如同无限循环小数一般，反复循环重复下去（1、2、3、4、5、1、2、3......），第0、5、10......位都是相同的。如果星期可以放在数组 arr 中，我们可以认为对 0-base 上的自然数 d： arr[d] = arr[d \ mod \ 5] 注意到，一个月只有30天，一年有12个月。月和年，它们都是5的倍数，它们的变化不会对星期产生影响，举个例子：假设5月1日是星期一，6月1日过去了30天，仍然是星期一。

所以我们甚至可以忽略掉 y 和 m 在题目中的作用。只考虑 d 的差值，即 d_2 - d_1 ，由于日期只可能递增，所以我不妨让 d_2 借上 30 天（可以证明其不会对答案造成影响），以保证 d_2 + 30 - d_1 是正数，我们可以对 d_2 + 30 - d_1 进行模 5 运算求出它在 s 后续的第几个位置。

C++题解如下：

#include <bits/stdc++.h>

std::vector<std::string> weekdays = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

void solve() {
    long long y1, m1, d1, y2, m2, d2;
    std::string s;

    std::cin >> y1 >> m1 >> d1 >> s >> y2 >> m2 >> d2;

    long long dis = d2 - d1 + 30; // 保证正数
    // find 函数只是代替了冗长的 if else 语句，这不是算法的核心。
    long long index = find(weekdays.begin(), weekdays.end(), s) - weekdays.begin();

    index = (index + dis) % 5;

    std::cout << weekdays[index] << "\n";
}

int main () {

    int _;
    std::cin >> _;

    while (_--) {
        solve();
    }
}

C语言解法如下：

#include <stdio.h>

char weekdays[5][15] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

// 可以使用 string.h 的 strcmp 函数
bool is_equal(char a[], char b[]) {
    int i = 0;
    while (a[i] != '\0' && b[i] != '\0') {
        if (a[i] != b[i]) return false;
        i++;
    }
    return a[i] == b[i];
}

int find_index(char s[]) {
    for (int i = 0; i < 5; i++) {
        if (is_equal(weekdays[i], s)) {
            return i;
        }
    }
    return -1;
}

void solve() {
    long long y1, m1, d1, y2, m2, d2;
    char s[15];

    scanf("%lld %lld %lld %s %lld %lld %lld", &y1, &m1, &d1, s, &y2, &m2, &d2);

    long long dis = d2 - d1 + 30;
    int index = find_index(s);

    index = (index + dis) % 5;
    printf("%s\n", weekdays[index]);
}

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

    while (_--) {
        solve();
    }

    return 0;
}

C题 不要作弊

这是一个思维构造题，也许我们暂时不能在赛场中想到充分的理由证明它的正确，但是依然可以大胆猜测可能的答案。

不妨令所有的奇数都为1，所有的偶数都为0，这样不影响结果的奇偶性，方便我们进行推算。

注意到，偶数不会对奇偶的结果产生影响，要满足每列的和都为偶数，则必然需要每列的奇数数量是偶数个，总的奇数数量自然也是偶数个。而对于奇数的 n，永远无法给出偶数个奇数的积木，故所有奇数的 n 都不满足题目条件。

对于偶数的情况，我们率先考虑从左往右、从上往下的自然的构造，若 n / 2 为奇数，容易证明其满足题意的；对于 n / 2 为偶数，将奇数行的第一个积木与其下方相邻的偶数行的第二个积木交换。 \boxed{ \begin{vmatrix} 1 & 0 & 1 & 0 & \cdots & 0 \\ 1 & 0 & 1 & 0 & \cdots & 0 \\ 1 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 0 & 1 & 0 & \cdots & 0 \end{vmatrix}\quad转换为\quad \begin{vmatrix} 0 & 0 & 1 & 0 & \cdots & 0 \\ 1 & 1 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & 0 & \cdots & 0 \end{vmatrix}} 对于所有的 n / 2 为偶数的情况，均可用这种构造解决。也就是说，n 为偶数均符合题意，奇数均不符合题意。

D题 减肥

注意到这是一个数学题，核心公式 c_i = p×c_{i - 1}+ (1 - p) ×r_{i - 1} ，而目的是最大化\Sigma_{i=1}^{n}(c_i−r_i)。对于此种动态的问题，如果代入 c_{i - 1} 结果不怎么明显，那我们可以试着求一下邻项的差，这是高中数列题常用的方法 c_i - c_{i-1} = (p-1)×c_{i-1}+(1-p)×r_{i - 1} 乘法结合律 c_{i} - c_{i-1} = (p-1)×(c_{i-1} - r_{i - 1}) 移项可得 \frac{c_i - c_{i-1}}{p-1} = (c_{i-1} - r_{i-1}) 左边求和和高中常见的数列求和思想相似，右边求和即是我们的答案。累加可以得到 \Sigma_{i=1}^{n}(c_i−r_i)=\frac{c_{n+1} - c_1}{p - 1} 由于 p-1 是负数，保证 c_n 最小，则意味着左边的值最大，根据核心公式，可以证明每个 r_i 都取最小是最优的，所以我们需要保证每个不被确认的 r_i 都取 L。C++解法如下：

#include <bits/stdc++.h>

void solve()
{
    int n, k;
    double r0, c0, p, L, R;
    std::cin >> n >> k >> r0 >> c0 >> p >> L >> R;
    std::vector<double> r(n + 1, L);
    for (int i = 0; i < k; i++)
    {
        int x;
        double v;
        std::cin >> x >> v;
        r[x] = v;
    }
    double C1 = p * c0 + (1.0 - p) * r0;
    double C = C1;
    for (int i = 2; i <= n + 1; i++)
    {
        C = p * C + (1 - p) * r[i - 1];
    }
    std::cout << std::fixed << std::setprecision(6) << (C1 - C) / (1 - p) << "\n";
}

int main () {

    int _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }
}

C语言解法如下：

#include <stdio.h>

void solve() {
    int n, k;
    double r0, c0, p, L, R;
    scanf("%d %d %lf %lf %lf %lf %lf", &n, &k, &r0, &c0, &p, &L, &R);
    double r[100005];

    for (int i = 0; i <= n; i++) {
        r[i] = L;
    }

    for (int i = 0; i < k; i++) {
        int x;
        double v;
        scanf("%d %lf", &x, &v);
        r[x] = v;
    }

    double C1 = p * c0 + (1.0 - p) * r0;
    double C = C1;
    for (int i = 2; i <= n + 1; i++) {
        C = p * C + (1.0 - p) * r[i - 1];
    }

    printf("%lf\n", (C1 - C) / (1.0 - p));
}

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

    while (_--) {
        solve();
    }

    return 0;
}

E题 galgame领域大神

显然，要满足每个角色活动次数都不同，最划算的做法是按照公差为1的等差数列进行互动。例如K = 4 的时候，最划算的精力值消耗是 {1, 2, 3, 4} 而不是 {2, 3, 4, 5}。

可以使用等差数列公式让复杂度达到 O(1)。C++代码如下：

#include <bits/stdc++.h>

void solve()
{
    long long N, K;
    std::cin >> N >> K;

    long long need = (K + 1) * K / 2;
    if (need <= N) std::cout << "Yes\n";
    else std::cout << "No\n";
}

int main () {

    int _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }
}

F题 打乱的歌单

这里有三个论断：

  1. 注意到，我们可以保证，对每首歌曲最多只需要一次移动的操作，就能构成任意的歌单顺序，包括让它们严格递增。
  2. 注意到，选定一个不移动的歌曲的序列，随后进行有限次操作，这个序列必将由原来的离散状态变为连续的状态（原因是序列中间的任何未选中的歌曲都将被移动出去，而序列外的歌曲无法移入序列中间）。
  3. 我们定义把一个歌曲移到队首，则它会放置在分割线左边，把一个歌曲移到队尾，则它会放置在分割线右边，这种操作使得最后的歌单被分割线分割，但是我们依然可以保证，对每首歌曲最多只需要一次移动的操作，就能让歌单以任意顺序分布在分割线的任意相对位置。

论断 1 确保每个歌曲进行一次操作能达成题意，因此我们可以把题目反转过来，求最多的不用移动的歌曲个数，再用歌单长度减去它。而又因为题目要求，最后的歌单中任意一个连续子段必然是公差为 1 的等差数列，所以我们可以根据论断 2 和论断 3，把最长的不用移动的歌曲个数精确为最长的递增子序列，其公差为 1。

于是题目变成了，寻找数组中以 1 递增的最长子序列。C++代码如下：

#include <bits/stdc++.h>

void solve()
{
    int n;
    std::cin >> n;

    std::vector<int> arr(n), pos(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
        pos[arr[i]] = i;
    }

    int cur_len = 1, ans = 1;
    for (int i = 2; i <= n; i++) {
        if (pos[i] > pos[i - 1]) {
            cur_len++;
        } else {
            cur_len = 1;
        }
        ans = std::max(ans, cur_len);
    }

    std::cout << n - ans;
}

int main () {
    int _ = 1;
    while (_--) {
        solve();
    }
}

C语言解法如下：

#include <stdio.h>

void solve() {
    int n;
    scanf("%d", &n);
    int arr[10005], pos[10005];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        pos[arr[i]] = i;
    }
    int cur_len = 1, ans = 1;
    for (int i = 2; i <= n; i++) {
        if (pos[i] > pos[i - 1]) {
            cur_len++;
        } else {
            cur_len = 1;
        }
        if (cur_len > ans) ans = cur_len;
    }
    printf("%d\n", n - ans);
}

int main() {
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}