普及组复赛备考

2023/7/6

1.字符串(复习)

• 读入一个字符串，统计这个字符串中 $a-z$ 的个数。字符串长度 $\le 2 \times 10^5$ ，需输出 $26$ 行，每行一个数字，分别代表这个字母的出现次数。

  • 第一种：使用 $map$ 统计出现次数 ，时间复杂度 $O(n \log n)$ 。

    #include<bits/stdc++.h>
    using namespace std;
    string s;
    map<char , int> mp;
    int main(){
    	cin >> s;
    	for(int i = 0 ;  i < s.size() ; i++){
    		mp[s[i]]++;
    	}
    	for(int i = 'a' ; i <= 'z' ; i++){
    		cout << mp[i] << endl;
    	}
    	return 0;
    }
    

  • 第二种：使用普通数组统计，需注意下标要判断一下，时间复杂度 $O(n)$ 。

    #include<bits/stdc++.h>
    using namespace std;
    string s;
    int cnt[1000005];
    int main(){
    	cin >> s;
    	for(int i = 0 ;  i < s.size() ; i++){
    		if(s[i] >= 'a' && s[i] <= 'z'){
    			cnt[s[i] - 'a']++;
    		}
    	}
    	for(int i = 0 ; i < 26 ; i++){
    		cout << cnt[i] << endl;
    	}
    	return 0;
    }
    

• 读入字符串长度 $n$，一个字符串和一个整数 $m$ ，找到所有长度为 $m$ 的字串中字典序最小的那个。 $n \le 5 \times 10^4 , m \le n$ 。

  • 枚举每个字串的起始下标，再截取字符串，边枚举边记录答案，时间复杂度 $O(nm-m^2)$ 。

    #include<bits/stdc++.h>
    using namespace std;
    int  m;
    string s , ans;
    int main(){
    	cin >> m >> s;
    	ans = s.substr(0 , m);
    	for(int i = 1 ; i + m - 1 < s.size() ; i++){
    		ans = min(ans , s.substr(i , m));
    	}
    	cout << ans << endl;
    	return 0;
    }
    

2. Vector

• $vector$ 的基本操作：

  • $.push_back(x)$ 插入数据 $x$
  • $.pop_back()$ 删除最后一个数据
  • $.clear()$ 清空
  • $.size()$ vector 中的数据个数
  • $.insert(x, val)$ 在 vector 中插入一个元素

• 读入 $n$ ，再读入 $n$ 个整数，排序并去重输出，$n \le 2 \times 10^5$。

  • 时间复杂度 $O(n \log n)$ 。

    #include<bits/stdc++.h>
    using namespace std;
    int n , x;
    vector<int> vec;
    int main(){
    	cin >> n;
    	for(int i = 1 ; i <= n ; i++){
    		cin >> x;
    		vec.push_back(x);
    	}
    	sort(vec.begin() , vec.end());
    	int last = -1e9;
    	for(auto i : vec){
    		if(i != last){
    			cout << i << " ";
    			last = i;
    		}
    	}
    	return 0;
    }
    

• Mars OJ 1963

  • 说明：

    • 给 $n$ 个数，第奇数次输入的时候，输出当前数中的中位数。

  • 输入格式：

    • 第一行一个整数 $p\ (1 ≤ P ≤ 10^3)$ ，表示测试数据组数。 每组测试数据，第一行一个整数 $n\ (1 ≤ n < 10^4)$ ，表示元素个数。 接下来 $n$ 个整数，每 $10$ 个一行，最后一行可能不满 $10$ 个。

  • 输出格式：

    • 输出中位数时，也需要 $10$ 个一行，最后一行可能不满 $10$ 个，但至少会有 $1$ 个。

  • 样例：

    • 输入数据 $1$ :

      3 
      9 
      1 2 3 4 5 6 7 8 9 
      9 
      9 8 7 6 5 4 3 2 1 
      23 
      23 41 13 22 -3 24 -31 -11 -8 -7 
      3 5 103 211 -311 -45 -67 -73 -81 -99 
      -33 24 56
      

    • 输出数据 $1$ :

      5
      1 2 3 4 5
      5
      9 8 7 6 5
      12
      23 23 22 22 13 3 5 5 3 -3 
      -7 -3
      

  • 思路：

    • 类似于  priority_queue ，以二分的形式插入数组，使得数组是有序的，这里为了方便，用 $upper_bound$ 代替了。

  • 代码：

    #include<bits/stdc++.h>
    using namespace std;
    int p , n , x , cnt;
    vector<int> vec;
    int main(){
    	cin >> p;
    	while(p--){
    		vec.clear();
    		cnt = 0;
    		cin >> n;
    		cout << (n + 1) / 2 << endl;
    		for(int i = 1 ; i <= n ; i++){
    			cin >> x;
    			vec.insert(upper_bound(vec.begin() , vec.end() , x) , x);
    			if(i % 2 == 1){
    				cout << vec[(i - 1) / 2] << " ";
    				cnt++;
    				if(cnt % 10 == 0) cout << "\n";
    			}
    		}
    		if(cnt % 10 != 0) cout << "\n";
    	}
    	return 0;
    }
    

