研究生机试备考练习（2）- 落谷

TODO 还没学明白 TEX 公式格式导出到博客时还要更改

[mathjax]

目录展开

分治专题

1 快速幂 AC

将指数变成二进制数字，分别求每个 1 的结果

#include <cstdio>
typedef long long LL;
int to2(LL k,int result[]){
    int count = 0;
    while(k > 0){
        result[count] = k % 2;
        k >>= 1;        // 向右移位
        count ++;
    }
    return count;
}
int main(){
    LL b,p,k;
    int midres[32] = {};
    scanf("%lld %lld %lld",&b,&p,&k);
    LL finalres = 1;
    int count = to2(p,midres);
    LL num[32] = {b%k};
    for(int i = 1;i<count;i++){
        num[i] = num[i-1] * num[i-1] % k;
//        printf("%d-%lld ",i,num[i]);
    }
    for(int i = 0;i<count;i++){
        if(midres[i] == 1) {
            finalres *= num[i];
            finalres %= k;
        }
    }
    // 最后需要再 %k 否则 84分 （反例：2 0 1）
    printf("%lld^%lld mod %lld=%lld\n",b,p,k,finalres %k);
    return 0;
}

#include <cstdio>

typedef long long LL;

int to2(LL k,int result[]){

int count = 0;

while(k > 0){

result[count] = k % 2;

k >>= 1; // 向右移位

count ++;

}

return count;

}

int main(){

LL b,p,k;

int midres[32] = {};

scanf("%lld %lld %lld",&b,&p,&k);

LL finalres = 1;

int count = to2(p,midres);

LL num[32] = {b%k};

for(int i = 1;i<count;i++){

num[i] = num[i-1] * num[i-1] % k;

// printf("%d-%lld ",i,num[i]);

}

for(int i = 0;i<count;i++){

if(midres[i] == 1) {

finalres *= num[i];

finalres %= k;

}

// 最后需要再 %k 否则 84分（反例：2 0 1）

printf("%lld^%lld mod %lld=%lld\n",b,p,k,finalres %k);

return 0;

}

看了大佬题解发现，自己很多空间都是多余的。最后只要一个计数的答案，因此中间结果并不需要记录下来：

// 大佬题解
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long ans=1,i,j,k,m,n,b,p;
    scanf("%lld%lld%lld",&b,&m,&p);
    printf("%lld^%lld mod %lld=",b,m,p);
    while(m>0){
        if(m%2==1)
            ans=ans*b%p;
        b=b*b%p;
        m=m>>1;
    }
    printf("%lld",ans%p);
    return 0;
}

// 大佬题解

#include <bits/stdc++.h>

using namespace std;

int main(){

long long ans=1,i,j,k,m,n,b,p;

scanf("%lld%lld%lld",&b,&m,&p);

printf("%lld^%lld mod %lld=",b,m,p);

while(m>0){

if(m%2==1)

ans=ans*b%p;

b=b*b%p;

m=m>>1;

}

printf("%lld",ans%p);

return 0;

}

2 幂次方 AC

分治，递归，主要是括号格式问题

