A题-dlu

🧊题目大意

按照题目给定的图案规则，输出一个由 . 和 @ 组成的字符矩阵。由于图案结构固定，只与输入的 n 有关，因此直接按规则模拟打印即可。

🧮思路分析

题目本质是输出一个特定形状的字符画。观察输出结构可发现：

图案由若干段 . 和 @ 组成
每一行的拼接方式是固定的
只需要按题目描述的行块顺序逐行打印即可

为了简化打印过程，定义两个函数：

void f1(int x);  // 输出 x 个 '.'
void f2(int x);  // 输出 x 个 '@'

然后根据题目规律分三部分模拟：

上半部分：循环输出 2n 行，每行按固定段落组合
中间分隔部分：输出一行特殊结构
下半部分：输出若干行中空结构，最后输出底边

整体过程不涉及复杂算法，仅为字符模拟。

时间复杂度约为输出规模 (O(n^2))，满足要求。

完整代码如下：

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

void f1(int x);
void f2(int x);

int main() {
    int n;
    cin >> n;

    // 上半部分
    for (int i = 0; i < n * 2; i++) {
        f1(n * 2);
        f2(1);
        f1(n);
        f2(1);
        f1(3 * n + 1);
        cout << endl;
    }

    // 中间特殊行
    f1(1);
    f2(n * 2);
    f1(n);
    f2(1);
    f1(n);
    f2(1);
    f1(n * 2 - 2);
    f2(1);
    f1(1);
    cout << endl;

    // 下半部分中空区域
    for (int i = 0; i < n * 2 - 2; i++) {
        for (int j = 0; j < n * 6 + 3; j++)
            if (j == 1 || j == 2 * n || j == 3 * n + 1 || j == 4 * n + 2 || j == n * 6 + 1)
                cout << "@";
            else
                cout << ".";
        cout << endl;
    }

    // 底边
    f1(1);
    f2(n * 2);
    f1(n);
    f2(1);
    f1(n);
    f2(n * 2);
    f1(1);

    return 0;
}

void f1(int x) {
    for (int i = 0; i < x; i++) cout << ".";
}

void f2(int x) {
    for (int i = 0; i < x; i++) cout << "@";
}

B题-山里灵活的狗

🧊题目大意

活动持续 12 周，每周的登录天数不同。如果有至少 8 周的登录天数 ≥ 5 天，就可以领取奖励。

输入给出学长的所有登录记录，每条记录包含：

周编号 w（1 ≤ w ≤ 12）

登录星期 d（Mon, Tue, Wed, Thu, Fri, Sat, Sun）

需要判断活动结束后是否能拿到奖励。

🧮思路分析

我们要知道每一周学长登录了几天。因此可以用一个容器来统计每周的登录天数。

因为同一天重复登录只算一次，所以同一周内的天数要去重。这可以用：

map<int, set<string>> week_days;

这样 set 自动去重。

输入完毕后，遍历 week_days：

统计有多少周登录天数 ≥ 5。

如果这样的周数 ≥ 8，则输出 "Ayaka Yes!"，否则 "Ayaka No!"。

完整代码如下：

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

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

    int n;
    cin >> n;
    map<int, set<string>> week_days;  // 每周的登录天集合

    for (int i = 0; i < n; i++) {
        int w;
        string d;
        cin >> w >> d;
        week_days[w].insert(d); // 自动去重
    }

    int count_good = 0;
    for (auto &p : week_days) {
        if ((int)p.second.size() >= 5)
            count_good++;
    }

    if (count_good >= 8)
        cout << "Ayaka Yes!" << "\n";
    else
        cout << "Ayaka No!" << "\n";
}

C题-美味的胡汁

🧊题目大意

喝果汁时，每次可以喝 1 杯 / 2 杯 / 3 杯。给定 (n) 杯果汁，问一共有多少种喝完的方案数。

🧮思路分析

这是一道典型的三阶斐波那契数列题目设处理到 (n=k) 时的方案数为 (f(k))。最后一次喝果汁有三种可能：

