Skip to content

基本环境、技能与编程语言

编程环境

CCF在2022年把CSP-J/S中使用的系统升级到了NOI Linux 2.0，也使得比赛的环境发生了较大的变化。总体上来说，目前主流的训练和比赛环境如下：

  • 综合来看，易用性最好的环境是Code::Blocks，这是一个集成开发环境(Integrated Development Environment, IDE)，比以前的GUILE这些要好用不少。
  • 同时也提供Visual Studio Code和Sublime这两个代码编辑器，与Code::Blocks的区别，是作为编辑器，这两个软件没有预先配置好的编译、调试等集成功能，所以在比赛中使用起来会更麻烦。当然，VS Code和Sublime在业界使用非常广泛（类似的软件还有Vim和Notepad++等），选手要使用也是没有问题的，这时往往可以与命令行结合，直接在命令行调用gcc进行编译，调用gdb进行调试。
  • GCC/G++ 9.3.0，C++标准版本为C++14。C++14与之前的C++11都是所谓“现代C++”（2014年和2011年确定的国际标准），和之前的C++98/03相比变化很大。在业界，在新的开发中现代C++已经基本取代了老的C++，因为开发效率提升很多。对于信息学竞争来说，以下C++11/14的功能是值得和经常被使用的：
    • 自动类型：auto 
      set<string> a;
for (auto item: a) cout << item;
    • Lambda表达式： 
      sort (a, a+n, [] (int x, int y) {return x>y; });

基本计算机操作技能

NOI Linux 2的基本使用，可以见NOI Linux 2.0 食用指南这个文档。

C++编程语言

目前主流的信息学竞赛编程语言毫无疑问是C++。20年前，还是有比较多的使用Pascal语言的选手，也对应有不少信息学书籍使用Pascal。但随着计算机业界完全放弃Pascal，以及C++继续流行，逐渐信息学竞赛也都变成了以C++为主。Java/Python等语言理论上也可以使用，但是性能不能达到要求。

下面是信息学竞赛中必须掌握的C++语言特性和库函数。

以下主要来自：CCF-CSP认证C++常用标准库函数

输入输出

scanf/printf

头文件

#include <iostream>

int a;
scanf("%d", &a);
printf("%d\n", a);

控制符对应表

控制符 类型
%d int
%s char数组
%c char
%f float
%lf double
%lld long long
%x 16进制int
%o 8进制int
%llx 16进制long long
%llo 8进制long long

字符串

string

头文件 `#include <string>`

构造： 

string str("abcde",1,4);//从字符串“abcde”中截取从下标1开始，长度为2的字符串，“abcde”可以是char数组或string

查找： 

str.find(“bc”);//从头开始查找字符串（或字符）第一次出现的位置
str.rfind(“bc”);//从尾部开始查找字符串（或字符）第一次（即正向查找的最后一次）出现的位置

获取子串： 

string str2=str.substr(1,3);//从下标1开始获取长度为3的子串，3可以不传
替换指定字符 
#include<algorithm>
replace(str.begin(),str.end(),'b','c');

拆分字符串： 

#include <sstream>
#include <vector>

string str="abacad";
vector<string> strs;
istringstream iss(str);
string s;
while(getline(iss, s, 'a')) {
   strs.push_back(s);
}

比较：

可以直接用== < <=等进行比较，大小判断依据字典序，如"abc"<“ac”，因为第二个字符’b’<‘c’；

数据结构

对组(pair)

 头文件 #include <iostream>

构造 

pair<int,int> i(1,2);


使用pair<>为其中一个元素时，如pair<int,pair<int,int> > ，>>要分开，因为>>也是运算符

使用

cout<<i.first<<i.second;

映射

map

头文件 

# include <map>

构造： 

map<int,int> m;

插入：

1、键值对封装成pair插入map

pair<map< int,int >::iterator,bool > re= m.insert(pair<int,int>(1,2))；
返回说明： re->second表示插入是否成功；插入成功re->first是插入的迭代器，插入失败re->first是根据key查询到的迭代器，可根据迭代器删除、向前向后遍历，在需要根据value反向查到key时将插入时的迭代器储存下来会很有用。

2、赋值

m[1]=2；

注：

两种方法的区别： insert()，插入如果key已经存在则不会插入；m[1]赋值时key存在则会覆盖。

如何判断key是否已存在：不取决于是否同一个对象，只取决于对两个key进行比较运算时是否相等，实际上只有a<b和b<a都为假时才判断为相等，因为下一条：

比较判断中只会使用<，事实上C++标准库几乎做判断运算时都只会使用<，目的自然是少重载一些操作符，因此map中的key必须是可比较的，key是自定义类时要重载<操作符。

