首页 做题经验

# 数组

# 高精度

# 加法

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  string add(string a,string b){
 4      string s;                    // 存结果
 5      int c = 0;                   // 进位
 6      for(int i=a.size()-1,j=b.size()-1;i>=0||j>=0||c>0;i--,j--){
 7          if(i>=0)   c += a[i]-’0’;
 8          if(j>=0)   c += b[j]- ‘0’;
 9          s += (c%10)+ ‘0’;        // 注意这里的 s，低位在前，高位在后
10          c /= 10;
11      }
12      reverse(s.begin(),s.end());  // 反过来，高位在前，低位在后
13      return s;
14  }
15  int main(){
16      string a,b;  cin>>a>>b;      // 用字符串方式读入整数 a 和 b
17      cout<<add(a,b);
18      return 0;
19  }

# 乘法

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N = 10000;
 4  int a[N] = {0};                    // 存结果，注意大静态数组要定义在全局
 5  int main(){
 6      int n;   cin >> n;
 7      a[0] = 1;
 8      for(int i=1;i<= n;i++){                   // 模拟计算 n!
 9          int carry = 0;                        // 进位
10          for(int j=0;j< N;j++){                // 两个数相乘
11              a[j] = a[j] * i + carry;
12              carry = a[j] / 10;
13              a[j] = a[j] % 10;
14          }
15      }
16      int last;                                 // 准备打印。找到最高位，就是第一个不等于 0 的数
17      for(int i=N-1;i>=0;i--){
18          if (a[i] != 0){
19              last = i;
20              break;
21          }
22      }
23      for(int i=last; i>=0;i--) cout << a[i];  // 从最高位开始打印
24      return 0;
25  }

# 模拟

1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int a[201][201];   // 存矩阵
 4  int vis[201][201]; // 标记这个坐标的点是否已经取过
 5  int main(){
 6      int n,m;  cin >> n >> m;
 7      for(int i=1;i<=n;i++)
 8          for(int j=1;j<=m;j++)
 9              cin >> a[i][j];
10      int x=1, y=1;
11      cout << a[1][1];
12      vis[1][1] = 1;      // 标记这个坐标点已经取过
13      int sum = 1;
14      while(sum < n*m){   // 下面分别沿下、右、上、左 4 个方向取数
15          while(x+1<=n && vis[x+1][y]==0){
16              cout << “ “ << a[++x][y] ;
17              vis[x][y]=1;
18              sum++;
19          }
20          while(y+1<=m && vis[x][y+1]==0){
21              cout << “ “ << a[x][++y] ;
22              vis[x][y]=1;
23              sum++;
24          }
25          while(x-1>=1 && vis[x-1][y]==0){
26              cout << “ “ << a[--x][y] ;
27              vis[x][y]=1;
28              sum++;
29          }
30          while(y-1>=1 && vis[x][y-1]==0){
31              cout << “ “ << a[x][--y] ;
32              vis[x][y] = 1;
33              sum++;
34          }
35      }
36      return 0;
37  }

# 链表

# 链表实现

# 题目：自行车停放

【题目描述】有 n 辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。例如，停车棚里已经有 3 辆自行车，从左到右编号为 3、5、1，现在编号为 2 的第 4 辆自行车要停放在编号为 5 的自行车的左边，停车棚里的自行车编号就会变为 3、2、5、1。给定 n 辆自行车的停放情况，按顺序输出最后停放在车棚里的自行车编号。n≤100000。

【输入描述】第一行输入一个整数 n。第二行输入一个整数 x，表示第一辆自行车的编号。以下 n−1 行，每行输入 3 个整数 x、y、z。 z = 0 时，表示编号为 x 的自行车恰好停放在编号为 y 的自行车的左边。z = 1 时，表示编号为 x 的自行车恰好停放在编号为 y 的自行车的右边。

【输出描述】从左到右输出停车棚里的自行车编号。

【输入样例】

4

3

1 3 1

2 1 0

5 2 1

【输出样例】

3 2 5 1

# 双向链表

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  const int N = 200010;
 4  struct node{                          // 双向链表
 5      //int id;                         // 结点编号，没用到
 6      int data;                         // 数据
 7      int preid;                        // 指向前一个结点
 8      int nextid;                       // 指向后一个结点
 9  }nodes[N];