最后喝 1 杯：前面还有 (k-1) 杯 → (f(k-1))
最后喝 2 杯：前面还有 (k-2) 杯 → (f(k-2))
最后喝 3 杯：前面还有 (k-3) 杯 → (f(k-3))

因此得到递推式：

f(k)=f(k-1)+f(k-2)+f(k-3)

只要先算出初始状态：

f(0)=1
f(1)=1
f(2)=2

就可以从小到大递推到所需的 (n)。

时间复杂度为 (O(n))，远小于 1s 时限。

完整代码如下：

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

vector<long long> a;

void jieguo() {
    for (long long i = 3; i <= 60; i++) {
        long long b = a[i-3] + a[i-2] + a[i-1];
        a.push_back(b);
    }
}

signed main() {
    long long t;
    cin >> t;

    a.push_back(1); // n=0 时的方案数
    a.push_back(1); // n=1 时的方案数
    a.push_back(2); // n=2 时的方案数

    jieguo(); // 预处理递推到 60

    while (t--) {
        long long n;
        cin >> n;
        cout << a[n] << endl;
    }
    return 0;
}

D-小明的日历

📘 题目描述

如果给定的年月日是合法的日期，则输出 YES；
否则输出 NO。

闰年规则：

四年一闰，百年不闰，四百年再闰。

即：

如果能被 400 整除，是闰年；
否则如果能被 100 整除，不是闰年；
否则如果能被 4 整除，是闰年；
否则不是闰年。

💡 思路分析

先判断月份是否合法：
- 合法月份应在 1~12 之间，否则直接输出 NO。
再判断日期是否合法：
- 每个月允许的最大天数不同。
- 闰年的 2 月有 29 天，平年的 2 月有 28 天；
- 4、6、9、11 月有 30 天；
- 其他月份（1、3、5、7、8、10、12）有 31 天。

判断闰年：

bool isLeap = (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);

根据月份检查最大天数是否合法。

完整代码如下：

#include <iostream>
using namespace std;

bool isLegalDate(int y, int m, int d) {
    // 月份非法
    if (m < 1 || m > 12) return false;
    // 日期非法
    if (d < 1) return false;

    // 判断是否闰年
    bool isLeap = (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);

    // 判断每个月的最大天数
    switch (m) {
        case 1: case 3: case 5: case 7: case 8: case 10: case 12:
            return d <= 31;
        case 4: case 6: case 9: case 11:
            return d <= 30;
        case 2:
            return isLeap ? (d <= 29) : (d <= 28);
        default:
            return false;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int y, m, d;
        cin >> y >> m >> d;
        cout << (isLegalDate(y, m, d) ? "YES" : "NO") << endl;
    }
    return 0;
}

E题-或许他真的是斗地主大王

🧊题目大意

输入若干张牌的点数（可能出现的点数为 3~10）。需要判断这些点数中是否存在 五个连续点数都出现过：

若存在，则输出 "Shun Zi"
否则输出 "Dan Zhang"

🧮思路分析

因为点数范围很小（3~10），可以用一个数组统计每个点数是否出现过。

设：

int a[20];

a[x] 表示点数 x 出现的次数
每读到一个点数 j，就让 a[j]++

读完之后，我们只需要在数组中检查：

是否存在 5 个连续位置的值都不为 0。

具体做法：

用变量 j 记录当前连续出现的长度
遍历点数范围：
- 若 a[i]==0，说明断开，j=0
- 否则连续长度 j++
- 一旦 j==5 就说明存在顺子

时间复杂度为 (O(n))，满足要求。

完整代码如下：

#include <stdio.h>

int main() {
    int i, n, j;
    int a[20] = {0};

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &j);
        a[j]++;
    }

    for (i = 0, j = 0; i < 11; i++) {
        if (a[i] == 0)
            j = 0;
        else
            j++;
        if (j == 5)
            break;
    }

    if (j == 5)
        printf("Shun Zi");
    else
        printf("Dan Zhang");

    return 0;
}

F-小明的游戏

📘 题目描述

小明在玩一个游戏，给定一个长度为 n 的整数数组 a，他需要找到其中出现次数 超过一半（> n/2） 的元素，这个元素称为 多数元素（Majority Element）。

