果壳语法杯ROUND6题解

YZY Lv3
  2025-06-17 20:41:46 2025-06-17 20:41:46 Created   2025-06-17 20:41:46 2025-06-17 20:41:46 Updated      

宋祖校场演练记

题目背景

显德年间，后周世宗柴荣亲征南唐，战至寿州城下，势如破竹。

兵贵练而不贵多。寿州城下，柴荣命令军中诸将，于大营校场比试演练，以立威仪。
赵匡胤麾下将士过万，遂按军籍编号，自 至 依次记录。

演练初始，诸将得分皆为零。
每次比试，两将对垒，胜者得 分，败者得 分，未有平局，得分可为负数。

比试日久，至演练终局，得知第 至第 号将士之最终得分，惟赵匡胤（第 号将士）所得未明。

然每场比试得分之总和不变，初终如一，故赵匡胤最终得分必然唯一。

为了将来能够顺利建功立业，请你帮赵匡胤计算他的得分。

输入输出格式

输入格式

输入包含两行：

  • 第一行：一整数 ，表示将士人数；
  • 第二行： 个整数，第 个数表示编号为 的将士最终得分。

输出格式

输出一行整数，表示编号为 的赵匡胤的最终得分。

题目样例

样例#01

1
2
4
1 -2 -1
1
2

以下是一个可能的演练过程，其中第 、、 号将士的最终得分分别为 、、：

  • 初始时，诸将得分均为 ，即：(0, 0, 0, 0)
  • 第 号将士与第 号将士对垒，第 号胜。得分变化为：(1, -1, 0, 0)
  • 第 号将士与赵匡胤（第 号）比试，赵匡胤胜。得分变化为：(0, -1, 0, 1)
  • 第 号将士与第 号将士再战，第 号胜。得分变化为：(1, -2, 0, 1)
  • 第 号将士与第 号将士比试，第 号胜。得分变化为：(1, -1, -1, 1)
  • 第 号将士与赵匡胤比试，赵匡胤胜。得分变化为：(1, -2, -1, 2)
  • 最终第 号得分 ，第 号得分 ，第 号得分 ，赵匡胤得分 。

样例#02

1
2
4
0 0 0
1
0

样例#03

1
2
6
10 20 30 40 50
1
-150

数据范围

  • 输入均为整数。

解题思路

设定 第 x 个选手 得分为
1 -2 -1
1 -2 -1 ?

通过分析 4 个选手 参加 的场数固定 假设为 k 场 则 1 ~4 参加的场数相加 一定为 2*k

对于每场 一定有一个人 得分为 -1 另一个人得分 为1
所以 将 1~4 加起来一定为 0

因此 对于n个人 $$\sum_{i=1}^n(score_i) = \sum_{i=1}^{n-1} {score_{i}}+ score_n = 0$$

所以有

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
void solve();
int main(){
        solve();
}
void solve()
{
        int n,x;
        cin>>n;
        n--;
        int sum = 0;
        while(n--)
        {
                cin>>x;
                sum+=x;
        }
        cout<<-sum;
}

赵匡胤的箭

题目背景

显德年间，后周世宗柴荣亲征南唐，麾下都虞候赵匡胤，统兵随行，威震江淮。

时赵匡胤尚效命周室，未有称帝之志，然英武已显。
南征之前，赵匡胤于大营校场试射百箭，以示军威，安士气。

天道无常，凡三之数，风生云起，扰乱箭势，致使不中靶；
其余诸箭，皆应手而发，百步穿杨。

请依次记录赵匡胤试箭之成败，呈于帅帐。

输入格式

一行一个整数 ，表示赵匡胤将军所试射的箭数。

输出格式

输出一行字符，长度恰为 ，第 i 个字符表示赵匡胤第 i 次试箭是否命中靶心。

  • 若第 支箭命中靶心，输出大写字母 ‘T’；
  • 若第 支箭脱靶，输出大写字母 ‘F’。

题目样例

样例#01

1
7
1
TTFTTFT

样例#02

1
9
1
TTFTTFTTF

样例解释

第一组样例中，第 3 次与第 6 次试箭为三之数，故未中靶心，输出 F；

第二组样例中，第 3，6，9 次试箭为三之数，故未中靶心，输出 F；

数据范围

  • 输出只有大写字母 ‘T’ 或 ‘F’

解题思路

根据输入是否是三的倍数做输出