10  int now;                              // 链表的当前结点
11  int locate[N];                        //locate [x] = now，值为 x 的结点的位置在 nodes [now]
12  void init() {                         // 初始化
13      nodes[0].nextid = 1;
14      nodes[1].preid  = 0;
15      now = 2;
16  }
17  void insert(int k, int x) {           // 插入一个 nodes [now]，插到 nodes [k] 的右边
18      nodes[now].data = x;
19      locate[x] = now;                  // 记录值为 x 的结点的位置
20      nodes[now].nextid = nodes[k].nextid;
21      nodes[now].preid = k;
22      nodes[nodes[k].nextid].preid = now;
23      nodes[k].nextid = now;
24      now++;
25  }
26  int main() {
27      int n,a;  cin>>n>>a;              //a 是第一辆自行车的编号
28      init();
29      insert(0, a);
30      n--;
31      while (n--) {
32          int x,y,z; cin>>x>>y>>z;
33          int temp = locate[y];          // 用 locate [] 快速定位
34          if (z==0)                      // 把 x 插到 y 的左边
35              insert(nodes[temp].preid, x); 
36          else                           // 把 x 插到 y 的右边
37              insert(temp, x);
38      }
39      for (int i = nodes[0].nextid; i != 1; i = nodes[i].nextid)
40          cout << nodes[i].data << “ “;
41      return 0;
42  }

list

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  list<int>::iterator locate[100003];    // 小技巧
 4  int main(){
 5     int n,a; cin>>n>>a;
 6     list<int> L;                        // 链表
 7     L.push_back(a);                     // 插入第一个编号
 8     locate[a] = L.begin();              // 迭代器地址存入数组
 9     n--;
10     while(n--){
11          int x,y,z; cin>>x>>y>>z;
12          list<int>::iterator temp = locate[y];
13          if(z==0){                      // 把 x 插到 y 的左边
14              L.insert(temp,x);
15              locate[x] = --temp;        // 将新插入的元素地址记录到数组中
16          }
17             else{
18              L.insert(++temp,x);
19              locate[x] = --temp;
20          }
21      }
22      for(list<int>::iterator it=L.begin();it!=L.end();it++)
23          cout << *it <<” “;
24      return 0;
25  }

# 队列

# 手写

1  #define MAXQSIZE 100003                   // 自定义队列大小
 2  struct myqueue{
 3      int data[MAXQSIZE];                   // 分配静态空间
 4      int head;                             // 队首，指向队首的元素
 5      int rear;                             // 队尾，指向下一个可以存放元素的空位置
 6      bool init(){                          // 初始化队列
 7          head = rear = 0;
 8          return True;
 9      }
10      int size(){                           // 返回队列长度
11          return (rear - head + MAXQSIZE) % MAXQSIZE;
12      }
13      bool empty(){                         // 判断队列是否为空
14          if(size()==0) return True;
15          else          return False;
16      }
17      bool push(int e){                     // 在队尾插入新元素。新的 rear 指向下一个空的位置
18           if((rear + 1) % MAXQSIZE == head ) return False; // 队列满
19           data[rear] = e;
20           rear = (rear + 1) % MAXQSIZE;
21           return True;
22      }
23      bool pop(int &e){                     // 删除队首元素，并返回它
24           if(head == rear) return False;   // 队列空
25           e = data[head];
26           head = (head + 1) % MAXQSIZE;
27           return True;
28      }
29      int front(){                          // 返回队首元素，但不进行删除操作
30          return data[head];
31      }
32  };

# 题目：队列操作

【题目描述】根据输入的操作命令操作队列。

【输入描述】第一行输入一个数字 N。接下来的 N 行，每行输入的第一个数字为操作命令：1 表示入队、2 表示出队并输出、3 表示计算队列中元素的个数并输出。1≤N≤50。

【输出描述】若干行每行显示一个执行 2 或 3 命令的输出结果。注意：2 出队命令可能会出现空队出队（下溢），请输出 “no”，并退出。

【输入样例】

7

1 19

1 56

2

3

2

3

2

【输出样例】

19

1

56

0

no

# stl queue

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  int main(){
 4      queue<int> q;
 5      int n;  cin>>n;    
 6      while(n--){
 7       int num;  cin>>num;
 8       switch(num){
 9            case 1:
10                 int element;     cin>>element;
11                   q.push(element);
12                 break;
13            case 2:
14                    if(q.empty()==0){ cout<<q.front()<<endl; q.pop();}
15                 else{                 cout<<”no”<<endl;         return 0;}
16                 break;
17            case 3:
18                cout<<q.size()<<endl;
19                 break;
20      }
21      }
22      return 0;
23  }

# 手写

