第 1 次实验

A. 杨辉三角

--> 题目背景

杨辉三角，又称帕斯卡三角形，是二项式系数在三角形中的一种几何排列。杨辉三角在中国南宋数学家杨辉 1261 年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623-1662）在 1654 年发现这一规律，所以这个表又叫做帕斯卡三角形。

杨辉三角具有许多有趣的性质：

• 每行数字左右对称
• 第 $n$ 行的数字有 $n$ 项
• 每个数字等于它上方两数字之和

小蓝鲸在学习了杨辉三角后，尝试自己构造一个有 $n$ 层高的杨辉三角。

--> 题目描述

给定一个正整数 $n$，输出前 $n$ 层杨辉三角。

--> 输入格式

一个正整数 $n$，表示要输出的杨辉三角的层数。

--> 输出格式

输出 $n$ 层杨辉三角，每层数字之间用空格分隔，每层输出完毕后换行。

--> 样例输入 #1

5

--> 样例输出 #1

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

--> 样例输入 #2

7

--> 样例输出 #2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

--> 数据范围

• 对于 100% 的数据，$1 \le n \le 20$。

Solution

按照 a[i][0] = a[i][i] = 1; a[i][j] = a[i-1][j] + a[i-1][j-1] (0<j<i) 的构造规则进行构造即可

#include <bits/stdc++.h>
#define MAX_SIZE 20

using namespace std;

int a[MAX_SIZE+1][MAX_SIZE+1];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    // 构造
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0 || j == i)
                a[i][j] = 1;
            else {
                a[i][j] = a[i-1][j] + a[i-1][j-1];
            }
        }
    }

    // 输出
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }   
    return 0;
}

---

B. 小蓝鲸旋转矩阵

--> 题目描述

小蓝鲸在计算机中用二维数组的形式存储了一个个矩阵。现给定一个包含 $m × n$ 个元素的矩阵（$m$ 行，$n$ 列），请帮助小蓝鲸按照顺时针螺旋顺序，返回矩阵中的所有元素。

--> 输入格式

第一行包含一个整数 $m$，表示矩阵的行数。

第二行包含一个整数 $n$，表示矩阵的列数。

接下来 $m$ 行，每行 $n$ 个整数，表示矩阵每行的各个元素。

--> 输出格式

顺时针螺旋顺序返回的元素，每个元素之间用空格隔开。

--> 示例

Input:

3
3
1 2 3
4 5 6
7 8 9

Output:

1 2 3 6 9 8 7 4 5

--> 数据说明

$1 \leq m, n \leq 20$

$1 \leq$ 矩阵元素的值 $\leq 100$

时间限制：1s

空间限制：128MB

Solution

可以采用递归，也可以设置上下左右四个边界进行收缩

#include <bits/stdc++.h>
#define MAX_SIZE 20

int a[MAX_SIZE+1][MAX_SIZE+1];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    // 读入矩阵
    int m, n; cin >> m >> n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }

    // 设置四个方向的边界
    int up = 1, down = m, left = 1, right = n;
    int p=1,q=1;
    while(1){
        // 左 -> 右
        for(int j = left; j <= right; j++) 
            cout << a[up][j] << " ";
        up++;
        if(up > down) break;    // 判断是否到达中心，退出循环
        // 上 -> 下
        for(int i = up; i <= down; i++) 
            cout << a[i][right] << " ";
        right--;
        if(left > right) break;
        // 右 -> 左
        for(int j = right; j >= left; j--) 
            cout << a[down][j] << " ";
        down--;
        if(up > down) break;
        // 下 -> 上
        for(int i = down; i >= up; i--) 
            cout << a[i][left] << " ";
        left++;
        if(left > right) break;
    }
    return 0;
}

---

C. 小蓝鲸摸牌

--> 题目描述

牌组中的每张卡牌都对应有一个唯一的整数。小蓝鲸想进行一些奇妙的操作，以想要的顺序对这套卡片进行排序。

小蓝鲸有一组未展示的卡牌，卡牌上的数字按从小到大的顺序排列。

小蓝鲸会重复执行以下步骤，直到展示所有卡牌为止：

1. 从牌组顶部抽一张牌，展示它，然后将其从牌组中移出。
2. 如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
3. 如果仍有未展示的牌，那么返回步骤 1。否则，停止行动。

小蓝鲸希望找到一个合适的顺序，使得按照上面的规则摸牌时，能以递增顺序展示卡牌。

答案中的第一张牌被认为处于牌堆顶部。

--> 输入格式

第一行包含一个整数 $n$，表示牌组中的卡牌数量。第二行包含 $n$ 个整数，表示牌组中的卡牌上面的数字。

--> 输出格式

初始牌堆自顶向下的顺序序列。

--> 示例

Input:

7  
2 3 5 7 11 13 17

Output:

2 13 3 11 5 17 7

解释：

我们得到的牌组顺序为 [2,3,5,7,11,13,17]（这个顺序不重要），然后将其重新排序。

重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。

我们展示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。

我们展示 3，然后将 11 移到底部。牌组现在是 [5,17,7,13,11]。

我们展示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。

我们展示 7，然后将 13 移到底部。牌组现在是 [11,17,13]。

我们展示 11，然后将 17 移到底部。牌组现在是 [13,17]。

我们展示 13，然后将 17 移到底部。牌组现在是 [17]。

最后我们展示 17。

所有卡片都是按递增顺序排列展示的。

--> 数据说明

$1 \leq n \leq 1024$

$1 \leq$ 卡牌整数的值 $\leq 10^6$

数据中每个元素互不重复，输入数据已经按升序排列。

时间限制：1s

空间限制：128MB

Solution

我们给出的输出，按照“约瑟夫环问题”中每隔 i 张牌拿走一张牌的规则（本题中 i = 1），顺序恰好对应输入（注意这里的“输入递增”并没有必要，只要卡片展示顺序符合输入数据即可）

所以本题需要实现的是一个“逆约瑟夫环”操作：通过抽牌顺序还原原牌组顺序

这里采用数据数组 + 记录元素是否访问过的 bool 数组进行循环链表的模拟

#include <bits/stdc++.h>
#define MAX_SIZE 1024

int card[MAX_SIZE+1];   // 抽取的顺序
bool vis[MAX_SIZE+1];   // 访问标记
int ans[MAX_SIZE+1];    // 原牌组顺序

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    // 输入
    int n; cin >>n;
    for(int i = 0; i < n; i++) {
        cin >> card[i];
        vis[i] = false;
    }

    // 从第一张牌开始初始化
    int i = 0; vis[0] = true; ans[0] = card[0];

    for(int p = 1; p <= n-1; p++){
        // 前进两格
        int c = 0; 
        while(c < 2){
             i = (i + 1) % n;
            if(vis[i] == false){
                c++;
            }
        }
        // 取出
        vis[i] = true;
        ans[i] = card[p];
    }

    // 输出
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    return 0;
}

2025-11-212025-11-21