题目保证数组中 一定存在多数元素。

💡 思路分析

这题其实是著名的 Boyer–Moore 投票算法（Boyer–Moore Majority Vote Algorithm） 的典型应用。

因为多数元素出现次数超过一半，

如果我们把多数元素和非多数元素两两“抵消”，最后剩下的一定是多数元素。

🔍 算法步骤

初始化候选值 candidate 为数组第一个元素；
计数器 count = 1；
从第二个元素开始遍历：
- 如果当前元素与 candidate 相同，count++；
- 否则 count--；
- 如果 count == 0，说明当前候选值被“抵消”完了，就更新：
  - candidate = 当前元素
  - count = 1
遍历结束后，candidate 即为多数元素。

🧮 示例讲解

输入：

7
1 2 3 2 2 2 5

执行过程：

元素	candidate	count	说明
1	1	1	初始化
2	1	0	不同，count--，为 0，换候选
3	3	1	换成 3
2	3	0	不同，count--，为 0，换候选
2	2	1	新候选 2
2	2	2	相同，count++
5	2	1	不同，count--

最终 candidate = 2 ✅

完整代码如下：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int candidate = nums[0];
    int count = 1;

    for (int i = 1; i < n; i++) {
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }
    }

    cout << candidate << endl;
    return 0;
}

G题-捡灰

🧊题目大意

题目要求构造一个 n × n 的 01 矩阵，并且在满足题目限制的情况下，让矩阵中 1 的数量尽可能多。最后需要输出：

最大的 1 的数量
在这种最优情况下的方案数 m

🧮思路分析

由于题目要求 1 尽可能多，所以我们先把矩阵全部初始化为 1，再通过把部分 1 替换为 0 来满足题意。

1）先观察全 1 时的结构

以 n = 5 为例，把行列按奇偶标记：

偶 奇 偶 奇 偶
偶 1  1  1  1  1
奇 1  1  1  1  1  Y
偶 1  1  1  1  1
奇 1  1  1  1  1  Y
偶 1  1  1  1  1
    Y     Y

在全 1 的情况下，已经有部分行/列满足题目限制（图中用 Y 标记）。这些行/列已经达到最大值，修改会破坏条件，所以不能动。

2）只能修改未满足条件的行/列

因此我们只能在未满足条件的行/列中把部分 1 换成 0。仍以 n = 5 为例，用 ? 表示可替换的位置：

偶 奇 偶 奇 偶
偶 ?  1  ?  1  ?
奇 1  1  1  1  1  Y
偶 ?  1  ?  1  ?
奇 1  1  1  1  1  Y
偶 ?  1  ?  1  ?
    Y     Y

3）每行/列最多替换一个 1

因为目标是让 1 尽可能多，显然偶数行/列的最优情况是：

每行/列尽量保留最多的 1
也就是每行/列最多只能替换 1 个 1 为 0

4）方案数是阶乘

设可替换的行数为 a，可替换的列数也为 a（对称）。那么可替换的位置一共有 a × a = a^2 个。

当我们替换掉一个位置后：

剩下可替换的行、列各减少 1
下一次就只剩 (a-1) × (a-1) = (a-1)^2 个位置可选

如此递推下去：

m = a * (a-1) * (a-2) * ... * 1 = a!

5）求 a 的大小

当 n 为偶数时：未满足条件的行/列数量为 n/2（即奇数下标的个数）所以 m = (n/2)!
当 n 为奇数时：未满足条件的行/列数量为 n/2 + 1（即偶数下标的个数）所以 m = (n/2 + 1)!

6）最大 1 的数量

每个未满足条件的行/列都会替换掉 1 个 1，一共替换 a 个 1，故最大 1 的数量为：

sum = n*n - a

完整代码如下：

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

signed main() {
    int n;
    cin >> n;

    int a = (n + 1) / 2;   // 未满足条件的行/列数量
    int m = 1;

    for (int i = 2; i <= a; i++) {
        m *= i;           // m = a!
    }

    int sum = n * n - a;  // 最大 1 的数量
    cout << sum << endl << m << endl;
    return 0;
}