1  #include <bits/stdc++.h>
 2  using namespace std;
 3  #define MAXQSIZE 100003        // 自定义队列大小
 4  struct myqueue{
 5      int data[MAXQSIZE];        // 分配静态空间
 6      int head;                  // 队首，指向队首的元素
 7      int rear;                  // 队尾，指向下一个可以存放元素的空位置
 8      bool init(){               // 初始化
 9          head = rear = 0;
10          return True;
11      }
12      int size(){ return (rear - head + MAXQSIZE) % MAXQSIZE;}// 返回队列长度
13      bool empty(){              // 判断队列是否为空
14          if(size()==0) return True;
15          else          return False;
16      }
17      bool push(int e){                     // 在队尾插入新元素，rear 指向下一个空的位置
18           if((rear + 1) % MAXQSIZE == head ) return False; // 队列满
19           data[rear] = e;
20           rear = (rear + 1) % MAXQSIZE;
21           return True;
22      }
23      bool pop(int &e){                     // 删除队首元素，并返回它
24           if(head == rear) return False;   // 队列空
25           e = data[head];
26           head = (head + 1) % MAXQSIZE;
27           return True;
28      }
29      int front(){ return data[head];}      // 返回队首元素，但是不进行删除
30  }Q;
31  int main(){
32      Q.init();                             // 初始化队列
33      int n;  cin>>n;
34      for(int i=0;i<n;i++)    {
35       int num;  cin>>num;
36       switch(num){
37            case 1:
38                int element;  cin>>element;
39                  Q.push(element);
40                break;
41            case 2:
42                  if(!Q.empty()){
43                     cout<<Q.front()<<endl;
44                     int tmp;
45                     Q.pop(tmp);
46                }
47                else{ cout<<”no”<<endl; return 0;}
48                break;
49            case 3:
50                cout<<Q.size()<<endl;
51                 break;
52       }
53      }
54      return 0;
55  }

# 优先队列

1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int main() {
 4      pair<int,string> a(1, “abc”), b(7, “xyz”), c(5, “mn”);
 5      priority_queue<pair<int, string>> x;  // 队首元素总是最大值
 6      x.push(a);  
 7      x.push(b);  
 8      x.push(c);
 9      while (!x.empty()){
10          cout<<x.top().first<<” “<<x.top().second<<” --- “;
11          x.pop();
12      }
13      cout<<”\n”;
14      priority_queue<pair<int, string> ,vector<pair<int, string>> ,greater<pair<int,  
15  string>>> y;  // 队首元素总是最小值
16      y.push(a);     
17      y.push(b);  
18      y.push(c);    
19      while (!y.empty()) {
20         cout<<y.top().first<<” “<<y.top().second<<” --- “;
21         y.pop();
22      }
23      return 0;
24  }
7 xyz --- 5 mn --- 1 abc ---
1 abc --- 5 mn --- 7 xyz ---
# 栈


# 手写


1  const int N = 100100;                     // 定义栈的大小
 2  struct mystack{
 3      int a[N];                             // 存放栈元素
 4      int t = -1;                           // 栈顶位置
 5      void push(int x){ a[++t] = x; }       // 入栈
 6      int top()       { return a[t]; }      // 读栈顶元素，不弹出
 7      void pop()       { t--;         }     // 弹出栈顶元素
 8      int empty()      { return t==0?1:0;}  // 返回 1 表示栈为空
 9  };
# 题目：汉诺塔




# 递归


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  int sum = 0, m;
 4  void hanoi(char a,char b,char c,int n){ // 递归函数
 5      if(n==1) {
 6          sum++;
 7          if(sum==m) cout<<”#”<<n<<”: “<<a<<”->”<<c<<endl;
 8      }
 9      else {                              // 把 n 层递归到 n-1 层
10          hanoi(a,c,b,n-1);               // 把 Y 从 A 移动到 B 上
11          sum++;
12          if(sum==m) cout<<”#”<<n<<”: “<<a<<”->”<<c<<endl;
13          hanoi(b,a,c,n-1);               // 把 Y 从 B 移动到 C 上
14      }
15  }
16  int main(){
17      int n;    cin>>n>>m;
18      hanoi(‘A’, ‘B’, ‘C’,n);
19      cout<<sum<<endl;
20      return 0;
21  }
# 手写


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 30;
 4  int sum = 0, m;
 5  struct mystack{
 6      int a[N];                            // 存放栈元素
 7      int t = -1;                          // 栈顶位置
 8      void push(int x){ a[++t] = x; }      // 把 x 入栈
 9      int top()       { return a[t];}      // 返回栈顶元素
10      void pop()      { t--;        }      // 弹出栈顶元素
11      int empty()     { return t==0?1:0;}  // 返回 1 表示空
12  }st[4];                                  // 定义 3 根杆子：st [1]、st [2]、st [3]。st [0] 不用
13  void move(int x, int y,int n){           // 移动圆盘
14      int element = st[x].top();           // 从杆子 x 上取出顶部的圆盘放到杆子 y 上
15      st[x].pop();
16      st[y].push(element);
17      sum++;
18      char a,b;                            // 用于输出
19      if(x==1)  a=’A’;  if(x==2)  a=’B’;  if(x==3)  a=’C’;
20      if(y==1)  b=’A’;  if(y==2)  b=’B’;    if(y==3)  b=’C’;
21      if(sum == m) cout<<”#”<<n<<”: “<<a<<”->”<<b<<endl;
22  }
23  void hanoi(int n, int x, int y, int z){
24      if(n==1) move(x,z,n);
25      else{
26            hanoi(n-1, x, z, y);
27               move(x,z,n);
28               hanoi(n-1, y, x, z);
29      }
30  }
31  int main(){
32      int n;    cin>>n>>m;
33      for(int i=n;i>=1;i--)                // 初始状态：在第 1 根杆子上添加 n 个圆盘
34          st[1].push(i);
35      hanoi(n,1,2,3);
36      cout<<sum<<endl;
37      return 0;
38  }
# stl stack