# include <cstdio>
int mi[15] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};// 这里直接偷懒了
void devide(int n){
    if(n == 2)printf("2");
    else if (n == 4)printf("2(2)");
    else{
        int sgn = 0,never = 0;
        for(int i = 14;i>=0;i--){
            if (n >= mi[i] && n > 3){
                if (sgn != 0)printf("+");
                printf("2(");
                devide(i);
                printf(")");
                n -= mi[i];
                sgn ++;
            }else if (n == 3){
                if (sgn != 0)printf("+");
                printf("2+2(0)");
                n = 0;
                sgn ++;
            }else if (n == 2){
                if (sgn == 0)printf("(2)");
                else printf("+2");
                n = 0;
                sgn ++;
            }else if (n == 1){
                if(sgn > 0 && never == 0){
                    printf("+2(0)");
                    never = 1;
                }
            }
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    devide(n);
    return 0;
}

# include <cstdio>

int mi[15] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};// 这里直接偷懒了

void devide(int n){

if(n == 2)printf("2");

else if (n == 4)printf("2(2)");

else{

int sgn = 0,never = 0;

for(int i = 14;i>=0;i--){

if (n >= mi[i] && n > 3){

if (sgn != 0)printf("+");

printf("2(");

devide(i);

printf(")");

n -= mi[i];

sgn ++;

}else if (n == 3){

if (sgn != 0)printf("+");

printf("2+2(0)");

n = 0;

sgn ++;

}else if (n == 2){

if (sgn == 0)printf("(2)");

else printf("+2");

n = 0;

sgn ++;

}else if (n == 1){

if(sgn > 0 && never == 0){

printf("+2(0)");

never = 1;

}

int main(){

int n;

scanf("%d",&n);

devide(n);

return 0;

}

对于这道题，一开始的几个不需要括号的我单独列出来了，而大佬救是不同凡响，一句话解决

大佬题解

#include<bits/stdc++.h>
using namespace std;
string run(int x,int i=0,string s=string("")){
    if(x==0)return string("0");
    do if(x&1)s=(i==1?"2":"2("+run(i)+")")+(s==""?"":"+")+s;//拼接字符串，应题意，要把低次方接在后面
    while(++i,x>>=1);//每次向右移位
    return s;
}
int main(){
    int x;cin>>x;
    cout<<run(x)<<endl;
}

#include<bits/stdc++.h>

using namespace std;

string run(int x,int i=0,string s=string("")){

if(x==0)return string("0");

do if(x&1)s=(i==1?"2":"2("+run(i)+")")+(s==""?"":"+")+s;//拼接字符串，应题意，要把低次方接在后面

while(++i,x>>=1);//每次向右移位

return s;

}

int main(){

int x;cin>>x;

cout<<run(x)<<endl;

}

3 逆序对

线段树 # TODO

入门详解

· 在数组表示🌲的时候，通常左孩子 2*v 在代码中写成 v<<1；右孩子 2*v+1 写成 v<<1|1

4 画图

杨辉三角是真的秀。常规方法：建一个 1024 * 2048 的 char 矩阵，将图腾先倒置处理，最后倒序输出。

递归专题

1 台阶问题 AC

# TEX 最原始的思路是 $(a_n = a_{n-1} + … + a_{n-k})$ 代码如下

# include <cstdio>
int n,k,solution[100001] = {1};

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i<=n;i++){
        for(int j = i-k;j<i;j++){
            if(j >= 0)
                solution[i]=(solution[i] + solution[j])%100003;
        }
    }
//    for(int i = 0;i<=n;i++){
//        printf("%d ",solution[i]);
//    }
    printf("%d",solution[n]);
}

# include <cstdio>

int n,k,solution[100001] = {1};

int main(){

scanf("%d%d",&n,&k);

for(int i = 1;i<=n;i++){

for(int j = i-k;j<i;j++){

if(j >= 0)

solution[i]=(solution[i] + solution[j])%100003;

}

// for(int i = 0;i<=n;i++){

// printf("%d ",solution[i]);

// }

printf("%d",solution[n]);

}

大佬的高级方法：

高级递归 O( n ) ： ( a_n = 2 * a_{n-1} – a_{i-k-1} )
矩阵乘法 O( n * logk )：设 n = 4，

$$\begin{matrix} let \quad A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix} &
B = \begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ a_{n-3} \end {bmatrix}\end{matrix}$$

那么

$$\begin{matrix} B &* &A &= &\begin{bmatrix} a_{n+1} \\ a_{n} \\ a_{n-1} \\ a_{n-2} \end {bmatrix} \end{matrix}$$

所以 $( a_n = (B * A^{n-k})[1] )$ ，此处就可以使用快速幂的方法

树状数组 O( n * logk )：树状数组可以解决的问题都可以用线段树解决，但是树状数组的系数要少很多

2 数的划分 AC

这个题做的太奇妙了，我都还没弄懂具体细节，写了个 dfs，题目样例对了，交上去竟然一次 AC

# include <cstdio>
int n,k;
int solu(int n,int k,int min){  // min 是本次子划分最小的数字
    if (n == 1 || k == 1)return 1;
    if (min > n)return 0;
    int solution = 0;
    for(int i = min;i<=n/k;i++){
        // 每个划分都是从小到大划分
        solution += solu(n-i,k-1,i);
    }
    return solution;
}
int main(){
    scanf("%d%d",&n,&k);
    printf("%d",solu(n, k, 1));
}

# include <cstdio>

int n,k;

int solu(int n,int k,int min){ // min 是本次子划分最小的数字

if (n == 1 || k == 1)return 1;

if (min > n)return 0;

int solution = 0;

for(int i = min;i<=n/k;i++){

// 每个划分都是从小到大划分

solution += solu(n-i,k-1,i);

}

return solution;

}

int main(){

scanf("%d%d",&n,&k);

printf("%d",solu(n, k, 1));

}

看到有人用 #include <bits/stdc++.h>，意思是包含所有的 C++ 头文件，百炼 OJ 亲测可用！然鹅本地 XCode 的 GCC 竟然不行==

3 传球游戏 AC

太爽了，又是一次 AC

# include <cstdio>
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int res[30][30] = {};
    for(int i = 0;i<m;i++){
        if(i == 0){
            for(int j = 0;j<n;j++){
                if (j == n-1 || j % n == 1)
                    res[i][j] = 1;
            }
        }else{
            for(int j = 0;j<n;j++){
                res[i][j] = res[i-1][(j+n-1)%n] + res[i-1][(j+n+1)%n];
            }
        }
    }
//    for(int i = 0;i<m;i++){
//        for(int j = 0;j<n;j++){
//            printf("%d ",res[i][j]);
//        }
//        printf("\n");
//    }
    printf("%d",res[m-1][0]);
    return 0;
}

# include <cstdio>

int main(){

int n,m;

scanf("%d%d",&n,&m);

int res[30][30] = {};

for(int i = 0;i<m;i++){

if(i == 0){

for(int j = 0;j<n;j++){

if (j == n-1 || j % n == 1)

res[i][j] = 1;

}

}else{

for(int j = 0;j<n;j++){

res[i][j] = res[i-1][(j+n-1)%n] + res[i-1][(j+n+1)%n];

}

// for(int i = 0;i<m;i++){

// for(int j = 0;j<n;j++){

// printf("%d ",res[i][j]);

// }

// printf("\n");

// }

printf("%d",res[m-1][0]);

return 0;

}

我的想法就是模拟一次次传播，看到一位大佬和我方法差不多，但是代码风格很新奇：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[50][50];
int main()
{
    cin>>n>>m;f[0][0]=1;
    for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    if(f[i][j])
    f[i+1][(j-1+n)%n]+=f[i][j], // 后面是‘，’可以并列语句，少大括号。
    f[i+1][(j+1)%n]+=f[i][j];
    cout<<f[m][0];
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n,m,f[50][50];

int main()

{

cin>>n>>m;f[0][0]=1;

for(int i=0;i<m;i++)

for(int j=0;j<n;j++)

if(f[i][j])

f[i+1][(j-1+n)%n]+=f[i][j], // 后面是‘，’可以并列语句，少大括号。

f[i+1][(j+1)%n]+=f[i][j];

cout<<f[m][0];

return 0;

}

4 电梯 AC

DFS，有个小错找了好久。记得一定要回溯！不然本条路线的 vis 会被其它路线影响

# include <cstdio>
# include <vector>
# define min(x,y) x<y ? x : y
using namespace std;
vector<int>graph[205];
int vis[205] = {},ans = 0X7fffffff;

void DFS(int start,int step,int end){
//    printf("%d - %d -\n",start,step);
    if (start == end){
        ans = step;
    }
    if (step >= ans);  // 剪枝！
    else if (graph[start].size() > 0){
        vis[start] = 1;
        for(int i = 0;i<graph[start].size();i++){
            if (vis[graph[start][i]] == 0)
                DFS(graph[start][i],step+1,end);
        }
        vis[start] = 0; // 回溯，否则其它并行道路会受当前道路的影响而走不通
    }
}
int main(){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    for(int i = 1;i<=n;i++){
        int temp;
        scanf("%d",&temp);
        if (temp != 0){
            if (i > temp)
                graph[i].push_back(i - temp);
            if (i + temp <= n)
                graph[i].push_back(i + temp);
        }
    }
    vis[a] = 1;
    int step = 0;
    DFS(a,step,b);
    printf("%d",ans == 0X7fffffff?-1:ans);
    return 0;
}

# include <cstdio>

# include <vector>

# define min(x,y) x<y ? x : y

using namespace std;

vector<int>graph[205];

int vis[205] = {},ans = 0X7fffffff;

void DFS(int start,int step,int end){

// printf("%d - %d -\n",start,step);

if (start == end){

ans = step;

}

if (step >= ans); // 剪枝！

else if (graph[start].size() > 0){

vis[start] = 1;

for(int i = 0;i<graph[start].size();i++){

if (vis[graph[start][i]] == 0)

DFS(graph[start][i],step+1,end);

}

vis[start] = 0; // 回溯，否则其它并行道路会受当前道路的影响而走不通

}

int main(){

int n,a,b;

scanf("%d %d %d",&n,&a,&b);

for(int i = 1;i<=n;i++){

int temp;

scanf("%d",&temp);

if (temp != 0){

if (i > temp)

graph[i].push_back(i - temp);

if (i + temp <= n)

graph[i].push_back(i + temp);

}

vis[a] = 1;

int step = 0;

DFS(a,step,b);

printf("%d",ans == 0X7fffffff?-1:ans);

return 0;

}

5 数字三角形 AC

这道题就是 POJ 2760，也是《引导》第十章第一题，当时做太难了，于是放弃了这本书，开始刷落谷的递归动态规划，没想到现在竟然秒杀。之前其实是粗心的错误，结点的父节点并不是 <<1，这不是二叉树！！

# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 1000001;

int main(){
    int n,tri[maxn] = {},sum[maxn] = {};
    scanf("%d",&n);
    scanf("%d",&tri[1]);
    sum[1] = tri[1];
    int count = 2;
    for(int i = 2;i<=n*(n+1)/2;i++){
        scanf("%d",&tri[i]);
        if (i != count*(count+1)/2 &&
            i-1 != count*(count+1)/2){
            int father = i - count*(count-1)/2 + (count-2)*(count-1)/2;
            sum[i] = tri[i] + max(sum[father-1],sum[father]);
        }
        else if(i == count*(count+1)/2){
            int father = count*(count-1)/2;
            sum[i] = tri[i] + sum[father];
        }
        else if(i == count*(count+1)/2 + 1){
            int father = count*(count-1)/2 + 1;
            sum[i] = tri[i] + sum[father];
            count ++;
        }
    }
//    // 打印和三角
//    count = 1;
//    printf("\n");
//    for(int i = 1;i<=n*(n+1)/2;i++){
//        printf("%3d ",sum[i]);
//        if(i == count*(count+1)/2){
//            printf("\n");
//            for(int j = 0;j<(n - count);j++){
//                printf("  ");
//            }
//            count++;
//        }
//    }
//    // 打印原三角
//    count = 1;
//    printf("\n");
//    for(int i = 1;i<=n*(n+1)/2;i++){
//        printf("%3d ",tri[i]);
//        if(i == count*(count+1)/2){
//            printf("\n");
//            for(int j = 0;j<(n - count);j++){
//                printf("  ");
//            }
//            count++;
//        }
//    }
    int maxsum = sum[n*(n-1)/2];
    for(int i = n*(n-1)/2;i<=n*(n+1)/2;i++){
        maxsum = maxsum > sum[i]?maxsum:sum[i];
    }
    printf("%d",maxsum);
    return 0;
}

# include <cstdio>

# include <algorithm>

using namespace std;

const int maxn = 1000001;

int main(){

int n,tri[maxn] = {},sum[maxn] = {};

scanf("%d",&n);

scanf("%d",&tri[1]);

sum[1] = tri[1];

int count = 2;

for(int i = 2;i<=n*(n+1)/2;i++){

scanf("%d",&tri[i]);

if (i != count*(count+1)/2 &&

i-1 != count*(count+1)/2){

int father = i - count*(count-1)/2 + (count-2)*(count-1)/2;

sum[i] = tri[i] + max(sum[father-1],sum[father]);

}

else if(i == count*(count+1)/2){

int father = count*(count-1)/2;

sum[i] = tri[i] + sum[father];

}

else if(i == count*(count+1)/2 + 1){

int father = count*(count-1)/2 + 1;

sum[i] = tri[i] + sum[father];

count ++;

}

// // 打印和三角

// count = 1;

// printf("\n");

// for(int i = 1;i<=n*(n+1)/2;i++){

// printf("%3d ",sum[i]);

// if(i == count*(count+1)/2){

// printf("\n");

// for(int j = 0;j<(n - count);j++){

// printf(" ");

// }

// count++;

// }

// // 打印原三角

// count = 1;

// printf("\n");

// for(int i = 1;i<=n*(n+1)/2;i++){

// printf("%3d ",tri[i]);

// if(i == count*(count+1)/2){

// printf("\n");

// for(int j = 0;j<(n - count);j++){

// printf(" ");

// }

// count++;

// }

int maxsum = sum[n*(n-1)/2];

for(int i = n*(n-1)/2;i<=n*(n+1)/2;i++){

maxsum = maxsum > sum[i]?maxsum:sum[i];

}

printf("%d",maxsum);

return 0;

}

然而大佬就厉害了：用一维数组做，妙哉！

首先是边读边做，第一层循环 i 从 n 到 1，第二层循环 j 从 i 到 n（为了每次都能取到上次的值）,每次读入一个变量 p，

状态转移方程：a[j] = max{a[j],a[j+1]}+p（a[j]表示走到第 i 层第 j 个时的最大值）。最后输出 a 数组的最大值即可。

下面我来用测试数据模拟一下 (注意：要开1002的数组，不然会越界)：

a[1] a[2] a[3] a[4] a[5] a[6]

初始化：  0  0  0  0  0 0

第一次：  0  0  0  0  7 0

第二次：  0  0  0 10 15 0

第三次：  0  0 18 16 15 0

第四次：  0 20 25 20 19 0

第五次： 24 30 27 26 24 0

a[1] a[2] a[3] a[4] a[5] a[6]

初始化： 0 0 0 0 0 0

第一次： 0 0 0 0 7 0

第二次： 0 0 0 10 15 0

第三次： 0 0 18 16 15 0

第四次： 0 20 25 20 19 0

第五次： 24 30 27 26 24 0

代码（c/c++）：

#include<cstdio>
int n,a[1002],i,j,ans,p;
int max(int &x,int &y){return x>y?x:y;}
int main(){
    scanf("%d",&n);
        for(i=n;i;i--)
            for(j=i;j<=n;j++)
                scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
        for(i=1;i<=n;i++)
            ans=max(ans,a[i]);
        printf("%d",ans);
        return 0;
}

#include<cstdio>

int n,a[1002],i,j,ans,p;

int max(int &x,int &y){return x>y?x:y;}

int main(){

scanf("%d",&n);

for(i=n;i;i--)

for(j=i;j<=n;j++)

scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;

for(i=1;i<=n;i++)

ans=max(ans,a[i]);

printf("%d",ans);

return 0;

}

一些其他的没啥用的概念：

register 关键字：请求编译器尽可能的将变量存在 CPU 内部寄存器中，而不是通过内存寻址访问，以提高效率。
inline：用法

6 数字分段 TODO

7 丢瓶盖 TODO

这两题都是二分法

8 过河卒 AC

用DFS超时

# include <cstdio>
int m,n,x,y;
int g[21][21] = {},vis[21][21] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};

bool legal(int x,int y){
    if (x < 0 || y < 0 || x > m || y >n || g[x][y] || vis[x][y])return false;
    return true;
}

void DFS(int i,int j){
    vis[i][j] = 1;
    if (i == m && j == n)res++;
    else{
        if (legal(i+1,j)) DFS(i+1,j);
        if (legal(i,j+1)) DFS(i,j+1);
//        if (legal(i-1,j)) DFS(i-1,j);
//        if (legal(i,j-1)) DFS(i,j-1);
    }
    vis[i][j] = 0;
}
int main(){
    scanf("%d %d %d %d",&m,&n,&x,&y);
    g[x][y] = 1;
    for (int i = 0;i<8;i++){
        int nx = x+a[i][0],ny = y+a[i][1];
        if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
            g[nx][ny] = 1;
    }
    DFS(0,0);
    printf("%d",res);
    return 0;
}

# include <cstdio>

int m,n,x,y;

int g[21][21] = {},vis[21][21] = {},res = 0;

int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};

bool legal(int x,int y){

if (x < 0 || y < 0 || x > m || y >n || g[x][y] || vis[x][y])return false;

return true;

}

void DFS(int i,int j){

vis[i][j] = 1;

if (i == m && j == n)res++;

else{

if (legal(i+1,j)) DFS(i+1,j);

if (legal(i,j+1)) DFS(i,j+1);

// if (legal(i-1,j)) DFS(i-1,j);

// if (legal(i,j-1)) DFS(i,j-1);

}

vis[i][j] = 0;

}

int main(){

scanf("%d %d %d %d",&m,&n,&x,&y);

g[x][y] = 1;

for (int i = 0;i<8;i++){

int nx = x+a[i][0],ny = y+a[i][1];

if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)

g[nx][ny] = 1;

}

DFS(0,0);

printf("%d",res);

return 0;

}

递推 AC

// 2020-03-16 11:46:57
// https://www.luogu.com.cn/problem/P1002
# include <cstdio>
#include<algorithm>
using namespace std;
int m,n,x,y;
int g[30][30] = {},vis[30][30] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
unsigned long long f[30][30];

int main(){
    scanf("%d %d %d %d",&m,&n,&x,&y);
    g[x][y] = 1;
    for (int i = 0;i<8;i++){
        int nx = x+a[i][0],ny = y+a[i][1];
        if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
            g[nx][ny] = 1;
    }
    f[0][0] = 1;
    for(int i = 0;i<=m;i++){
        for(int j = 0;j<=n;j++){
            if (g[i][j])continue;
            f[i][j] = max(f[i][j],f[i-1][j]+f[i][j-1]);
        }
    }
    printf("%lld",f[m][n]);
    return 0;
}

// 2020-03-16 11:46:57

// https://www.luogu.com.cn/problem/P1002

# include <cstdio>

#include<algorithm>

using namespace std;

int m,n,x,y;

int g[30][30] = {},vis[30][30] = {},res = 0;

int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};

unsigned long long f[30][30];

int main(){

scanf("%d %d %d %d",&m,&n,&x,&y);

g[x][y] = 1;

for (int i = 0;i<8;i++){

int nx = x+a[i][0],ny = y+a[i][1];

if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)

g[nx][ny] = 1;

}

f[0][0] = 1;

for(int i = 0;i<=m;i++){

for(int j = 0;j<=n;j++){

if (g[i][j])continue;

f[i][j] = max(f[i][j],f[i-1][j]+f[i][j-1]);

}

printf("%lld",f[m][n]);

return 0;

}

9 出栈序列 AC

由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分

比x小

比x大

比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]

比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]

这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]

另外，由于x有n个取值，所以

ans = f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0];

