研究生机试备考练习(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 <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<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]);
}

大佬的高级方法:

  1. 高级递归 O( n ) : ( a_n = 2 * a_{n-1} – a_{i-k-1} )
  2. 矩阵乘法 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] )$ ,此处就可以使用快速幂的方法

  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 <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<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;
}

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;
}

然而大佬就厉害了:用一维数组做,妙哉!

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

状态转移方程:a[j] = max{a[j],a[j+1]}+pa[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

代码(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;
}

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

  • 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;
}

递推 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;
}

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;
}

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;
}

大佬的 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]);
}

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])

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;
}

线性数据结构

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;
}

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;
    }
}

其中,第一次写的时候遗漏了最大和为负的情况,例如数据“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
}

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;
}

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;
}

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());
}

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;
}

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;
}

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;

}

🌲

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;
}

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

  1. 建树传参时,无需每次都新建子串。只需要每次规定子串的起始位置,随机访问即可;
  2. 判断 FBI 时,if (exist1 == 0 && exist0 != 0) 直接写为 if (exist0) 就够了(本来前半段也是冗余的)
  3. 建树和后序遍历可以在同一个递归中完成,即在当前函数里,先遍历建树,再打印 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>
#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)

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

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

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

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;
}

但是为什么我的代码就要 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;
}

对比发现有如下原因:

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

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<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;
}

而这个方法可以有改进:

先补充一下 map:

  1. map第一个好处是作为一个数组,可以开很大!比如:map<int,int>x;,可以把x数组当成普通数组用,不过要注意一点:定义了x数组后,就不能使用c++的数组函数,比如 memset
  2. map第二个好处下标不一定是一个整数,可以甚至可以是一个字符串!map<下标类型,数值类型>; 比如:map<string,char>a; string st="123"; a[st]='1';
  3. 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;//结束程序
}

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;
}

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;
}

背包问题

背包九讲

模板

  1. 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;
  2. 完全背包: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]);
  3. 多重背包问题:有 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); } }
  4. 混合背包问题:综合起来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]);
  5. 二维背包问题: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]);
  6. 分组背包问题:有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;
}

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;
}

贪心

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;
}

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;
}

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;
}

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;
}

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

因为 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;
}

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;
}

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;
}

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))

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;
}

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;
}

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);
}

并查集

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;
}

2 种类并查集 100

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

初始化:

    fa[i] = i;
    fa[i + n] = i + 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;
}

3 种类并查集 AC

同上,这里的写法终于让我明白了:

  1. 由于有压缩路径,所以 fa[n] 和 findfa(n) 是等价的
  2. 谁是谁的爸爸都可以,因此本题解这样写也是可以滴,以后就以这个为准:
    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;
}

4 种类并查集 AC

三类,就开三倍的数组并查集:

捕食的关系这样维护:

若是同类,则 `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;
}

5 a bug’s life

18 保研机试原题 没有 oj 也不知道对错

// 2020-02-24 11:11:14
# include <cstdio>
int t,m,n,a,b,f[4005] = {};

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

int main(){
    scanf("%d",&t);
    for(int p = 1;p <=t;p++){
        int isfound = 0;
        scanf("%d %d",&n,&m);
        for(int i = 1;i<=n*2;i++)f[i] = i;
        for(;m;m--){
            scanf("%d %d",&a,&b);
//            printf("%d-%d-%d-%d-%d-%dmm\n",a,b,f[a],f[b],f[a+n],f[b+n]);
            if (find(a) == find(b) || find(a+n) == find(b+n))
                isfound = 1;
            else{
                f[f[a]] = f[b+n];
                f[f[b]] = f[a+n];
            }
//            printf("%d-%d-%d-%d-%d-%dmmhh\n",a,b,f[a],f[b],f[a+n],f[b+n]);

        }
        if (isfound)printf("Scenario #%d:\nSuspicious bugs found!",p);
        else printf("Scenario #%d:\nNo suspicious bugs found!",p);
    }
    return 0;
}

6 变性并查集 TODO

太烦了 懒得改了

# include <iostream>
using namespace std;

const int maxn = 30000;
int t,x,y,f[maxn+1],l[maxn+1] = {},u[maxn+1] = {};
// f 是 father;l 是当前位于第几层,0为队首;u 是该节点下面有多少个;
char c;

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

// 在寻找祖宗的同时,更新各个长辈的层数
int findandplus(int x,int y){
    l[x] = l[x] + l[y] + 1;
    if (x == f[x])return x;
    else return f[x] = findandplus(f[x],y);
}

// 返回同一队列中两点之间的距离
int getlength(int x,int y){
    int xx = l[x],yy = l[y];
    return (xx>yy)?(xx-yy):(yy-xx);
}

int main(){
    std::ios::sync_with_stdio(false);
    cin>>t;
    for(int i = 0;i<=maxn;i++)f[i] = i;
    for(;t;t--){
        cin>>c>>x>>y;
        if (c == 'M'){
            f[findandplus(x,y)] = y;
        }else{
            if (find(x) != find(y)) cout<<"-1"<<endl;
            else {
                cout<<getlength(x,y)-1<<endl;
            }
        }
        for(int i = 1;i<10;i++){
            printf("%d-%d ",f[i],l[i]);
        }printf("\n");
    }
    return 0;
}
//6
//M 2 3
//C 1 2
//M 2 4
//C 4 2
//M 6 5
//M 3 5

7 并查集模板题 AC

# include <cstdio>
int fa[20001] = {};
int m,n,a,b,c;

int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
void p(){
    for(int i = 0;i<=n;i++)printf("%d ",fa[i]);
    printf("\n");
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<=n;i++)fa[i] = i;
    for(;m;m--){
        scanf("%d %d %d",&a,&b,&c);
        if (a == 1)fa[find(c)] = find(b);
        else {
            if (find(c) == find(b))printf("Y\n");
            else printf("N\n");
        }
//        p();
    }
    return 0;
}

8 亲戚 AC

# include <cstdio>
int fa[5005] = {},n,m,p,a,b;
int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    scanf("%d %d %d",&n,&m,&p);
    for(int i = 0;i<=n;i++)fa[i] = i;
    for(;m;m--){
        scanf("%d %d",&a,&b);
        fa[find(a)] = find(b);
    }
    for(;p;p--){
        scanf("%d %d",&a,&b);
        if (find(a) == find(b)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

9 奶酪联通 AC

# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;
int t,n,h,r,a,b,c;
int fa[1002] = {};
struct point{
    int x,y,z;
    point(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
};
vector<point>v;
vector<int>top,bottom;
bool neighbour(point a, point b,int r){
    return pow((a.x-b.x), 2)+pow((a.y-b.y), 2)+pow((a.z-b.z), 2) <= pow(r * 2.0,2);
}
int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    scanf("%d",&t);
    for(;t;t--){
        scanf("%d %d %d",&n,&h,&r);
        v.clear();
        bottom.clear();
        top.clear();
        v.push_back(point(0,0,0));
        for(int i = 0;i<=n;i++)fa[i] = i;
        for(int i = 1;i<=n;i++){
            scanf("%d %d %d",&a,&b,&c);
            v.push_back(point(a,b,c));
            if (c <= r)bottom.push_back(i);
            if (c + r >= h)top.push_back(i);
            for(int j = 1;j<i;j++){
                if (neighbour(v[j], v[i], r))fa[find(i)] = find(j);
            }
        }
//        for(int i = 0;i<=n;i++)printf("%d ",fa[i]);
//        printf("\n");
        int sgn = 0;
        for(int i = 0;i<bottom.size();i++){
            for(int j = 0;j<top.size();j++){
                if (find(bottom[i]) == find(top[j])){
                    sgn = 1;
                    printf("Yes\n");
                    break;
                }
            }
            if (sgn)break;
        }
        if (!sgn)printf("No\n");
    }
    return 0;
}

10 搭配购买 AC

背包 + 并查集

== x’ 判断

# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
int n,m,w,v,p,u;
long long fa[10005] = {},f[10005] = {};
struct cloud{
    long long value,price,id;
    double ratio;
    cloud(int _v,int _p,int _id){
        value = _v;
        price = _p;
        id = _id;
        ratio = double(value)/double(price);
    };
    cloud(){};
};
long long find(long long x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
vector<cloud>c;
bool cmp(cloud a,cloud b){
    if (a.ratio > b.ratio)return a.ratio>b.ratio;
    else return a.price<b.price;
}
int main(){
    scanf("%d %d %d",&n,&m,&w);
    for (int i = 0;i<n;i++)fa[i] = i;
    for (int i = 0;i<n;i++){
        scanf("%d %d",&v,&p);
        c.push_back(cloud(p,v,i));
    }
    for (int i = 0;i<m;i++){
        scanf("%d %d",&u,&v);
        fa[find(v-1)] = find(u-1);
    }
    for(int i = 0;i<n;i++){
        if(fa[i] != i){
            c[find(i)].price += c[i].price;
            c[find(i)].value += c[i].value;
            c[i].price = 0;
            c[i].value = 0;
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=w;j>=c[i].price;j--)
            f[j]=max(f[j],f[j-c[i].price]+c[i].value); //01背包
    printf("%lld\n",f[w]);
    return 0;
}

11 并查集内计数 AC

# include <cstdio>
int fa[2][10005] = {},n,m,p,q,a,b;
int find(int x,int typ){
    if (fa[typ][x] == x)return x;
    else return fa[typ][x] = find(fa[typ][x],typ);
}
void merge(int a,int b,int typ){
    if (find(a,typ) != find(b,typ))
        fa[typ][find(a,typ)] = find(b,typ);
}
int main(){
    scanf("%d %d %d %d",&n,&m,&p,&q);
    for(int i = 0;i<=n;i++)fa[0][i] = i;
    for(int i = 0;i<=m;i++)fa[1][i] = i;
    for(;p;p--)scanf("%d %d",&a,&b),merge(a,b,0);
    for(;q;q--)scanf("%d %d",&a,&b),merge(-a,-b,1);
    int ca = 0,cb = 0;
    for(int i = 0;i<=n;i++)
        if (find(i,0) == find(1,0))ca ++;
    for(int i = 0;i<=m;i++)
        if (find(i,1) == find(1,1))cb ++;
    printf("%d",ca>cb?cb:ca);
    return 0;
}

12 统计并查集的数 AC

用 set.size() 统计不同 father 的个数

# include <cstdio>
# include <set>
using namespace std;
int fa[1005] = {},m,n,a,b;
int find(int x){
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
void merge(int a,int b){
    if (find(a) != find(b))
        fa[find(a)] = find(b);
}
int main(){
    while(scanf("%d",&n) && n){
        scanf("%d",&m);
        for(int i = 0;i<=n;i++)fa[i] = i;
        for(;m;m--){
            scanf("%d %d",&a,&b);
            merge(a,b);
        }
        set<int>st;
        for(;n;n--)st.insert(find(n));
        printf("%d\n",(int)st.size()-1);
    }
    return 0;
}

13 运动会 AC

map + 并查集

# include <cstdio>
# include <string>
# include <iostream>
# include <map>
using namespace std;
int fa[20005] = {},m,n,k,a,b;
string s1,s2;
map<string,int>ma;
int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
void merge(int a,int b){
    if (find(a) != find(b))
        fa[find(a)] = find(b);
}
int main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i = 0;i<=n;i++)fa[i] = i;
    for(int i = 0;i<n;i++){
        cin>>s1;
        ma.insert(make_pair(s1, i));
    }
    for(int i = 0;i<m;i++){
        cin>>s1>>s2;
        merge(ma[s1],ma[s2]);
    }
    cin>>k;
    for(;k;k--){
        cin>>s1>>s2;
        if (find(ma[s1]) == find(ma[s2])) cout<<"Yes.\n";
        else cout<<"No.\n";
    }
    return 0;
}

而大佬的方法,直接把 fa[] 改成 string 到 string 的 map

#include<iostream>
#include<cstdio>
#include<map>//map库
using namespace std;
map<string,string> a;//建立映射
string fin(string x){//查找字符串x的祖先
    if(a[x]==x) return x;
    else return a[x]=fin(a[x]);//路径压缩
}
int main(){
    int n,m,k;
    string s1,s2;//s1,s2可重复使用
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>s1;//选手名字
        a[s1]=s1;//每个人的祖先初始化为自己
    }
    for(int i=1;i<=m;++i){
        cin>>s1>>s2;//两位选手
        string x1=fin(s1),x2=fin(s2);//合并
        if(x1!=x2) a[x1]=x2;
    }
    cin>>k;
    for(int i=1;i<=k;++i){
        cin>>s1>>s2;
        string x1=fin(s1),x2=fin(s2);//查询
        if(x1!=x2) printf("No.\n");
        else printf("Yes.\n");
    }
    return 0;//后话:STL大法好!
}

14 最小生成树 AC

kruscarl 并查集实现

# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int fa[5010] = {};
int n,m,f,t,e;
struct edge{
    int from,to,length;
    edge(int f,int t,int e):from(f),to(t),length(e){}
};
bool cmp(edge a,edge b){
    return a.length < b.length;
}
vector<edge>lst;
int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<=n;i++)fa[i] = i;
    for(int i = 0;i<m;i++){
        scanf("%d %d %d",&f,&t,&e);
        lst.push_back(edge(f,t,e));
    }
    sort(lst.begin(), lst.end(), cmp);
    int res = 0;
    for(int i = 0,j = 0;i<n-1;j++){
        if (j == m){
            printf("orz");
            return 0;
        }
//        printf("%d %d %d %d\n",lst[j].from,lst[j].to,find(lst[j].from),find(lst[j].to));
        if (find(lst[j].from) != find(lst[j].to)){
            res += lst[j].length;
            fa[find(lst[j].from)] = find(lst[j].to);
            i++;
        }
    }
    printf("%d",res);
    return 0;
}

15 无线通信网 AC

kruscal 控制最后有 p-s+1 个联通区块

# include <cstdio>
# include <vector>
# include <cmath>
# include <algorithm>
using namespace std;
int fa[250005] = {};
int s,p,x,y;
struct edge{
    int from,to;
    double length;
    edge(int f,int t,double e):from(f),to(t),length(e){}
};
struct node{
    int x,y;
    node(int _x,int _y):x(_x),y(_y){}
};
bool cmp(edge a,edge b){
    return a.length < b.length;
}
double cal(node a,int x,int y){
    return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
}
vector<edge>elst;
vector<node>nlst;
int find(int x){
    if (fa[x] == x)return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    scanf("%d %d",&s,&p);
    for(int i = 0;i<p;i++){
        scanf("%d %d",&x,&y);
        for(int j = 0;j<nlst.size();j++){
            elst.push_back(edge(i,j,cal(nlst[j],x,y)));
        }
        nlst.push_back(node(x,y));
    }
    sort(elst.begin(),elst.end(),cmp);
    for(int i = 0;i<p+1;i++)fa[i] = i;
    double res = 0.0;
    for(int i = 0,j = 0;i<p-s;j++){
        if (find(elst[j].from) != find(elst[j].to)){
            fa[find(elst[j].from)] = find(elst[j].to);
            i++;
            res = elst[j].length;
        }
    }
    printf("%.02lf",res);
    return 0;
}

16 家谱 AC

不能用 insert,因为 key 不能重复!

# include <cstdio>
# include <map>
# include <string>
# include <iostream>
using namespace std;
map<string,string>fa;
char sgn;
string f,s;
int main(){
    while(scanf("%c",&sgn) && sgn != '$'){
        if (sgn == '#') {
            cin>>f;
            // map 里面没有,才加入
//            if (fa.find(f) == fa.end()) fa.insert(make_pair(f, f));
            if (fa[f] == "") fa[f] = f;

        }
        else if(sgn == '+'){
            cin>>s;
//            fa.insert(make_pair(s, f));
            fa[s] = f;

        }
        else if(sgn == '?'){
            cin>>s;
            cout<<s<<' ';
            while(fa[s] != s)s = fa[s];
            cout<<s<<endl;
        }
    }
    return 0;
}

17 刻录光盘 AC

并查集是双向的,但此题为单向

不管那些特殊点(比如同一个 cluster 里面,可能有多个源点),用一个数组存一下每一个点有没有直系的父亲,其他的跟并查集没啥区别。最后 O(n) 扫一遍的时候加以判断,如果是没有直系父亲的,直接加一,其他的如果是祖先也加一。

# include <cstdio>
# include <vector>
# include <set>
using namespace std;
int fa[205] = {},havefa[205] = {};
int n,a;
int find(int x){
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++) fa[i] = i;
    for(int i = 1;i<=n;i++){
        while(scanf("%d",&a) && a){
            havefa[a] = 1;
            if (find(a) != find(i))
                fa[find(a)] = find(i);
        }
    }
//    for(int i = 1;i<=n;i++)printf("%d ",havefa[i]);
//    printf("\n");
//    for(int i = 1;i<=n;i++)printf("%d ",fa[i]);
//    printf("\n");
    int count = 0;
    for(int i = 1;i<=n;i++)
        if (!havefa[i] || fa[i] == i) count++;
    printf("%d",count);
    return 0;
}

//
//9
//6 4 0
//8 5 4 0
//1 5 7 0
//1 0
//1 0
//6 0
//1 8 0
//0
//0

入门综合练习

1 水 AC

注意等号!

//2020-02-24 14:33:41
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;

int n,s,a,b,ta,tb;

struct apple{
    int h,f;
    apple(int _h,int _f):h(_h),f(_f){}
};

bool cmp(apple a,apple b){
    return a.f < b.f;
}

int main(){
    scanf("%d%d%d%d",&n,&s,&a,&b);
    int hmax = a+b,count = 0;
    vector<apple>lst;
    for(int i = 0;i<n;i++){
        scanf("%d %d",&ta,&tb);
        lst.push_back(apple(ta, tb));
    }
    sort(lst.begin(),lst.end(),cmp);
    for(int i = 0;i<n;i++){
//        printf("%d-%d-%d-%d\n",lst[i].h,lst[i].f,s,count);
        if (lst[i].h <= hmax){
            if (s >= lst[i].f){
                s -= lst[i].f;
                count++;
            }else break;
        }
    }
    printf("%d",count);
    return 0;
}

2 ABC 三位数比例 AC

太粗心了!!一定稳重!!

// 2020-02-24 15:06:56

# include <cstdio>
# include <algorithm>

bool meet(int a,int b,int c){
    if (a > 987 || a < 102 || b > 987 || b < 102 ||c > 987 || c < 102)
        return false;
    int sum = a * 1000000 + b * 1000 + c,now;
    int hash[10] = {};
    for(int i = 0;i<10;i++){
        now = sum % 10;
        if(hash[now] != 0)return false;
        else{
            hash[now] ++;
            sum /= 10;
        }
    }
    return true;
}
int getup(int a){
    for(int i = 100;i <= 999;i++){
        if (i%a == 0)return i;
    }
    return 102;
}
int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    int end = 987/c*a+1,start = getup(a),is = 0;
    for(int i = start;i<=end;i+=a){
        if (meet(i,i/a*b,i/a*c)){
            printf("%d %d %d\n",i,i/a*b,i/a*c);
            is = 1;
        }
    }
    if (is == 0)printf("No!!!");
    return 0;
}

3 哥德巴赫猜想 AC

由于是需要三个数字和为n,限定了3,就非常简单,无需 DFS 了

// 2020-02-24 15:39:13

# include <cstdio>
using namespace std;

int n,prime[20000] = {2,3,5,7,11,13,17,19};

bool isprime(int n){
    for(int i = 0;prime[i]>0 && prime[i] < n;i++){
        if (n % prime[i] == 0)return false;
    }
    return true;
}

void getPrime(int n){
    int k = 8;
    for (int i = 23;i<=n;i++){
        if (isprime(i))prime[k++] = i;
    }
}

void get(int n){
    for(int i = 0;prime[i] != 0;i++){
        for(int j = i;prime[j] != 0;j++){
            for(int k = j;prime[k] != 0;k++){
                if (prime[i] + prime[j] + prime[k] == n){
                    printf("%d %d %d",prime[i],prime[j],prime[k]);
                    return;
                }
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    getPrime(n);
//    for(int i = 0;prime[i] != 0;i++){
//        printf("%d ",prime[i]);
//    }
    get(n);
    return 0;
}

4 小鱼 AC

// 2020-02-25 08:53:30

# include <cstdio>

int main(){
    double s,x,step = 7.0,now = 0.0;
    int p = 0;
    scanf("%lf %lf",&s,&x);
    for(int i = 0;;i++){
        if (now >= s-x && now <= s+x)p++;
        if (now >= s+x)break;
        now += step;step *= 0.98;   // 先检查!否则还没走就被发现的检查不出来了
    }
    if (p>=2) printf("y");
    else printf("n");
    return 0;
}

5 记忆化搜索 AC

# include <cstdio>
# define LL long long
# define maxn 30
int n[maxn][maxn][maxn] = {};
int w(int a,int b,int c){
    if (a <= 0 || b <= 0 || c <= 0)
//        return n[a][b][c] = 1;    一开始这样写,越界了!!
        return 1;
    else if (a > 20 || b > 20 || c > 20)
        return n[20][20][20] = w(20,20,20);
    else if (n[a][b][c] != 0)
        return n[a][b][c];
    else if (a < b && b < c)
        return n[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
    else
        return n[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);
}
int main(){
    LL a,b,c;
    while(1){
        int res;
        scanf("%lld %lld %lld",&a,&b,&c);
        if (a == -1 && b == -1 && c == -1)return 0;
        res = w((int)a,(int)b,(int)c);
        printf("w(%lld, %lld, %lld) = %d\n",a,b,c,res);
    }
    return 0;
}

6 枚举

# include <cstdio>
int main(){
    int n;
    scanf("%d",&n);
    int i = 1,sum = 0,lastsum = 0;
    for(;sum<n;i++){
        lastsum = sum;
        sum += i;
    }
    if (i%2 == 0) printf("%d/%d",i-n+lastsum,n-lastsum);
    else printf("%d/%d",n-lastsum,i-n+lastsum);
    return 0;
}

7 解方程 AC

注意 -0.000 问题,以及每一个 num 都必须 * isnegative * isinverted

# include <cstdio>
# include <cstring>
int a = 0,b = 0,isnegative = 1,isinverted = 1,end = 1;
// isnegative 是负数 isinverted 在等号右边 end 结束
char variable;
void input(){
    int num = 0;
    char c = getchar();
//    printf("char = %c--\n",c);
    while(c >= '0' && c <= '9'){
        num *= 10;
        num += int(c-'0');
        c = getchar();
    }
//    printf("num = %d\n",num);
    if (c >= 'a' && c <= 'z') {
        if (num != 0)a += (isnegative * num * isinverted);
        else a += isnegative * isinverted;
        variable = c;
    }
    else {
        b += (isnegative * isinverted * num);
        if (c == '-')isnegative = -1;
        else if (c == '+')isnegative = 1;
        else if (c == '='){
            isinverted = -1;
            isnegative = 1; //一定别忘了回归正号!
        }
        else end = 0;
    }
//    printf("%d %d---\n",a,b);
}
int main(){
    while(end){
        input();
    }
    double res = -double(b)/(double)a;
    if (b != 0 && !(res<0.001 && res>-0.001))
        printf("%c=%.03lf",variable,res);
    else printf("%c=%.03lf",variable,0.000);    // 第5点:常数为零
    return 0;
}

高精度

全都直接用 python!

1 高精度 + – x: 1601 2142 1303

题解过于简单,略

2 数楼梯 AC

注意修改系统递归深度!同时 return b[n] = sth 在 python 是不正确的语法!

import sys   
sys.setrecursionlimit(100000) # 修改最大递归深度,否则报错
a = int(input())
b = [0]*5001
b[0] = 0;b[1] = 1;b[2] = 2
def getsolution(n):
    if b[n] == 0:
       b[n] = getsolution(n-1) + getsolution(n-2)
    return b[n]
if a>0:
    print(getsolution(a))
else:
    print(0)

然而,一个大佬题解让人刮目相看:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数 
void hp(int k)//高精度加法,k来存阶数 
{    
    int i;
    for(i=1;i<=len;i++)
     f[k][i]=f[k-1][i]+f[k-2][i];//套用公式 
    for(i=1;i<=len;i++)             //进位 
     if(f[k][i]>=10)
     {
         f[k][i+1]+=f[k][i]/10;
         f[k][i]=f[k][i]%10;
         if(f[k][len+1])len++;
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    f[1][1]=1; f[2][1]=2;         //初始化 
    for(i=3;i<=n;i++)              //从3开始避免越界 
     hp(i);                         
    for(i=len;i>=1;i--)             //逆序输出 
     printf("%d",f[n][i]);
    return 0;
}

由于输入是 int 范围,故不需要用字符串,高精用 f[][i] 也能表示!!

3 阶乘 AC

# https://www.luogu.com.cn/problem/P1591
import re
n = int(input())
for i in range(n):
    m = [int(i) for i in input().split(' ')]
    res = 1
    for j in range(1,m[0]+1):
        res = res * j
    r = str(res)
    p = re.findall(str(m[1]),r)
    print(len(p))

4 B进制星球 AC

其他进制加法,直接字符算

# include <map>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
char hashtable[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
map<char,int>mp;
int b;
char x[2001],y[2001],z[2005];
int pluss(char x,char y,int sgn){
    return mp[x]+mp[y]+sgn;
}
int main(){
    for(int i = 0;i<37;i++) mp[hashtable[i]] = i;
    scanf("%d",&b);
    scanf("%s %s",x,y);
    reverse(x, x+strlen(x));
    reverse(y, y+strlen(y));
    int sgn = 0;
    if (strlen(x) < strlen(y)){
        for(int i = strlen(x);i<=strlen(y);i++)x[i] = '0';
        y[strlen(y)] = '0';
    }else{
        for(int i = strlen(y);i<=strlen(x);i++)y[i] = '0';
        x[strlen(x)] = '0';
    }
    for(int i = 0;i<strlen(x) && i < strlen(y);i++){
        int t = pluss(x[i],y[i],sgn);
        if (i == strlen(x)-1 && t == 0)break;
        if (t >= b){
            z[i] = hashtable[t-b];
            sgn = 1;
        }else{
            z[i] = hashtable[t];
            sgn = 0;
        }
    }
    reverse(z, z+strlen(z));
    printf("%s",z);
}

数学问题

1 next_permutation AC

# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,p,t;

int main(){
//    printf("fas");
//    return 0;
    scanf("%d%d",&n,&p);
    vector<int>a;
    for(int i = 0;i<n;i++){
        scanf("%d",&t);
        a.push_back(t);
    }
    for(int i = 0;i<p;i++){
        next_permutation(a.begin(), a.end());
    }
    for(int i = 0;i<n;i++){
        printf("%d",a[i]);
        if (i < n-1) printf(" ");
    }
    return 0;
}

2 高精 AC

10**500 会超时!

import math
a = int(input())
res = 1
b=pow(2,a,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
print(int(a * math.log(2,10))+1)
r = str("%0500d" % (b-1))
for i in range(10):
    print(r[i*50:(i+1)*50])

3 枚举 AC

虽然是两个数字枚举,但是不需要枚举两层,一层即可


// https://www.luogu.com.cn/problem/P1147
# include <cstdio>
# include <cmath>
# include <algorithm>
# include <vector>
using namespace std;
int m;
struct node{
    int x, y;
    node(int _x,int _y):x(_x),y(_y){}
};

bool cmp(node a,node b){return a.x < b.x;}

vector <node>res;
int main(){
    scanf("%d",&m);
    for(int i = 1;i<=m;i++){
        if (m*2%i == 0 && (m*2/i)%2 == 1){
            int j = m*2/i;
            res.push_back(node(abs(i-j)/2+1,(i+j)/2));
        }
    }
    sort(res.begin(), res.end(), cmp);
    for (int i =0 ;i<res.size();i++){
        printf("%d %d\n",res[i].x,res[i].y);
    }
    return 0;
}

4 分解质因数 AC

#include<bits/stdc++.h>
using namespace std;
int x,y,p,ans=1,a;
int main()
{
    cin>>x>>y;
    if(y%x!=0)cout<<0;
    else
    {
        p=y/x;
        a=2;
        while(p!=1)
        {
            while(p%a!=0)a++;
            while(p%a==0)p/=a;
            a++;ans*=2;
        }
        cout<<ans;
    }
    return 0;
}

5 next_permutation AC

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

int n,a[10] = {};
void print(){
    for(int i = 1;i<=n;i++)printf("%5d",a[i]);
    printf("\n");
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)a[i] = i;
    do{
        print();
    }while(next_permutation(a+1, a+n+1));
    return 0;
}

6 约数研究 AC

# include <cstdio>
int n;
int main(){
    scanf("%d",&n);
    int res = 0;
    for(int i = 1;i<=n;i++){
        res += n/i;
    }
    printf("%d",res);
}

排序

1 unique AC

unique 返回 n 为前面不重复的最后位置

// 2020-02-27 09:28:33
# include <cstdio>
# include <algorithm>
using namespace std;
int n,num[10000] = {};

int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d",&num[i]);
    }
    sort(num,num+n);
    int p = unique(num,num+n)-num;
    printf("%d\n",p);
    for(int i = 0;i<p;i++){
        printf("%d",num[i]);
        if (i <n-1)printf(" ");
    }
    return 0;
}

2 分数线划定 AC

检查的时候优先检查数组下标!

# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
struct s{
    int id,score;
    s (int _a,int _b):id(_a),score(_b){}
};
int n,m,a,b;
vector<s>lst;
bool cmp(s a,s b){
    if (a.score != b.score)return a.score > b.score;
    else return a.id < b.id;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%d %d",&a,&b);
        lst.push_back(s(a,b));
    }
    sort(lst.begin(),lst.end(),cmp);
    int finalscore = lst[int(m*1.5)-1].score,i = m*1.5-1;
    for(;i<n;i++){
        if (lst[i].score < finalscore)break;
    }
    printf("%d %d\n",finalscore,i);
    for(int k = 0;k<i;k++){
        printf("%d %d\n",lst[k].id,lst[k].score);
    }
    return 0;
}

3 高精比较大小 AC

n = int(input())
now = -1;maxn = -1;pos = -1
for i in range(n):
    now = int(input())
    if now > maxn:
        maxn = now
        pos = i
print(str(pos+1) + '\n' + str(maxn))

4 结构排序 AC

这道题真坑,“序号” 和 “编号” 是不同的,要排序两次。好好读题!

# include <cstdio>
# include <algorithm>
using namespace std;
int n,k,e[10],p;
struct m{
    int id,v,x;
    m(){}
    m(int _id,int _v):id(_id),v(_v),x(0){}
}lst[20002];
bool cmp(m a,m b){
    if (a.v != b.v)return a.v > b.v;
    else return a.id < b.id;
}
int main(){
    scanf("%d %d",&n,&k);
    for(int i = 1;i<=10;i++) scanf("%d",&e[i%10]);
    for(int i = 1;i<=n;i++){
        scanf("%d",&p);
        lst[i] = m(i,p);
    }
    sort(lst+1,lst+n+1,cmp);
    for(int i = 1;i<=n;i++){
        lst[i].x = i;
        lst[i].v += e[i%10];
    }
    sort(lst+1,lst+n+1,cmp);
    for(int i = 1;i<=k;i++){
        printf("%d",lst[i].id);
        if (i < k)printf(" ");
    }
    return 0;
}

5 结构体归并排序 AC

放到两个组,然后归并,只需要 O(n)

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

# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,r,q,temp;

struct man{
    int id,s,w;
    man(int _id,int _s):id(_id),s(_s),w(0){}
};
vector<man>l;

bool cmp(man a,man b){
    if (a.s != b.s)return a.s > b.s;
    else return a.id < b.id;
}

void merge(vector<man>a,vector<man>b){
    int i = 0,j = 0;
    for(int p = 0;p<2*n;p++){
//        printf("%d %d %d\n",p,i,j);
        if (cmp(a[i],b[j])){
            l[p] = a[i++];
        }else{
            l[p] = b[j++];
        }
        if (i == n){
            for(;j<n;j++)l[++p] = b[j];
            break;
        }else if (j == n){
            for(;i<n;i++)l[++p] = a[i];
            break;
        }
    }
}

int main(){
    scanf("%d %d %d",&n,&r,&q);
    for(int i = 0;i<2 * n;i++){
        scanf("%d",&temp);
        l.push_back(man(i+1,temp));
    }
    for(int i = 0;i<2 * n;i++){
        scanf("%d",&temp);
        l[i].w = temp;
    }
    sort(l.begin(), l.end(), cmp);
    for(int ii = 0;ii<r;ii++){
        
        vector<man>a;   // 赢家进入 a,输进入 b
        vector<man>b;
        
        for(int i = 0;i<n;i++){
            if (l[i*2].w > l[2*i + 1].w){
                l[i*2].s++;
                a.push_back(l[i*2]);
                b.push_back(l[i*2+1]);
            }else{
                l[i*2+1].s++;
                b.push_back(l[i*2]);
                a.push_back(l[i*2+1]);
            }
        }
        
//        for(int i = 0;i<n;i++) printf("%d-%d ",a[i].id,a[i].s);
//        printf("\n");
//        for(int i = 0;i<n;i++) printf("%d-%d ",b[i].id,b[i].s);
//        printf("\n");

        merge(a,b);     // AB 合并

//        sort(l.begin(), l.end(), cmp);  // 超时
        
//        for(int i = 0;i<n*2;i++) printf("%d-%d ",l[i].id,l[i].s);
//        printf("\n");
        
    }

    printf("%d",l[q-1].id);
    return 0;
}

6 水题 AC

# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
int getscore(int q,int p,int g,int x,int l){
    int sum = 0;
    if (q > 80 && l > 0)sum +=8000;
    if (q > 85 && p > 80)sum += 4000;
    if (q > 90)sum += 2000;
    if (x && q > 85)sum += 1000;
    if (p > 80 && g)sum += 850;
    return sum;
}
int n,maxmoney = 0,totalmoney = 0;
char na[21],finalna[21],g,x;
int q,p,l;
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%s %d %d %c %c %d",na,&q,&p,&g,&x,&l);
        int temp = getscore(q,p,g=='Y'?1:0,x=='Y'?1:0,l);
        totalmoney += temp;
        if (temp > maxmoney){
            maxmoney = temp;
            for(int i = 0;i<strlen(na);i++){
                finalna[i] = na[i];
            }finalna[strlen(na)] = '\0';
        }
    }
    printf("%s\n%d\n%d",finalna,maxmoney,totalmoney);
    return 0;
}

7 水题 AC

# include <cstdio>
# include <algorithm>
using namespace std;
struct stu{
    int ch,all,id;
    stu(){};
    stu(int _a,int _b,int _c):id(_a),ch(_b),all(_c){}
}s[301];
bool cmp(stu a,stu b){
    if (a.all != b.all)return a.all > b.all;
    else if (a.ch != b.ch)return a.ch > b.ch;
    else return a.id < b.id;
}
int main(){
    int n,a,b,c;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%d %d %d",&a,&b,&c);
        s[i] = stu(i,a,a+b+c);
    }
    sort(s+1,s+n+1,cmp);
    for(int i = 1;i<=5;i++){
        printf("%d %d\n",s[i].id,s[i].all);
    }
    return 0;
}

8 水hash AC

# include <cstdio>
# include <algorithm>
using namespace std;
int n,m,p,a[1000] = {};
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<m;i++){
        scanf("%d",&p);
        a[p] ++;
    }
    int c = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<a[i];j++){
            printf("%d",i);
            c++;
            if (c < m)printf(" ");
        }
    }
}

9 第k小 AC

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[5000010];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    nth_element(a,a+k,a+n);//使第k小整数就位
    printf("%d",a[k]);//调用第k小整数
}

10 水 AC

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

11 水 结构体排序 AC

# include <cstdio>
# include <algorithm>
# include <cmath>
using namespace std;
int n,a,b,c;
double sum = 0.0;
struct node{
    int x,y,z;
    node(){};
    node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
}lst[50001];
bool cmp(node a,node b){
    return a.z < b.z;
}
double dis(node a,node b){
    return (sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2)+pow((a.z-b.z),2)));
}
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d %d %d",&a,&b,&c);
        lst[i] = node(a,b,c);
    }
    sort(lst,lst+n,cmp);
    double res = 0;
    for(int i = 1;i<n;i++){
        res += dis(lst[i],lst[i-1]);
    }
    printf("%.03lf",res);
    return 0;
}

1 DJ WA

明明跟模板都一样。。

# include <cstdio>
# include <algorithm>
# include <stack>
# define MAXN 0x7fffffff
# define _rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
using namespace std;
int n,G[10][10],dis[10],vis[10] = {},pre[10] = {};
void Dj(int start){
    fill(dis,dis+n,MAXN);
    dis[start] = 0;
    _rep(ii,0,n){
        int MIN = MAXN,k = -1;
        _rep(i, 0, n){
            if (dis[i] < MIN && vis[i] == 0){
                MIN = dis[i];
                k = i;
            }
        }
        if (k == -1)return;vis[k] = 1;
        _rep(i, 0, n){
            if (vis[i] == 0 && dis[i] > dis[k] + G[k][i]){
                dis[i] = dis[k] + G[k][i];
                pre[i] = k;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    _rep(i,0,n){
        _rep(j,0,n){
            scanf("%d",&G[i][j]);
        }
    }
    Dj(0);
    printf("%d\n",dis[n-1]);
    int now = n-1;
    stack<int>st;
    _rep(i, 0, n){
        if (now == 0)break;
        st.push(now);
        now = pre[now];
    }
//    _rep(i, 0, n){printf("%d-",pre[i]);}
    printf("1");
    while(!st.empty()){
        printf(" %d",st.top()+1);
        st.pop();
    }
    return 0;
}

2 求最小环 70

我的 70 分方法(三个点 TLE):从有出入度的点开始,挨个遍历 TODO

# include <cstdio>
const int maxn = 200000;
int n,next[maxn] = {},prev[maxn] = {};
int getcircle(int x,int n){
    int i = x,count = 1;
    int vis[maxn] = {};
    while(next[i] != x && !vis[i]){
        count ++;
        if (count>=n)break;
        vis[i] ++;
        i = next[i];
    }
    return count;
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%d",&next[i]);
        prev[next[i]] = 1;
    }
    int min = n;
    for(int i = 1;i<=n;i++){
        if(prev[i] && next[i]){
            int p = getcircle(i,n);
            min = min<p?min:p;
            if(min == 2)break;
        }else{  // 如果 i 点入度为零,则把从 i 出发的边也删去
            prev[next[i]] = 0;
        }
    }
    printf("%d",min);
    return 0;
}

3 二分图染色 40

TODO 真的看不懂题解

# include <cstdio>
# include <vector>
using namespace std;
int f[20001],n,m,ta,tb;
int find(int x){
    if (f[x] == x)return x;
    return f[x] = find(f[x]);
}
void merge(int a,int b){
    f[find(a)] = find(b);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=2 * n;i++)f[i] = i;
    for(int i = 0;i<m;i++){
        scanf("%d %d",&ta,&tb);
        if (find(ta) == find(tb) || find(ta + n) == find(tb + n)){
            printf("Impossible");
            return 0;
        }else{
            // 种类并查集 分成两类
            merge(ta, tb+n);
            merge(ta+n, tb);
        }
    }
    int count = 0;
    for(int i = 1;i<=n;i++){
        if (f[i] > n)count ++;
    }
    printf("%d",count>(n-count)?(n-count):count);
    return 0;
}

4 最大父亲 AC

从大到小,反向遍历,能遍历到的就是自己作为父亲的

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

int n,m,a,b,fa[100005],now = 0;
vector<int>g[100005];

void find(int x){
    if (fa[x])return;
    fa[x] = now;
    for(int i = 0;i<g[x].size();i++){
        find(g[x][i]);
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for(;m;m--){
        scanf("%d %d",&a,&b);
        g[b].push_back(a);
    }
    for(int i = n;i>0;i--){
        now = i;
        find(i);
    }
    for(int i = 1;i<=n;i++){
        printf("%d",fa[i]);
        if (i < n)printf(" ");
    }
    return 0;
}

5 BFS + DFS AC


# include <cstdio>
# include <vector>
# include <queue>
# include <algorithm>
using namespace std;
const int maxn = 100002;
int n,m,a,b,vis[maxn],countn = 0;
vector<int>g[maxn];
void init(){
    for(int i = 0;i<=n;i++)vis[i] = 0;
    countn = 0;
}
void DFS(int start){
    countn++;
    printf("%d ",start);
    vis[start] = 1;
//    if (countn < n) printf(" ");
//    else printf("\n");
    for(int i = 0;i<g[start].size();i++){
        if (!vis[g[start][i]])DFS(g[start][i]);
    }
}
void BFS(int x){
    queue<int>q;
    q.push(x);
    vis[x] = 1;
    while(!q.empty()){
        int f = q.front();
        q.pop();
        countn ++;
        printf("%d ",f);
//        if (countn < n) printf(" ");
//        else printf("\n");
        for(int i = 0;i<g[f].size();i++){
            if (!vis[g[f][i]]) {
                q.push(g[f][i]);
                vis[g[f][i]] = 1;
            }
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(;m;m--){
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
    }
    for(int i = 1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
    }
    DFS(1);
    init();
    printf("\n");
    BFS(1);
    return 0;
}

6 食物链 TODO

# include <cstdio>
# include <vector>
using namespace std;
# define maxn 5005
int isbegin[maxn] = {},isend[maxn] = {},vis[maxn] = {},c[maxn][maxn] = {},n,m,a,b,countn = 0;
vector<int>g[maxn],hashbegin,hashend;

int DFS(int start,int end){
    if (c[start][end]) return c[start][end];
    int res = 0;
    if (start == end) {res = 1;}
    else{
        for(int i = 0;i<g[start].size();i++){
            if (!vis[g[start][i]]){
                vis[g[start][i]] = 1;
                res += DFS(g[start][i],end);
                vis[g[start][i]] = 0;
            }
        }
    }
    res %= 80112002;
    c[start][end] = res;
    return res;
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++){
        isbegin[i] = 1;
        isend[i] = 1;
    }
    for(;m;m--){
        scanf("%d %d",&a,&b);
        isbegin[a] = 0;
        isend[b] = 0;
        g[b].push_back(a);
    }
    for(int i = 1;i<=n;i++)if(isbegin[i])hashbegin.push_back(i);
    for(int i = 1;i<=n;i++)if(isend[i])hashend.push_back(i);

    for(int i = 0;i<hashbegin.size();i++){
        for(int j = 0;j<hashend.size();j++){
            for(int i = 0;i<=n;i++)vis[i] = 0;
            countn += DFS(hashbegin[i],hashend[j]);
        }
    }
    printf("%d",countn%80112002);
    return 0;
}

7 围棋 AC

# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int g[102][102] = {},ori[102][102] = {};
int n;
char c;
void DFS(int x,int y,int color){
    for(int i = 0;i<4;i++){
        int nx = x+dir[i][0], ny = y + dir[i][1];
        if (nx >=0 && ny >= 0 && nx <n && ny < n && g[nx][ny] == 0)
        {g[nx][ny] = color;DFS(nx,ny,color);}
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%*c");
        for(int j = 0;j<n;j++){
            scanf("%c",&c);
            if (c == 'B'){g[i][j] = 2;ori[i][j] = 1;}
            else if (c == 'W'){g[i][j] = 1;ori[i][j] = 1;}
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if (ori[i][j])DFS(i,j,g[i][j]);
        }
    }
//    for(int i = 0;i<n;i++){
//        for(int j = 0;j<n;j++){
//            printf("%d",g[i][j]);
//        }printf("\n");
//    }
    int count = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if (g[i][j] == 2)count ++;
        }
    }
    printf("%d %d",count,n*n-count);
    return 0;
}

8 DFS AC

# include <cstdio>
int g[101][101] = {},vis[101][101] = {};
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n,m,k,x,y,tempsum = 0,maxsum = 0;
void DFS(int x,int y){
    vis[x][y] = 1;
    for(int i = 0;i<4;i++){
        int nx = x + dir[i][0],ny = y + dir[i][1];
        if (nx > 0 && ny > 0 && nx <= n && ny <= m && vis[nx][ny] == 0 && g[nx][ny] == 1){
            tempsum ++;
            DFS(nx,ny);
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 0;i<k;i++){
        scanf("%d %d",&x,&y);
        g[x][y] = 1;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if (g[i][j] == 1 && vis[i][j] == 0){
                tempsum = 1;
                DFS(i,j);
                maxsum = maxsum>tempsum?maxsum:tempsum;
            }
        }
    }
    printf("%d",maxsum);
    return 0;
}

9 拓扑排序 WA TODO

# include <cstdio>
# include <vector>
using namespace std;
const int maxn = 50005;
vector<int>fa[maxn];
int w[maxn] = {},res[maxn] = {},maxres[maxn] = {},r = 0;
int n,temp;
void DFS(int x){
    for(int i = 0;i<fa[x].size();i++){
        res[fa[x][i]] += res[x];
        if (res[fa[x][i]] > maxres[fa[x][i]]){
            maxres[fa[x][i]] = res[fa[x][i]];
            DFS(fa[x][i]);
        }
        res[fa[x][i]] -= res[x];
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%d",&temp);
        scanf("%d",&w[i]);
        res[i] = w[i];
        maxres[i] = w[i];
        scanf("%d",&temp);
        while(temp){
            fa[i].push_back(temp);
            scanf("%d",&temp);
        }
    }
    DFS(n);
//    for(int i = 1;i<=n;i++){
//        printf("%d ",res[i]);
//    }printf("\n");
//    for(int i = 1;i<=n;i++){
//        printf("%d ",maxres[i]);
//    }
    int maxmax = 0;
    for(int i = 1;i<=n;i++){
        maxmax = maxmax > maxres[i] ? maxmax : maxres[i];
    }
    printf("%d",maxmax);
    return 0;
}

简单模拟

1 覆盖地毯 AC

从后往前,有覆盖就输出

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

2 多项式输出 AC

分类讨论模拟

# include <cstdio>
int main(){
    int n,k[101],sgn = 0;
    scanf("%d",&n);
    for(int i = n;i>=0;i--)scanf("%d",&k[i]);
    for(int i = n;i>1;i--){
        if (k[i] > 0){
            if (sgn == 0){
                sgn = 1;
                if (k[i] == 1)printf("x^%d",i);
                else printf("%dx^%d",k[i],i);
            }else{
                if (k[i] == 1)printf("+x^%d",i);
                else printf("+%dx^%d",k[i],i);
            }
        }else if (k[i] < 0){
            sgn = 1;
            if (k[i] == -1)printf("-x^%d",i);
            else printf("%dx^%d",k[i],i);
        }
    }
    if (k[1] > 0){
        if (sgn == 0){
            sgn = 1;
            if (k[1] == 1)printf("x");
            else printf("%dx",k[1]);
        }else{
            if (k[1] == 1)printf("+x");
            else printf("+%dx",k[1]);
        }
    }else if (k[1] < 0){
        sgn = 1;
        if (k[1] == -1)printf("-x");
        else printf("%dx",k[1]);
    }
    if (k[0] > 0){
        if (sgn == 0){
            printf("%d",k[0]);
        }else{
            printf("+%d",k[0]);
        }
    }else if (k[0] < 0){
        printf("%d",k[0]);
    }
    return 0;
}

3 FIFO 内存置换 AC

# include <cstdio>
# include <queue>
using namespace std;
int n,m,t,inmem[1005] = {};
queue<int>q;
int main(){
    scanf("%d %d",&m,&n);
    int count = 0;
    for(int i = 0;i<n;i++){
        scanf("%d",&t);
        if (!inmem[t]){
            count ++;
            if (q.size() < m){
                q.push(t);
                inmem[t] = 1;
            }else{
                int k = q.front();
                q.pop();
                q.push(t);
                inmem[k] = 0;
                inmem[t] = 1;
            }
        }
    }
    printf("%d",count);
    return 0;
}

4 排座椅 AC

# include <cstdio>
# include <algorithm>
# include <vector>
# define min(a,b) (a)>(b)?(b):(a)
using namespace std;
int m,n,k,l,d,x1,x2,y1,y2,x[1005] = {},y[1005] = {};
struct node{
    int x,i;
    node(int _x,int _i):x(_x),i(_i){}
};
bool cmp(node a,node b){return a.x > b.x;}
int main(){
    scanf("%d %d %d %d %d",&m,&n,&k,&l,&d);
    for(;d;d--){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        if (x1 == x2) y[min(y1,y2)]++;
        else if (y1 == y2) x[min(x1,x2)]++;
    }
    vector<node>xn;
    vector<node>yn;
    for(int i = 0;i<n;i++){
        if (x[i])xn.push_back(node(x[i],i));
        if (y[i])yn.push_back(node(y[i],i));
    }
    sort(xn.begin(),xn.end(),cmp);
    sort(yn.begin(),yn.end(),cmp);
    
    // 最后输出还要按照 id 排序
    int resx[1005],resy[1005];
    for(int j = 0;j<k;j++){
        resx[j] = xn[j].i;
    }
    for(int j = 0;j<l;j++){
        resy[j] = yn[j].i;
    }
    sort(resx,resx+k);
    sort(resy,resy+l);
    for(int j = 0;j<k;j++){
        printf("%d",resx[j]);
        if (j < k-1) printf(" ");
    }printf("\n");
    for(int j = 0;j<l;j++){
        printf("%d",resy[j]);
        if (j < l-1) printf(" ");
    }
    return 0;
}

5 水模拟 AC

# include <cstdio>
int n,na,nb,a[200],b[200],resa = 0,resb = 0;
void get(int a,int b){
//    printf("%d %d\n",a,b);
    if ((a == 0 && b == 2)||(a == 0 && b == 3)||(a == 1 && b == 3)||(a == 2 && b == 4)||(a == 3 && b == 4)||(a == 1 && b == 0)||(a == 2 && b == 1)||(a == 3 && b == 2)||(a == 4 && b == 1)||(a == 4 && b == 0)){
        resa += 1;
    }else if ( a != b ){
        resb ++;
    }
}
int main(){
    scanf("%d %d %d",&n,&na,&nb);
    for (int i = 0;i<na;i++)scanf("%d",&a[i]);
    for (int i = 0;i<nb;i++)scanf("%d",&b[i]);
    for (int i = 0;i<n;i++){
        get(a[i%na],b[i%nb]);
    }
    printf("%d %d",resa,resb);
    return 0;
}

6 水模拟 AC

# include <cstdio>
int lr[100002],n,m,pos = 0,t,l;
char na[100002][22];
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++)scanf("%d %s",&lr[i],na[i]);
    for(int i = 0;i<m;i++){
        scanf("%d %d",&t,&l);
        if (t == lr[pos])pos = (pos + n - l)%n;
        else pos = (pos + n + l)%n;
    }
    printf("%s",na[pos]);
    return 0;
}

7 乒乓 AC

别忘了只输入一个 E 的情况

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

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
char c[70000],temp;
int w = 0,e = 0;
void end11(){
    if ((w >= 11 || e >= 11) && abs(w-e) >= 2){
        printf("%d:%d\n",w,e);
        w = 0;
        e = 0;
    }
}
void end21(){
    if ((w >= 21 || e >= 21) && abs(w-e) >= 2){
        printf("%d:%d\n",w,e);
        w = 0;
        e = 0;
    }
}
int main(){
    int i = 0;
    while(scanf("%c",&temp)){
        if (temp == 'W' ||temp =='L') c[i++] = temp;
        else if (temp == 'E')break;
    }
//    printf("%s",c);
    if (strlen(c) == 0)printf("0:0\n\n0:0");
    for (int i = 0;i<strlen(c);i++){
        if (c[i] == 'W')w++;
        else e++;
        end11();
        if (i == strlen(c)-1){
            printf("%d:%d\n",w,e);
            w = 0;
            e = 0;
        }
    }printf("\n");
    for (int i = 0;i<strlen(c);i++){
        if (c[i] == 'W')w++;
        else e++;
        end21();
        if (i == strlen(c)-1){
            printf("%d:%d\n",w,e);
            w = 0;
            e = 0;
        }
    }
    return 0;
}

8 扫雷 AC

# include <cstdio>
# include <cstring>
int m,n;
char in[105][106];
int get(int x,int y){
    int count = 0;
    if (x-1 >= 0 && y-1 >= 0 && in[x-1][y-1] == '*')count ++;
    if (x-1 >= 0 && in[x-1][y] == '*')count ++;
    if (x-1 >= 0 && y+1 < n && in[x-1][y+1] == '*')count ++;
    if (x+1 < n && y+1 < n && in[x+1][y+1] == '*')count ++;
    if (x+1 < n && in[x+1][y] == '*')count ++;
    if (x+1 < n && y-1 >= 0 && in[x+1][y-1] == '*')count ++;
    if (y+1 < n && in[x][y+1] == '*')count ++;
    if (y-1 < n && in[x][y-1] == '*')count ++;
    return count;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%*c");
        for(int j = 0;j<m;j++){
            scanf("%c",&in[i][j]);
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if (in[i][j] != '*')printf("%d",get(i,j));
            else printf("*");
        }
        printf("\n");
    }
    return 0;
}

9 高精阶乘 AC

#2020-03-12 08:52:28

n = int(input())
res = 0
for i in range(1,n+1):
    now = 1
    for j in range(1,i+1):
        now = now*j
    res += now
    # print(now)
print(res)

10 旋转 WA TODO

# include <cstdio>
int a[505][505] = {},n,m,x,y,r,z;
int main(){
    scanf("%d %d",&n,&m);
    int count = 1;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            a[i][j] = count ++;
    for(;m;m--){
        int temp[505][505] = {};
        scanf("%d %d %d %d",&x,&y,&r,&z);
//        printf("%d-%d-%d-%d\n",x,y,r,z);
        if (z == 0){
            for(int i = 0;i<=r*2;i++){
                for(int j = 0;j<=r*2;j++){
                    temp[j+x-r][x+r-i] = a[i+x-r][j+x-r];}}}
        else{
            for(int i = 0;i<=r*2;i++){
                for(int j = 0;j<=r*2;j++){
                    temp[x+r-j][i+x-r] = a[i+x-r][j+x-r];}}}
        
        for(int i = 0;i<=r*2;i++){
            for(int j = 0;j<=r*2;j++){
                a[i+x-r][j+x-r] = temp[i+x-r][j+x-r];}}
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            printf("%d",a[i][j]);
            if (j < n)printf(" ");
        }
        printf("\n");
    }
    return 0;
}

11 找牛模拟 AC

// # 2020-03-13 08:32:40

# include <cstdio>
# include <cstring>

char g[11][11];
int cx,cy,fx,fy,countc = 0,countf = 0,count = 0;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}},v[21][21][4][21][21][4] = {};

int main(){
    for(int i = 0;i<10;i++){
        // Windows换行符是两个,因此要用 %s 输入,避免麻烦
        scanf("%s",g[i]);
        for(int j = 0;j<10;j++){
            if (g[i][j] == 'C') {
                cx = i;
                cy = j;
            }
            if (g[i][j] == 'F') {
                fx = i;
                fy = j;
            }
        }
//        scanf("%*c");
    }
    int sgn = 0;
    while(1){
//        printf("((%d-%d)(%d-%d))",cx,cy,fx,fy);
        count ++;
        if (v[cx][cy][countc][fx][fy][countf] == 1){
            printf("%d",0);
            return 0;
        }
        v[cx][cy][countc][fx][fy][countf] ++;
        int ccx = cx + dir[countc][0],ccy = cy + dir[countc][1],ffx = fx + dir[countf][0],ffy = fy + dir[countf][1];
        if (ccx >= 0 && ccx < 10 && ccy >= 0 && ccy < 10 && g[ccx][ccy] != '*'){
            cx = ccx;
            cy = ccy;
            sgn++;
        }else countc = (countc+1)%4;
        if (ffx >= 0 && ffx < 10 && ffy >= 0 && ffy < 10 && g[ffx][ffy] != '*'){
            fx = ffx;
            fy = ffy;
            sgn++;
        }else countf = (countf+1)%4;
        if (cx == fx && cy == fy){
            printf("%d\n",count);
            return 0;
        }
//        if ((g[cx][cy] == 'C' && g[fx][fy] == 'F') && sgn > 4){
//            printf("%d",0);
//            return 0;
//        }
    }
    return 0;
}

12 数方块 AC

# include <cstdio>
# define LL long long
int main(){
    LL n,m;
    scanf("%lld %lld",&n,&m);
    LL s = n*(n+1)*m*(m+1)/4;
    LL a = m>n?m:n,b = m<n?m:n;
    LL sum = 0;
    for(LL i = 1;i<=b;i++){
        sum += (a+1-i)*(b+1-i);
    }
    printf("%lld %lld",sum,s-sum);
    return 0;
    
}

13 涂国旗 AC

# include <cstdio>
# include <cstring>
char c[50];
int n,m,a[55][3] = {};
int get(int i,int j){
    int res = 0;
    for(int p = 0;p<i;p++)res += a[p][0];
    for(int p = i;p<j;p++)res += a[p][1];
    for(int p = j;p<n;p++)res += a[p][2];
//    printf("res=%d,",res);
    return res;

}
int main(){
    scanf("%d %d%*c",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%s",c);
        for(int j = 0;j<m;j++){
            if (c[j] != 'W')a[i][0] ++;
            if (c[j] != 'B')a[i][1] ++;
            if (c[j] != 'R')a[i][2] ++;
        }
    }
//    for(int i = 0;i<n;i++)printf("%d %d %d\n",a[i][0],a[i][1],a[i][2]);
    int sum = 0xffffff;
    for(int i = 1;i<n-1;i++){
        for(int j = i+1;j<n;j++){
            int s = get(i,j);
            sum = sum<s?sum:s;
        }
    }
    printf("%d",sum);
    return 0;
}

14 站队枚举 AC

# include <cstdio>
# include <cstring>
int a[105][105] = {},r,c,k,count = 0;
char ch[105];
int main(){
    scanf("%d %d %d%*c",&r,&c,&k);
    for(int i = 0;i<r;i++){
        scanf("%s",ch);
        for(int j = 0;j<c;j++){
            if (ch[j] == '#') a[i][j] = 1;
        }a[i][c] = 1;
    }
    // 外圈包围 1
    for(int j = 0;j<=c;j++)a[r][j] = 1;
    
//    for(int i = 0;i<r;i++){
//        for(int j = 0;j<c;j++){
//            printf("%d ",a[i][j]);
//        }
//        printf("\n");
//    }
    // 行
    for (int i = 0;i<r+1;i++){
        int start = -1;
        for(int j = 0;j<c+1;j++){
            if(a[i][j]){
                int end = j;
                int p = end - start - 1;
                if(p-(k-1) > 0){
//                    printf("+++%d %d %d %d\n",i,start,end,p);
                    count += (p-(k-1));}
                start = j;
            }
        }
//        printf("%d-",count);
    }
    // 列
    if(k != 1){ // 如果是一个人,行列就重复了
        for (int i = 0;i<c+1;i++){
            int start = -1;
            for(int j = 0;j<r+1;j++){
                if(a[j][i]){
                    int end = j;
                    int p = end - start - 1;
                    if(p-(k-1) > 0){
                        //                    printf("+++%d %d %d %d\n",i,start,end,p);
                        count += (p-(k-1));}
                    start = j;
                }
            }
        }
    }
   
    printf("%d",count);

    return 0;
}

15 回文质数 AC

# include <cstdio>
# include <cmath>
# include <string>
# include <algorithm>
using namespace std;
int a,b,prime[100000000] = {2,3,5};
bool isp(int x){
    for(int i = 0;prime[i] <= sqrt(x);i++){
        if (x%prime[i] == 0)return false;
    }
    return true;
}
void get(int b){
    int count = 3;
    for(int i = 7;i<b;i++){
        if (isp(i)) prime[count++] = i;
    }
}
bool ishw(int x){
    string t = to_string(x);
    string u = t;
    reverse(t.begin(), t.end());
    return t == u;
}
int main(){
    scanf("%d %d",&a,&b);
//    get(b);
//    for (int i = 0;prime[i] != 0;i++){
//        if (prime[i] >= a && ishw(prime[i])) printf("%d,",prime[i]);
//    }
    int res[10000] = {5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
    for(int i = 0;res[i] <= b;i++){
        if (res[i] >= a)printf("%d\n",res[i]);
    }
}

16 火柴棒等式 AC

# include <cstdio>
int num[10] = {6,2,5,5,4,5,6,3,7,6},n,a,b,c;
int getuse(int x){
    if (x == 0)return 6;
    int res = 0;
    while (x != 0){
        int p = x%10;
        x /= 10;
        res += num[p];
    }
    return res;
}
int main(){
    scanf("%d",&n);
    n-=4;
    int r = 0;
    for(int i = 0;i<1000;i++){
        for(int j = 0;j<1000;j++){
            if (getuse(i)+getuse(j)+getuse(i+j) == n){
                r++;
//                printf("%d+%d=%d (%d)(%d)(%d)\n",i,j,i+j,getuse(i),getuse(j),getuse(i+j));
            }
        }
    }
    printf("%d",r);
    return 0;
}

17 凑等边三角形 AC

# include <cstdio>
int n,hash[5004] = {},t;
long long res = 0;
int main(){
    scanf("%d",&n);
    for(;n;n--){
        scanf("%d",&t);
        hash[t] ++;
    }
    for(int i = 1;i<2505;i++){
        for(int j = i;i+j<5001;j++){
            if (hash[i+j] > 1 && hash[i] > 0 && hash[j] > 0){
                if (i != j)
                    res += (hash[i] * hash[j] * hash[i+j] * (hash[i+j]-1) /2);
                else res += (hash[i] * (hash[j]-1) * hash[i+j] * (hash[i+j]-1) /4);
            }
        }
    }
    printf("%lld",res%(1000000007));
}

字符串处理

1 水 AC

# 2020-03-05 14:23:32

ch = input().split(" ")
num = ["","one", "two", "three", "four", "five", "six", "seven", "eight", "nine", 'ten', 'eleven', "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty"]
res = []
ii = [0]*21
def get(i):
    if ii[i] != 0:
        return ii[i]
    else:
        ii[i] = pow(i,2,100)
        return ii[i]

for w in ch:
    for i in range(1,21):
        if num[i] == w:
            res.append("%02d"%get(i))
            break
        elif w == 'a' or w == 'another' or w == 'first':
            res.append("01")
            break
        elif w == 'both' or w == 'second':
            res.append("04")
            break
        elif w == 'third':
            res.append("09")
            break
if len(res) == 0:
    print(0)
else:
    res.sort()
    r = ''
    for i in range(len(res)):
        r += res[i]
    print(int(r))

python 结构体排序:


>>> student_tuples = [
        ('john', 'A', 15),
        ('jane', 'B', 12),
        ('dave', 'B', 10),
]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

2 字符串计数 + 质数判断 AC

# include <cstdio>
# include <cstring>
int hashtable[26] = {}, prime[8] = {2,3,5,7,11,13,17,19};
char c[200];
bool isprime(int res){
    if (res == 1)return false;
    int sgn = 1;
    for(int i = 0;i<8;i++){
        if (res != prime[i] && res % prime[i] == 0)sgn = 0;
    }
    return sgn;
}
int main(){
    scanf("%s",c);
    for(int i = 0;i<strlen(c);i++){
        hashtable[int(c[i]-'a')]++;
    }
    int ma = -1,mi = 200;
    for(int i = 0;i<26;i++){
        if (hashtable[i] != 0){
            if (ma < hashtable[i])ma = hashtable[i];
            if (mi > hashtable[i])mi = hashtable[i];
        }
    }
    int res = ma - mi;
//    int res = 0;
//    scanf("%d",&res);
    if (isprime(res))printf("Lucky Word\n%d",res);
    else printf("No Answer\n0");
    return 0;
}

3 split + len AC

n = int(input())
typ = 0
cc = ""
for i in range(n):
    c = input().split(" ")
    if len(c) == 3:
        if c[0] == 'a':
            typ = 1
        elif c[0] == 'b':
            typ = 2
        elif c[0] == 'c':
            typ = 3
        if (typ == 1):
            cc = ("%d+%d=%d" % (int(c[1]),int(c[2]),int(c[1])+int(c[2])))
        elif (typ == 2):
            cc = ("%d-%d=%d" % (int(c[1]),int(c[2]),int(c[1])-int(c[2])))
        elif (typ == 3):
            cc = ("%d*%d=%d" % (int(c[1]),int(c[2]),int(c[1])*int(c[2])))
    elif len(c) == 2:
        if (typ == 1):
            cc = ("%d+%d=%d" % (int(c[0]),int(c[1]),int(c[1])+int(c[0])))
        elif (typ == 2):
            cc = ("%d-%d=%d" % (int(c[0]),int(c[1]),int(c[0])-int(c[1])))
        elif (typ == 3):
            cc = ("%d*%d=%d" % (int(c[0]),int(c[1]),int(c[1])*int(c[0])))
    print(cc + "\n" + str(len(cc)))

4 字符串计数 AC

import re

a = input().lower()
b = input().lower()
lb = b.split(" ")
count = 0
for i in range(len(lb)):
    if a == lb[i]:
        count += 1
if count > 0:
    pos = lb.index(a)
    index = 0
    for i in range(pos):
        index += len(lb[i]) + 1
    print(str(count) + ' ' + str(index))
else:
    print(-1)

5 反转数字 AC

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

char c[30];
char a[30],b[30];
int typ = 0;

int get(char c[]){
    int i = 0;
    for(;i<strlen(c);i++){
        if (c[i] == '.'){typ = 1;return i;}
        if (c[i] == '/'){typ = 2;return i;}
        if (c[i] == '%'){typ = 3;return i;}
        a[i] = c[i];
    }
    return i;
}
void printa(char c[]){
    int sgn = 1;
    for(int i = 0;i<strlen(c);i++){
        if (c[i] != '0')sgn = 0;
        if (sgn == 0)printf("%c",c[i]);
    }
    if(sgn == 1)printf("0");    //整数部分为 0 没有考虑
}

int mzero(char c[]){
    for(int i = 0;i<strlen(c);i++){
        if (c[i] != '0')return i;
    }
    return (int)strlen(c);
}

int main(){
    scanf("%s",c);
    int pos = get(c);
    if (typ == 0){
        reverse(a, a+pos);
        printa(a);
    }
    else if (typ == 1){
        reverse(a,a+pos);
        for(int i = pos+1;i<strlen(c);i++) b[i-pos-1] = c[i];
        int bpos = mzero(b);
        reverse(b+bpos,b+strlen(b));
//        printf("%s",a);
        printa(a);
        printf(".");
        if (bpos == strlen(b))printf("0");
        else
            for(int i = bpos;i<strlen(b);i++)
                printf("%c",b[i]);
    }
    else if (typ == 2){
        reverse(a,a+pos);
        for(int i = pos+1;i<strlen(c);i++) b[i-pos-1] = c[i];
        reverse(b,b+strlen(b));
        printa(a);
        printf("/");
        printa(b);  // 小数和分数也是不同的!
    }else if (typ == 3){
        reverse(a, a+pos);
        printa(a);
        printf("%%");
    }
}

6 字符串树状图 AC

# include <cstdio>
# include <cstring>
# include <iostream>
using namespace std;
char c[105];
int hashtable[26] = {};
int main(){
    for (int ii = 0;ii < 4;ii ++){
        cin.getline(c,105);
//        printf("%d %s\n",ii,c);
        for(int i = 0;i<strlen(c);i++){
            if (c[i] != ' ')hashtable[c[i] - 'A'] ++;
        }
    }
    int maxcount = 0;
    for(int i = 0;i<26;i++){
//        printf("%d ",hashtable[i]);
        maxcount = maxcount < hashtable[i]?hashtable[i]:maxcount;
    }
    for(int i = 0;i<maxcount;i++){
        for(int j = 0;j<26;j++){
            if (hashtable[j] < maxcount - i)printf(" ");
            else printf("*");
            if (j < 25)printf(" ");
        }
        printf("\n");
    }
    for(int i = 0;i<26;i++){
        printf("%c",'A' + i);
        if (i < 25)printf(" ");
    }
}

搜索

1 暴力 AC

# include <cstdio>
int n,start[10005] = {},count = 0,vis[102][102] = {};
char a[102][102];

void DFS(int start){
    int x = start/n,y = start%n;
    if (x + 6 < n && y + 6 <n)
        if (a[x+1][y+1] == 'i' && a[x+2][y+2] == 'z' && a[x+3][y+3] == 'h' && a[x+4][y+4] == 'o' && a[x+5][y+5] == 'n' && a[x+6][y+6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x+i][y+i] = 1;
    if (x - 6 >= 0 && y - 6 >= 0)
        if (a[x-1][y-1] == 'i' && a[x-2][y-2] == 'z' && a[x-3][y-3] == 'h' && a[x-4][y-4] == 'o' && a[x-5][y-5] == 'n' && a[x-6][y-6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x-i][y-i] = 1;
    if (x - 6 >= 0 && y + 6 < n)
        if (a[x-1][y+1] == 'i' && a[x-2][y+2] == 'z' && a[x-3][y+3] == 'h' && a[x-4][y+4] == 'o' && a[x-5][y+5] == 'n' && a[x-6][y+6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x-i][y+i] = 1;
    if (x + 6 < n && y - 6 >= 0)
        if (a[x+1][y-1] == 'i' && a[x+2][y-2] == 'z' && a[x+3][y-3] == 'h' && a[x+4][y-4] == 'o' && a[x+5][y-5] == 'n' && a[x+6][y-6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x+i][y-i] = 1;
    if (x - 6 >= 0)
        if (a[x-1][y] == 'i' && a[x-2][y] == 'z' && a[x-3][y] == 'h' && a[x-4][y] == 'o' && a[x-5][y] == 'n' && a[x-6][y] == 'g')
            for (int i = 0;i<7;i++)
                vis[x-i][y] = 1;
    if (x + 6 < n)
        if (a[x+1][y] == 'i' && a[x+2][y] == 'z' && a[x+3][y] == 'h' && a[x+4][y] == 'o' && a[x+5][y] == 'n' && a[x+6][y] == 'g')
            for (int i = 0;i<7;i++)
                vis[x+i][y] = 1;
    if (y + 6 < n)
        if (a[x][y+1] == 'i' && a[x][y+2] == 'z' && a[x][y+3] == 'h' && a[x][y+4] == 'o' && a[x][y+5] == 'n' && a[x][y+6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x][y+i] = 1;
    if (y - 6 >= 0)
        if (a[x][y-1] == 'i' && a[x][y-2] == 'z' && a[x][y-3] == 'h' && a[x][y-4] == 'o' && a[x][y-5] == 'n' && a[x][y-6] == 'g')
            for (int i = 0;i<7;i++)
                vis[x][y-i] = 1;
}

int main(){
    scanf("%d",&n);
    for (int i = 0;i<n;i++){
        scanf("%s",a[i]);
        for (int j = 0;j<n;j++){
            if (a[i][j] == 'y'){
                start[count++] = n*i+j;
            }
        }
//        scanf("%*c");
    }
    for (int i = 0;i<count;i++){
        DFS(start[i]);
    }
    for (int i = 0;i<n;i++){
        for (int j = 0;j<n;j++){
            if (vis[i][j] == 1){
                printf("%c",a[i][j]);
            }else{
                printf("*");
            }
        }
        printf("\n");
    }
    return 0;
}

2 DFS基础 AC

DFS 步骤:

判断是否到达终点
循环「下一步」
    vis++
    走下一步
    vis--
# include <cstdio>
int g[6][6] = {},vis[6][6] = {},count = 0;
int n,m,t,sx,sy,ex,ey,tx,ty;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void DFS(int x,int y){
    if (x == 0 || y == 0 || x > n || y > m)return;
    if (x == ex && y == ey){
        count++;
        return;
    }
    for (int i = 0;i<4;i++){
        if (vis[x+dir[i][0]][y+dir[i][1]] == 0 && g[x+dir[i][0]][y+dir[i][1]] == 0){
            vis[x][y] = 1;
            DFS(x+dir[i][0],y+dir[i][1]);
            vis[x][y] = 0;

        }
    }
}

int main(){
    scanf("%d %d %d",&n,&m,&t);
    scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
    for (;t;t--){
        scanf("%d %d",&tx,&ty);
        g[tx][ty] = 1;
    }
    DFS(sx, sy);
    printf("%d",count);
    return 0;
}

DFS 模板:

int search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i++)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t+1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
}

3 数组染色 AC

逆向思维:从四周开始,BFS 染色题目不要求的0,最后反着输出即可

BFS注意数组下标要先判断

# include <cstdio>
# include <queue>
using namespace std;
int g[51][51] = {},vis[51][51] = {};
int n;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
struct point{
    int x,y;
    point(int _x,int _y):x(_x),y(_y){}
};
void BFS(int x,int y){
    vis[x][y] = 1;
    queue<point>q;
    q.push(point(x,y));
    while(!q.empty()){
        point top = q.front();
        q.pop();
        for (int i = 0;i<4;i++){
            if (top.x+dir[i][0] > 0 && top.x+dir[i][0] < n && top.y+dir[i][1] > 0 && top.y+dir[i][1] < n && vis[top.x+dir[i][0]][top.y+dir[i][1]] == 0 && g[top.x+dir[i][0]][top.y+dir[i][1]] == 0){
                q.push(point(top.x+dir[i][0],top.y+dir[i][1]));
                vis[top.x+dir[i][0]][top.y+dir[i][1]] =1;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        for (int j = 0;j<n;j++){
            scanf("%d",&g[i][j]);
        }
    }
    for (int i = 0;i<n;i++){
        if (vis[i][0] == 0 && g[i][0] == 0) BFS(i,0);
        if (vis[i][n-1] == 0 && g[i][n-1] == 0) BFS(i,n-1);
        if (vis[0][i] == 0 && g[0][i] == 0) BFS(0,i);
        if (vis[n-1][i] == 0 && g[n-1][i] == 0) BFS(n-1,i);
    }
    for (int i = 0;i<n;i++){
        for (int j = 0;j<n;j++){
            if (vis[i][j] == 1) printf("0");
            else if (g[i][j]  == 1) printf("1");
            else if (g[i][j]  == 0) printf("2");
            if (j < n-1)printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

4 01迷宫 WA


# include <cstdio>
# include <queue>
using namespace std;
const int maxn = 1005;
// g 存迷宫,vis 存每次 BFS 的是否访问,res 存每个点的联通结果,就不用每次都 BFS 了
int g[maxn][maxn] = {}, res[maxn][maxn] = {};
int n,m,x,y;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

struct node{
    int x,y;
    node(int _x,int _y):x(_x),y(_y){}
};

int BFS(int x,int y){
    if (res[x][y] != 0) return res[x][y];
    int vis[maxn][maxn] = {};
    vis[x][y] = 1;
    queue<node>q;
    q.push(node(x,y));
    while(!q.empty()){
        node top = q.front();
        q.pop();
        vis[top.x][top.y] = 1;
        for (int i = 0;i<4;i++){
            if (top.x + dir[i][0] >= 0 && top.x + dir[i][0] <n
                && top.y + dir[i][1] >= 0 && top.y + dir[i][1] <n
                && g[top.x][top.y] != g[top.x + dir[i][0]][top.y + dir[i][1]]
                && vis[top.x + dir[i][0]][top.y + dir[i][1]] == 0)
                q.push(node(top.x + dir[i][0],top.y + dir[i][1]));
        }
    }
    int count = 0;
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            if (vis[i][j] == 1) count ++;
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            if (vis[i][j] == 1) res[i][j] = count;
    return count;
}

int main(){
    scanf("%d %d",&n,&m);
    char t;
    for (int i = 0;i<n;i++){
        scanf("%*c");
        for (int j = 0;j<n;j++){
            scanf("%c",&t);
            if (t == '0')g[i][j] = 0;
            else g[i][j] = 1;
        }
    }

    for (;m;m--){
        scanf("%d %d",&x,&y);
        int aa = BFS(x-1,y-1);
        printf("%d\n",aa);

//        for(int i = 0;i<n;i++){
//            printf("\n");
//            for(int j = 0;j<n;j++)
//                printf("%3d ",res[i][j]);
//            }
//        printf("\n");
        
    }
    return 0;
}

5 马的遍历 AC

带深度的 BFS

// 2020-03-07 08:12:16
# include <cstdio>
# include <queue>
using namespace std;

int x,y,a,b,g[401][401] = {};
int dir[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};

struct node{
    int x,y,depth;
    node(int _x,int _y,int _d):x(_x),y(_y),depth(_d){}
};

int main(){
    scanf("%d %d %d %d",&x,&y,&a,&b);
    for (int i = 0;i<x;i++)
        for(int j = 0;j<y;j++)
            g[i][j] = -1;
    int step = 0;
    g[a-1][b-1] = 0;
    queue<node>q;
    q.push(node(a-1,b-1,0));
    while(!q.empty()){
        int topx = q.front().x,topy = q.front().y,d = q.front().depth;
        q.pop();
        step = d+1;
        for (int i = 0;i<8;i++){
            if (topx+dir[i][0] < x && topx+dir[i][0] >= 0 &&
                topy+dir[i][1] < y && topy+dir[i][1] >= 0 &&
                g[topx+dir[i][0]][topy+dir[i][1]] == -1){
                g[topx+dir[i][0]][topy+dir[i][1]] = step;
                q.push(node(topx+dir[i][0],topy+dir[i][1],step));
            }
        }
    }
    for(int i = 0;i<x;i++){
        for(int j = 0;j<y;j++){
            printf("%-5d",g[i][j]);
        }
        printf("\n");
    }
    return 0;
}

6 数字三角 AC

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

int n,ssum,a[15][15] = {1,1,1,1,1};
int num[15];

void print(){
    for (int i = 1;i<=n;i++){
        printf("%d",num[i]);
        if (i < n)printf(" ");
    }
}

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

int get(){
    int sum = 0;
    for(int i = 0;i<=n;i++){
        sum += num[i] * a[n][i];
        if (sum > ssum){
            sort(num+i,num+n+1,cmp);
            // 将后面从大到小排序,jiu那么 next_permutation 的值就变小了
            return 999999;
        }
    }
//    print();
//    printf("\n%d\n",sum);
    return sum;
}

int main(){
    scanf("%d %d",&n,&ssum);
    for (int i = 1;i<=n;i++){
        for(int j = 1;j<i;j++){
            a[i][j] = a[i-1][j] + a[i-1][j-1];
        }
        a[i][i] = 1;
    }
    int fi[n+1];
    for (int p = 0;p<=n;p++)fi[p] = a[n][p];
    for (int i = 0;i<=n;i++)num[i] = i;
    
//    mmin 跟 mmax 搞反了
    sort(fi+1,fi+n+1);
    int mmin = 0;
    for(int i = 0;i<=n;i++)
        mmin += num[i] * fi[i];
//    printf("mmin=%d\n",mmin);
    int mmax = 0;
    for(int i = 0;i<=n;i++)
        mmax += num[n+1-i] * fi[i];
//    printf("mmax=%d\n",mmax);

    if (ssum < mmax || ssum > mmin)return 0;
    
    do{
        int now = get();
        if (now == ssum) {print();return 0;}
    }while(next_permutation(num+1, num+n+1));
    return 0;
    
}

7 记忆化 DFS AC

// 2020-03-08 08:51:00

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

int r,c,g[101][101],vis[101][101] = {},res[101][101] = {};
int mmax = 0,maxl = 0;

int DFS(int x,int y,int depth){
    if (res[x][y])return res[x][y];
    res[x][y] = 1;
    if (x+1 < r && g[x+1][y] < g[x][y]) {
        DFS(x+1,y,depth+1);
        res[x][y] = max(res[x][y],res[x+1][y] + 1);
    }
    if (y+1 < c && g[x][y+1] < g[x][y]) {
        DFS(x,y+1,depth+1);
        res[x][y] = max(res[x][y],res[x][y+1] + 1);
    }
    if (x-1 >= 0 && g[x-1][y] < g[x][y]) {
        DFS(x-1,y,depth+1);
        res[x][y] = max(res[x][y],res[x-1][y] + 1);
    }
    if (y-1 >= 0 && g[x][y-1] < g[x][y]) {
        DFS(x,y-1,depth+1);
        res[x][y] = max(res[x][y],res[x][y-1] + 1);
    }
    return res[x][y];
}

int main(){
    scanf("%d %d",&r,&c);
    for (int i = 0;i<r;i++){
        for (int j = 0;j<c;j++){
            scanf("%d",&g[i][j]);
        }
    }
    for(int i = 0;i<r;i++){
        for (int j = 0;j<c;j++){
            res[i][j] = DFS(i,j,1);
            maxl = maxl > res[i][j] ? maxl : res[i][j];
        }
    }
    printf("%d",maxl);
    return 0;
}

记忆化模板:

int DFS(int x){
    if (meet) return res[x];
    for (next_step){
        res[x] = max(res[x],res[next]+1)
    }
    return res[x];
}

8 自然数拆分 AC

DFS 模板题

# include <cstdio>
# include <vector>
using namespace std;
int n;
vector<int>v;

void DFS(int i,int left){
    if (left == 0){
        for(int p = 0;p<v.size();p++){
            printf("%d",v[p]);
            if (p<v.size()-1)printf("+");
        }
        printf("\n");
    }
    else{
        for(int j = i;j<=left;j++){
            v.push_back(j);
            DFS(j,left-j);
            v.erase(v.end()-1);
            if (v.size() == 0)break;
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n/2;i++)DFS(i,n);
}

9 数联通区域数 AC

BFS :TLE

//# 2020-03-10 09:05:02
// 换行符的输入要放在哪一行的前面!
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n,m,vis[101][101] = {},g[101][101] = {};
int dir[8][2] = {{1,0},{0,1},{1,-1},{1,1},{-1,0},{0,-1},{-1,1},{-1,-1}};
char c;
struct node{
    int x,y;
    node(int _x,int _y):x(_x),y(_y){}
};
void BFS(int x,int y){  // 超时
    queue<node>q;
    q.push(node(x,y));
    while(!q.empty()){
        int tx = q.front().x,ty = q.front().y;
        q.pop();
        vis[tx][ty] = 1;
        for(int i = 0;i<8;i++){
            int nx = tx + dir[i][0],ny = ty + dir[i][1];
            if(nx >= 0 && ny >= 0 && nx <n && ny < m
               && vis[nx][ny] == 0 && g[nx][ny] == 1){
                q.push(node(nx,ny));
            }
        }
    }
}
void DFS(int tx,int ty){    // ok
    for(int i = 0;i<8;i++){
        int nx = tx + dir[i][0],ny = ty + dir[i][1];
        if(nx >= 0 && ny >= 0 && nx <n && ny < m
           && vis[nx][ny] == 0 && g[nx][ny] == 1){
            vis[nx][ny] = 1;
            DFS(nx,ny);
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    vector<node>water;
    for (int i = 0;i<n;i++){
        scanf("%*c");
        for(int j = 0;j<m;j++){
            scanf("%c",&c);
            if (c == 'W'){
                g[i][j] = 1;
                water.push_back(node(i,j));
            }
        }
    }
    int count = 0;
    for(int p = 0;p<water.size();p++){
        int i = water[p].x,j = water[p].y;
        if (vis[i][j] == 0){
            DFS(i,j);
            count ++;
            
        }
    }
//    for(int i = 0;i<n;i++){
//        for(int j = 0;j<m;j++){
//            printf("%d ",g[i][j]);
//            }printf("\n");
//    }
    printf("%d",count);
    return 0;
}

10 DFS AC

# include <cstdio>
# include <algorithm>
using namespace std;
# define min(a,b) a<b?a:b
int ss = 1,tt = 0,n,s[11] = {},t[11] = {},res = 1000000000;

void DFS(int now){
    for(int i = now+1;i<n;i++){
        ss *= s[i];
        tt += t[i];
        res = min(abs(ss-tt),res);
        DFS(i);
        ss /= s[i];
        tt -= t[i];
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++)scanf("%d %d",&s[i],&t[i]);
    DFS(-1);
    printf("%d",res);
}

11 选数 DFS + isprime AC

# include <cstdio>
# include <vector>
# include <cmath>
using namespace std;
int n,k,a[21],res = 0,prime[1000000] = {2,3};
vector<int>v;

bool isprime(int p){
    for(int i = 0;prime[i] < sqrt(p);i++){
        if (p%prime[i] == 0) return false;
    }
    return true;
}

void getprime(int i){
    int count = 0;
    for(int j = 2;j<i;j++){
        if (isprime(j)) prime[count++] = j;
    }
}

bool isprimefast(int num){
    for(int i = 0;prime[i] < num+10;i++){
        if (prime[i] == num)return true;
    }
    return false;
}


void DFS(int p,int num){
    if (num == k){
        int sum = 0;
        for(int i = 0;i<v.size();i++){
            sum += v[i];
        }
        if(isprimefast(sum)){
            res++;
//            printf("sum = %d\n",sum);
        }
    }else{
        for(int i = p+1;i<n;i++){
            v.push_back(a[i]);
            DFS(i,num+1);
            v.erase(v.end()-1);
        }
    }
}

int main(){
    scanf("%d %d",&n,&k);
    int total = 0;
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
        total += a[i];
    }
    getprime(total);
//    for (int i = 0;i<100;i++)printf("%d ",prime[i]);
    DFS(-1,0);
    printf("%d",res);
}

12 考前抱佛脚 AC

# include <cstdio>
# define min(a,b) (a) < (b) ? (a) : (b)
int s[4],course[4][21],sum[4],totaltime = 0,grouptime,mintime;
void DFS(int group,int now){
    if (grouptime >= (sum[group]+1)/2)
        mintime = min(grouptime,mintime);
    else {
        for(int i = now + 1;i<s[group];i++){
            grouptime += course[group][i];
            DFS(group,i);
            grouptime -= course[group][i];
        }
    }
}
int main(){
    for (int i = 0;i<4;i++)scanf("%d",&s[i]);
    for (int i = 0;i<4;i++){
        int tempsum = 0;
        for(int j = 0;j<s[i];j++){
            scanf("%d",&course[i][j]);
            tempsum += course[i][j];
        }
        sum[i] = tempsum;
    }
    for(int i = 0;i<4;i++){
        grouptime = 0,mintime = sum[i];
        DFS(i,-1);
//        printf("%d|",mintime);
        totaltime += mintime;
    }
    printf("%d",totaltime);
    return 0;
}

13 Meteor Shower 56 TODO

# include <cstdio>
# include <cstring>
# define min(a,b) (a)<(b)?(a):(b)
int g[310][310] = {},f[310][310] = {},vis[310][310] = {};
int m,tx,ty,tt,res = 1000000;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void DFS(int x,int y,int step){
    if(g[x][y] == 0){
//        printf("(%d),%d,%d,%d----",res,x,y,step);
        res = min(res,step);
        return;
    }
    else{
        for(int i = 0;i<4;i++){
            int nx = x+dir[i][0],ny = y + dir[i][1];
            if (nx >= 0 && ny >= 0 && vis[nx][ny] == 0 && (g[nx][ny] == 0 || g[nx][ny] > step+1) && step < res){
                // step < res 剪枝
                // g[nx][ny] > step+1 : +1 !!!
                vis[nx][ny] = 1;
                DFS(nx,ny,step+1);
                vis[nx][ny] = 0;
                // 要回溯
            }
        }
    }
}

int main(){
    scanf("%d",&m);
    for(;m;m--){
        scanf("%d %d %d",&tx,&ty,&tt);
        // 输入的时候可能不是按照时间顺序输入
        if (g[tx][ty] == 0 || g[tx][ty] > tt)g[tx][ty] = tt;
        if (tx-1 >= 0 && (g[tx-1][ty] == 0 || g[tx-1][ty] > tt))g[tx-1][ty] = tt;
        if (ty-1 >= 0 && (g[tx][ty-1] == 0 || g[tx][ty-1] >tt))g[tx][ty-1] = tt;
        if (g[tx+1][ty] == 0 || g[tx+1][ty] > tt)g[tx+1][ty] = tt;
        if (g[tx][ty+1] == 0 || g[tx][ty+1] > tt)g[tx][ty+1] = tt;
    }
//    for (int i = 0;i<5;i++){
//        for(int j = 0;j<5;j++){
//            printf("%d ",g[i][j]);
//        }printf("\n");
//    }
    DFS(0,0,0);
    if (res < 1000000)printf("%d",res);
    else printf("-1");
    return 0;
}

14 烤鸡 AC

# include <cstdio>
# include <vector>
using namespace std;
int n,total = 0;
vector<int>res;
vector<int>p[10];
void prints(){
//    二维数组下标弄反
    for (int j = 0;j<p[0].size();j++){
        for(int i = 0;i<9;i++){
            printf("%d ",p[i][j]);
        }printf("%d\n",p[9][j]);
    }
}
void print(){
    total++;
    for(int i = 0;i<10;i++){
        p[i].push_back(res[i]);
    }
}
void DFS(int left,int count){
    if (count == 10 && left == 0)print();
    else {
        for(int i = 1;i<=3;i++){
            left -= i;
            count += 1;
            res.push_back(i);
            if (!(left + count < 10 || left < 0)) DFS(left,count);
            left += i;
            count -= 1;
            res.pop_back();
        }
    }
}
int main(){
    scanf("%d",&n);
    if (n < 10 || n > 30){
        printf("0");
        return 0;
    }
    DFS(n,0);
    printf("%d\n",total);
    prints();
    return 0;
}

15 组合数 AC

# include <cstdio>
# include <vector>
using namespace std;
int n,r;
vector<int>res;
void print(){
    for(int i = 0;i<r;i++)printf("%3d",res[i]);
    printf("\n");
}
void DFS(int now,int count){
    if (count == r)print();
    else{
        for(int i = now+1;i<=n;i++){
            res.push_back(i);
            DFS(i,count+1);
            res.pop_back();
        }
    }
}
int main(){
    scanf("%d %d",&n,&r);
    DFS(0,0);
}

数组查找

1 A-B=C AC

# include <cstdio>
# include <map>
using namespace std;
long long n,c,a[200005] = {},ans = 0;
map<long long, long long>m;
int main(){
    scanf("%lld %lld",&n,&c);
    for(int i = 0;i<n;i++){
        scanf("%lld",&a[i]);
        m[a[i]]++;
        a[i] += c;
    }
//    for (map<long long, long long>::iterator it = m.begin();it != m.end();it++){
//        printf("%lld %lld--", it->first,it->second);
//    }
    for(int i = 0;i<n;i++){
        ans += m[a[i]];
    }
    printf("%lld",ans);
    return 0;
}

2 查找最接近数字 AC

对于upper_bound来说,返回的是被查序列中第一个大于查找值的指针,也就是返回指向被查值>查找值的最小指针,lower_bound则是返回的是被查序列中第一个大于等于查找值的指针,也就是返回指向被查值>=查找值的最小指针。

函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!

# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 100000;
int a[maxn] = {},b,m,n;
long long res = 0;
int main(){
    scanf("%d %d",&m,&n);
    for(int i = 0;i<m;i++)scanf("%d",&a[i]);
    sort(a,a+m);
    for(int i = 0;i<n;i++){
        scanf("%d",&b);
        int pos = (int)(upper_bound(a, a+m, b) - a);
        if (pos == 0){
            res += (a[pos] - b);
        }else if (pos == m){
            res += (b - a[pos-1]);
        }
        else {
            int x = a[pos],y = a[pos-1];
            res += ((x-b) < (b-y) ? (x-b) : (b-y));
        }
//        printf("(%d)",a[pos]);
//        printf("%d ",res);
    }
    printf("%lld",res);
    return 0;
}

3 查找利率 TODO

理解不了题意,不知道是怎么四舍五入的

# include <cstdio>
# include <algorithm>
# include <cmath>
using namespace std;
double a,sum,each,mon;
bool cool(int x){
    double xx = x/10000.0;
    printf("%lf ",xx);
    double res = 0,p = xx+1;
    for(int i = 0;i<mon;i++){
        res += int((each)/pow(p,i+1)*100);
    }
    printf(" %lf\n",res/100.0);
    if (abs(res/100.0-sum) < 0.01)return 1;
    else return 0;
}
int main(){
    scanf("%lf %lf %lf",&sum,&each,&mon);
    for(int i= 1;i<40;i++){
        if (cool(i)){
            printf("%f",(float)i/100.0);
            break;
        }
    }
    printf("%f",a);
    return 0;
}

发表评论