1  #include<bits/stdc++.h>
 2  using namespace std;
 3  const int N = 30;
 4  int sum = 0, m;
 5  stack<int> st[4];
 6  void move(int x, int y,int n){  // 移动圆盘
 7      int element = st[x].top();  // 从杆子 x 上取出顶部的圆盘放到杆子 y 上
 8      st[x].pop();
 9      st[y].push(element);
10      sum++;
11      char a,b;  // 用于输出
12      if(x==1)  a=’A’;  if(x==2)  a=’B’;  if(x==3)  a=’C’;
13      if(y==1)  b=’A’;  if(y==2)  b=’B’;    if(y==3)  b=’C’;
14      if(sum == m) cout<<”#”<<n<<”: “<<a<<”->”<<b<<endl;
15  }
16  void hanoi(int n, int x, int y, int z){
17      if(n==1) move(x,z,n);
18      else{
19           hanoi(n-1, x, z, y);
20           move(x,z,n);
21           hanoi(n-1, y, x, z);
22      }
23  }
24  int main(){
25      int n;    cin>>n>>m;
26      for(int i=n;i>=1;i--)
27          st[1].push(i);
28      hanoi(n,1,2,3);
29      cout<<sum<<endl;
30      return 0;
31  }
# 砍竹子




#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010,M = 10; // 一根竹子砍到高度为 1，最多需要砍 6 次，这里设 M=10 次
ll f[N][M];                  //f [i][j]：第 i 根竹子被砍后的高度，f [i][0] 是竹子被砍最后一次后的高度
ll stk[M];                   // 手写栈
int main(){
    int n; scanf("%d",&n);
    int ans = 0;
    for(int i = 0;i < n;i++){
        ll x;    scanf("%lld",&x);
        int top = 0;
        while(x > 1){              
            stk[++top] = x;        // 记录竹子高度
            x = sqrtl(x / 2 + 1);   // 砍后更新竹子高度
        }
        ans += top;                // 每根竹子单独砍，总共砍 top 次
        for(int j = 0,k = top;k;j++,k--)
            f[i][j] = stk[k];      // 第 i 根竹子的高度
    }
    for(int j = 0;j < M;j++)
        for(int i = 1;i < n;i++)
            if(f[i][j] && f[i][j] == f[i - 1][j]) // 如果相邻的竹子等高，则可以一起砍
                ans--;                            // 少砍一次
    printf("%d\n",ans);
    return 0;
}
注意：


在 C++ 中， sqrt()  函数用于计算平方根，其参数可以是  float 、 double  或  long double  类型的数值。对于不同类型的参数， sqrt()  函数会返回相应类型的平方根值。


    

  • 如果参数是  float  类型，则  sqrt()  返回  float  类型的平方根值。
    • 

  • 如果参数是  double  类型，则  sqrt()  返回  double  类型的平方根值。
    • 

  • 如果参数是  long double  类型，则  sqrt()  返回  long double  类型的平方根值。
    • 



在代码中使用  sqrt()  函数时，根据实际情况选择正确的数据类型，并确保参数和返回值的类型匹配。如果需要对  long double  类型的数值计算平方根，则可以使用  sqrtl()  函数。


因此，在上面的代码中，如果需要对  long long  类型的数值计算平方根，可以使用  sqrt()  函数，而如果需要对  long double  类型的数值计算平方根，则可以使用  sqrtl()  函数。


# 二叉树


      

          
      

  


   


    

  
    
      
    
    更新于