参考代码 1

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;
        cin>>n;
        for(int i = 1;i<=n;i++)
        {
                if(i%3) cout<<"F";
                else cout<<"T";
         } 
        return 0;
}

参考代码 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;                // 箭数
    if(!(cin>>n)) return 0;
    string s(n,'T');      // 先假设全部命中
    for(int i=2;i<n;i+=3) // 0-基下的 2,5,8,… 即 3 的倍数
        s[i]='F';
    cout<<s<<"\n";
    return 0;
}

宋祖铸兵策

题目背景

显德年间，后周世宗柴荣亲征南唐，师次寿州，围城已久，旌旗蔽日，兵马屯扎。

寿州（今安徽寿县）古代就是铁矿资源地，矿产遍布四方，唯因战事紧急，赵匡胤奉命急炼兵器以备突袭。

铁料品质高低不一，需工匠锻炼而成兵器。铁矿中，每块铁料有其天然品质为正整数 。

炼制兵器时，成品兵器之刚性系数，计算规则如下：

  • 将铁块品质 除以工匠能力值 ，取其整数部分（即商）；
  • 将铁块品质 除以工匠能力值 所余之余数，加于上述所得；
  • 商与余数之和，便为该兵器的刚性系数。

简言之，刚性系数为：
铁块品质除以工匠能力值所得的商与余数之和。

赵匡胤欲于每次开采所得之铁矿中，择最佳品质铁料，铸成锋锐兵器。

围城之际，赵匡胤数度遣人临时开采铁矿。每次开采，矿洞内铁矿品质在区间 之内，而寻找到的工匠能力值为 。

请你助赵匡胤，求出区间 内，最大可得之刚性系数。

输入输出格式

输入格式

第一行包含一个整数 ，表示数据组数。

接下来 行，每行包含三个整数 ，分别表示矿洞中铁矿的最低品质，最高品质与找到的工匠能力值。

输出格式

对于每组数据，输出一行一个整数，表示对应矿洞中和铁匠能锻造的最大刚性系数。

题目样例

样例#01

1
2
3
4
5
6
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
1
2
3
4
5
2
4
5
999999999
5

样例说明

以第一组数据为例，工匠能力值为 ，铁块品质区间为 。逐一计算：

  • 品质 ：，余 ，刚性系数为 ；
  • 品质 ：，余 ，刚性系数为 ；
  • 品质 ：，余 ，刚性系数为 ；
  • 品质 ：，余 ，刚性系数为 。

故最大刚性系数为 。

数据范围

  • ，
  • ，
  • $1 \leq a_i \l

题意描述

本题为 在区间 中求使 最大的 x

暴力解

直接枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define N int(1e8)
int st[N];
int top; 
int main(){
    int t;
    cin>>t;
    while(t--){
        long long l,r,a;
        cin>>l>>r>>a;
        long long m = 0;
        while(l<=r){
            m = max(m,l/a+l%a);
            l++;
        }
        cout<<m<<endl;
        
    }
    return 0;
}

结论

在区间 中， 都有 为区间 中最大值。

因此在区间 中 为区间最大值。

当前仅当 , 满足

因此，如果存在x ，则 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define N int(1e8)
int st[N];
int top; 
int main(){
    int t;
    cin>>t;
    while(t--){
        long long l,r,a;
        cin>>l>>r>>a;
        long long re = r%a;
        if(r-re>l){
            l = r-re-1;
        }
        cout<<max(r/a+r%a,l/a+l%a)<<endl; 
        
    }
    return 0;
}

宋祖布阵策

题目背景

显德年间，后周世宗柴荣北伐南唐，遣殿前都虞候赵匡胤自行领兵，进攻清流关。

清流关地势险峻，城池高固，易守难攻。
赵匡胤屯兵关下，需设攻具以破城防。军中所余器材有限，各长短不一，依次以正整数 计量。

赵匡胤欲依现有器材布设攻阵。每个阵列要求：

  • 轮廓闭合，边长相等；
  • 每条边由一根器材独立成形；
  • 器材不可接续，不可折断；
  • 每根器材仅能使用一次。

请助赵匡胤，计算最多能同时构建多少个符合要求的阵列。

输入输出格式

输入格式

输入包含两行：

  • 第一行包含一个整数 ，表示器材数量；
  • 第二行包含 个正整数 ，表示各器材的长度。

输出格式

输出一个整数，表示最多能同时成形的阵列数。

题目样例