这，就是传说中的卡特兰数

# include <cstdio>
int n,f[20] = {1,1};
int main(){
    scanf("%d",&n);
    for(int i = 2;i<=n;i++){
        for (int j = 0;j<i;j++){
            f[i] += f[j]  * f[i-j-1];
        }
    }
    printf("%d",f[n]);
    return 0;
}

# include <cstdio>

int n,f[20] = {1,1};

int main(){

scanf("%d",&n);

for(int i = 2;i<=n;i++){

for (int j = 0;j<i;j++){

f[i] += f[j] * f[i-j-1];

}

printf("%d",f[n]);

return 0;

}

10 数的计算 AC

我的方法过于暴力，但是也能过

# include <cstdio>
int n,f[1005] = {1};
int main(){
    scanf("%d",&n);
    for (int i = 1;i<=n;i++){
        for(int j = 0;j<=i/2;j++){
            f[i]+=f[j];
        }
    }
    // 这里其实可以只算到 f[n/2]，最后输出累加和
    printf("%d",f[n]);
    return 0;
}

# include <cstdio>

int n,f[1005] = {1};

int main(){

scanf("%d",&n);

for (int i = 1;i<=n;i++){

for(int j = 0;j<=i/2;j++){

f[i]+=f[j];

}

// 这里其实可以只算到 f[n/2]，最后输出累加和

printf("%d",f[n]);

return 0;

}

大佬的 DP 方法：

#include<cstdio>
using namespace std;
int main(){
    int n,cnt=1,i,f[1010];
    f[0]=f[1]=1;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        if(i%2==0){
            f[i]=f[i-1]+f[i/2];
        }else{
            f[i]=f[i-1];
        }
    }
    printf("%d\n",f[n]);
}

#include<cstdio>

using namespace std;

int main(){

int n,cnt=1,i,f[1010];

f[0]=f[1]=1;

scanf("%d",&n);

for(i=2;i<=n;i++){

if(i%2==0){

f[i]=f[i-1]+f[i/2];

}else{

f[i]=f[i-1];

}

printf("%d\n",f[n]);

}

11 蜜蜂采蜜 AC

看到范围 1000，用高精！

# 2020-03-17 09:58:32
inn = input().split(" ")
m = int(inn[0])
n = int(inn[1])
f = [0]*1005
f[m] = 1
for i in range(m+1,n+1):
    f[i] = f[i-1] + f[i-2]
print(f[n])

# 2020-03-17 09:58:32

inn = input().split(" ")

m = int(inn[0])

n = int(inn[1])

f = [0]*1005

f[m] = 1

for i in range(m+1,n+1):

f[i] = f[i-1] + f[i-2]

print(f[n])

12 铺瓷砖 AC

这种题考数学，写出前几项，找规律

# include <cstdio>
int n,f[1000000] = {0,1,2,5};
int main(){
    scanf("%d",&n);
    for (int i = 4;i<=n;i++){
        f[i] = f[i-3]+ f[i-1]*2;
        f[i] %= 10000;
    }
    printf("%d",f[n]);
    return 0;
}

# include <cstdio>

int n,f[1000000] = {0,1,2,5};

int main(){

scanf("%d",&n);

for (int i = 4;i<=n;i++){

f[i] = f[i-3]+ f[i-1]*2;

f[i] %= 10000;

}

printf("%d",f[n]);

return 0;

}

线性数据结构

1 报数淘汰 AC

非常简单的数组模拟

#include <cstdio>
int main(){
    int n,m,count = 0,j = 0;
    scanf("%d %d",&n,&m);
    int vis[100] = {};
    for(int i = 0;i<n;){
        if (vis[j%n] == 0){
            count ++;
        }
        if (count == m){
            vis[j%n] = 1;
            count = 0;
            printf("%d",j%n + 1);
            if (i < n-1)printf(" ");
            i++;
        }
        j++;
    }
    return 0;
}

#include <cstdio>

int main(){

int n,m,count = 0,j = 0;

scanf("%d %d",&n,&m);

int vis[100] = {};

for(int i = 0;i<n;){

if (vis[j%n] == 0){

count ++;

}

if (count == m){

vis[j%n] = 1;

count = 0;

printf("%d",j%n + 1);

if (i < n-1)printf(" ");

i++;

}

j++;

}

return 0;

}

2 最大子段和 AC

#include <cstdio>
int main(){
    int n,sum = 0,sgn = 0,max = -0x3fffffff;
    scanf("%d",&n);
    int a[n];
    // 输入，并判断数列中是否有正数
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
        if (a[i] > 0)sgn = 1;
        max = max<a[i]?a[i]:max;
    }
    if (sgn == 0){  // 如果全为负，则选一个最大的
        printf("%d",max);
        return 0;
    }else{  // 有正数，则挑选、舍弃
        for(int i = 0;i<n;i++){
            sum += a[i];
            if (sum <= 0)sum = 0;
    //        printf("%d- ",sum);
            max = max<sum?sum:max;
        }
        printf("%d",max);
        return 0;
    }
}

#include <cstdio>

int main(){

int n,sum = 0,sgn = 0,max = -0x3fffffff;

scanf("%d",&n);

int a[n];

// 输入，并判断数列中是否有正数

for(int i = 0;i<n;i++){

scanf("%d",&a[i]);

if (a[i] > 0)sgn = 1;

max = max<a[i]?a[i]:max;

}

if (sgn == 0){ // 如果全为负，则选一个最大的

printf("%d",max);

return 0;

}else{ // 有正数，则挑选、舍弃

for(int i = 0;i<n;i++){

sum += a[i];

if (sum <= 0)sum = 0;

// printf("%d- ",sum);

max = max<sum?sum:max;

}

printf("%d",max);

return 0;

}

其中，第一次写的时候遗漏了最大和为负的情况，例如数据“1 -1”答案就不对，于是分类进行讨论

而大佬的方法就厉害了，先判断大于零，再加当前的数字，就能统一算法了！！

#include<cstdio>
int n,j,sum,maxx;
int main(){
    scanf("%d%d",&n,&maxx);
    sum=maxx;//输入n
    while(--n){
        scanf("%d",&j);
        sum=sum>0?sum:0;
        sum+=j;
        maxx=maxx>sum?maxx:sum;
    }//贪心，如果负了就舍去
    return (printf("%d",maxx))&0;//输出并return 0
}

#include<cstdio>

int n,j,sum,maxx;

int main(){

scanf("%d%d",&n,&maxx);

sum=maxx;//输入n

while(--n){

scanf("%d",&j);

sum=sum>0?sum:0;

sum+=j;

maxx=maxx>sum?maxx:sum;

}//贪心，如果负了就舍去

return (printf("%d",maxx))&0;//输出并return 0

}

3 括号匹配 AC

送分题

#include<cstdio>
int main(){
    int count = 0;
    char ch;
    while(1){
        scanf("%c",&ch);
        if (ch == '(')count ++;
        else if(ch == ')')count --;
        else if(ch == '@')break;
        if (count < 0){
            printf("NO");
            return 0;
        }
    }
    if (count == 0)printf("YES");
    else printf("NO");
    return 0;
}

#include<cstdio>

int main(){

int count = 0;

char ch;

while(1){

scanf("%c",&ch);

if (ch == '(')count ++;

else if(ch == ')')count --;

else if(ch == '@')break;

if (count < 0){

printf("NO");

return 0;

}

if (count == 0)printf("YES");

else printf("NO");

return 0;

}

4 链表优化 40 TLE TODO

我直接用的 stl 里面的 vector，我想不到有什么优化的方法。找的过程如果用 hashtable，可以缩短到 O(1) 时间找到，但是在插入的时候，hashtable 就要花费 O(n) 的时间来修改，我现在这样是花费多个 O(logn)，改 hash 难道不是得不偿失吗？

# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;

int main(){
    int n,m,lr,v;
    vector<int>team(1,1);
    scanf("%d",&n);
    for(int i = 1;i<n;i++){
        scanf("%d %d",&v,&lr);
        team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);
    }
    scanf("%d",&m);
    for(int i = 0;i<m;i++){
        scanf("%d",&v);
        vector<int>::iterator res = find(team.begin( ), team.end( ), v);
        if (res != team.end())
            team.erase(res);
    }
    for(int i = 0;i<team.size();i++){
        printf("%d",team[i]);
        if(i != team.size()-1)printf(" ");
        else printf("\n");
    }
    return 0;
}

# include <cstdio>

# include <vector>

# include <algorithm>

using namespace std;

int main(){

int n,m,lr,v;

vector<int>team(1,1);

scanf("%d",&n);

for(int i = 1;i<n;i++){

scanf("%d %d",&v,&lr);

team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);

}

scanf("%d",&m);

for(int i = 0;i<m;i++){

scanf("%d",&v);

vector<int>::iterator res = find(team.begin( ), team.end( ), v);

if (res != team.end())

team.erase(res);

}

for(int i = 0;i<team.size();i++){

printf("%d",team[i]);

if(i != team.size()-1)printf(" ");

else printf("\n");

}

return 0;

}

5 后缀表达式 AC

一开始担心除法，用的 float，67分，改成 long long，AC

# include <cstdio>
# include <cstring>
# include <stack>
using namespace std;
long long calcu(long long b,long long a,char ch){
    if (ch == '*')return a*b;
    else if (ch == '/')return a/b;
    else if (ch == '-')return a-b;
    else return a+b;
}
int main(){
    char ch;
    int num = 0;
    stack<long long>n;
    while(1){
        scanf("%c",&ch);
        if (ch >= '0' && ch <= '9')
            num = num * 10 + ch - '0';
        else if (ch == '.') {
            n.push(num);
            num = 0;
        }else if (ch == '@'){
            break;
        }else{
            long long tempa = n.top();n.pop();
            long long tempb = n.top();n.pop();
            n.push(calcu(tempa,tempb,ch));
        }
    }
    printf("%d",(int)n.top());
}

# include <cstdio>

# include <cstring>

# include <stack>

using namespace std;

long long calcu(long long b,long long a,char ch){

if (ch == '*')return a*b;

else if (ch == '/')return a/b;

else if (ch == '-')return a-b;

else return a+b;

}

int main(){

char ch;

int num = 0;

stack<long long>n;

while(1){

scanf("%c",&ch);

if (ch >= '0' && ch <= '9')

num = num * 10 + ch - '0';

else if (ch == '.') {

n.push(num);

num = 0;

}else if (ch == '@'){

break;

}else{

long long tempa = n.top();n.pop();

long long tempb = n.top();n.pop();

n.push(calcu(tempa,tempb,ch));

}

printf("%d",(int)n.top());

}

6 水list AC

# include <cstdio>
int a[2000001],n,m,d;
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++)scanf("%d",&a[i]);
    for(int i = 0;i<m;i++){
        scanf("%d",&d);
        printf("%d\n",a[d-1]);
    }
    return 0;
}