3. Map

• $map$ 数组是一个特殊的普通数组。

• $map$ 不需要在定义时确定大小，用到多少下标就开多少空间。

• $map$ 的 $key$ 和 $value$ 可以是任何可以进行比较大小的类型。

• $map$ 的定义格式为 $map<$ 数据类型 , 数据类型 $>$ 名字。

• $map$ 的基本操作：

  • $.find(key)$ 判断 $map$ 中是否有某个 $key$ 。

  • $.erase(key)$ 用来删除某个 $key$ 。

• Mars OJ 1140

  • 说明：

    • $2077$ 年，哥斯拉卷土重来，有 $n$ 个不同的哥斯拉要袭击地球，为了保卫我们的家园，我们根据每个哥斯拉的身高( $h$ )体重( $w$ )为哥斯拉命名( $name$ )，也就是我们根据哥斯拉的身高体重就可以知道这个哥斯拉叫什么（任意两个哥斯拉的身高体重不会同时相同）。如果侦察队队员们在野外遭遇哥斯拉，那就需要根据哥斯拉的身高体重向总部报告哥斯拉的名称，侦察队一共遇到了 $m$ 次怪兽,问侦察队向总部报告的哥斯拉的名称。

  • 输入格式：

    • 第 $1$ 行两个数，$n,m(1<n,m\le1000)$，分别表示：哥斯拉的总数；侦察队遇到哥斯拉的数量。

      第 $2$ 到 $n + 1$ 行，每行一个字符串 $name$（不超过 $10$ 个字符）,两个数 $h$ 和 $w$ $(1<h,w<200)$ ,分别表示哥斯拉的名称，哥斯拉的身高，体重。

      第 $n+2$ 到 $n+m+2$ 行，每行两个数 $H,W(1<H,W<200)$ ，表示侦察队遇到的哥斯拉的身高体重。

  • 输出格式：

    • 输出 $m$ 行，表示每次侦察队遇到哥斯拉的名字。如果身高体重是未记录的，则输出 $Error$ 。

  • 样例：

    • 输入数据 $1$ ：

      3 3
      xiaohong 1 2
      xiaoming 2 3
      hanmeimei 3 4
      1 2
      3 4
      3 3
      

    • 输出数据 $1$ ：

      xiaohong
      hanmeimei
      Error
      

  • 思路：由于题目中给了两个信息判断名字，所以可以用 map<pair<int , int> , xxx> mp 的形式存储，当此编号不存在，输出 $Error$ ，否则输出 $mp$ 中存的名字。

  • 代码：

    #include<bits/stdc++.h>
    using namespace std;
    int n , m;
    map<pair<int , int> , string> mp;
    map<pair<int , int> , int> mp2;
    int main(){
    	cin >> n >> m;
    	for(int i = 1 ; i <= n ; i++){
    		string s1;
    		int t1 , t2;
    		cin >> s1 >> t1 >> t2;
    		mp2[make_pair(t1 , t2)] = 1;
    		mp[make_pair(t1 , t2)] = s1;
    	}
    	while(m--){
    		int x1 , x2;
    		cin >> x1 >> x2;
    		if(mp2[{x1 , x2}] == 0) puts("Error");
    		else cout << mp[{x1 , x2}] << "\n";
    	}
    	return 0;
    }
    

• $map$ 的遍历：

  • 第一种：

    map<xxx , xxx>::iterator it;
    for(it = mp.begin() ; it != mp.end() ; it++){
        cout << (it -> first) << " " << (it -> second) << "\n";
    }
    

  • 第二种 ( 部分 c++ 语言编译无法通过，建议开 c++ 17 进行使用 )：

    for(auto it : mp){
        cout << it.first << " " << it.second << "\n";
    }
    

4. Set

• $set$ 是一个有序集合，里面的数据是按从小到大的顺序排好序的。

• 在定义一个 $set$ 时，要指明这个集合中的元素的数据类型。

• $set$ 的定义格式为 $set<$ 数据类型 $>$ 名字。

• 注意，$set$ 会自动去重，若想保留多个一样的数据，需使用 $map$ 。

• $set$ 的基本操作：

  • $.insert(x)$ 将 $x$ 插入到集合中。
  • $.erase(x)$ 将集合中的数据 $x$ 删掉。
  • $.find(x)$ 若存在 $x$ ，会返回 $x$ 对应的迭代器，否则返回 $.end()$ 。

• $set$ 的遍历跟 $map$ 一样，可参考 $3.map$ 章。

• 重温：读入 $n$ ，再读入 $n$ 个整数，排序并去重输出，$n \le 2 \times 10^5$。

  • 将输入的数插入 $set$ 集合，再顺序遍历输出即可。

    #include<bits/stdc++.h>
    using namespace std;
    int n , x;
    set<int> st;
    int main(){
    	cin >> n;
    	for(int i = 1 ; i <= n ; i++){
    		cin >> x;
    		st.insert(x);
    	}
    	for(auto i : st){
    		cout << i << " ";
    	}
    	return 0;
    }
    