样例#01

1
2
1
1
1
0

样例#02

1
2
4
1 1 2 2
1
0

样例#03

1
2
6
2 2 3 3 3 3
1
1

样例#04

1
2
9
4 2 2 2 2 4 2 4 4
1
2

样例说明

  • 第二组 虽然可以构造 (2,2,2) 但其中一个
    2 是由两个 1 组成的
  • 第三组可使用 根长度为 的器材拼成一个正方阵；
  • 第四组可用四根长度为 的器材成一阵，另以四根长度为 的器材成另一阵，共 个阵列。

数据范围

  • ；
  • 。

题意简述

题目给定不同长度的材料 只能用其中相同长度的 拼搭出来 正多边形
比如 1 2 1 1 2 2 2 就可以用长度 为1的材料 拼接一个 正三角形 和 用长度 为2的材料 拼接一个正四边形。
题目想要求出 最多可以组合多少个正多边形

做题思路

通过分析，我们发现对于一个长度为x的材料来说，尽量多的组成正多边形 其实就是去组成正三角形。

  1. 求解出每种长度木棒的个数
  2. 对于每种木棒 拼出的最多个数 为 num[x]/3

参考代码

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

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

    int n; if(!(cin>>n)) return 0;
    const int M=1'000'000;
    static int cnt[M+1]={0};   // 计数
    for(int i=0,x;i<n;i++){
        cin>>x;
        ++cnt[x];
    }
    ll ans=0;
    for(int i=1;i<=M;i++) ans+=cnt[i]/3;
    cout<<ans<<"\n";
    return 0;
}

宋祖清册策

题目背景

显德年间，后周世宗柴荣亲征南唐，遣殿前都虞候赵匡胤自领兵马，鏖战江淮，克清流关，复取滁州城。

城破之后，赵匡胤为抚安百姓，急命清点户籍，登册造籍，以定徭役兵赋。时值战乱新平，百姓流离失所，民籍荒废，城中居民杂处，未有秩序。

官吏仓促立册，录入各户，唯因形势匆忙，登记无序，名册上居民顺序错乱无章，不能循序。

赵匡胤素重治安，以法制民。为整肃城中百姓，复定纲纪，赵匡胤下令：

  • 清册之中，每户应有一编号，编户齐备，编号为 至 ，一一对应，绝无重号；
  • 册中居民当依编号自小至大依次排列，次第井然，以示法治；
  • 每次整顿操作，吏卒可点名两户，互换二者在清册之中之列位；
  • 各户不得擅动位置，亦不得自行更易，唯官吏指令，方可移列；
  • 更易操作无数量限制。
  • 整顿完成，需如实录明整顿步骤，记下每次交换所涉及的两户列位编号；
  • 整顿后，需确保清册顺序为（），一一对应，编号无误。

然则清册初立错杂无章，官吏徒有法令，不知如何整顿而从速。赵匡胤念军政之急，召能吏参议，求最佳整序之策，令不误国事，不扰民生。

任务说明

你需参赞赵匡胤，定一策令，使得最终清册之居民编号，依次为 （），无一错位。

你应具录整顿步骤，列出所需操作次数及每次操作所交换的两户位置。

输入输出格式

输入格式

输入一共两行：

第一行一整数 ，表示城中居民户数；

第二行 个正整数，表示初始登记的居民编号顺序。

保证编号各不相同，且为 至 之间整数，清册初立，顺序错杂，需整顿。

输出格式

第一行输出整顿操作的总次数 K

接下来 K 行，每一行，输出一对整数 ，表示将清册中第 户与第 户居民的列位交换。

整顿完成后，清册中居民编号应严格依次为 。

题目样例

样例#01

1
2
5
3 4 1 2 5
1
2
3
2
1 3
2 4

样例说明
操作改变序列如下

  • 最初为 。
  • 第一次操作将第一和第三个元素对调，得到 。
  • 第二次操作将第二和第四元素对调，得到 。

** 其他输出结果，例如以下结果，也被认为是正确的：**

1
2
3
4
5
4
2 3
3 4
1 2
2 3

样例#02

1
2
4
1 2 3 4
1
0

样例#03

1
2
3
3 1 2
1
2
3
2
1 2
2 3

数据范围

  • ；
  • 输入的居民编号为 至 的一个排列，且互不相同。

题目分析