H题-利滚利

🧊题目大意

输入一个整数 n。需要输出 n * n 的结果，并且保留两位小数的形式。

🧮思路分析

因为输入的 n 是整数，所以 n * n 一定也是整数。题目要求保留两位小数，我们可以直接：

先输出整数部分 n*n
再在后面拼接字符串 .00

这样无需使用浮点数，简单且不会有精度问题。

当然也可以用 double/float 存储并格式化输出两位小数，但这里直接拼接即可。

完整代码如下：

#include <stdio.h>

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

    printf("%d.00", n * n);

    return 0;
}

I题-球

🧊题目大意

袋子里有 a 个白球和 b 个黑球。每次从袋子里随机取出 2 个球：

如果取出的两个球颜色相同（白白 / 黑黑），往袋子里放入 1 个白球
如果颜色不同（白黑），往袋子里放入 1 个黑球

不断操作直到袋子里只剩 1 个球。问最后一个球是黑球的概率是多少。

🧮思路分析

这类“每次取两球再放一球”的问题，总球数每次减少 1，最终一定剩 1 个球。关键在于观察黑球数量的奇偶性是否变化。

考虑每一种取法对黑球数量 b 的影响：

取到两白（WW）
- 黑球数不变
- 放回白球，黑球数仍不变
取到两黑（BB）
- 黑球数减少 2
- 放回白球
- 黑球数变化为 b - 2（奇偶性不变）
取到一白一黑（WB）
- 黑球数减少 1
- 放回黑球
- 黑球数变化为 b（同样奇偶性不变）

所以 无论怎么取球，黑球数量的奇偶性始终不变。

若初始 b 为奇数，则最终剩下的黑球数也为奇数但最后只剩 1 个球 ⇒ 只能是 1 个黑球概率为 1
若初始 b 为偶数，则最终黑球数也为偶数最后只剩 1 个球 ⇒ 只能是 0 个黑球（即白球）概率为 0

因此结论：

b 是奇数 ⇒ 输出 1
b 是偶数 ⇒ 输出 0

完整代码如下：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        if (b % 2) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

J题-来吧粥起

🧩题目大意

签到题

看n个数字的累加和，看是否 ≥ 1,000,000（100 万）。

💡注意

sum要开longlong，会爆int

完整代码如下：

#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;
        cin >> n;
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            sum += x;
        }
        if (sum >= 1000000)
            cout << "Y\n";
        else
            cout << "N\n";
    }
    return 0;
}

K题-binggun 的质数

🧊题目大意

给定两个正整数 a, b。判断是否存在整数 x, y（满足题目要求的范围，通常为非负或正整数），使得：

x * a + y * b 是一个质数。

输出 "Yes" 或 "No"。

🧮思路分析

结论

当且仅当满足下面任一条件时，x * a + y * b 为质数有解：

a, b 中至少有一个是质数
gcd(a, b) = 1

证明

1）当 `a, b` 其中一个为质数

不妨设 a 为质数。取：

x = 1 , y = 0

则：

x * a + y * b = a

显然是质数，所以有解。

2）当 `a, b` 均不是质数

先说明：若 x = 0 或 y = 0，则

x * a + y * b 只能等于 a 或 b，但二者都不是质数，因此不可能得到质数。

所以若要有解，只能考虑：

x > 0 且 y > 0

下面证明：

当 x > 0, y > 0 时， x * a + y * b 为质数 当且仅当 gcd(a, b) = 1

（1）必要性

设：

k = x * a + y * b gcd(a, b) = g

由于 g 同时整除 a 和 b，因此 g 也整除 k，即：

g | k

又因为 x, y > 0，所以 k > g，于是必有：

k = t * g , 且 t >= 2

若 g != 1，则 k 有大于 1 的因子 g，因此 k 不可能是质数。

所以要让 k 为质数，只能有：

gcd(a, b) = 1

（2）充分性

已知 Frobenius 硬币问题的结论：

当 gcd(a, b) = 1 时，对于任意正整数 n，只要满足：

n > ab - a - b

就一定存在正整数解 x, y 使得：