5.标记法

• 读入一个整数 $n\ (n \le 10^3)$ ，接下来输入 $n$ 个整数 $x$ $(1 \le x < 2^{31})$ ，分别判断是否是质数，如果是输出 $Yes$ ，否则输出 $No$ 。

  • 由于数据较小，可以暴力：

    • 即一个整数一个整数挨个儿判断是否是质数，时间复杂度 $O(n\sqrt{x})$ ，最坏情况下运行 $4.634 \times 10^7$ 次，不会超时。

    • 至于判断质数，约数是成对出现的，假设 $k$ 是 $x$ 的约数，那么必有 $x \div k$ 是 $x$ 的约数。所以只用枚举到 $\sqrt{x}$ 即可。

    • 注意：需特判 $x=1$ 的情况。

    • 注意：计算 $i \times i$ 时可能超出 $int$ 范围，记得开 $long \ long$ 。

      #include<bits/stdc++.h>
      #define int long long
      using namespace std;
      int n , x;
      bool check(int num){
      	if(num == 1) return false;
      	for(int i = 2 ; i * i <= num ; i++){
      		if(num % i == 0) return false;
      	}
      	return true;
      }
      signed main(){
      	cin >> n;
      	for(int i = 1 ; i <= n ; i++){
      		cin >> x;
      		if(check(x) == true) cout << "Yes\n";
      		else cout << "No\n";
      	}
      	return 0;
      }
      

• 读入一个正整数 $n\ (n < 2^{31})$ ，找出这个正整数中出现次数最多的数字是谁 ( 相同次数输出数字小的数字 )。

  • 思路：每次将 $n % 10$ 的结果记录，再 $\div 10$ 。

  • 第一种：使用 $map$ + $pair$ 存储。

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    map<int , int> mp;
    pair<int , int> ans;
    int main(){
    	cin >> n;
    	while(n != 0){
    		mp[n % 10]++;
    		n /= 10;
    	}
    	for(int i = 0 ; i <= 9 ; i++){
    		if(mp[i] > ans.second){
    			ans = make_pair(i , mp[i]);
    		}
    	}
    	cout << ans.first;
    	return 0;
    }
    

  • 第二种：使用普通数组 $+$ 两个变量存储。

    #include<bits/stdc++.h>
    using namespace std;
    int n , maxn = -1e9 , maxid;
    int cnt[15];
    int main(){
    	cin >> n;
    	while(n != 0){
    		cnt[n % 10]++;
    		n /= 10;
    	}
    	for(int i = 0 ; i <= 9 ; i++){
    		if(cnt[i] > maxn){
    			maxn = cnt[i];
    			maxid = i;
    		}
    	}
    	cout << maxid;
    	return 0;
    }
    

6.唯一分解定理

• 每个大于 $1$ 的自然数均可以写为质数的积。

• 这些素因子按大小排列之后，写法仅有一种方式。

• 输入一个正整数 $n \ (n \le 10^9)$ ，输出它的唯一分解。

  #include<bits/stdc++.h>
  using namespace std;
  int n;
  int main(){
  	cin >> n;
  	for(int i = 2 ; i * i <= n ; i++){
  		while(n % i == 0){
  			cout << i << " ";
  			n /= i;
  		}
  	}
  	if(n != 1) cout << n;
  	return 0;
  }
  

7.约数个数定理

• 已知 $n$ 可以分解成如下形式 $n={p_1}^{a_1} \times {p_2}^{a_2} \times \cdots \times {p_k}^{a_k}$ 。
• 根据乘法原理，$n$ 的约数个数是 $(a_1+1) \times (a_2+1)\times \cdots \times (a_k+1)$ 。

8.结构体

struct node{
	string name;
    int birth[3];
    long long identity;
    string addr;
    bool operator <(const node &hh) const{
        if(birth[0] != hh.birth[0]) return birth[0] < hh.birth[0];
        if(birth[1] != hh.birth[1]) return birth[1] < hh.birth[1];
        if(birth[2] != hh.birth[2]) return birth[2] < hh.birth[2];
    }
};

• 如上定义了一个结构体，这是和 $int,float$ 一样的数据类型。
• 结构体的名字代表这种数据类型。
• 使用该数据类型，需要定义该类型的变量。

本栏目推荐文章
• 手把手教你MongoDB 数据库连接URL 格式、authSource参数
• 字符串格式化
• [JMeter] JMeter的测试报告格式转换(.jtl => html)
• 绑定方法与非绑定方法md
• 2024年更新「GIS数据」全国的GeoJSON、shp格式数据下载获取(精确到乡镇街道级)
• 第六天：shell脚本编程基础格式规范及变量
• axios中使用qs.stringify格式化get请求参数
• 使用daplink下载任意格式固件
• ARM ELF文件格式
• stm32 文件格式对比

复赛 备考 格式 md复赛 备考 格式md 复赛 备考 备考2023 备考cka 复赛 试题csp-j 2023 复赛 试题 答案csp-j 复赛 简要 思路csp-j 复赛 随笔csp-s 2023 复赛 游记csp-s 2023