首页 做题经验

# 临阵摸鱼

# 注意

无脑 longlong

# 读数据

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int a[N];
int main(){
    int n; cin >> n;
    int cnt = 0;
    while(scanf("%d", &a[cnt]) != EOF)   cnt++;    // 注意读数据的写法
    sort(a, a+cnt);
    int ans1, ans2;
    for(int i = 1; i < cnt; i++) {
        if(a[i] - a[i-1] > 1)   ans1 = a[i-1]+1;   // 查找断号
        if(a[i] == a[i-1])      ans2 = a[i];       // 查找重号
    }
    cout << ans1 << ' ' << ans2;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool cmp(int a, int b){return a>b;}    // 降序
int main(){
    int n,m;  cin>>n>>m;
    for(int i=1;i<=n;i++)  a[i]=i;
    while(m--){
        int p,q; scanf("%d%d",&p,&q);
        if(p==1) sort(a+q,a+n+1);      // 升序 q～n
        if(p==0) sort(a+1,a+q+1,cmp);  // 降序 1～q
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

# 读字符

cin 不能读空格，getline 可以

getline(cin,str);

# 数字位数处理

while(x){
        int b = x % 10; // 获取十进制下的每个数位
        x /= 10; // 将十位变为个位
    }

# 日期处理

注意输出格式，用 printf %02d

for(int year=2000;year<=2022;year++)
for(int month=1;month<=12;month++)
for(int day=1;day<=31;day++)
{
	if(month == 1 || month == 3 || month == 5 || month == 7 ||
month == 8 || month == 10 || month == 12);
	else if(month == 2)
	{
		if((year%4==0&&year%100!=0) || year % 400 == 0)
		{
			if(day > 29) break;
		}
		else
		{
			if(day > 28) break;
		}
	}
	else
	{
		if(day > 30) break;
	}
}
#include <bits/stdc++.h>
using namespace std;
int m1[] = {0, 1, 3, 5, 7, 8, 10, 12}; // 存储大月
int m2[] = {0, 4, 6, 9, 11}; // 存储小月
int main() {
    int year = 2014, month = 11, day = 9;
    for (int i = 1; i <= 1000; i++) {
        day++;
        for (int j = 1; j <= 7; j++) { // 判断是否是大月
            if (month == m1[j] && day == 32) { // 大月满 32 天进下一月
                month++;
                day = 1; // 天数重新回到 1 号
                break;
            }
        }
        for (int j = 1; j <= 4; j++) { // 判断是否是小月
            if (month == m2[j] && day == 31) { // 小月满 31 天进下一月
                month++;
                day = 1;
                break;
            }
        }
        if (month == 2) { // 单独判断 2 月
            if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { // 判断是否是闰年
                if (day == 30) { // 闰年满 30 天进下一月
                    month++;
                    day = 1;
                }
            } else {
                if (day == 29) { // 平年满 29 天进下一月
                    month++;
                    day = 1;
                }
            }
        }
        if (month == 13) { // 满 13 月进 1 年
            month = 1; // 月份回到 1 月重新计数
            year++;
        }
    }
    cout << year << "-" << month << "-" << day;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
    int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    int y=2014,d=9,m=11,w;
    for(w=0;w<1000;w++){
      if((y%4==0&&y%100!=0)||(y%400==0)) mon[2]=29;
      else  mon[2]=28;
      d++;
      if(d>mon[m]){
        d=1;
        m++;
      }
      if(m>12){
        y++;
        m=1;
      }
    }
    printf("%04d-%02d-%02d",y,m,d);
    return 0;
}
# 高精度


#include <bits/stdc++.h>
using namespace std;
string add(string a,string b){
    string s;                    // 存结果
    int c = 0;                   // 进位
    for(int i=a.size()-1,j=b.size()-1;i>=0||j>=0||c>0;i--,j--){
        if(i>=0)   c += a[i]-'0';
        if(j>=0)   c += b[j]- '0';
        s += (c%10)+ '0';        // 注意这里的 s，低位在前，高位在后
        c /= 10;
    }
    reverse(s.begin(),s.end());  // 反过来，高位在前，低位在后
    return s;
}
int main(){
    string a,b;  cin>>a>>b;      // 用字符串方式读入整数 a 和 b
    cout<<add(a,b);
    return 0;
}
# stl


list


1  // 定义一个 list
 2      list<int>node;
 3  // 为链表赋值，例如定义一个包含 n 个结点的链表
 4      for(int i=1;i<=n;i++)  
 5          node.push_back(i); 
 6  // 遍历链表，用 it 遍历链表，例如从头遍历到尾
 7      list<int>::iterator it = node.begin();
 8      while(node.size()>1){           //list 的大小由 STL 管理
 9           it++;
10           if(it == node.end())       // 循环链表，end () 是 list 末端下一位置
11                  it = node.begin();                                              
12      }
13  // 删除一个结点
14      list<int>::iterator next = ++it;
15      if(next==node.end())  next=node.begin();  // 循环链表
16      node.erase(--it);              // 删除这个结点，使得 node.size () 自动减 1
17      it = next;                     // 更新 it
18  // 插入结点，见例题 3-4 “自行车停放”
stack






queue






priority






pair


pair<int,int> pos;
pos.first = 1;
pos.second = 1;
a = make_pair(1,1);
a = pair<int,int>(1,1);
# 结构体排序


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  struct stu{
 4      int id;      // 学号
 5      int c,m,e;   // 语文、数学、英语成绩
 6      int sum;
 7  }st[305];
 8  bool cmp(stu a,stu b){
 9      if(a.sum > b.sum)       return True;
10      else if(a.sum < b.sum)  return False;
11      else{                                 //a.sum == b.sum
12          if(a.c > b.c)       return True;
13          else if(a.c < b.c)  return False;
14          else{                             //a.c == b.c
15              if(a.id > b.id) return False;
16              else return True;
17          }
18      }
19  }
20  int main(){
21      int n;    cin>>n;
22      for(int i=1;i<=n;i++){
23          st[i].id = i;                              // 学号
24          cin >> st[i].c >> st[i].m >> st[i].e;
25          st[i].sum = st[i].c + st[i].m + st[i].e;   // 总分
26      }
27      sort(st+1,st+1+n,cmp);
28      for(int i=1;i<=5;i++)  cout<<st[i].id<<’ ‘<<st[i].sum<<”\n”;
29      return 0;
30  }
# 双指针


#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
    int n, S;
    cin >> n >> S;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int sum = 0, ans = 1e8;
    for (int i = 0, j = 0; i < n;) {
        if (sum < S) {
            sum += a[i];
            i++;
        } else {
            ans = min(i - j, ans);
            sum -= a[j];
            j++;
        }
    }
    if (ans == 1e8) {
        cout << 0;
    } else {
        cout << ans;
    }
    return 0;
}
# dfs


如果搜索所有的路径，应该用 DFS；如果只搜索最短的路径，则应该用 BFS。


搜索所有路径


1  ans;                                 // 答案，用全局变量表示
 2  void dfs（层数，其他参数）{
 3      if （出局判断){                    // 到达最底层，或者满足条件退出 
 4          更新答案;                     // 答案一般用全局变量表示
 5          return;                      // 返回到上一层
 6      }
 7      （剪枝）                           // 在进一步 DFS 之前剪枝
 8      for （枚举下一层可能的情况）          // 对每一种情况继续 DFS 
 9          if (used[i] == 0) {          // 如果状态 i 没有用过，就可以进入下一层
10              used[i] = 1;             // 标记状态 i，表示已经用过，在更底层不能再使用
11              dfs（层数+1，其他参数）;     // 下一层 
12              used[i] = 0;             // 恢复状态，回溯时，不影响上一层对这个状态的使用
13              }
14      return;                          // 返回到上一层
15  }
# 全排列


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
 4  bool vis[20];     // 记录第 i 个数是否用过
 5  int b[20];        // 生成的一个全排列
 6  void dfs(int s,int t){
 7      if(s==t) {                                     // 递归结束，产生一个全排列
 8         for(int i=0; i<t; ++i)  cout<<b[i]<< “ “;   // 输出一个排列            
 9         cout<<”;  “;
10         return;
11      }
12      for(int i=0;i<t;i++)
13          if(!vis[i]){
14              vis[i]=True;
15              b[s]=a[i];
16              dfs(s+1,t);
17              vis[i]=False;
18          }
19  }
20  int main(){
21      int n=3;
22      dfs(0,n);     // 前 n 个数的全排列
23      return 0;
24  }
# 组合


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int a[]={1,2,3,4,5,6,7,8,9,10};
 4  int vis[10];
 5  void dfs(int k) {  
 6      if (k == 3) {
 7          for(int i=0;i<3;i++)
 8              if(vis[i])  cout<<a[i];
 9          cout<<”-”;
10      }
11      else {
12          vis[k] = 0;          // 不选中第 k 个数
13          dfs(k + 1);          // 继续搜下一个数
14          vis[k] = 1;          // 选这个数
15          dfs(k + 1);          // 继续搜下一个数
16      }
17  }
18  int main() {
19      dfs(0); // 从第一个数开始
20      return 0;
21  }
# bfs


image-20240408200158606


#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, y;                                 // 坐标
    string path;                              //path，记录从起点 (0,0) 到这个点 (x,y) 的完整路径
};
char mp[31][51];                             // 存地图
char k[4] = {'D', 'L', 'R', 'U'};            //4 个方向，按字典序
int dir[4][2] = <!--swig0-->;
int vis[30][50];                             // 标记。vis=1: 已经搜过，不用再搜
void bfs(){
    node start;
    start.x = 0;  start.y = 0;  start.path = "";  // 定义起点
    vis[0][0] = 1;                               // 标记起点被搜过
    queue<node> q;
    q.push(start);                               // 把第一个点放进队列，开始 BFS
    while(!q.empty()){
        node now = q.front();   q.pop();         // 取出队首，弹走队首        
        if(now.x == 29 && now.y == 49){          // 第一次遇到终点，就是字典序最小的最短路径
            cout << now.path;                     // 输出完整路径
            return;
        }
        for(int i = 0; i < 4; i++){               // 扩散 4 个方向的邻居点
            node next;
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];
            if(next.x < 0 || next.x >= 30 || next.y < 0 || next.y >= 50) continue;     // 越界了
            if(vis[next.x][next.y] == 1 || mp[next.x][next.y] == '1') //vis=1：已经搜过；mp=1：是障碍
                continue;                   
            vis[next.x][next.y] = 1;             // 标记已被搜过
            next.path = now.path + k[i];         // 记录完整路径：复制上一个点的路径，加上这一步的路径
            q.push(next);
        }
    }
}
int main(){
    for(int i = 0; i < 30; i++)  cin >> mp[i];   // 读题目给的迷宫地图数据
    bfs();
    return 0;
}
# 连通性