其实本题无非就是输出一种排序方式使序列有序

  • 排序解法：只要能在一定复杂度内完成排序即可，排序的过程就是对应答案，只需要用栈或者队列存储过程即可。
    • 暴力分：冒泡，选择等超慢的 排序均可 反正是拿五十分的暴力分。
    • 排序正解：快排或者归并排序，拿到复杂度全分
  • 贪心&&链表: 由于元素是1~n的可以利用这里的特殊性质。
    • 本题采用一种奇怪链表模拟交换的思路。 这题补完可以去尝试ABC395D
    • 由于贪心局部最优的性质，我们只要能在第x步使元素x移动到第x个位置即可，并且并不会影响到前面位置的选择。
    • 比如 5 3 4 1 2
      1. 元素在 4 位置 1 与 4 交换 得到 1 3 4 5 2
      2. 元素在 5 位置 2 与 5 交换 得到 1 2 4 5 3
      3. 元素在 5 位置 3 与 5 交换 得到 1 2 3 5 4
      4. 元素在 5 位置 4 与 5 交换 得到 1 2 3 4 5

做题思路

本题难点主要在查找 对应位置的元素x在哪个位置
如果使用遍历的方法 复杂度
所以维护一个数组的方式，用一个数组来记得每个元素所在的下标

  • 只关心三个元素的交换，
    • 下标x的元素 k
    • 元素x的位置
    • 元素k的位置
  • 将 x当前位置上的元素 存储到 x所在位置 num[num1[x]] = num[x]
  • 将1中移动过去的元素 更新下标 num1[num[x]] = num1[x]

参考代码 1

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;
#define N int(3e5+10)
int num[N],num1[N];
pair<int,int> st[N];
int ans;
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>num[i];
        num1[num[i]] = i;
    }

    for(int i = 1;i<=n;i++)
    {
        if(num[i]!=i)
        {
            int x = num1[i];
            int y = num[i];
            st[++ans] = {i,x};
            num[i] = i;
            num[x] = y;
            num1[y] = x;
        }
    }
    cout<<ans<<endl;
    for(int i = 1;i<=ans;i++)
    {
        cout<<st[i].first<<" "<<st[i].second<<endl;
    }
    return 0;   
    
}

参考代码 2

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
38
39
40
41
42
43

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII>ans; 
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2]; 
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            if (i != j) { 
                ans.push_back({i, j});
                swap(arr[i], arr[j]);
            }
            i++;
            j--;
        }
    }

    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    vector<int> arr(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    quickSort(arr, 1, n );
    cout<<ans.size()<<endl;
    for (auto x : ans) {
        cout << x.first << " " << x.second << endl;
    }

    return 0;
}
  • Title: 果壳语法杯ROUND6题解
  • Author: YZY
  • Created at : 2025-06-17 20:41:46
  • Updated at : 2025-06-17 20:41:46
  • Link: https://blog.dtoj.team/2025/06/17/round6云/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
果壳语法杯ROUND6题解
  1. 宋祖校场演练记
    1. 题目背景
    2. 输入输出格式
    3. 输入格式
    4. 输出格式
    5. 题目样例
    6. 样例#01
    7. 样例#02
    8. 样例#03
    9. 数据范围
    10. 解题思路
    11. 参考代码
  • 赵匡胤的箭
    1. 题目背景
    2. 输入格式
    3. 输出格式
    4. 题目样例
    5. 样例#01
    6. 样例#02
    7. 数据范围
    8. 解题思路
    9. 参考代码 1
    10. 参考代码 2
  • 宋祖铸兵策
    1. 题目背景
    2. 输入输出格式
    3. 输入格式
    4. 输出格式
    5. 题目样例
    6. 样例#01
    7. 数据范围
    8. 题意描述
    9. 暴力解
    10. 结论
  • 宋祖布阵策
    1. 题目背景
    2. 输入输出格式
    3. 输入格式
    4. 输出格式
    5. 题目样例
    6. 样例#01
    7. 样例#02
    8. 样例#03
    9. 样例#04
    10. 数据范围
    11. 题意简述
    12. 做题思路
    13. 参考代码
  • 宋祖清册策
    1. 题目背景
    2. 任务说明
    3. 输入输出格式
    4. 输入格式
    5. 输出格式
    6. 题目样例
    7. 样例#01
    8. 样例#02
    9. 样例#03
    10. 数据范围
    11. 题目分析
    12. 做题思路
    13. 参考代码 1
    14. 参考代码 2