专题一 学习C++

2025ACM寒假集训

专题一 学习C++

102400226 石华波 Vjudge账号:DustLi

问题一 Long

问题陈述

对于一个正整数X，级别为X 的 龙字符串 是一个长度为 (X+3)的字符串，由一个 L、X 次出现的 o、一个 n 和一个 g 按此顺序排列而成。

给定一个正整数N。打印级别为N 的龙字符串。 注意，大写字母和小写字母是有区别的。

约束条件

  • 1≤N≤20241≤N≤2024
  • N是一个整数。

解题思路

读取整数N后，输出L，再通过循环输出N个o，最后输出n、g即可，AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <iostream>
using namespace std;

int main() {
    int N;
    cin>>N;
    cout<<'L';
    while(N--) cout<<'o';
    cout<<"ng"<<endl;
    return 0;
}

问题二 YES or YES？

问题陈述

有一个长度为 3 的字符串 s，由大写和小写英文字母组成。检查它是否等于 “YES”（不带引号），其中每个字母可以是任意大小写。例如，“yES”、“Yes”、“yes” 都是允许的。

解题思路

逐个判断字符是否为’y’、‘Y’……即可，AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    cin>>N;
    while(N--) {
        string s;
        cin>>s;
        if(s[0]!='y'&&s[0]!='Y') cout<<"NO"<<endl;
        else if(s[1]!='e'&&s[1]!='E') cout<<"NO"<<endl;
        else if(s[2]!='s'&&s[2]!='S') cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

问题三 Even? Odd? G

问题陈述

Bessie那惨无人道的二年级老师搞了一个有 N 个正整数 I 的表叫Bessie去判断“奇偶性”（这个词语意思向二年级的学生解释，就是“这个数是单数，还是双数啊？”）。Bessie被那个表的长度深深地震惊到了，竟然跟栋栋的泛做表格一样多道题！！！毕竟她才刚刚学会数数啊。

写一个程序读入N个整数，如果是双数，那么在单立的一行内输出"even"，如果是单数则类似地输出"odd".

数据范围：每个正整数不超过 10^60

解题思路

数据范围远超int 或者long long能表示的范围，但题目仅要求判断奇偶，故以string的方式读入，判断最后一位的奇偶即可。幸运的是，数字的ASCII码的奇偶性与其本身一致，故不需要额外进行处理，AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    cin>>N;
    while(N--) {
        string s;
        cin>>s;
        if(s[s.length()-1]%2) cout<<"odd"<<endl;
        else cout<<"even"<<endl;
    }
    return 0;
}

问题4 Problem Generator

问题陈述

Vlad计划下个月举办m轮比赛。每一轮比赛应包含难度等级为’A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, 和 ‘G’ 的一个问题。

Vlad已经准备了n个问题，其中第i个问题的难度等级为a(i)。可能这些问题数量不够，所以他可能需要再想出一些问题。

Vlad希望尽可能少地想出问题，因此他请你找出他需要想出的问题的最少数量，以便举办m轮比赛。

例如，如果m=1，n=10，a= ‘BGECDCBDED’，那么他需要想出两个问题：一个难度等级为’A’，一个难度等级为’F’。

解题思路

依题意，每种问题需要m个，故读入m、n，计算每种问题已有数量和总共所需之差再求和即可（缺少的问题<0的不计），AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        int m;
        char c;
        cin>>n>>m;
        int cnt[]={m,m,m,m,m,m,m};
        int ans=0;
        while(n--) {
            cin>>c;
            cnt[c-65]--;
        }
        for(int i=0;i<7;i++) if(cnt[i]>0) ans+=cnt[i];
        cout<<ans<<endl;
    }
    return 0;
}

问题五 rules

问题陈述

小 A 制定了一些规则，每条规则有一个代号，代号为不超过 10^9的非负整数。

小 A 的国家有 n位居民，每位居民每天会且仅会遵守 1条规则。小 A 记录了 m天里每天每位居民遵守的规则代号。