# include <cstdio>

int a[2000001],n,m,d;

int main(){

scanf("%d %d",&n,&m);

for(int i = 0;i<n;i++)scanf("%d",&a[i]);

for(int i = 0;i<m;i++){

scanf("%d",&d);

printf("%d\n",a[d-1]);

}

return 0;

}

7 map AC

hash 空间不够，改成 map

#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{
    scanf("%d%d",&n,&q);
    while(q--)
    {
        scanf("%d %d %d",&p,&i,&j);
        if(p==1)
        {
            scanf("%d",&k);
            b[i*1000000+j]=k;
        }
        else printf("%d\n",b[i*1000000+j]);
    }
    return 0;
}

#include<cstdio>

#include<map>

using namespace std;

int n,q,p,k;

map<long long,int>b;

long long i,j;

int main()

{

scanf("%d%d",&n,&q);

while(q--)

{

scanf("%d %d %d",&p,&i,&j);

if(p==1)

{

scanf("%d",&k);

b[i*1000000+j]=k;

}

else printf("%d\n",b[i*1000000+j]);

}

return 0;

}

8 模拟栈 AC

# include <cstdio>
# include <stack>
using namespace std;
int q,n;
stack<int>st;
int main(){
    scanf("%d",&q);
    for(;q;q--){
        scanf("%d",&n);
        int a[n+1],b[n+1];
        for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
        for(int i = 0;i<n;i++){scanf("%d",&b[i]);}
        int i = 0,j = 0;
        for(;i<n;i++){
            st.push(a[i]);
            while (b[j] == st.top()){
                st.pop();
                j++;
                if (st.empty())break;
            }
        }
        if (st.size())printf("No\n");
        else printf("Yes\n");
        while (!st.empty())st.pop();
    }
    return 0;

}

# include <cstdio>

# include <stack>

using namespace std;

int q,n;

stack<int>st;