查询：

map<int,int>::iterator iter=m.find(1);//1是key
if(iter==m.end())
   cout<<"没有该键值对";

如何使用结果：

查询结果要用迭代器iterator 接收，iterator相当于pair的指针

int key=iter->first;
int value=iter->second;

其他方法：

clear(); //清空全部 
erase(map<int,int>::iterator);  //删除一个
begin(); //返回指向map头的迭代器
end();  //返回指向map末尾的迭代器，不是最后一个元素，仅作为判空
rbegin();//返回一个指向最后一个元素的反向迭代器
count(key)； /返回1或0，1表示存在，0表示不存在
size(); //返回当前元素个数
max_size();//返回可容纳的最大元素个数

遍历：

for(map< int,int >::iterator iter=m.begin();iter!=m.end();++iter){
    cout<<"key:"<<iter->first<<"vlaue"<<iter->second<<endl;
}

在遍历过程中删除该元素：

for(map< int,int >::iterator iter=m.begin();iter!=m.end();){
    m.erase(iter++);
}

自定义排序规则：

定义时可额外传一个结构体，重载其操作符()即可，传参类型需为key的变量类型：

struct SortInt{
    bool operator()(const int &a,const int &b){//const和引用非必须。基本数据类型不建议使用引用，引用底层是指针，反而降低速度，这里仅做演示
        return a <= b;
    }
};
map<int,int,SortInt> m;
unordered_map

头文件

# include <unordered_map>

方法与map相同

map与unordered_map的区别：map是用红黑树实现的，自带排序，默认按key从小到大排序

unordered_map是用hash表实现的，因此插入查询都比map快，但储存时并不排序，只用映射的功能而不排序建议用unordered_map

集合(set)

头文件

# include <set>

基本方法与map相似，底层也是由红黑树实现，默认元素保持从小到大排序。

优先队列/最大堆(priority_queue)

头文件 

# include <queue>

构造

默认最大堆：

priority_queue <int,vector<int> > q; //可以省略vector<int>

最小堆：

priority_queue <int,vector<int>,greater<int> > q;

greater<>中可以是任意类型，表示使用>号，默认less<>表示使用<号，被判断大小的双方位置不变

push()  //插入一个元素
pop()  //删除队头元素
size() //返回当前元素个数
empty() //判断队列是否为空
top() //返回队头元素

重写比较方式或使用结构体，要重载 <（或>） 操作符:

bool operator < (const type &a,const type &b){
    return a.id<b.id;
}

判断操作符的重载不能修改输入值，所以传参如果是引用类型，必须用const修饰，否则报错，也可以是非引用类型

与set对应同样也有unordered_set，方法类似，略。

容器(vector)

头文件 

# include <vector>

push_back(const T& x);  //向量尾部增加一个元素X
iterator begin(); //返回向量头指针，指向第一个元素
iterator end(); //返回向量尾指针，指向向量末尾元素的下一个位置
size(); //返回当前元素个数

常用算法

快速排序(sort)

头文件 

# include <algorithm>

对数组

 int a[10]={1,3,4,2};
 sort(a,a+3);//从数组下标0开始，到下标3不包含下标3从小到大排序

对容器

 vector<int> a={1,3,4,2};
 sort(a.begin(),a.begin()+4);//从数组下标0开始，到下标4不包含下标4从小到大排序

注：快速排序不是稳定排序，不能保证两个相等的变量前后顺序不变

其他：

auto

自动变量，占位符，由编译器编译时自动替换为原本变量；

map< int,int > m;
for(auto iter=m.begin();iter!=m.end();++iter){
    cout<<"key:"<<iter->first<<"vlaue"<<iter->second<<endl;
}

5.2 位运算

运算符 运算
& 与运算
| 或运算
~ 按位取反
^ 异或运算
<< 左移位，补0
>> 右移位，正数补0，负数补1

重载命名空间中的操作符

如果用pair<>作为set的元素时，想要重载操作符<按自己的方法排序，在全局代码中重载是没有用的，因为在set中的代码会先在pair<>的原命名空间(std)中找操作符，所以要在命名空间中重载操作符（但是无法使用模板）：

namespace std{
 bool operator < (const pair<int,int> &x,const pair<int,int> &y){
  return y.first<x.first||!(x.first<y.first)&&x.second<y.second;
 }
}

万能头文件

使用后编辑器自动找对应头文件，无需写一堆头文件

#include <bits/stdc++.h>

注：在部分OJ系统中是不支持的，不过目前ccf-csp认证是支持的