现在小 A 想要考察代号为 k的规则是否符合民意，具体考察方法如下：

  • 如果在某一天里，有大于等于一半的人遵守了规则 k，那么小 A 认为在这一天规则 k是符合民意的。
  • 如果在大于等于一半的天数里，规则 k符合民意，那么他会认为规则 k是正确的。否则，他会认为规则 k是错误的。

如果小 A 的规则 k是正确的，请你输出 YES，否则请你输出 NO。

解题思路

分别计算每一天遵循该规则的居民数量是否大于等于总数的一半，最后再计算符合民意的天数是否大于等于m的一半即可（实现方法使用的是将遵循规则的居民数量、符合民意的天数乘以2与总居民数、m进行比较，不需要引入float类型，乘法比除法更快），AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;

int main() {
    int n,m,k;
    int cntt=0;
    cin>>n>>m>>k;
    for(int z=0;z<m;z++) {
        int cntd=0;
        for(int i=0;i<n;i++) {
            int d;
            cin>>d;
            cntd += d==k;
        }
        cntt += 2*cntd>=n;
    }
    if(2*cntt>=m) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

问题六 Many Replacement

问题陈述

给定一个长度为 N的字符串 S，由小写英文字母组成。

你将对字符串 S 执行 Q 次操作。 第 i次操作 (1≤i≤Q)由一对字符 (c(i),d(i)) 表示，对应以下操作：

  • 将字符串 S中所有字符 c(i)替换为字符 d(i)。

在所有操作完成后，打印字符串 S。

约束条件

  • 1≤N≤2×10^5
  • S是一个长度为 N的字符串，由小写英文字母组成。
  • 1≤Q≤2×10^5
  • c(i)和 d(i)是小写英文字母 (1≤i≤Q)
  • N和 Q是整数。

解题思路

在字符串长度较长的情况下，每次都遍历字符串进行修改是不现实的（很有可能会TLE）。发现经过多次交换后，每个字母对应映射到另一字母，那么维护一个字母表（初始映射到自身），每次对字母表的映射进行修改，在最后再遍历字符串进行修改即可，AC代码：

 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

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    string s;
    int Q;
    cin>>N>>s>>Q;
    char Letters[26];
    for(int i=0;i<26;i++) Letters[i]=i+'a';
    while(Q--) {
        char c,d;
        cin>>c>>d;
        for(int i=0;i<26;i++) {
            if(Letters[i]==c) {
                Letters[i]=d;
            }
        }
    }
    for(int i=0;i<N;i++) {
        s[i]=Letters[s[i]-'a'];
    }
    cout<<s<<endl;
    return 0;
}

问题七 更好的交换

问题陈述

小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 n行 n列的方阵 A，第 i行第 j列的位置上有一个正整数 A(i,j)。

与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则之一操作：

  • 选择拼图上的第 x行和第 y行，交换这两行；
  • 选择拼图上的第 x列和第 y列，交换这两列。

为了复原这个拼图，小 S 将会操作共 m次，每次操作格式如下：

  • 1 x y，表示交换第 x行和第 y行；
  • 0 x y，表示交换第 x列和第 y列；

请你输出复原后的拼图。

解题思路

发现并不需要实际地交换行和列，只需要维护两个数组Row、Col，对数组中行与列映射代表的行与列关系进行修改即可，与上一题其实类似。AC代码：

 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

#include <iostream>
using namespace std;

int Matrix[1002][1002];
int Row[1002],Col[1002];

int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cin>>Matrix[i][j];
        }
    }
    for(int i=1;i<=n;i++) Row[i]=Col[i]=i;
    while(m--) {
        int op,x,y;
        cin>>op>>x>>y;
        if(op) swap(Row[x],Row[y]);
        else swap(Col[x],Col[y]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cout<<Matrix[Row[i]][Col[j]]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

学习总结

本专题内容主要为C++基础语法，通过学习，对时间复杂度和空间复杂度的计算有了更深入的了解，对STL的内容有了了解。

Licensed under CC BY-NC-SA 4.0
© 2025 - 2026 Dust_Li
2025寒假ACM新生线上集训
使用 Hugo 构建
主题 Stack 由 Jimmy 设计