int main(){

scanf("%d",&q);

for(;q;q--){

scanf("%d",&n);

int a[n+1],b[n+1];

for(int i = 0;i<n;i++){scanf("%d",&a[i]);}

for(int i = 0;i<n;i++){scanf("%d",&b[i]);}

int i = 0,j = 0;

for(;i<n;i++){

st.push(a[i]);

while (b[j] == st.top()){

st.pop();

j++;

if (st.empty())break;

}

if (st.size())printf("No\n");

else printf("Yes\n");

while (!st.empty())st.pop();

}

return 0;

}

🌲

1 FBI 树 AC

简单的二叉树概念题，递归建树，后序遍历

//data
//3
//10001011
//                  f
//             f          f
//         f      b    f      i
//        i  b  b  b  i  b  i  i
# include <cstdio>
# include <cmath>
using namespace std;
struct Node{
    char value;
    Node * lch;
    Node * rch;
};
char getCh(char a[],int length){
    int exist0 = 0,exist1 = 0;
    for(int i = 0;i<length;i++){
        if (a[i] == '1')exist1 ++;
        else if (a[i] == '0')exist0 ++;
        if (exist0 != 0 && exist1 != 0)return 'F';
    }
    if (exist1 == 0 && exist0 != 0)return 'B';
    else if (exist0 == 0 && exist1 != 0)return 'I';
    else return 'F';
}
void cutChar(char ch[],char newch[],int start,int afterlen){
    for(int i = 0;i<afterlen;i++){
        newch[i] = ch[start + i];
    }
    newch[afterlen] = '\0';
//    printf("= %d ",afterlen);
//    for(int i = 0;i<afterlen;i++){
//        printf("%c",newch[i]);
//    }
//    printf("\n");
}
Node *generateTree(char ch[],int n){
    if (n == -1)return NULL;
    int length = pow(2,n);
    Node *root = new Node;
    root -> value = getCh(ch, length);
//    printf("=== ch->%s\n",ch);
//    printf("=== root -> %c \n",root->value);
    char newchl[(length/2)+1],newchr[(length/2)+1];
    cutChar(ch, newchl, 0, (length/2));
    cutChar(ch, newchr, (length/2), (length/2));
    root -> lch = generateTree(newchl, n-1);
    root -> rch = generateTree(newchr, n-1);
    return root;
}
void backOrder(Node *root){
    if (root == NULL)return;
    backOrder(root->lch);
    backOrder(root->rch);
    printf("%c",root->value);
}
int n,length = 1;
int main(){
    scanf("%d",&n);
    length <<= n;
    char ch[length+1];
    scanf("%s",ch);
    Node *root = generateTree(ch,n);
    backOrder(root);
    return 0;
}

//data

//3

//10001011

// f

// f f

// f b f i

// i b b b i b i i

# include <cstdio>

# include <cmath>

using namespace std;

struct Node{

char value;

Node * lch;

Node * rch;

};

char getCh(char a[],int length){

int exist0 = 0,exist1 = 0;

for(int i = 0;i<length;i++){

if (a[i] == '1')exist1 ++;

else if (a[i] == '0')exist0 ++;

if (exist0 != 0 && exist1 != 0)return 'F';

}

if (exist1 == 0 && exist0 != 0)return 'B';

else if (exist0 == 0 && exist1 != 0)return 'I';

else return 'F';

}

void cutChar(char ch[],char newch[],int start,int afterlen){

for(int i = 0;i<afterlen;i++){

newch[i] = ch[start + i];

}

newch[afterlen] = '\0';

// printf("= %d ",afterlen);

// for(int i = 0;i<afterlen;i++){

// printf("%c",newch[i]);

// }

// printf("\n");

}

Node *generateTree(char ch[],int n){

if (n == -1)return NULL;

int length = pow(2,n);

Node *root = new Node;

root -> value = getCh(ch, length);

// printf("=== ch->%s\n",ch);

// printf("=== root -> %c \n",root->value);

char newchl[(length/2)+1],newchr[(length/2)+1];

cutChar(ch, newchl, 0, (length/2));

cutChar(ch, newchr, (length/2), (length/2));

root -> lch = generateTree(newchl, n-1);

root -> rch = generateTree(newchr, n-1);

return root;

}

void backOrder(Node *root){

if (root == NULL)return;

backOrder(root->lch);

backOrder(root->rch);

printf("%c",root->value);

}

int n,length = 1;

int main(){

scanf("%d",&n);

length <<= n;

char ch[length+1];

scanf("%s",ch);

Node *root = generateTree(ch,n);

backOrder(root);

return 0;

}

但是看了大佬题解，发现自己的想法有多处冗余：

建树传参时，无需每次都新建子串。只需要每次规定子串的起始位置，随机访问即可；
判断 FBI 时，if (exist1 == 0 && exist0 != 0) 直接写为 if (exist0) 就够了（本来前半段也是冗余的）
建树和后序遍历可以在同一个递归中完成，即在当前函数里，先遍历建树，再打印 root->value；也可以是在后序遍历的过程中加一些操作。

参考代码如下两种：

#include <iostream>
using namespace std;
char s[1050];
void maketree(int x,int y){ // 此函数是在建树的模板上改的
    if(y>x){
        maketree(x,(x+y)/2);
        maketree((x+y+1)/2,y);
    }
    int B=1,I=1;
    for(int i=0;i<=y-x;i++){
        if(s[x+i]=='1') B=0;
        else if(s[x+i]=='0') I=0;
    }
    if(B) cout<<'B';
    else if(I) cout<<'I';
    else cout<<'F';
}
int main() {
    int n;
    cin>>n>>s;
    maketree(0,(1<<n)-1);
    return 0;
}

#include <iostream>

using namespace std;

char s[1050];

void maketree(int x,int y){ // 此函数是在建树的模板上改的

if(y>x){

maketree(x,(x+y)/2);

maketree((x+y+1)/2,y);

}

int B=1,I=1;

for(int i=0;i<=y-x;i++){

if(s[x+i]=='1') B=0;

else if(s[x+i]=='0') I=0;

}

if(B) cout<<'B';

else if(I) cout<<'I';

else cout<<'F';

}

int main() {

int n;

cin>>n>>s;

maketree(0,(1<<n)-1);

return 0;

}

#include <iostream>
#include <string>
using namespace std;
char FBI(string s)  // 此函数是在后序遍历模板的基础上改的
{
    if (s.length() > 1)
    {
        cout << FBI(s.substr(0, s.length()/2));
        cout << FBI(s.substr(s.length()/2, s.length()/2));
    }
    if (s == string(s.length(), '0')) return 'B';
    if (s == string(s.length(), '1')) return 'I';
    return 'F';
}
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    cout << FBI(s);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

char FBI(string s) // 此函数是在后序遍历模板的基础上改的

{

if (s.length() > 1)

{

cout << FBI(s.substr(0, s.length()/2));

cout << FBI(s.substr(s.length()/2, s.length()/2));

}

if (s == string(s.length(), '0')) return 'B';

if (s == string(s.length(), '1')) return 'I';

return 'F';

}

int main()

{

int n;

cin >> n;

string s;

cin >> s;

cout << FBI(s);

return 0;

}

另外有个小技巧：

在输入长串的时候，写 A+1 就能从 A[1] 开始输入了： scanf("%s", A+1);；此时若想测长度，则需要用 strlen(A+1)

本题还有一个很巧的想法：

直接将 0101 字符串转换为 BIBI 字符串，0->b，1->i
倒着建树：一开始字符串为叶节点，父节点的 FBI 可以根据两个孩子直接决定（妙），这样每一层一个字符串，直接合并，就是完全二叉树的层序遍历
后序遍历，按照下标访问完全二叉树的元素即可
以上想法其实就是线段树的想法 = =

☆ 很多🌲的题目根本不需要事实上把🌲建出来！

2 中序 + 后序求先序 AC

基础送分题

# include <cstdio>
# include <iostream>
# include <string>
using namespace std;
struct Node{
    char v;
    Node* lch;
    Node* rch;
};
Node* buildtree(string inorder,string backorder){
    Node* root = new Node;
    int size = (int)backorder.size() - 1;
    root -> v = backorder[size];
    root -> lch = root -> rch = NULL;
    string::size_type pos = inorder.find(root -> v);
    if (pos != string ::npos){
        if (pos > 0)
            root -> lch = buildtree(inorder.substr(0,pos), backorder.substr(0,pos));
        if (size - pos > 0)
            root -> rch = buildtree(inorder.substr(pos+1,size - pos), backorder.substr(pos,size - pos));
    }
    return root;
}
void forthOrder(Node *root){
    if (root == NULL)return;
    printf("%c",root->v);
    forthOrder(root->lch);
    forthOrder(root->rch);
}
int main(){
    string inorder,backorder;
    cin>>inorder>>backorder;
    Node* root = buildtree(inorder,backorder);
    forthOrder(root);
    return 0;
}

# include <cstdio>

# include <iostream>

# include <string>

using namespace std;

struct Node{

char v;

Node* lch;

Node* rch;

};

Node* buildtree(string inorder,string backorder){

Node* root = new Node;

int size = (int)backorder.size() - 1;

root -> v = backorder[size];

root -> lch = root -> rch = NULL;

string::size_type pos = inorder.find(root -> v);

if (pos != string ::npos){

if (pos > 0)

root -> lch = buildtree(inorder.substr(0,pos), backorder.substr(0,pos));

if (size - pos > 0)

root -> rch = buildtree(inorder.substr(pos+1,size - pos), backorder.substr(pos,size - pos));

}

return root;

}

void forthOrder(Node *root){

if (root == NULL)return;

printf("%c",root->v);

forthOrder(root->lch);

forthOrder(root->rch);

}

int main(){

string inorder,backorder;

cin>>inorder>>backorder;

Node* root = buildtree(inorder,backorder);

forthOrder(root);

return 0;

}

但是为什么我的代码就要 40 行，大佬的代码只要 20 行呢？

先附上大佬的代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
    if (in.size()>0){
        char ch=after[after.size()-1];
        cout<<ch;//找根输出
        int k=in.find(ch);
        beford(in.substr(0,k),after.substr(0,k));
        beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；
    }
}
int main(){
    string inord,aftord;
    cin>>inord;cin>>aftord;//读入
    beford(inord,aftord);cout<<endl;
    return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

void beford(string in,string after){

if (in.size()>0){

char ch=after[after.size()-1];

cout<<ch;//找根输出

int k=in.find(ch);

beford(in.substr(0,k),after.substr(0,k));

beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；

}

int main(){

string inord,aftord;

cin>>inord;cin>>aftord;//读入

beford(inord,aftord);cout<<endl;

return 0;

}

对比发现有如下原因：

只需要一轮递归：在前序遍历的基础上更改即可
根本不需要真正建树，只需要递归输出 root 即可
变量和函数名，在能表示意义的前提下，越短越好

3 新二叉树 AC

送分题，记住二叉树模板，按照规则建树即可

# include <cstdio>
# include <iostream>
# include <cstring>
using namespace std;
struct Node{
    char c;
    Node* l = NULL;
    Node* r = NULL;
};
Node* newNode(char a){
    Node* root = new Node;
    root -> c = a;
    root -> l = root -> r = NULL;
    return root;
}
Node* create(char a,char b,char c){
    Node* root = new Node;
    Node* lc = new Node;
    Node* rc = new Node;
    root -> c = a;
    if (b != '*'){
        lc -> c = b;
        root -> l = lc;
    }
    if (c != '*'){
        rc -> c = c;
        root -> r = rc;
    }
    return root;
}
void insert(Node* now,char a,char b,char c){
    if(now == NULL)return;
    else if(now -> c == a){
        if (b != '*') now -> l = newNode(b);
        if (c != '*') now -> r = newNode(c);
    }else{
        insert(now -> l, a, b, c);
        insert(now -> r, a, b, c);
    }
}
void forthOrder(Node *root){
    if (root == NULL)return;
    printf("%c",root->c);
    forthOrder(root->l);
    forthOrder(root->r);
}
int main(){
    int n;
    scanf("%d\n",&n);
    char a,b,c;
    scanf("%c%c%c\n",&a,&b,&c);
    Node* root = create(a,b,c);
    for(int i = 1;i<n-1;i++){
        scanf("%c%c%c\n",&a,&b,&c);
        insert(root,a,b,c);
    }
    scanf("%c%c%c",&a,&b,&c);
    insert(root,a,b,c);
    forthOrder(root);
    return 0;
}

# include <cstdio>

# include <iostream>

# include <cstring>

using namespace std;

struct Node{

char c;

Node* l = NULL;

Node* r = NULL;

};

Node* newNode(char a){

Node* root = new Node;

root -> c = a;

root -> l = root -> r = NULL;

return root;

}

Node* create(char a,char b,char c){

Node* root = new Node;

Node* lc = new Node;

Node* rc = new Node;

root -> c = a;

if (b != '*'){

lc -> c = b;

root -> l = lc;

}

if (c != '*'){

rc -> c = c;

root -> r = rc;

}

return root;

}

void insert(Node* now,char a,char b,char c){

if(now == NULL)return;

else if(now -> c == a){

if (b != '*') now -> l = newNode(b);

if (c != '*') now -> r = newNode(c);

}else{

insert(now -> l, a, b, c);

insert(now -> r, a, b, c);

}

void forthOrder(Node *root){

if (root == NULL)return;

printf("%c",root->c);

forthOrder(root->l);

forthOrder(root->r);

}

int main(){

int n;

scanf("%d\n",&n);

char a,b,c;

scanf("%c%c%c\n",&a,&b,&c);

Node* root = create(a,b,c);

for(int i = 1;i<n-1;i++){

scanf("%c%c%c\n",&a,&b,&c);

insert(root,a,b,c);

}

scanf("%c%c%c",&a,&b,&c);

insert(root,a,b,c);

forthOrder(root);

return 0;

}

但是实际上，仍然，“很多🌲的题目根本不需要事实上把🌲建出来”：

#include<iostream>
#include<string>
#include<cstring>//不加会CE
using namespace std;
int n;
string s;
int main()
{
    cin>>n;
    cin>>s;
    for(int i=2;i<=n;++i)//由于第一个为原串，所以单独输入
    {
        string ss;//前序遍历序列
        cin>>ss;
        int x=s.find(ss[0]);//找到这个子树的根节点在原串中的位置
        s.erase(x,1);//清除根节点
        s.insert(x,ss);//加入子树
    }
    for(int i=0;i<s.size();++i)
    if(s[i]!='*') cout<<s[i];//不输出空节点
    else continue;
}

#include<iostream>

#include<string>

#include<cstring>//不加会CE

using namespace std;

int n;

string s;

int main()

{

cin>>n;

cin>>s;

for(int i=2;i<=n;++i)//由于第一个为原串，所以单独输入

{

string ss;//前序遍历序列

cin>>ss;

int x=s.find(ss[0]);//找到这个子树的根节点在原串中的位置

s.erase(x,1);//清除根节点

s.insert(x,ss);//加入子树

}

for(int i=0;i<s.size();++i)

if(s[i]!='*') cout<<s[i];//不输出空节点

else continue;

}

或者树，直接用 n*3 的二维数组来存储：

#include<bits/stdc++.h>
using namespace std;
int n;
char a[30][3];
void f(char x)
{
    if(x!='*')
    {
        cout<<x;
        for(int i=1;i<=n;i++)
            if(a[i][0]==x)
            {
                f(a[i][1]);
                f(a[i][2]);
            }
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    f(a[1][0]);
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;

char a[30][3];

void f(char x)

{

if(x!='*')

{

cout<<x;

for(int i=1;i<=n;i++)

if(a[i][0]==x)

{

f(a[i][1]);

f(a[i][2]);

}

return;

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

cin>>a[i][0]>>a[i][1]>>a[i][2];

f(a[1][0]);

return 0;

}

而这个方法可以有改进：

先补充一下 map：

map第一个好处是作为一个数组，可以开很大！比如：map<int,int>x;，可以把x数组当成普通数组用，不过要注意一点：定义了x数组后，就不能使用c++的数组函数，比如 memset
map第二个好处下标不一定是一个整数，可以甚至可以是一个字符串！map<下标类型,数值类型>; 比如：map<string,char>a; string st="123"; a[st]='1';
map不仅可以开一维数组，还可以开二维数组。比如：map<int,map<int,int>;注意这里是一定要有空格的，否则会编译错误

于是，此题可以用 map + 并查集解决（就不用了 O(n) 寻找了）：

#include <bits/stdc++.h>
using namespace std;
map<char,char>x;//用map来记录一个节点的左儿子
map<char,char>y;//用map来记录一个节点的右儿子
char a[35];//节点
void find(char ch){//并查集
    cout<<ch;
    if(x[ch]!='*')find(x[ch]);
    if(y[ch]!='*')find(y[ch]);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        char left,right;
        cin>>a[i]>>left>>right;
        x[a[i]]=left;
        y[a[i]]=right;
    }find(a[1]);//开始遍历整棵树
    return 0;//结束程序
}

#include <bits/stdc++.h>

using namespace std;

map<char,char>x;//用map来记录一个节点的左儿子

map<char,char>y;//用map来记录一个节点的右儿子

char a[35];//节点

void find(char ch){//并查集

cout<<ch;

if(x[ch]!='*')find(x[ch]);

if(y[ch]!='*')find(y[ch]);

}

int main(){

int n;

cin>>n;

for(int i=1;i<=n;i++){

char left,right;

cin>>a[i]>>left>>right;

x[a[i]]=left;

y[a[i]]=right;

}find(a[1]);//开始遍历整棵树

return 0;//结束程序

}

4 对称二叉树 52

思路有错，懒得继续改了

# include <cstdio>
# include <string>
# define maxn 1000001
using namespace std;
int n;
int tree[maxn][3],childnum[maxn];
string tempa,temp2;

bool c(int i){
    printf("%d",i);
    int l = tree[i][1],r = tree[i][2];
    while(1){
        if (tree[l][1] != -1 && tree[r][2] != -1){
            l = tree[i][1];
            r = tree[i][2];
        }else if (tree[l][1] == -1 && tree[r][2] == -1){
            return 1;
        }else return 0;
    }
}

int check(int i){  // 如果是平衡，返回孩子个数，如果不平衡，返回-1
    if (tree[i][1] != -1 && tree[i][2] != -1){
    // 两边均有孩子
        if (tree[tree[i][1]][0] == tree[tree[i][2]][0]){
        // 两边均有孩子，且左右孩子相等
             int a,b;
             a = check(tree[i][1]);
             b = check(tree[i][2]);
             if (c(i) && a == b && b >= 0){
             // 两边均有孩子，且左右子树相等，且左右孩子均为对称
                 childnum[i] = a * 2 + 2;
                 return a * 2 + 2;
             }else {
             // 两边均有孩子，且左右子树相等，但左右孩子不均为对称
                 childnum[i] = -1;
                 return -1;
             }
        }
        else {
            // 两边均有孩子，但左右孩子不相等
            childnum[i] = -1;
            return -1;
        }
    }
    else if (tree[i][1] == -1 && tree[i][2] == -1){
        // 叶节点
        childnum[i] = 0;
        return 0;
    }
    else {
        // 仅一边有孩子
        childnum[i] = -1;
        return -1;
    }
}

int main(){
    scanf("%d",&n);
    if (n == 0){
        printf("0");
        return 0;
    }
    for(int i = 1;i<=n;i++){
        scanf("%d",&tree[i][0]);
        childnum[i] = -2;
    }
    for(int i = 1;i<=n;i++){
        scanf("%d %d",&tree[i][1],&tree[i][2]);
    }
    for(int i = 1;i<=n;i++){ // 检查每个节点
        check(i);
    }
    int max = 0;
    for(int i = 1;i<=n;i++){
//        printf("%d,",childnum[i]);
        max = max>childnum[i]?max:childnum[i];
    }
    printf("%d",max+1);
    return 0;
}

# include <cstdio>

# include <string>

# define maxn 1000001

using namespace std;

int n;

int tree[maxn][3],childnum[maxn];

string tempa,temp2;

bool c(int i){

printf("%d",i);

int l = tree[i][1],r = tree[i][2];

while(1){

if (tree[l][1] != -1 && tree[r][2] != -1){

l = tree[i][1];

r = tree[i][2];

}else if (tree[l][1] == -1 && tree[r][2] == -1){

return 1;

}else return 0;

}

int check(int i){ // 如果是平衡，返回孩子个数，如果不平衡，返回-1

if (tree[i][1] != -1 && tree[i][2] != -1){

// 两边均有孩子

if (tree[tree[i][1]][0] == tree[tree[i][2]][0]){

// 两边均有孩子，且左右孩子相等

int a,b;

a = check(tree[i][1]);

b = check(tree[i][2]);

if (c(i) && a == b && b >= 0){

// 两边均有孩子，且左右子树相等，且左右孩子均为对称

childnum[i] = a * 2 + 2;

return a * 2 + 2;

}else {

// 两边均有孩子，且左右子树相等，但左右孩子不均为对称

childnum[i] = -1;

return -1;

}

else {

// 两边均有孩子，但左右孩子不相等

childnum[i] = -1;

return -1;

}

else if (tree[i][1] == -1 && tree[i][2] == -1){

// 叶节点

childnum[i] = 0;

return 0;

}

else {

// 仅一边有孩子

childnum[i] = -1;

return -1;

}

int main(){

scanf("%d",&n);

if (n == 0){

printf("0");

return 0;

}

for(int i = 1;i<=n;i++){

scanf("%d",&tree[i][0]);

childnum[i] = -2;

}

for(int i = 1;i<=n;i++){

scanf("%d %d",&tree[i][1],&tree[i][2]);

}

for(int i = 1;i<=n;i++){ // 检查每个节点

check(i);

}

int max = 0;

for(int i = 1;i<=n;i++){

// printf("%d,",childnum[i]);

max = max>childnum[i]?max:childnum[i];

}

printf("%d",max+1);

return 0;

}

4 先序+中序求后续 AC

其实也是不用建树的

# include <cstdio>
# include <cstring>
using namespace std;
char before[30],inorder[30];
struct node{
    char c;
    node* l;
    node* r;
}*root;
node* get(char ll[],char in[]){
    node *root;
    root = new node;
    root -> c = ll[0];
    root -> l = NULL;
    root -> r = NULL;
    int i = 0;
    for(;i<strlen(in);i++){
        if (in[i] == ll[0])break;
    }
    char a[30] = {},b[30] = {},c[30] = {},d[30] = {};
    for(int j = 1;j<i+1;j++)a[j-1] = ll[j];
    for(int j = i+1;j<strlen(ll);j++)b[j-i-1] = ll[j];
    for(int j = 0;j<i;j++)c[j] = in[j];
    for(int j = i+1;j<strlen(in);j++)d[j-i-1] = in[j];
    if(strlen(a) > 0)root -> l = get(a,c);
    if(strlen(b) > 0)root -> r = get(b,d);
    return root;
}
void postorder(node *root){
    if (root -> l != NULL)postorder(root->l);
    if (root -> r != NULL)postorder(root->r);
    printf("%c",root->c);
}
int main(){
    scanf("%s %s",inorder,before);
    root = get(before,inorder);
    postorder(root);
    printf("\n");
    return 0;
}

# include <cstdio>

# include <cstring>

using namespace std;

char before[30],inorder[30];

struct node{

char c;

node* l;

node* r;

}*root;

node* get(char ll[],char in[]){

node *root;

root = new node;

root -> c = ll[0];

root -> l = NULL;

root -> r = NULL;

int i = 0;

for(;i<strlen(in);i++){

if (in[i] == ll[0])break;

}

char a[30] = {},b[30] = {},c[30] = {},d[30] = {};

for(int j = 1;j<i+1;j++)a[j-1] = ll[j];

for(int j = i+1;j<strlen(ll);j++)b[j-i-1] = ll[j];

for(int j = 0;j<i;j++)c[j] = in[j];

for(int j = i+1;j<strlen(in);j++)d[j-i-1] = in[j];

if(strlen(a) > 0)root -> l = get(a,c);

if(strlen(b) > 0)root -> r = get(b,d);

return root;

}

void postorder(node *root){

if (root -> l != NULL)postorder(root->l);

if (root -> r != NULL)postorder(root->r);

printf("%c",root->c);

}

int main(){

scanf("%s %s",inorder,before);

root = get(before,inorder);

postorder(root);

printf("\n");

return 0;

}

背包问题

背包九讲

模板

01 背包：n 件物品，背包容量 V，第 i 件物品费用 w[i]，价值 v[i]for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]); 初始化：
- 恰好装满背包：f[0] = 0;f[1] = ... = f[V] = -∞;
- 无需恰好装满：f[0] = f[1] = ... = f[V] = 0;
完全背包：n 种物品，每种无限个，背包容量 V，第 i 件物品费用 w[i]，价值 v[i]
- 转换为 01 背包：第 i 种物品拆成费用为 w[i]∗2^k、价值为 v[i]∗2^k 的若干件物品，即每种物品拆成 log(V/w[i]) 件物品
- O(VN) 的算法：for (int i = 1; i <= n; i++) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);
多重背包问题：有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 p[i] 件可用，每件费用是 w[i]，价值是 v[i]转化为 01 背包问题for (int i = 1; i <= n; i++) { int num = min(p[i], V / w[i]); for (int k = 1; num > 0; k <<= 1) { if (k > num) k = num; num -= k; for (int j = V; j >= w[i] * k; j--) f[j] = max(f[j], f[j - w[i] * k] + v[i] * k); } }
混合背包问题：综合起来p[i]:每个物品的件数，0代表无穷个 for (int i = 1; i <= n; i++) if (p[i] == 0) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]); else for (int k = 1; k <= p[i]; k++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
二维背包问题：for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) for (int k = T; k >= g[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
分组背包问题：有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。for (所有的组k) for (int j = V; j >= 0; j--) for (所有属于组k的i) f[j] = max{f[j], f[j - w[i]] + v[i]}

1 01背包 AC

# include <cstdio>
# include <algorithm>
using namespace std;

const int maxn = 30001;
int main(){
    int n,m;
    int a[maxn],b[maxn] = {},f[maxn] = {};
    scanf("%d %d",&n,&m);
    for(int i = 0;i<m;i++){
        scanf("%d %d",&a[i],&b[i]);
        b[i] *= a[i];
    }
    for(int i = 0;i<m;i++){
        for(int j = n;j>=a[i];j--){
            f[j] = max(f[j],f[j-a[i]] + b[i]);
        }
    }
    printf("%d",f[n]);
    return 0;
}

# include <cstdio>

# include <algorithm>

using namespace std;

const int maxn = 30001;

int main(){

int n,m;

int a[maxn],b[maxn] = {},f[maxn] = {};

scanf("%d %d",&n,&m);

for(int i = 0;i<m;i++){

scanf("%d %d",&a[i],&b[i]);

b[i] *= a[i];

}

for(int i = 0;i<m;i++){

for(int j = n;j>=a[i];j--){

f[j] = max(f[j],f[j-a[i]] + b[i]);

}

printf("%d",f[n]);

return 0;

}

2 小A点菜 AC

见题解： https://www.luogu.com.cn/blog/user23325/solution-p1164

# include <cstdio>
int count = 0,n,m,a[10001] = {},f[101][10001]={0};
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=m;++j)
        {
            // 为了第一个考虑，故 i 从 1 开始
            if(j==a[i])f[i][j]=f[i-1][j]+1;
            if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
            if(j<a[i]) f[i][j]=f[i-1][j];
        }
    printf("%d",f[n][m]);
    return 0;
}

# include <cstdio>

int count = 0,n,m,a[10001] = {},f[101][10001]={0};

int main(){

scanf("%d%d",&n,&m);

for(int i = 1;i<=n;i++) scanf("%d",&a[i]);

for(int i = 1;i<=n;++i)

for(int j = 1;j<=m;++j)

{

// 为了第一个考虑，故 i 从 1 开始

if(j==a[i])f[i][j]=f[i-1][j]+1;

if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];

if(j<a[i]) f[i][j]=f[i-1][j];

}

printf("%d",f[n][m]);

return 0;

}

贪心

1 合并果子 AC

用优先级队列，当下最小的两个

# include <cstdio>
# include <queue>
using namespace std;

int main(){
    int n,temp,res = 0;
    scanf("%d",&n);
    priority_queue<int, vector<int>, greater<int> >pq;
    for(int i = 0;i<n;i++) {
        scanf("%d",&temp);
        pq.push(temp);
    }
    while(pq.size() > 1){
        int a = pq.top();pq.pop();
        int b = pq.top();pq.pop();
        int c = a + b;
        res += c;
        pq.push(c);
    }
    printf("%d",res);
    return 0;
}

# include <cstdio>

# include <queue>

using namespace std;

int main(){

int n,temp,res = 0;

scanf("%d",&n);

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

for(int i = 0;i<n;i++) {

scanf("%d",&temp);

pq.push(temp);

}

while(pq.size() > 1){

int a = pq.top();pq.pop();

int b = pq.top();pq.pop();

int c = a + b;

res += c;

pq.push(c);

}

printf("%d",res);

return 0;

}

2 数列分段Section I AC

水

# include <cstdio>
int main(){
    int n,m,count = 0,now = 0,temp;
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%d",&temp);
        if(now + temp > m){
            count++;
            now = temp;
        }else{
            now += temp;
        }
    }
    printf("%d",count+1);
    return 0;
}

# include <cstdio>

int main(){

int n,m,count = 0,now = 0,temp;

scanf("%d %d",&n,&m);

for(int i = 0;i<n;i++){

scanf("%d",&temp);

if(now + temp > m){

count++;

now = temp;

}else{

now += temp;

}

printf("%d",count+1);

return 0;

}

3 混和牛奶 AC

# include <cstdio>
# include <queue>
using namespace std;

struct milk{
    int volume,price;
    friend bool operator < (milk m1,milk m2){
        return m1.price > m2.price;
    }
    milk(int _p,int _a):volume(_a),price(_p){};
};
int main(){
    int n,m,p,a,res = 0;
    priority_queue<milk>pq;
    scanf("%d%d",&n,&m);
    for(int i = 0;i<m;i++){
        scanf("%d%d",&p,&a);
        pq.push(milk(p,a));
    }
    while(n > 0){
        milk now = pq.top();
        if (n > now.volume){
            res += (now.volume * now.price);
            pq.pop();
            n -= now.volume;
        }else{
            res += (n * now.price);
            break;
        }
    }
    printf("%d",res);
    return 0;
}

# include <cstdio>

# include <queue>

using namespace std;

struct milk{

int volume,price;

friend bool operator < (milk m1,milk m2){

return m1.price > m2.price;

}

milk(int _p,int _a):volume(_a),price(_p){};

};

int main(){

int n,m,p,a,res = 0;

priority_queue<milk>pq;

scanf("%d%d",&n,&m);

for(int i = 0;i<m;i++){

scanf("%d%d",&p,&a);

pq.push(milk(p,a));

}

while(n > 0){

milk now = pq.top();

if (n > now.volume){

res += (now.volume * now.price);

pq.pop();

n -= now.volume;

}else{

res += (n * now.price);

break;

}

printf("%d",res);

return 0;

}

4 排队接水 AC

总时间要用 long long，相等时按序号排序

# include <cstdio>
# include <queue>
using namespace std;

struct s{
    int n,i;
    s(int _n,int _i):n(_n),i(_i){};
    friend bool operator < (s s1,s s2){
        if (s1.n != s2.n) return s1.n > s2.n; // 平
        else return s1.i > s2.i;
    }
};

int main(){
    int n,temp;
    long long res = 0; // int 不行
    priority_queue<s>pq;
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d",&temp);
        pq.push(s(temp,i+1));
    }
    for(int j = 0;j<n;j++){
        s now = pq.top();
        printf("%d",now.i);
        res += (n-j-1) * now.n;
        pq.pop();
        if (j < n-1) printf(" ");
        else printf("\n");
    }
    printf("%.02lf\n",(double)res/n); // float 不行
    return 0;
}

# include <cstdio>

# include <queue>

using namespace std;

struct s{

int n,i;

s(int _n,int _i):n(_n),i(_i){};

friend bool operator < (s s1,s s2){

if (s1.n != s2.n) return s1.n > s2.n; // 平

else return s1.i > s2.i;

}

};

int main(){

int n,temp;

long long res = 0; // int 不行

priority_queue<s>pq;

scanf("%d",&n);

for(int i = 0;i<n;i++){

scanf("%d",&temp);

pq.push(s(temp,i+1));

}

for(int j = 0;j<n;j++){

s now = pq.top();

printf("%d",now.i);

res += (n-j-1) * now.n;

pq.pop();

if (j < n-1) printf(" ");

else printf("\n");

}

printf("%.02lf\n",(double)res/n); // float 不行

return 0;

}

还有一个好方法，不需优先队列或结构体排序：

因为 n <= 1000，所以给每个 ti 都 * 1001，在加上当前序号，可以保证排序的时候序号不干扰排序，又可以方便输出序号（只需 mod 1001 输出序号，／1001 输出时间）

5 纪念品分组 AC

# include <cstdio>
# include <algorithm>
using namespace std;
bool cmp(int a,int b){return a>b;}
int main(){
    int w,n,a[50001] = {};
    scanf("%d%d",&w,&n);
    for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
    sort(a, a+n, cmp);
    for(int i = 0;i<n-1;i++){
//        printf("%d ",a[i]);
        if (a[n-1] + a[i] <= w)n--;
    }
    printf("%d",n);
    return 0;
}

# include <cstdio>

# include <algorithm>

using namespace std;

bool cmp(int a,int b){return a>b;}

int main(){

int w,n,a[50001] = {};

scanf("%d%d",&w,&n);

for(int i = 0;i<n;i++){scanf("%d",&a[i]);}

sort(a, a+n, cmp);

for(int i = 0;i<n-1;i++){

// printf("%d ",a[i]);

if (a[n-1] + a[i] <= w)n--;

}

printf("%d",n);

return 0;

}

6 线段覆盖 AC

每个线段按结束点从小到大排序，按照这个顺序贪心放置即可

# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;

struct test{
    int begin,end;
    test(int _begin,int _end):begin(_begin),end(_end){};
};

bool cmp(test a,test b){
    return a.end < b.end;
}

int main(){
    int n;
    scanf("%d",&n);
    vector<test>lst;
    for(int i = 0;i<n;i++){
        int b,e;
        scanf("%d %d",&b,&e);
        lst.push_back(test(b,e));
    }
    int count = 0,nowend = 0;
    sort(lst.begin(),lst.end(),cmp);
    for(int i = 0;i<n;i++){
        if (lst[i].begin >= nowend){
            nowend = lst[i].end;
            count ++;
        }
    }
    printf("%d",count);
    return 0;
}

# include <cstdio>

# include <algorithm>

# include <vector>

using namespace std;

struct test{

int begin,end;

test(int _begin,int _end):begin(_begin),end(_end){};

};

bool cmp(test a,test b){

return a.end < b.end;

}

int main(){

int n;

scanf("%d",&n);

vector<test>lst;

for(int i = 0;i<n;i++){

int b,e;

scanf("%d %d",&b,&e);

lst.push_back(test(b,e));

}

int count = 0,nowend = 0;

sort(lst.begin(),lst.end(),cmp);

for(int i = 0;i<n;i++){

if (lst[i].begin >= nowend){

nowend = lst[i].end;

count ++;

}

printf("%d",count);

return 0;

}

7 移动纸牌 AC

第一堆只能从第二堆索取或者给予，满足第一堆后，就可以删去这一堆，以此类推，删去所有堆

# include <cstdio>

int main(){
    int n,sum = 0;
    int a[101] = {};
    scanf("%d",&n);
    for (int i = 0;i<n;i++){
        scanf("%d",&a[i]);
        sum += a[i];
    }
    int avg = sum/n,count = 0;
    for (int i = 0;i<n;i++)a[i] -= avg;
    for (int i = 0;i<n;i++){
        if (a[i] != 0){
            a[i+1] += a[i];
            count ++;
        }
    }
    printf("%d",count);
    return 0;
}

# include <cstdio>

int main(){

int n,sum = 0;

int a[101] = {};

scanf("%d",&n);

for (int i = 0;i<n;i++){

scanf("%d",&a[i]);

sum += a[i];

}

int avg = sum/n,count = 0;

for (int i = 0;i<n;i++)a[i] -= avg;

for (int i = 0;i<n;i++){

if (a[i] != 0){

a[i+1] += a[i];

count ++;

}

printf("%d",count);

return 0;

}

8 高精度 AC

高精度直接用 python！同时注意 // 的使用

n = int(input())
king = input().split()
a = []
for i in range(n):
    k = input().split()
    a.append([int(k[0]),int(k[1])])
# print(a,king)
a.sort(key = lambda x:x[0]*x[1])
maxsum = 0;product = int(king[0])
for i in a:
    now = product//i[1]
    # // 用来求商，要比除法再取整快得多！
    if now>maxsum:
        maxsum = now
    product = product * i[0]
print(int(maxsum))

n = int(input())

king = input().split()

a = []

for i in range(n):

k = input().split()

a.append([int(k[0]),int(k[1])])

# print(a,king)

a.sort(key = lambda x:x[0]*x[1])

maxsum = 0;product = int(king[0])

for i in a:

now = product//i[1]

# // 用来求商，要比除法再取整快得多！

if now>maxsum:

maxsum = now

product = product * i[0]

print(int(maxsum))

9 水题 AC

# include <cstdio>
int n,en = 0;
int a[1002][1002] = {};
int sumx[1002] = {},sumy[1002] = {};
struct empty{
    int x,y;
    empty(){};
    empty(int _x,int _y):x(_x),y(_y){}
}e[10002];
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            scanf("%d",&a[i][j]);
            if (!a[i][j])e[en++] = empty(i,j);
            else{
                sumx[i] += a[i][j];
                sumy[j] += a[i][j];
            }
        }
    }
    int max = 0;
    if (en == 0)printf("Bad Game!");
    else{
        for(int i = 0;i<en;i++){
            int t = sumx[e[i].x] + sumy[e[i].y];
            if (t > max)max = t;
        }
        printf("%d",max);
    }
    return 0;
}

# include <cstdio>

int n,en = 0;

int a[1002][1002] = {};

int sumx[1002] = {},sumy[1002] = {};

struct empty{

int x,y;

empty(){};

empty(int _x,int _y):x(_x),y(_y){}

}e[10002];

int main(){

scanf("%d",&n);

for(int i = 0;i<n;i++){

for(int j = 0;j<n;j++){

scanf("%d",&a[i][j]);

if (!a[i][j])e[en++] = empty(i,j);

else{

sumx[i] += a[i][j];

sumy[j] += a[i][j];

}

int max = 0;

if (en == 0)printf("Bad Game!");

else{

for(int i = 0;i<en;i++){

int t = sumx[e[i].x] + sumy[e[i].y];

if (t > max)max = t;

}

printf("%d",max);

}

return 0;

}

10 水题 AC

# include<cstdio>
long long n,x,a[100005] = {};
int main(){
    scanf("%lld %lld",&n,&x);
    for(int i = 1;i<=n;i++)scanf("%lld",&a[i]);
    long long res = 0;
    for(int i = 1;i<=n;i++){
        if (a[i] + a[i-1] > x){
            long long p = a[i] + a[i-1] - x;
            a[i] -= p;
            res += p;
        }
    }
    printf("%lld",res);
    return 0;
}

# include<cstdio>

long long n,x,a[100005] = {};

int main(){

scanf("%lld %lld",&n,&x);

for(int i = 1;i<=n;i++)scanf("%lld",&a[i]);

long long res = 0;

for(int i = 1;i<=n;i++){

if (a[i] + a[i-1] > x){

long long p = a[i] + a[i-1] - x;

a[i] -= p;

res += p;

}

printf("%lld",res);

return 0;

}

11 铺设道路 AC

# include <cstdio>
int n,a[100005] = {};
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int finish = 1,count = 0;
    while (finish){
        int start = 0,minn = 0,sgn = 0;
        for(int i = 1;i<=n+1;i++){
            if (a[i]){
                sgn ++;
                if(a[i-1]){
                    minn = minn<a[i]?minn:a[i];
                }else{
                    start = i;
                    minn = a[i];
                }
            }else{
                if(a[i-1]){
                    count+= minn;
                    for (int p = start;p<i;p++)a[p]-=minn;
                }
            }
        }
//        for (int i = 1;i<=n;i++)printf("%d ",a[i]);
//        printf("%d\n",count);
        if (sgn == 0)break;
    }
    printf("%d",count);
}

# include <cstdio>

int n,a[100005] = {};

int main(){

scanf("%d",&n);

for(int i = 1;i<=n;i++){

scanf("%d",&a[i]);

}

int finish = 1,count = 0;

while (finish){

int start = 0,minn = 0,sgn = 0;

for(int i = 1;i<=n+1;i++){

if (a[i]){

sgn ++;

if(a[i-1]){

minn = minn<a[i]?minn:a[i];

}else{

start = i;

minn = a[i];

}

}else{

if(a[i-1]){

count+= minn;

for (int p = start;p<i;p++)a[p]-=minn;

}

// for (int i = 1;i<=n;i++)printf("%d ",a[i]);

// printf("%d\n",count);

if (sgn == 0)break;

}

printf("%d",count);

}

并查集

1 联通

并查集 + Kruskal：按照时间从小到大排序，每修一条路，如果这条路的两端本身 father 不同（即不连通），则联通的区域数 -1，当联通区域数 == 1 时，则成功

# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
int n,m,f,t,l,father[1002] = {};
struct road{
    int from,to,length;
    road(int _f,int _t,int _l):from(_f),to(_t),length(_l){}
};
bool cmp(road a,road b){
    return a.length < b.length;
}
int findfather(int n){
    while(n!=father[n]){n = father[n];}
    return n;
}
void printfather(){
    for(int i = 0;i<5;i++)printf(":%d",father[i]);
    printf("\n");
}
int main(){
    scanf("%d %d",&n,&m);
    vector<road>a;
    for(int i = 0;i<m;i++){
        scanf("%d %d %d",&f,&t,&l);
        a.push_back(road(f,t,l));
    }
    sort(a.begin(),a.end(),cmp);
    for(int i = 0;i<n+1;i++) father[i] = i;
    for(int i = 0;i<m;i++){
        int fa = findfather(a[i].to),fb = findfather(a[i].from);
        if (fa!=fb){
            father[fa] = fb;
            n --;
            if (n == 1){
                printf("%d",a[i].length);
                return 0;
            }
        }
//        printfather();printf("%d",n);
    }
    printf("-1");
    return 0;
}

# include <cstdio>

# include <algorithm>

# include <vector>

using namespace std;

int n,m,f,t,l,father[1002] = {};

struct road{

int from,to,length;

road(int _f,int _t,int _l):from(_f),to(_t),length(_l){}

};

bool cmp(road a,road b){

return a.length < b.length;

}

int findfather(int n){

while(n!=father[n]){n = father[n];}

return n;

}

void printfather(){

for(int i = 0;i<5;i++)printf(":%d",father[i]);

printf("\n");

}

int main(){

scanf("%d %d",&n,&m);

vector<road>a;

for(int i = 0;i<m;i++){

scanf("%d %d %d",&f,&t,&l);

a.push_back(road(f,t,l));

}

sort(a.begin(),a.end(),cmp);

for(int i = 0;i<n+1;i++) father[i] = i;

for(int i = 0;i<m;i++){

int fa = findfather(a[i].to),fb = findfather(a[i].from);

if (fa!=fb){

father[fa] = fb;

n --;

if (n == 1){

printf("%d",a[i].length);

return 0;

}

// printfather();printf("%d",n);

}

printf("-1");

return 0;

}

2 种类并查集 100

种类并查集，两种，开二倍数组

初始化：

    fa[i] = i;
    fa[i + n] = i + n;

fa[i] = i;

fa[i + n] = i + n;

关键步骤：

    s[s[x+n]]=s[y];
    s[s[x]]=s[y+n];

s[s[x+n]]=s[y];

s[s[x]]=s[y+n];

同时，此题的路径压缩也是非常之妙

// 2020-02-23 17:05:59
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;

int n,m,fa[40005] = {};
struct edge{
    int a,b,value;
    edge(int _a,int _b,int _v):a(_a),b(_b),value(_v){}
};

bool cmp(edge a,edge b){
    return a.value>b.value;
}

int findfa(int n){
    if (fa[n] == n) return n;
    return fa[n] = findfa(fa[n]);   // 路径压缩，妙！
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++){
        fa[i] = i;
        fa[i + n] = i + n;      // 种类并查集，两种，开两倍容量数组？
    }
    int tempa,tempb,tempv;
    vector<edge>lst;
    for(int i = 0;i<m;i++){
        scanf("%d %d %d",&tempa,&tempb,&tempv);
        lst.push_back(edge(tempa,tempb,tempv));
    }
    sort(lst.begin(),lst.end(),cmp);
    for(int i = 0;i<m;i++){
        if (findfa(lst[i].a) == findfa(lst[i].b) || findfa(lst[i].a + n) == findfa(lst[i].b + n)){
            printf("%d",lst[i].value);
            return 0;
        }
        // 以下两步为种类并查集的关键步骤
        fa[fa[lst[i].a + n]] = fa[lst[i].b];
        fa[fa[lst[i].a]] = fa[lst[i].b + n];
    }
    printf("0");
    return 0;
}

// 2020-02-23 17:05:59

# include <cstdio>

# include <vector>

# include <algorithm>

using namespace std;

int n,m,fa[40005] = {};

struct edge{

int a,b,value;

edge(int _a,int _b,int _v):a(_a),b(_b),value(_v){}

};

bool cmp(edge a,edge b){

return a.value>b.value;

}

int findfa(int n){

if (fa[n] == n) return n;

return fa[n] = findfa(fa[n]); // 路径压缩，妙！

}

int main(){

scanf("%d %d",&n,&m);

for(int i = 0;i<n;i++){

fa[i] = i;

fa[i + n] = i + n; // 种类并查集，两种，开两倍容量数组？

}

int tempa,tempb,tempv;

vector<edge>lst;

for(int i = 0;i<m;i++){

scanf("%d %d %d",&tempa,&tempb,&tempv);

lst.push_back(edge(tempa,tempb,tempv));

}

sort(lst.begin(),lst.end(),cmp);

for(int i = 0;i<m;i++){

if (findfa(lst[i].a) == findfa(lst[i].b) || findfa(lst[i].a + n) == findfa(lst[i].b + n)){

printf("%d",lst[i].value);

return 0;

}

// 以下两步为种类并查集的关键步骤

fa[fa[lst[i].a + n]] = fa[lst[i].b];

fa[fa[lst[i].a]] = fa[lst[i].b + n];

}

printf("0");

return 0;

}

3 种类并查集 AC

同上，这里的写法终于让我明白了：

由于有压缩路径，所以 fa[n] 和 findfa(n) 是等价的
谁是谁的爸爸都可以，因此本题解这样写也是可以滴，以后就以这个为准：

    if (不同类){
        fa[findfa(ta + n)] = findfa(tb);
        fa[findfa(tb + n)] = findfa(ta);
    }else if (同类){
        fa[findfa(ta)] = findfa(tb);
    }

if (不同类){

fa[findfa(ta + n)] = findfa(tb);

fa[findfa(tb + n)] = findfa(ta);

}else if (同类){

fa[findfa(ta)] = findfa(tb);

}

// 2020-02-23 21:31:50
# include <cstdio>
# include <iostream>

//# include <vector>
//# include <algorithm>
using namespace std;

int n,m,fa[2502] = {};

int findfa(int n){
//    两种不同的路径压缩
//    1
//    if(fa[n] == n)return n;
//    return fa[n] = findfa(fa[n]);
//    2
    if (fa[n] != n) fa[n] = findfa(fa[n]);
    return fa[n];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++){
        fa[i] = i;fa[i+n] = i+n;
    }
    for(int i = 0;i<m;i++){
        char c;
        int ta,tb;
        cin>>c>>ta>>tb;
//        scanf("%*c%c %d %d",&c,&ta,&tb); //%*c是上一行的换行，为什么这个就不行？？#TODO
        if (c == 'E'){
            fa[findfa(ta + n)] = findfa(tb);
            fa[findfa(tb + n)] = findfa(ta);
        }else if (c == 'F'){
            fa[findfa(ta)] = findfa(tb);
        }
    }
    int s=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i) s++; //找有多少祖先，就是有多少团伙
        }
    printf("%d",s);
    return 0;
}

// 2020-02-23 21:31:50

# include <cstdio>

# include <iostream>

//# include <vector>

//# include <algorithm>

using namespace std;

int n,m,fa[2502] = {};

int findfa(int n){

// 两种不同的路径压缩

// 1

// if(fa[n] == n)return n;

// return fa[n] = findfa(fa[n]);

// 2

if (fa[n] != n) fa[n] = findfa(fa[n]);

return fa[n];

}

int main(){

scanf("%d%d",&n,&m);

for(int i = 1;i<=n;i++){

fa[i] = i;fa[i+n] = i+n;

}

for(int i = 0;i<m;i++){

char c;

int ta,tb;

cin>>c>>ta>>tb;

// scanf("%*c%c %d %d",&c,&ta,&tb); //%*c是上一行的换行，为什么这个就不行？？#TODO

if (c == 'E'){

fa[findfa(ta + n)] = findfa(tb);

fa[findfa(tb + n)] = findfa(ta);

}else if (c == 'F'){

fa[findfa(ta)] = findfa(tb);

}

int s=0;

for(int i=1;i<=n;i++){

if(fa[i]==i) s++; //找有多少祖先，就是有多少团伙

}

printf("%d",s);

return 0;

}

4 种类并查集 AC

三类，就开三倍的数组并查集：

捕食的关系这样维护：

若是同类，则 `x+n*k & y+n*k` 共父

若 x 吃 y，则 `x + n*k & y + n*(k-1)` 共父

若是同类，则 `x+n*k & y+n*k` 共父

若 x 吃 y，则 `x + n*k & y + n*(k-1)` 共父

前面如果用了 find()，那么后面可以直接用 f[]

# include <cstdio>

int n,k,f[150005];

int find(int x){
    if (x == f[x])return x;
    return f[x] = find(f[x]);
}

int main(){
    scanf("%d %d",&n,&k);
    int x,y,z,count = 0;
    for(int ii = 1;ii<=n*3;ii++)f[ii] = ii;
    for(;k;k--){    //循环的简单写法
        scanf("%d %d %d",&z,&x,&y);
//        printf("%d\%d\%d-",z,x,y);
        if (x > n || y > n){count ++;continue;}
        else{
            if (z == 1){
                if (find(x+n) == find(y) || find(x) == find(y+n)){
//                    if (x != y){
                        count ++;continue;
//                    }
                }else{
                    f[find(x)] = find(y);
                    f[find(x+n)] = find(y+n);
                    f[find(x+n+n)] = find(y+n+n);
                }
            }else {
//              if (x == y){count ++;continue;}// 多余的
                if (find(x) == find(y) || find(x) == find(y+n)){
                    count ++;continue;
                }else{
                    f[find(x)] = find(y+n+n);
                    f[find(x+n)] = find(y);
                    f[find(x+n+n)] = find(y+n);
                }
            }
        }
    }
    printf("%d\n",count);
    return 0;
}