首页

# 江西七校联盟第二场题解

写在前面
提交状态从 Wating\color{brown}{Wating} 到 PendingPending 再到 Accepted\color{green}{Accepted} 亦或是 TLE、WA\color{red}{TLE}、\color{red}{WA}，你学到的是知识，排名 rankrank 对你而言，并不重要。曾经你视为人生唯一目标的高考 rankrank，到现在也只不过是个数字而已，只有学到知识才是正道。与此同时也希望江西七校各位新生，在七校联合训练中，能看看别的学校的、和你们同级的同学都是什么样的，他们都在做些什么。山外面有更高的山，人眼外有更厉害的人。

大家完全不用担心自己的问题显得好像很～～"低级"~~ 就不敢提问，问题不解决就一直是问题。希望大家敢于在群里提出自己的问题，不仅提升效率还能和大家一起交流。希望在 20252025 年，程序设计竞赛在江西省能是每一个怀揣好奇与热忱的同学都能参与的事情，而不再只是少数人攀登的高塔。

江西财经大学出题组祝各位江西七校同学：越活越年轻，越活越开心

题目传送门

# A - 小兰气泡水

# 题目大意

告诉桃花它不用开了，我等的人它已经来了\color{deeppink}{\text{告诉桃花它不用开了，我等的人它已经来了}}

题目本质上是判断给定的序列 A=(a1,...,an)A=(a_1,...,a_n) 是

  • 严格单调递增序列
    • 即为：对于所有 1≤i<j≤n,ai<aj1 \le i < j \le n,a_i < a_j
  • 非严格单调递增序列
    • 即为：对于所有的 1≤i<j≤n,ai≤aj1 \le i < j \le n, a_i \le a_j
  • 其他序列

# 数据范围

  • 1≤n≤1001 \le n \le 100
  • 1≤ai≤10001 \le a_i \le 1000

# 题解

转换一下题意其实题目就很简单了，利用循环判断 a[i] 和 a[i - 1] 的关系即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int n, a[101];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    
    bool flag = 0;
    
    for (int i = 2; i <= n; i++) {
        if (a[i] < a[i - 1]) {
            cout << "illegal\n";
            return 0;
        }
        else if (a[i] == a[i - 1])
            flag = 1;
    }
    
    if (flag)    cout << "no\n";
    else    cout << "yes\n";
}

# B - 别样的数字大战

# 题目大意

往前走

哈基詹与哈基君正在愉快地进行小游戏，规则如下：

  1. 选定一个正整数连续序列 [l,r][l,\,r] 和一个正整数变量 x←lx\gets l。
  2. 两名玩家轮流从序列中删除一个能被 xx 整除的数 。哈基詹总是先手。每次操作后 x←x+1x \gets x + 1。如果某位玩家当前无法删去这样的数，则该玩家输掉游戏。

显然哈基詹和哈基君都是绝顶聪明的，他们都会以最佳策略进行行动，你能判断出这场别样的数字大战的赢家是谁吗？

# 题解

首先不难想到对于 xx 我们在序列中可以删除的数为 x,2x,3x,…,nxx,2x,3x,\ldots,nx，同时有 xx 的初始值为 ll，则当 r<2lr \lt 2l 时，我们只能删除 xx 本身。
这样游戏就变成了轮流取一个数问最后谁没取到的经典问题，有当序列长度为奇数时先手必赢，长度为偶数时先手必败的结论。

然后我们不难发现，若一个人拿到的第一个 xx 为偶数，那么此人往后只能选择偶数。而当 xx 为奇数时，2x2x 为偶数，因此若一个人拿到的第一个 xx 为奇数，此人在一定条件下也能选择偶数。这样就导致了偶数数量的减少，使得只能选择偶数的那个人少了一个可以选择的数，当 x>r2x \gt \frac{r}{2} 时，游戏转变为如上所述的轮流取数的问题，而偶数方因为必然选择的数已经被取走而陷入必败的局面。

因此当 ll 为奇数，r<2lr \lt 2l 时，区间长度为奇数 zyf 赢，否则 zj 赢；r≥2lr \ge 2l 时，则 zyf 一定赢（做法就是开局把 2l2l 删除）。
当 ll 为偶数时，因为 2l2l 也是偶数，如果开局能把 2l2l 拿走，则后期必然导致无路可走，因此 zyf 开局只能拿 ll，问题转换为在 zj 视角下的以奇数开局：则当 r<2(l+1)r\lt2(l+1) 时，问题取决于区间长度奇偶性（因为二人都无法拿走任何东西）；r≥2(l+1)r\ge2(l+1) 时则 zj 必赢。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        if (r < 2 * (l + !(l % 2))) { // 这里合并了 l 奇偶不同的判断，偶数则判断 2*(l+1)
            if ((r - l + 1) % 2)
                cout << "zyf\n";
            else
                cout << "zj\n";
        } else {
            if (l % 2)
                cout << "zyf\n";
            else
                cout << "zj\n";
        }
    }
    return 0;
}