n = a * x + b * y

而质数有无穷多个，因此我们总能找到一个足够大的质数 p，满足：

p > ab - a - b

于是 p 必可写成：

p = a * x + b * y

即存在 x, y 使得 x * a + y * b 为质数。

所以当 gcd(a, b) = 1 时一定有解。

完整代码如下：

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

bool check(int x);

int main() {
    int a, b, flag = 0;
    cin >> a >> b;

    if (__gcd(a, b) == 1 || check(a) || check(b))
        flag = 1;

    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}

bool check(int x) {
    if (x < 2) return false;
    for (int i = 2; i < x; i++)
        if (x % i == 0) return false;
    return true;
}

L-捌族人的密钥

🧩 一、题意理解

题目说「拾族人」和「捌族人」需要使用秘钥交流,并给出了一个秘钥映射表，每两位数字映射一个对应字符

具体映射规则如下：

范围（十进制）对应字符说明：

十进制范围	对应字符	说明
0 ~ 9	`'0' ~ '9'`	数字字符
10	`','`	逗号
11	`'.'`	句号
12 ~ 37	`'A' ~ 'Z'`	26 个大写字母
38 ~ 63	`'a' ~ 'z'`	26 个小写字母

🧮 二、编码过程（例子）

输入如：

516172

我们每两个数为一组：

[51] [61] [72]

这三个八进制数换算成十进制：

51₈ = 5×8 + 1 = 41 61₈ = 6×8 + 1 = 49 72₈ = 7×8 + 2 = 58

再根据映射表：

41 → 'd' 49 → 'l' 58 → 'u'

所以输出 "dlu"

完整代码如下：


int main(){
    int T, key;
    char print;
    cin >> T;
    string code;
    while (T--){
        cin >> code;
        for (int i = 1; i <= code.size(); i += 2){
            // 将两位字符转成一个八进制数
            key = (code[i-1] - 48) * 8 + (code[i] - 48);
            

            // 映射到字符
            if (key >= 0 && key <= 9)
                key += 48;       // '0' ~ '9'
            else if (key >= 12 && key <= 37)
                key += 53;       // 'A' ~ 'Z'，因为 12+53=65('A')
            else if (key >= 38 && key <= 63)
                key += 59;       // 'a' ~ 'z'，因为 38+59=97('a')
            else if (key == 10)
                key = 44;        // ','
            else if (key == 11)
                key = 46;        // '.'
            
            print = key;
            cout << print;
        }
        cout << endl;
    }
    return 0;
}

大连大学2025年11月程序设计竞赛 题解

A题-dlu

🧊题目大意

🧮思路分析

完整代码如下：

B题-山里灵活的狗

🧊题目大意

🧮思路分析

完整代码如下：

C题-美味的胡汁

🧊题目大意

🧮思路分析

完整代码如下：

D-小明的日历

📘 题目描述

💡 思路分析

完整代码如下：

E题-或许他真的是斗地主大王

🧊题目大意

🧮思路分析

完整代码如下：

F-小明的游戏

📘 题目描述

💡 思路分析

🔍 算法步骤

🧮 示例讲解

完整代码如下：

G题-捡灰

🧊题目大意

🧮思路分析

1）先观察全 1 时的结构

2）只能修改未满足条件的行/列

3）每行/列最多替换一个 1

4）方案数是阶乘

5）求 a 的大小

6）最大 1 的数量

完整代码如下：

H题-利滚利

🧊题目大意

🧮思路分析

完整代码如下：

I题-球

🧊题目大意

🧮思路分析

完整代码如下：

J题-来吧粥起

🧩题目大意

💡注意

完整代码如下：

K题-binggun 的质数

🧊题目大意

🧮思路分析

结论

证明

1）当 a, b 其中一个为质数

2）当 a, b 均不是质数

（1）必要性

（2）充分性

完整代码如下：

L-捌族人的密钥

🧩 一、题意理解

🧮 二、编码过程（例子）

完整代码如下：

大连大学2025年11月程序设计竞赛题解

1）当 `a, b` 其中一个为质数

2）当 `a, b` 均不是质数