dfs


(1) 从图上任意一个点 u 开始遍历，标记点 u 已经被搜索过。


(2) 递归点 u 的所有符合连通条件的邻居点。


(3) 递归结束，找到了与点 u 连通的所有点，这是一个连通块。


(4) 不与点 u 连通的、其他没有访问到的点，继续用上述步骤处理，直到找到所有的连通块。


bfs


(1) 从图上任意一个点 u 开始遍历，把它放进队列中。


(2) 弹出队首 u，标记点 u 已经被搜索过，然后搜索点 u 的邻居点，即与点 u 连通的点，将其放到队列中。


(3) 弹出队首，标记为已被搜索过，然后搜索与它连通的邻居点，放进队列。


#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];
int vis[N][N];
int d[4][2] = <!--swig1-->; //4 个方向
int flag;
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = 1;      // 标记这个 “#” 被搜索过
    while (q.size()) {
        pair<int, int> t = q.front();
        q.pop();
        int tx = t.first, ty = t.second;
        if( mp[tx][ty+1]== '#' && mp[tx][ty-1]== '#' &&
            mp[tx+1][ty]== '#' && mp[tx-1][ty]== '#'   )
            flag = 1; // 上、下、左、右都是陆地，不会被淹没
        for (int i = 0; i < 4; i++) {    // 扩展 (tx,ty) 的 4 个邻居点
            int nx = tx + d[i][0], ny = ty + d[i][1];
            if(vis[nx][ny]==0 && mp[nx][ny]== '#'){  // 把陆地放进队列
                vis[nx][ny] = 1;  // 注意：这一句必不可少
                q.push({nx, ny});
            }
        }
    }
}
int main() {
    int n;  cin >> n;
    for (int i = 0; i < n; i++)  cin >> mp[i];
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (mp[i][j] == '#' && vis[i][j]==0) {
                flag = 0;
                bfs(i, j);
                if(flag == 0)  // 这座岛屿全部被淹没
                    ans++;     // 统计岛屿的数量
            }
    cout << ans << endl;
    return 0;
}
/*
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];                           // 地图
int vis[N][N]={0};                       // 标记是否搜索过
int d[4][2] = <!--swig2-->; //4 个方向
int flag;                                // 用于标记这座岛屿是否被完全淹没
void dfs(int x, int y){
    vis[x][y] = 1;                       // 标记这个 “#” 被搜索过。请思考为什么在这里标记
    if( mp[x][y+1]== '#' && mp[x][y-1]== '#' &&
        mp[x+1][y]== '#' && mp[x-1][y]== '#'   )
        flag = 1;                        // 上、下、左、右都是陆地，所以这是一个高地，不会被淹没
    for(int i = 0; i < 4; i++){          // 继续 DFS 周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
        if(vis[nx][ny]==0 && mp[nx][ny]== '#')    // 注意为什么要判断 vis [][]
            dfs(nx,ny);                  // 继续 DFS 未搜索过的陆地，目的是标记它们
    }
}
int main(){
    int n;   cin >> n;
    for (int i = 0; i < n; i++)   cin >> mp[i];
    int ans = 0 ;
    for(int i = 0; i < n; i++)         //DFS 所有像素点
        for(int j = 0; j < n; j++)
            if(mp[i][j]== '#' && vis[i][j]==0){
                flag = 0;              // 假设这座岛屿被淹没
                dfs(i,j);              // 查找这座岛屿中有没有高地，如果有，则置 flag=1
                if(flag == 0) ans++;   // 这座岛屿确实被淹没了，统计被淹没岛屿的数量
            }
    cout<<ans<<endl;
    return 0;
}
# 剪枝


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N=15;
 4  int n, m;
 5  int a[N][N], vis[N][N];                       // 格子是否被访问过
 6  int sum, ans=100000;
 7  int d[4][2] = { {1,0},{0,-1},{0,1},{-1,0} };  //4 个方向
 8  void dfs(int x, int y, int c, int s) {
 9      if (2*s>sum)  return;                     // 剪枝
10      if (2*s==sum) {
11          if (c<ans && vis[0][0]) ans = c;      // 左上角格子最少数量
12          return;
13      }
14      vis[x][y]=1;
15      for (int k=0; k<4; k++) {
16          int tx=x+d[k][0], ty=y+d[k][1];
17          if (tx>=0 && tx<n && ty>=0 && ty<m && !vis[tx][ty])
18              dfs(tx,ty,c+1,s+a[x][y]);
19      }
20      vis[x][y]=0;
21  }
22  int main() {
23      cin>>m>>n;
24      for (int i=0; i<n; i++)
25          for (int j=0; j<m; j++)
26              cin>>a[i][j], sum+=a[i][j];       // 求所有格子的和
27      dfs(0,0,0,0);
28      cout<<(ans==100000 ? 0 : ans);
29      return 0;
30  }
# 二分


bool check(int x)
{
// 进行某些操作
}
// 二分查找函数
int binarySearch()
{
	int l = 1, r = n; // 初始化左右边界
while (r - l > 1) // 当右边界与左边界相差大于 1 时
{
	int mid = (l + r) >> 1; // 取中间位置 防溢出
	if (check(mid)) // 如果满足条件
		r = mid; // 更新右边界为 mid
	else
		l = mid; // 否则更新左边界为 mid
}
if (check(l)) // 如果满足条件
	return l; // 返回左边界值
else if (check(r)) // 如果满足条件
	return r; // 返回右边界值
return -1; // 否则返回 - 1
}
# 区间最值


1  #include <bits/stdc++.h>
 2  using namespace std;
 3  int main(){
 4      int a[7] = {5,7,1,2,3,6,9};
 5      int id = min_element(a+2, a+5) - a;   // 注意，区间 [a+2, a+5) 左闭右开，不包括 a+5
 6      cout<<a[id]<< “\n”;                   // 输出最小值 1
 7      id = max_element(a+2, a+5) - a;
 8      cout<<a[id]<< “\n”;                   // 输出最大值 3
 9      int s = accumulate(a+2, a+5,0);       // 最后的 0 表示从 0 开始累加
10      cout<<s<<”\n”;                        // 输出区间和 6
11      return 0;
12  }
# st


1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N = 500001;
 4  int n,m;
 5  int a[N],dp[N][40];                    
 6  void st_init(){
 7      for(int i=1;i<=n;i++)  dp[i][0] = a[i];         // 初始化区间长度为 1 时的值
 8      int p = (int)(log(double(n)) / log(2.0));       //int p=log2 (n);  // 此处有两种写法
 9      for(int k=1;k<=p;k++)                                     // 用 dp [] 递推计算区间
10          for(int s=1;s+(1<<k)<=n+1;s++)
11              dp[s][k]=max(dp[s][k−1], dp[s+(1<<(k-1))][k-1]);  // 最大值
12  }
13  int st_query(int L,int R){
14      int k = (int)(log(double(R-L+1)) / log(2.0));  //int k = log2 (R-L+1); // 两种方法求 k
15      return max(dp[L][k],dp[R-(1<<k)+1][k]);        // 最大值
16  }
17  int main(){
18      scanf(“%d%d”,&n,&m);
19      for(int i=1;i<=n;i++)  scanf(“%d”,&a[i]);
20      st_init();
21      for(int i=1;i<=m;i++){
22          int L,R; scanf(“%d%d”,&L,&R);
23          printf(“%d\n”,st_query(L,R));
24      }
25      return 0;
26  }
# 前缀和


1  #include <bits/stdc++.h>
 2  using namespace std;
 3  int a[11]={0,4,5,6,7,8,9,10,11,12,13};  //a [0] 不用
 4  int sum[11]={0};
 5  int main (){
 6  // 预处理，计算前缀和
 7       sum[1]=a[1];
 8       for(int i =2;i<=10;i++) sum[i] = a[i]+ sum[i-1];
 9  // 输出前缀和
10       cout << “sum[]=”;
11       for(int i =1;i<=10;i++) cout<<sum[i]<< “ “;    cout <<”\n”;
12  // 用前缀和反推计算数组 a []
13       cout << “  a[]=” << a[1]<< “ “;
14       for(int i =2;i<=10;i++) cout << sum[i] - sum[i-1]<< “ “;
15  // 求区间和，例如计算 [5,8] 的区间和
16       cout << “\n”<< “ [5,8]= “<<sum[8]-sum[4];
17       return 0;
18  }
# 二维前缀和


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int s[550][550];
 4  int main(){
 5      int n,m,k;  cin>>n>>m>>k;
 6      for(int i=1;i<=n;i++)
 7          for(int j=1;j<=m;j++){
 8              int v; scanf(“%d”,&v);
 9              s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+v;   // 预计算二维前缀和
10          }
11      long long ans = 0;
12      for(int i1=1;i1<=n;i1++)                              // 暴力查询二维子矩阵
13          for(int i2=i1;i2<=n;i2++)
14              for(int j1=1; j1<=m; j1++)
15                  for(int j2=j1; j2<=m; j2++) {
16                      int z = s[i2][j2]-s[i2][j1-1]-s[i1-1][j2]+s[i1-1][j1-1];
17                      if(z<=k) ans++;
18                  }
19      cout<<ans;
20  }
# 一维差分


for(int i=1;i<=n;i++)
d[i]=a[i]-a[i-1];
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m, a[MAXN], d[MAXN], sumd[MAXN];
int main() {
    cin >> n >> m;
    
    // 读入数组 a 的元素，计算差分数组 d
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    
    // 进行 m 次区间操作
    for (int i = 1; i <= m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        d[l] += c;
        d[r + 1] -= c;
    }
    
    // 求最终的前缀和，即修改后的数组 a
    for (int i = 1; i <= n; i++) {
        sumd[i] = sumd[i - 1] + d[i];
        cout << sumd[i] << " ";
    }
    
    return 0;
}
# 并差集


1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N = 8e5+5;
 4  int s[N];
 5  void init_set(){                  // 初始化
 6     for(int i=1; i<=N; i++)  s[i] = i;
 7  }
 8  int find_set(int x){              // 查找
 9    //if (x==s[x]) return x;
10    //else return find_set (s [x]);   // 这两行合并为下面的一行
11      return x==s[x]? x:find_set(s[x]);
12  }
13  void merge_set(int x, int y){     // 合并
14      x = find_set(x);
15      y = find_set(y);
16      if(x != y) s[x] = s[y];       //y 成为 x 的父结点，x 的集是 y
17  }
18  int main (){
19      init_set();
20      int n,m; cin>>n>>m;
21      while(m--){
22           int op,x,y; cin>>op>>x>>y;
23           if(op == 1)   merge_set(x, y);
24           if(op == 2){
25                 if(find_set(x)==find_set(y)) cout << “YES”<<endl;
26                 else                                cout << “NO”<<endl;
27           }
28      }
29      return 0;
30  }
1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N=1e5+100;
 4  vector<int> edge[N]; // 邻接表
 5  int s[N],vis[N],ring[N];
 6  int start,flag;
 7  int tot;      // 环上点的数量
 8  void init_set(){
 9       for(int i=1;i<=N;i++)   s[i]=i;
10  }
11  int find_set(int x){
12       if(x!=s[x])  s[x]=find_set(s[x]);
13       return s[x];
14  }
15  void merge_set(int x,int y){
16       int tmp = x;
17       x = find_set(x);
18       y = find_set(y);
19       if(x!=y) s[y]=s[x];         // 此 x 和 y 处于环中，记录一个点
20       else     start = tmp;      
21  }
22  void dfs(int x,int step){        // 从起点 start 出发找一条回到 start 的环路
23       if(flag)    return;
24       if(x==start)                // 绕了一圈回来了，环路结束
25            if(vis[x]==1){
26                  tot = step-1;
27                  flag = 1;
28                  return ;
29            }
30       ring[step] = x;
31       for(int i=0;i<edge[x].size();i++){
32            int y=edge[x][i];
33            if(!vis[y]){
34                  vis[y]=1;
35                  dfs(y,step+1);
36                  vis[y]=0;
37            }
38       }
39  }
40  int main(){
41      int n;   scanf(“%d”,&n);
42       init_set();
43       for(int i=1;i<=n;i++) {
44            int u,v;  scanf(“%d %d”,&u,&v);
45            edge[u].push_back(v);   edge[v].push_back(u);
46            merge_set(u,v);      // 找到环上一个点 start，merge_set () 执行后，全局变量 start 被赋值
47       }
48       flag = 0;    
49       dfs(start,1);             // 以 start 为起点再次搜索回来，这就是环
50       sort(ring+1,ring+1+tot);
51       for(int i=1;i<=tot;i++)  printf(“%d “,ring[i]);
52       return 0;
53  }
# 树状数组


处理动态前缀和 nlogn


1  #define lowbit(x)  ((x) & - (x))   
 2  int tree[N];
 3  void update(int x, int d) {   // 修改元素 a [x]，a [x]= a [x] + d
 4       while(x <= N) {
 5           tree[x] += d;  
 6           x += lowbit(x); 
 7       }
 8  } 
 9  int sum(int x) {              // 返前缀和 ans = a [1] + a [2] +... + a [x]
10        int ans = 0;
11        while(x > 0){
12            ans += tree[x];  
13            x -= lowbit(x);
14        }
15       return ans;
16  }
1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N = 1000;
 4  #define lowbit(x)  ((x) & - (x))
 5  int tree[N]={0};
 6  void update(int x, int d) {   // 修改元素 a [x],a [x] = a [x] + d
 7       while(x <= N) {
 8           tree[x] += d;
 9           x += lowbit(x);
10       }
11  }
12  int sum(int x) {             // 返回前缀和 sum = a [1] + a [2] +...+ a [x]
13       int ans = 0;
14       while(x > 0){
15           ans += tree[x];
16           x -= lowbit(x);
17       }
18       return ans;
19  }
20  // 以上是树状数组的代码
21  int a[11]={0,4,5,6,7,8,9,10,11,12,13};  // 注意：a [0] 不用
22  int main (){
23  // 计算 tree [] 数组
24       for(int i=1;i<=10;i++)  update(i,a[i]);
25  // 查询区间和，例如查询 [5,8]
26       cout << “old: [5,8] = “<<sum(8)-sum(4)<< “\n”;
27  // 模拟一次修改：a [5] = a [5]+100
28       update(5,100);
29  // 重新查询 [5,8] 区间和
30       cout << “new: [5,8] = “<<sum(8)-sum(4);
31       return 0;
32  }
# 线段树


区间查询问题（最值、区间和）是线段树的一个基本应用场景。


1  void push_up(int p){                           // 从下往上传递区间值
 2       //tree [p] = tree [ls (p)] + tree [rs (p)];    // 区间和
 3       tree[p] = max(tree[ls(p)], tree[rs(p)]);  // 区间最大值
 4  }
 5  void build(int p,int pl,int pr){               // 结点编号 p 指向 [pl, pr]
 6       if(pl==pr){                               // 到达最底层的叶子结点，存叶子结点的值
 7            tree[p] = -INF;
 8            return;
 9       }
10       int mid = (pl+pr) >> 1;                   // 分治：折半
11       build(ls(p),pl,mid);                      // 递归左子结点
12       build(rs(p),mid+1,pr);                    // 递归右子结点
13       push_up(p);                               // 从下往上传递区间值
14  }
1  void update(int p,int pl,int pr,int L,int R,int d){  // 区间修改，更新 [L, R] 内的最大值
 2       if(L<=pl && pr<=R){                      // 完全覆盖，直接返回这个结点，不用再深入它的子树
 3            tree[p] = d;
 4            return;
 5       }
 6       int mid=(pl+pr)>>1;
 7       if(L<=mid) update(ls(p),pl,mid,L,R,d);   // 递归左子树
 8       if(R>mid)  update(rs(p),mid+1,pr,L,R,d); // 递归右子树
 9       push_up(p);                              // 更新
10       return;
11  }
1  int query(int p,int pl,int pr,int L,int R){                   // 查询 [L, R] 的最大值
 2       int res = -INF;
 3       if (L<=pl && pr<=R) return tree[p];                      // 完全覆盖
 4       int mid=(pl+pr)>>1;
 5       if (L<=mid) res = max(res, query(ls(p),pl,mid,L,R));     //L 与左部分有重叠
 6       if (R>mid)  res = max(res, query(rs(p),mid+1,pr,L,R));   //R 与右部分有重叠
 7       return res;
 8  }
1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 200001;
 4  const int INF = 0X7FFFFFFF;
 5  int ls(int p){ return p<<1;  }                 // 左子结点，编号是 p*2
 6  int rs(int p){ return p<<1|1;}                 // 右子结点，编号是 p*2+1
 7  int tree[N<<2];                                //4 倍空间
 8  void push_up(int p){                           // 从下往上传递区间值
 9       //tree [p] = tree [ls (p)] + tree [rs (p)];    // 区间和
10       tree[p] = max(tree[ls(p)], tree[rs(p)]);  // 区间最大值
11  }
12  void build(int p,int pl,int pr){               // 结点编号 p 指向 [pl, pr]
13       if(pl==pr){                               // 到达最底层的叶子结点，存叶子结点的值
14            tree[p] = -INF;
15            return;
16       }
17       int mid = (pl+pr) >> 1;                  // 分治：折半
18       build(ls(p),pl,mid);                     // 递归左子结点
19       build(rs(p),mid+1,pr);                   // 递归右子结点
20       push_up(p);                              // 从下往上传递区间值
21  }
22  void update(int p,int pl,int pr,int L,int R,int d){ // 区间修改，更新 [L, R] 内的最大值
23       if(L<=pl && pr<=R){            // 完全覆盖，直接返回这个结点，不用再深入它的子树
24            tree[p] = d;
25            return;
26       }
27       int mid=(pl+pr)>>1;
28       if(L<=mid) update(ls(p),pl,mid,L,R,d);    // 递归左子树
29       if(R>mid)  update(rs(p),mid+1,pr,L,R,d);  // 递归右子树
30       push_up(p);                               // 更新
31       return;
32  }
33  int query(int p,int pl,int pr,int L,int R){    // 查询 [L, R] 的最大值
34       int res = -INF;
35       if (L<=pl && pr<=R)    return tree[p];    // 完全覆盖
36       int mid=(pl+pr)>>1;
37       if (L<=mid) res = max(res, query(ls(p),pl,mid,L,R));    //L 与左子结点有重叠
38       if (R>mid)  res = max(res, query(rs(p),mid+1,pr,L,R));  //R 与右子结点有重叠
39       return res;
40  }
41  int main (){
42       int t=0,cnt=0,m,D;
43       scanf (“%d%d”,&m,&D);
44       build(1,1,N);                    // 不用 build ()，这样写也行：update (1,1,N,1,N,-INF);
45       for (int b=1;b<=m;++b){
46             char c[2];  int x;   scanf (“%s %d”,c,&x);
47             if (c[0]==’A’){
48                   cnt++;
49                   update(1,1,N,cnt,cnt,(x+t)%D);       
50             }
51             else {
52                  t = query(1,1,N,cnt-x+1,cnt);
53                  printf (“%d\n”,t);
54             }
55       }
56       return 0;
57  }
# 动态规划


01


memset (dp,0,sizeof (dp));     // 清 0。这一行可以不写，因为全局静态数组自动初始化为 0


#include<bits/stdc++.h>
using namespace std;
const int N = 3011;
int w[N], c[N];    // 物品的价值和体积
int dp[N][N];
int solve(int n, int C){
    for(int i=1; i<=n; i++)
        for(int j=0; j<=C; j++){
            if(c[i]>j) dp[i][j]=dp[i-1][j];    // 第 i 个物品的体积比背包客量大，背包装不了
            else       dp[i][j]=max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]); // 第 i 个物品可以装入背包
    }
    return dp[n][C];
}
int main(){
    int n,C; cin>>n>>C;
    for(int i=1;i<=n;i++)   cin>>c[i]>>w[i];
    memset(dp,0,sizeof(dp));     // 清 0。这一行可以不写，因为全局静态数组自动初始化为 0
    cout << solve(n, C);
    return 0;
}
自上而下用带记忆化搜索的递归代码，自下而上用递推代码


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 3011;
 4  int w[N], c[N];  
 5  int dp[N][N];
 6  int solve(int i, int j){                    // 前 i 个物品，放进容量为 j 的背包
 7      if (dp[i][j] != 0)   return dp[i][j];   // 记忆化
 8      if(i == 0) return 0;
 9      if(c[i] > j)  dp[i][j] =  solve(i-1,j);  
10      else          dp[i][j] =  max(solve(i-1,j), solve(i-1,j-c[i])+w[i]);  
11      return dp[i][j] ;
12  }
13  int main(){
14      int n,C; cin >> n >> C;
15      for(int i=1;i<=n;i++)    cin >>c[i] >> w[i];
16      memset(dp,0,sizeof(dp));               // 清 0 
17      cout << solve(n, C) << endl;
18      return 0;
19  }
滚动数组


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 3011;
 4  int w[N], c[N];                    // 物品的价值和体积
 5  int dp[2][N];                      // 替换 int dp [][];
 6  int solve(int n, int C){
 7      int now = 0, old = 1;          //now 指向当前正在计算的一行，old 指向旧的一行
 8      for(int i=1; i<=n; i++){
 9          swap(old,now);             // 交替滚动。now 始终指向最新的一行
10          for(int j = 0; j <= C; j++){
11              if(c[i] > j)  dp[now][j] = dp[old][j];
12              else          dp[now][j] = max(dp[old][j], dp[old][j-c[i]]+w[i]);
13          }
14      }
15      return dp[now][C];             // 返回最新的行
16  }
17  int main(){
18      int n,C;  cin >> n >> C;
19      for(int i=1;i<=n;i++)    cin >> c[i] >> w[i];
20      memset(dp,0,sizeof(dp));       // 清 0，置初值为 0
21      cout << solve(n, C) << endl;
22      return 0;
23  }
1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 3011;
 4  int w[N], c[N];                      // 物品的价值和体积
 5  int dp[N];
 6  int solve(int n, int C){
 7      for(int i=1; i<=n; i++)
 8          for(int j=C; j>=c[i]; j--)  // 反过来循环
 9              dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
10      return dp[C];
11  }
12  int main(){
13      int n,C;   cin >> n >> C;
14      for(int i=1;i<=n;i++)   cin >> c[i] >> w[i];
15      memset(dp,0,sizeof(dp));       // 清 0，置初值为 0
16      cout << solve(n, C) << endl;
17      return 0;
18  }
最大重量


dp[j]  表示背包容量为 j 时，可以装入的物品的最大重量。状态转移方程为  dp[j] = max(dp[j], dp[j-w[i]] + w[i]) ，表示当前背包容量为 j 时，要么不装入第 i 个物品（ dp[j] ），要么装入第 i 个物品（ dp[j-w[i]] + w[i] ）。这里选择最大值，表示要装入尽可能多的物品。


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int dp[20010];
 4  int w[40];
 5  int main(){
 6      int V,n;   scanf(“%d%d”,&V,&n);
 7      for(int i=1;i<=n;i++) scanf(“%d”,&w[i]);
 8      for(int i=1; i<=n; i++)
 9          for(int j=V; j>=w[i]; j--)
10                dp[j] =max(dp[j], dp[j-w[i]]+w[i]);
11      printf(“%d\n”,V-dp[V]);
12  }
01 方案数


背包容量为 2022，物品体积为 1～2022，往背包中装 10 个物品，要求总体积为 2022，问一共有多少种方案。与标准 0/1 背包问题的区别是这一题是求方案总数。


定义 dp [][][]，dp [i] [j] [k] 表示从数字 1～i 取 j 个和为 k 的方案数。


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  long long dp[2222][11][2222]={0};
 4  int main(){
 5      for(int i=0;i<=2022;i++)    dp[i][0][0]=1;        // 特别注意这个初始化
 6      for(int i=1;i<=2022;i++)
 7           for(int j=1;j<=10;j++)                       // 注意：j 从小到大，或从大到小都行
 8              for(int k=1;k<=2022;k++){
 9                  if(k<i) dp[i][j][k] = dp[i-1][j][k];  // 无法装进背包
10                  else    dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-i];
11              }
12      cout << dp[2022][10][2022];
13      return 0;
14  }
 1  #include<bits/stdc++.h>
 2  using namespace std;
 3  long long dp[11][2222];
 4  int main(){
 5      dp[0][0]=1;
 6      for(int i=1;i<=2022;i++)
 7          for(int j=10;j>=1;j--)             // 注意：j 一定要从大到小
 8              for(int k=i;k<=2022;k++)
 9                  dp[j][k]+=dp[j-1][k-i];
10      cout << dp[10][2022];
11      return 0;
12  }
完全 bag


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 3011;
 4  int w[N], c[N];    // 物品的价值和体积
 5  int dp[N][N];
 6  int solve(int n, int C){
 7      for (int i = 1; i <= n; i++) {
 8          for (int j = C; j >= 0; j--) {    // 反过来也一样：for (int j=0;j<=C;j++) {  
 9              if(i==1)   dp[i][j] = 0;
10              else       dp[i][j] = dp[i - 1][j];  
11              for (int k = 0; k * c[i] <= j; k++)  // 在容量为 j 的背包中放 k 个物品
12                  dp[i][j] = max(dp[i][j], dp[i - 1][j - k * c[i]] + k * w[i]);
13          }
14      }
15      return dp[n][C];
16  }
17  int main(){
18      int n,C; cin >> n >> C;
19      for(int i=1;i<=n;i++)    cin >> c[i] >> w[i];
20      memset(dp,0,sizeof(dp));      
21      cout << solve(n, C) << endl;
22  return 0;
23  }
最长公共子序列






# string


#include<bits/stdc++.h>
using namespace std;
int main(){
    string str ="123456789abcdefghiaklmn";
    for(int i=0;i<10;i++)   cout<<str[i]<< " ";         // 把 str 看成一个字符串数组
    cout << endl;
    //find () 函数
    cout<<"1()23的位置:   "<<str.find("123")<<endl;     // 输出：123 的位置:   0
    cout<<"34在str[2]到str[n-1]中的位置:   "<<str.find("34",2)<<endl;
    // 输出：34 在 str [2] 到 str [n-1] 中的位置:   2
    cout<<"ab在str[0]到str[12]中的位置:    "<<str.rfind("ab",12)<<endl;
    // 输出：ab 在 str [0] 到 str [12] 中的位置:    9
    //substr () 函数
    cout<<"str[3]及以后的子串: "<<str.substr(3)<<endl;
    // 输出：str [3] 及以后的子串：456789abcdefghiaklmn
    cout<<"从str[2]开始的4个字符: "<<str.substr(2,4)<<endl;      // 若小于限制长度，则报错
    // 输出：从 str [2] 开始的 4 个字符：3456
    //find () 函数
    str.replace(str.find("a"), 5, "@#");
    cout<<str<<endl;           // 输出：123456789@#fghiaklmn
    //insert () 函数
    str.insert(2, "***");
    cout<<"从2号位置插入: "<<str<<endl;    // 输出：从 2 号位置插入：12***3456789@#fghiaklmn
    // 添加字符串：append () 函数
    str.append("$$$");
    cout<<"在字符串str后面添加字符串: "<<str<<endl;     // 输出：在字符串 str 后面添加字符串：12***3456789@#fghiaklmn$$$
    // 求字符串长度
    cout<<str.size()<<endl;
    cout<<str.length()<<endl;
    // 交换字符串：swap () 函数
    string str1="aaa",str2="bbb";
    swap(str1, str2);
    cout<<str1<<"  "<<str2<<endl;
    // 字符串比较：compare () 函数，若相等，则输出 0；若不等，则输出 1
    cout<<str1.compare(str2)<<endl;
    if(str1==str2) cout <<"==";      // 直接比较也行
    if(str1!=str2) cout <<"!=";
    return 0;
}
# KMP


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int Next[N];
void getNext(string p){               // 计算 Next [1]～Next [plen]
    Next[0]=0; Next[1]=0;
    for(int i=1; i < p.size(); i++){  // 把 i 的增加看成后缀的逐步扩展
        int j = Next[i];              //j 的后移：j 指向前缀阴影 w 的后一个字符
        while(j && p[i] != p[j])      // 阴影的后一个字符不相同
            j = Next[j];              // 更新 j
        if(p[i]==p[j])   Next[i+1] = j+1;
        else             Next[i+1] = 0;
    }
}
int kmp(string s, string p) {         // 在 s 中找 p
    int ans=0;
    int slen=s.size(), plen=p.size();
    int j=0;
    for(int i=0; i<slen; i++) {      // 匹配 s 和 p 的每个字符
        while(j && s[i]!=p[j])       // 失配了
             j=Next[j];              //j 滑动到 Next [j] 位置
        if(s[i]==p[j]) {             // 当前位置的字符匹配，继续
            j++;
            ans=max(ans,j);          // 统计最长匹配
        }
        if(j == plen) {              //j 到了 p 的末尾，找到了一个完全匹配
            // 这个匹配，在 s 中的起点是 i+1-plen，末尾是 i。如有需要，则可以输出：
            // printf(“at location=%d, %s\n”, i+1-plen,&s[i+1-plen]);
            return ans;              // 最长前缀就是 p 的长度，直接返回
        }
    }
    return ans;                     // 返回 p 在 s 中出现的最长前缀
}
int main(){
    string s, t;
    cin >> s >> t;
    getNext(t);                     // 预计算 Next [] 数组
    cout<<kmp(s, t);
    return 0;
}
# 快排


void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int i = l - 1, j = r + 1, x = q[l + r >> 1];
	while (i < j)
	{
		do i ++ ; while (q[i] < x);
		do j -- ; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
# 分治


# 进制转换


#include <iostream>
#include <string>
#include <algorithm> // 包含标准头文件
using namespace std;
long long s, base; // 定义两个长整型变量，s 为要转换的数，base 为进制
string p = "0123456789ABCDEF"; // 定义字符串 p，存储 16 进制数的所有可能字符
string ans; // 定义字符串 ans，用于存储转换后的结果
int main() {
    // 输入要转换的数 s 和进制 base
    cin >> s >> base;
    
    // 当 s 不为 0 时循环
    while (s) {
        // 将 s 对 base 取模的结果作为索引，将对应的字符添加到 ans 末尾
        ans.push_back(p[s % base]);
        // 将 s 除以 base，更新 s 的值
        s /= base;
    }
    
    // 将 ans 反转，因为从末尾开始计算的结果需要反转才能得到正确的结果
    reverse(ans.begin(), ans.end());
    
    // 输出转换后的结果
    cout << ans;
    
    return 0; // 返回 0，表示程序正常结束
}
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
    string s;
    long long base = 0, ans = 0, k = 0;
    
    // 输入字符串 s 和进制 base
    cin >> s >> base;
    
    // 从字符串末尾开始遍历
    for (int i = s.size() - 1; i >= 0; i--) {
        // 如果字符为大写字母
        if (s[i] >= 'A') {
            ans += (s[i] - 'A' + 10) * pow(base, k++); // 更新结果
        } else {
            ans += (s[i] - '0') * pow(base, k++); // 更新结果
        }
    }
    
    // 输出结果
    cout << ans;
    
    return 0;
}
# 快速幂


#define ll long long
// 求 a 的 b 次方对 p 取模的值
ll qpow(ll a, ll b, ll p) {
    ll res = 1 % p; //res 的初值为 1 % p
    
    while (b) { // 当指数不为 0
        if (b % 2 == 1) { // 如果指数为奇数，就把结果乘上 a 的当前次方的值
            res = (res % p) * (a % p) % p;
        }
        
        a = (a % p) * (a % p) % p; // 底数平方
        b /= 2; // 指数除 2
    }
    
    return res; // 返回答案
}
# 质数


#include <cmath> // 引入 sqrt 函数的头文件
// 试除法：判断一个整数 i 是不是素数，是则返回 true，否则返回 false
bool isprime(int i) {
    if (i < 2)
        return false;
    
    for (int j = 2; j <= sqrt(i); j++) {
        if (i % j == 0)
            return false;
    }
    
    return true;
}
const int N = 1000000; // 假设 N 为一个较大的数，表示筛选的范围
int primes[N], cnt; //primes [] 存储所有素数，cnt 记录素数的个数
bool f[N]; //f [i] 存储 i 是否被筛掉，true 表示被筛掉，false 表示未被筛掉
// 筛选出小于等于 n 的所有素数
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            primes[++cnt] = i; // 将当前素数 i 记录到 primes [] 数组中
        }
        for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
            f[i * primes[j]] = true; // 将 i 的倍数的素数筛掉
            if (i % primes[j] == 0) // 如果 i 能整除 primes [j]，则退出循环，防止重复筛选
                break;
        }
    }
}
# gcd


int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
# lcm


两个数的最大公约数 × 最小公倍数 = 两数 相乘


#include <bits/stdc++.h>
using namespace std;
// 求最大公约数
long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int main() {
    long long a, b;
    // 输入两个数
    cin >> a >> b;
    // 计算最小公倍数，并输出结果
    cout << a / gcd(a, b) * b;
    // 注意这里先乘再除可能会溢出，要先除再乘
    return 0;
}

      

          
      

  


   


    

  
    
      
    
    更新于