# C - 哈基鱼的校园跑

# 题目大意

十年 OIOI 一场空，不开 longlonglong~long 见祖宗

题目本质其实就是求 a,b,ca, b, c 的最小公倍数，另外注意一下数据范围开 long long 即可。

# 数据范围

  • 1≤a,b,c≤1051 \le a, b, c \le 10^5

# 题解

C++ 中的头文件 <numeric> 就包含了计算最小公倍数的函数 lcm(x, y) ，我们可以直接用它来输出答案。

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <numeric>
using namespace std;

long long a, b, c;

int main() {
    cin >> a >> b >> c;
    cout << lcm(a, lcm(b, c)) << endl;
}

当然，我们也可以自己实现求最大公因数的函数 gcd(x, y) ，进而实现求最小公倍数的函数 lcm(x, y) ，它们的关系是

\frac{x\ *\ y}{gcd(x,\ y)}$$而求最大公因数我们可以通过辗转相除法实现，感兴趣的宝宝可以自行了解[具体内容](https://oi-wiki.org/math/number-theory/gcd/)。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#define int long long   //此处偷点小懒;
using namespace std;

int a, b, c;

int gcd(int x, int y) {
    //利用 gcd(x, y) = gcd(y, x % y) 的性质;
    while (y != 0) {
        int temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

int lcm(int x, int y) {
    return x / gcd(x, y) * y;
}

signed main() { //因为偷懒的缘故，所以我们使用了signed，跟int是等同的;
    cin >> a >> b >> c;
    cout << lcm(a, lcm(b, c)) << endl;
}
# D - 疯狂星期四 ## 题目大意 > 愿这缕飘舞于空的温热，能为天空彼端带来一丝温暖 题目本质是，给出一个 $n$，判断 $3 \times x + 7 \times y = n$ 是否成立（$x, y \in \mathbb{N}_0$） ### 数据范围 - $1\le n \le 10^{5}$ - $1\le x_i \le 10^9$ ## 题解 ### 打表法 $x+3$ 肯定能从 $x$ 得到，所以当我们找到连续三个数字能被表示出来时，剩下的数字中大于这三个数字的数，都能被递推过来。
1
2
3
4
5
6
7
8
9
1 x
2 x
3 = 3 * 1 + 7 * 0
4 = x
...
11 x
12 = 3 * 4 + 7 * 0
13 = 3 * 2 + 7 * 1
14 = 3 * 0 + 7 * 2
我们找到了 $12,13,14$ 三个连续的数字，由这三个数字我们可以推到 $15,16,17$，同理我们可以无穷的向后递推。 因此当 $n$ 满足 $n > 11$ 都被表达。我们只需要判断前 $11$ 个数不行的即可。 ### 公式法： 根据题意扩展一下，对于互质的 $a, b$ 那么由 $ax + by, x \ge 0, y \ge 0$ 不能凑出的最大正整数是 $a \times b - a - b$。 （这是个数学结论，有兴趣的的同学可以去看看怎么证明的） 对于这道题，我们知道3，7互质。 我们求出 $x = 3 \times 7 - 3 - 7 = 11$，（$x$ 代表不能凑出的最大正整数） 进而从 $1$ 到 $11$ 进行特判，从而找到不能被组合的数字。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> m;
        if(m == 1 || m == 2 || m == 4 || m == 5 || m == 8 || m == 11)
            cout << "NO\n";
        else
	        cout << "YES\n";
    }
}
# E - God of Reversal ## 题目大意 > 除我衣上三重雪，天下谁人配白衣 $lengling$ 和 $sunny$ 将要进行 $n$ 场公平对决，但 $sunny$ 不知道的是，$lengling$ 觉醒了名为 **“God of Reversal”**（逆转之神）的替身。 替身有两个能力： 1. **Predict**（预知未来）：$lengling$ 可以预先知道接下来 $n$ 场对决的结局。 2. **Reversal**（逆转）：$lengling$ 可以在任意一场对决前开启此能力，并在任意一场对决结束后结束能力。这段区间内内的所有对决结果都将逆转。该能力最多只能使用一次。 每场对决必有胜负，但只有胜场数大于对手才能获得最终的胜利，请问 $lengling$ 是否能正确且恰当地使用能力，获得最终的胜利？ ### 数据范围 - $1 \le n \le 10^4$ - $a_i \in \{0,1\}$ 输出一行一个字符串。如果 $lengling$ 可以获胜，输出 `YES`；否则输出 `NO`。大小写敏感。 ## 题解： $n$ 场对局， 在提前知道结果的情况下，能否通过最多一次区间段胜负翻转使他的获胜场数大于 $sunny$。 这是道诈骗题。我们记 $lengling$ 和 $sunny$ 的胜场分别为 $s_1,s_2$ - 如果 `s1 > s2` ，不需要发动能力。 - 如果 `s1 = s2` ，令一局 $lengling$ 输的局反转结果即可。 - 如果均不符合，对 $n$ 场对决反转结果即可。 所以是必胜局。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int a[N], n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cout << "YES";
    
    return 0;
}
# F - 采果果 ## 题目大意 你有一个空数组，每次给你一个操作类型 - 操作一为往数组中放入一个给定数 $x$ - 操作二为从数组中取出最小数 $y$ 并输出，如果没有则输出 `null` ## 题解 可以发现题目的 $x$ 的限制很小，最大只有 $100$，因此我们可以考虑使用一个数组储存 $x$ 出现的次数，这里我们记作 $cnt$ - 对于每个操作一我们就将 `cnt[x]` 加一 - 而对于每个操作二，我们就遍历 $1 \to 100$ 的所有数 - 如果某一个 `cnt[i]` 大于 $0$，那我们就输出 $i$，并将 `cnt[i]` 减一 - 否则我们就继续遍历，如果遍历完后都没有找到一个对应 $i$，那么此时说明数组中没有一个数了，此时输出 `null` 即可
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int cnt[105], n, c, x;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> c;
        if(c == 1)
        {
            cin >> x;
            cnt[x]++;
        }
        else
        {
            int ans = -1;
            for (int i = 1; i <= 100; i++)
            {
                if(cnt[i])
                {
                    cnt[i]--;
                    ans = i;
                    break;
                }
            }
            if(ans != -1)
            {
                cout << ans << endl;
                continue;
            }
            cout << "null\n";
        }
    }
    return 0;
}
# G - 吃薯条的条件 ## 题目大意 - 输出 $5^n$ 的最后三位数字。 ### 数据范围 - $3 \le n \le 2 \times 10^{18}$ ## 题解 找规律题 我们通过计算前几项就能发现 - 当 $n$ 为奇数时最后三位数为 $125$ - $n$ 为偶数时最后三位数为 $625$
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

signed main() {
    int n;
    cin >> n;
    if (n % 2 == 0)
        cout << "625";
    else
        cout << "125";
}
# H - 哈基鱼与好字符串 ## 题目大意 > 愿得硕果累累日，笑看世间宁 给定一个长度为 $n$ 的小写字母字符串 $s$，判断该字符串是否为 “好字符串”。 **什么是好字符串** 将字符串 $s$ 拆分为 **至少两段**（形式为 $t_1 + t_2 + ... + t_k$，其中 $k \ge 2$），需满足： 对于 **任意** 两段 $t_i$ 和 $t_j$，都有 `ti 的首字符 != tj 的尾字符` ## 题解 将 “好字符串” 的判定条件简化为核心结论：**若字符串的首字符不等于尾字符，则为好字符串；否则不是好字符串** ### 证明过程 - **情况 1（首 ≠ 尾）**：拆成前 $n-1$ 个字符和最后 $1$ 个字符两段，因首尾字符不同，满足任意两段首 $\ne$ 尾，故为好字符串。 - **情况 2（首 = 尾）**：无论怎么拆，必有一段首为原串首、一段尾为原串尾（首 $=$ 尾），必然违反条件，故不是好字符串。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;              // 字符串长度
        string s;           // 输入字符串
        cin >> n >> s;
        // 判定首字符与尾字符是否相等，输出结果
        cout << (s.front() == s.back() ? "NO" : "YES") << '\n';
    }
    return 0;
}
- 左除 `A \ B`：求解方程 `A·X = B`，返回满足该方程组的解矩阵 X。MATLAB会根据矩阵 A 的性质自动选择最优解法： - 若 $A$ 是方阵且可逆，则直接求解精确解 - 若 $A$ 是矩形矩阵，则返回最小二乘解 - 右除 `A / B`：求解方程 `X·B = A`，转置后左除再转置。它适用于需要解右乘方程组的情况