devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯训练题目若干（东华20考研挑战题1-50）_16 8皇后·改 作者: turbo时间限制: 1s章节: 深度优先搜索 问题描述 : 规则同8皇

作者：你好赵伟 | 2024-03-02 11:27:22

赞

踩

16 8皇后·改 作者: turbo时间限制: 1s章节: 深度优先搜索 问题描述 : 规则同8皇

文章目录

前言

提交代码：
选择C/C++编程语言，因为有的时候会用到C++的一些方便的头文件什么的，还有我编写代码是有一部分是纯C的，因为做题来讲C的scanf和printf很方便。

解题解法质量：
关于我的解法和代码的精简程度，我是以当时做题的心态来解题的，由于当时急着刷完所有题目，所以难免会有一些题应该有其他更优的解法，我却用了比较暴力一点的，毕竟当时的劳动强度有点大，抓进度来着，如果有更好的解法，欢迎联系我，或者直接评论，共同学习，共同进步！还有就是有的题目思路是借鉴了网上其他大佬的思路来写的，掌握解题思路是解决程序问题的重中之重
本篇的题目质量挺高的，有大量的题目是竞赛中出现的，如果一时间消化不了，可以考虑多花一点时间

联系方式：

如果有问题交流咨询，可以加入QQ群：673852347

其他未尽事宜，还望海涵！

1 Huffuman树

作者: Turbo 时间限制: 1S 章节: 基本练习（数组）

问题描述 :
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　
本题任务： 对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入说明 :
输入的第一行包含一个正整数n（n<=100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出说明 :
输出用这些数构造Huffman树的总费用。

#include<stdio.h>//Author:summershell
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *((int *)b)-*((int *)a);
}
int main()
{
    int n,a[2020],sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",&a[i]);
    if(n==1)sum=a[0];
    while(n>1)
    {
        qsort(a,n,sizeof(a[0]),cmp);
        sum=sum+a[n-1]+a[n-2];//费用
        a[n-2]=a[n-2]+a[n-1];//把新加的和放进去
        n--;//删除了一个节点
    }
    printf("%d\n",sum);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

2 回文数

作者: lq 时间限制: 1S 章节: 基本练习 (这个lq莫不是？？？)

问题描述 :
1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求大于等于n的所有这样的四位十进制数。
输入说明 :
输入一个整数n，n<9999
输出说明 :
按从小到大的顺序输出满足条件的四位十进制数。

#include<stdio.h>//Author:summershell
int huiwen(int x)//已知4位数
{
    int sta[10],top=-1;
    while(x)
    {
        sta[++top]=x%10;
        x/=10;
    }
    for(int i=0;i<2;++i)if(sta[i]!=sta[3-i])return 0;
    return 1;
}
int main()//水题
{
    int n;
    scanf("%d",&n);
    n=n>999?n:1000;
    while(n<=9999)if(huiwen(n++))printf("%d\n",n-1);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

3 字母图形

作者: Turbo 时间限制: 1S 章节: 基本练习

问题描述 :
利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC

  • 1
  • 2
  • 3
  • 4
  • 5

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

输入说明 :
输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。
1 <= n, m <= 26。
输出说明 :
输出n行，每行m个字符，为你的图形。
无多余空格或空行。

#include<stdio.h>//Author:summershell
int main()//水题
{
    int n,m;
    char a[50][50];
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        for(int j=i;j>=0;--j)a[i][j]='A'+i-j;
        for(int j=i;j<=m;++j)a[i][j]='A'+j-i;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)printf("%c",a[i][j]);
        printf("\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

4 大阶乘计算

作者: Turbo 时间限制: 1S 章节: 基本练习（数组）

问题描述 :
　　输入一个正整数n，输出n!的值。

其中n!=1*2*3*…*n。

  • 1

n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。

参考算法：
使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
　　将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
　　首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

输入说明 :
　　输入包含一个正整数n，n<=1000。
输出说明 :
　　输出n!的准确值。

#include<stdio.h>//Author:summershell
int main()//大数阶乘 使用好数组即可
{
    int a[20200],n,len=1;//len表示长度
    for(int i=0;i<20200;++i)a[i]=0;
    a[1]=1;
    scanf("%d",&n);
    for(int i=1,j;i<=n;++i)
    {
        int temp=0;//temp暂存中间数
        for(j=1;j<=len;++j)
        {
            temp=(temp+i*a[j]);
            a[j]=temp%10;
            temp/=10;
        }
        while(temp){a[++len]=temp%10;temp/=10;}
    }
    for(int i=len;i>0;--i)printf("%d",a[i]);
    printf("\n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5 回形取数

作者: Turbo 时间限制: 1S 章节: 基本练习（数组）

问题描述 :
　　回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入说明 :
　　输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。
输出说明 :
　　输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。

#include<stdio.h>//Author:summershell
#include<string.h>
int n,m,a[220][220],flag[220][220],cou=0,x=1,y=1;//x,y 表示当前位置
int dir[4][2]={-1,0,0,-1,1,0,0,1},pos;
int judge(int a,int b)
{
    if(a>=1 && a<=m && b>=1 && b<=n && flag[a][b]==0)return 1;
    return 0;
}
int main()//让我想我了写贪吃蛇，哈哈哈
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]);
    memset(flag,0,sizeof(flag));//标记是否访问过
    pos=2;//初始方向向下
    while(cou<m*n)//蛇在动
    {
        if(judge(x,y))
        {
            printf(cou++==0?"%d":" %d",a[x][y]);
            flag[x][y]=1;
        }
        if( !judge(x+dir[pos][0],y+dir[pos][1]) )
        pos=(pos+1)%4;//+1表示向右转
        x+=dir[pos][0];
        y+=dir[pos][1];
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

如果有问题交流咨询，可以加入QQ群：673852347

6 龟兔赛跑预测

作者: Turbo 时间限制: 1S 章节: 模拟

问题描述 :
　　话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
　　然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。
输入说明 :
　　输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)
输出说明 :
　　输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。
　　第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。

比如：
输入
10 5 5 2 20
输出
D
4

输入
10 5 5 1 20
输出
R
3

#include<stdio.h>//Author:summershell
int main()//简单
{
    int v1,v2,t,s,L;
    scanf("%d %d %d %d %d",&v1,&v2,&t,&s,&L);

    int Rm=0,Tm=0,time=0;//Rm,Dm是兔子乌龟已经走过的路程

    while(Rm<L && Tm<L)//一次循环代表一秒
    {
        Rm+=v1;
        Tm+=v2;
        time++;
        if(Rm>=L || Tm>=L)break;
        while(Rm>=Tm+t)//兔子的休息时间
        {
            time+=s;//过去了s秒
            Tm+=s*v2;
            if(Tm>=L)break;
        }
    }
    if(Rm<L)//代表乌龟获胜
        printf("T\n%d\n",time-(Tm-L)/v2);
    else if(Tm<L)//兔子获胜
        printf("R\n%d\n",time-(Rm-L)/v1);
    else//都到终点了,都是公倍数 所以不存在小数秒的出现
        printf("D\n%d",time);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

7 Sine之舞

作者: Turbo 时间限制: 1S 章节: 其它

问题描述 :
　　最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
　　不妨设

An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)
　　Sn=(...(A1+n)A2+n-1)A3+...+2)An+1

  • 1
  • 2

FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。
输入说明 :
　　仅有一个数：N<201。
输出说明 :
　　请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

#include<stdio.h>//Author:summershell
#include<math.h>
void An(int n,int t)//模拟啊！
{
    if(t==n)printf("sin(%d)",n);
    else
    {
        printf("sin(%d",t);
        int temp=pow(-1,t+1);
        if(temp>0)
        printf("+");
        else printf("-");
        An(n,t+1);
        printf(")");
    }
}
void Sn(int n,int t)
{
    if(n>1)//仅仅不为1时才有括号
    {
        printf("(");
        Sn(n-1,t+1);
        printf(")");
    }
    An(n,1);
    printf("+%d",t);
}
int main()//简单
{
    int n;
    scanf("%d",&n);
    Sn(n,1);

    return 0;
}

/*
先找到规律
A(1)=sin(1)

A(2)=sin(1+sin(2))

A(3)=sin(1+sin(2-sin(3)))
*/

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

8 矩形面积交

作者: Turbo 时间限制: 1S 章节: 基本练习

问题描述 :
　　平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。
输入说明 :
　　输入仅包含两行，每行描述一个矩形。
　　在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。
输出说明 :
　　输出仅包含一个实数，为交的面积，保留到小数后两位。

#include<stdio.h>//Author:summershell
int main()//给出的点最好处理成一般情况
{
    double x1,y1,x2,y2,x3,y3,x4,y4;//矩形1是(x1,y1),(x2,x2)
    double xm,ym,xn,yn;
    scanf("%lf %lf",&xm,&ym);
    scanf("%lf %lf",&xn,&yn);
    x1=xm<xn?xm:xn;y1=ym<yn?ym:yn;//设法让(x1,y1)为左下的点，便于处理
    x2=xm>xn?xm:xn;y2=ym>yn?ym:yn;

    scanf("%lf %lf",&xm,&ym);
    scanf("%lf %lf",&xn,&yn);
    x3=xm<xn?xm:xn;y3=ym<yn?ym:yn;//设法让(x3,y3)为左下的点，便于处理
    x4=xm>xn?xm:xn;y4=ym>yn?ym:yn;

    double a,b,c,d,ans=0.00;//相交矩形的点
    a=x1>x3?x1:x3;b=y1>y3?y1:y3;
    c=x2<x4?x2:x4;d=y2<y4?y2:y4;
    if(a<c && b<d)//如果是交出了一个矩形
    ans=(c-a)*(d-b);
    printf("%.2f\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

9 矩阵乘法

作者: Turbo 时间限制: 1S 章节: 基本练习（循环）

问题描述 :

给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
　　例如：
　　A =
　　1 2
　　3 4
　　A的2次幂
　　7 10
　　15 22
输入说明 :
　　第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
输出说明 :
　　输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

#include<stdio.h>//Author:summershell
#include<string.h>
int main()//线性代数，永乐大帝,特判0次幂时候为E
{
    int a[100][100],b[100][100],c[100][100],m,n;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&a[i][j]);
            b[i][j]=a[i][j];//提前赋值好处理
        }
    for(int k=1;k<m;++k)//次幂
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                c[i][j]=0;
                for(int t=1;t<=n;++t)c[i][j]+=b[i][t]*a[t][j];//注意是b左乘a
            }
        memcpy(b,c,sizeof(c));//把结果赋值给b
    }
    if(m==0)memset(b,0,sizeof(b));
    for(int i=1;i<=n;++i)
    {
        if(m==0)b[i][i]=1;
        for(int j=1;j<=n;++j)
            printf(j==1?"%d":" %d",b[i][j]);
        printf("\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

10 分解质因数

作者: Turbo 时间限制: 1S 章节: 基本练习（循环）

问题描述 :
　　求出区间[a,b]中所有整数的质因数分解。
输入说明 :
　　输入两个整数a，b。
　　2<=a<=b<=10000
输出说明 :
　　每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看范例)

#include<stdio.h>//Author:summershell
int prime[10001];
void get_prime()
{
    for(int i=0;i<10001;++i)prime[i]=1;
    prime[0]=prime[1]=0;
    for(int i=2;i<10001;++i)
        if(prime[i]==1)
        for(int j=i+i;j<10001;j=j+i)
            prime[j]=0;
}
void fun(int n)
{
    int coun=0;//一共几个因数
    printf("%d=",n);
    while(n!=1)
    {
        for(int i=2;i<=n;++i)
        {
            if(prime[i]==1 && n%i==0)//逐个找出来因数
            {
                printf(coun++==0?"%d":"*%d",i);
                n/=i;
                break;
            }
        }
    }
    printf("\n");
}
int main()//给出的点最好处理成一般情况
{
    get_prime();
    int a,b;
    scanf("%d %d",&a,&b);
    while(a<=b)fun(a++);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

11 字符串对比

作者: Turbo 时间限制: 1S 章节: 基本练习（字符串）

问题描述 :
　　给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4种情况之一：
　　1：两个字符串长度不等。比如 Beijing 和 Hebei
　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入说明 :
　　包括两行，每行都是一个字符串
输出说明 :
　　仅有一个数字，表明这两个字符串的关系编号

#include<stdio.h>//Author:summershell
#include<string.h>
int main()//水题
{
    char s1[20],s2[20];
    scanf("%s",s1);
    scanf("%s",s2);
    int len1=strlen(s1),len2=strlen(s2);

    if(len1!=len2)printf("1\n");
    else
    {
        if(strcmp(s1,s2)==0)printf("2\n");
        else
        {
            for(int i=0;i<len1;++i)
                if(s1[i]>='A' && s1[i]<='Z')s1[i]=s1[i]-'A'+'a';
            for(int i=0;i<len2;++i)
                if(s2[i]>='A' && s2[i]<='Z')s2[i]=s2[i]-'A'+'a';
            if(strcmp(s1,s2)==0)printf("3\n");
            else printf("4\n");
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

12 时间转换

作者: Turbo 时间限制: 1S 章节: 基本练习

问题描述 :

给定一个以秒为单位的时间t，要求用“<H>:<M>:<S>”的格式来表示
这个时间。<H>表示时间，<M>表示分钟，而<S>表示秒，它们都是整数
且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，
则输出
“1:1:1”。

  • 1
  • 2
  • 3
  • 4
  • 5

输入说明 :
　　输入只有一行，是一个整数t（0<=t<=86399）。
输出说明 :

输出只有一行，是以“<H>:<M>:<S>”的格式所表示的时间，不包括引号。

  • 1
#include<stdio.h>//Author:summershell
int main()//水题
{
    int t,h=0,m=0,s=0,i=1;
    scanf("%d",&t);
    while(i++<=t)
    {
        s++;
        if(s>=60){s-=60;m++;}
        if(m>=60){m-=60;h++;}
    }
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

13 2n皇后问题

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。
问总共有多少种放法？
n小于等于8。
说明：同一条对角线是指包括两条主对角线的所有对角线，n=5时的棋盘从左上往右下有9条对角线，从右上往左下也有9条对角线。
比如，棋盘为：

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

  • 1
  • 2
  • 3
  • 4

表示一个4*4的棋盘，所有位置都可放皇后。
则可知有2种放法。

输入说明 :
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出说明 :
输出一个整数，表示总共有多少种放法。

我的这个解法现在看来比较复杂繁琐的很，有其他比较简约的解法

  • 1
#include<stdio.h>//Author:summershell
int n,a[50][50],sum=0;
int judge(int x,int y)//1代表有重复的
{
    for(int i=1;i<=n;++i)if(i!=x && a[i][y]==a[x][y])return 1;
    for(int i=1;i<=n;++i)if(i!=y && a[x][i]==a[x][y])return 1;
    for(int i=x-1,j=y-1;i>0&&j>0;i--,j--)//检查左斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x+1,j=y+1;i<=n && j<=n;i++,j++)//检查左斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x+1,j=y-1;i<=n&&j>0;i++,j--)//检查右斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x-1,j=y+1;i>0 && j<=n;i--,j++)//检查右斜对角线
        if(a[i][j]==a[x][y])return 1;
    return 0;
}
void Queen(int deep,int color)//每次往下一行放数,10是白皇后 -10是黑皇后
{
    if(deep>=n+1)//放置某个皇后完成
    {
        if(color==10)//放置白皇后完成时
        {
            Queen(1,-10);//黑皇后开始
        }
        else sum++;//否则就两个放置完成
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if(a[deep][i]==1)
        {
            a[deep][i]=color;
            if(judge(deep,i)==0)
            Queen(deep+1,color);
            a[deep][i]=1;
        }
    }
}
int main()//皇后问题
{

    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)scanf("%d",&a[i][j]);
    Queen(1,10);
    printf("%d\n",sum);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

如果有问题交流咨询，可以加入QQ群：673852347

14 芯片测试

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
　　每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
　　给出所有芯片的测试结果，问哪些芯片是好芯片。
输入说明 :
　　输入数据第一行为一个整数n，表示芯片个数。
　　第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。
输出说明 :
　　按从小到大的顺序输出所有好芯片的编号

#include<stdio.h>//Author:summershell
int main()//都说了 好的比坏的多，所以大多数的结果就是正确的结果
{
    int n,a[20][20];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;++j)scanf("%d",&a[i][j]);
    for(int i=0;i<n;++i)
    {
        int coun=-1;
        for(int j=0;j<n;++j)if(a[j][i])coun++;
        if(coun>=n/2)printf("%d ",i+1);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

15 FJ的字符串

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　FJ在沙盘上写了这样一些字符串：
　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”
　　… …
　　你能找出其中的规律并写所有的数列AN吗？
输入说明 :
　　仅有一个数：N ≤ 20。
输出说明 :
　　请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

#include<stdio.h>//Author:summershell
void dfs(int n)
{
    if(n==1)printf("A");
    else if(n==2)printf("ABA");
    else if(n==3)printf("ABACABA");
    else if(n==4)printf("ABACABADABACABA");
    else
    {
        dfs(n-1);
        printf("%c",'A'+n-1);
        dfs(n-1);
    }
}
int main()//规律就是依靠上一项来得到下一项,TLE了。改进下吧。抠搜一些能省则省，说不定就A了呢，嘤嘤嘤
{
    int n;
    scanf("%d",&n);
    dfs(n);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

16 8皇后·改

作者: turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入说明 :
一个8*8的棋盘。

数据规模和约定
　　棋盘上的数字范围0~99

输出说明 :
所能得到的最大数字和

#include<stdio.h>//Author:summershell
int n,a[50][50],w[50][50],maxnum=-100;
int judge(int x,int y)//1代表有重复的
{
    for(int i=1;i<=n;++i)if(i!=x && a[i][y]==a[x][y])return 1;
    for(int i=1;i<=n;++i)if(i!=y && a[x][i]==a[x][y])return 1;
    for(int i=x-1,j=y-1;i>0&&j>0;i--,j--)//检查左斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x+1,j=y+1;i<=n && j<=n;i++,j++)//检查左斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x+1,j=y-1;i<=n&&j>0;i++,j--)//检查右斜对角线
        if(a[i][j]==a[x][y])return 1;
    for(int i=x-1,j=y+1;i>0 && j<=n;i--,j++)//检查右斜对角线
        if(a[i][j]==a[x][y])return 1;
    return 0;
}
void Queen(int deep,int color,int weight)//每次往下一行放数,1000是皇后
{
    if(deep>=n+1)//放置某个皇后完成
    {
        if(maxnum<weight)//放置白皇后完成时
            maxnum=weight;
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if(a[deep][i]==1)
        {
            a[deep][i]=color;
            if(judge(deep,i)==0)
            Queen(deep+1,color,weight+w[deep][i]);
            a[deep][i]=1;
        }
    }
}
int main()//皇后问题,沿用13题的模板,修修补补 还能用嘛
{

    n=8;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
                scanf("%d",&w[i][j]);
                a[i][j]=1;
        }
    Queen(1,1000,0);
    printf("%d\n",maxnum);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

17 棋盘多项式

作者: turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张n*n的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。
　　此题，给你棋盘的规模n，以及挖洞情况，求放k个车的方案数(k从0到最多可放车数)
输入说明 :
第一行一个整数n表示棋盘大小
接下来n行，每行n个用空格隔开的数字0或1，0的形状表示洞，1表示没有洞

数据规模和约定
　　n<=8
输出说明 :
若干行，第i行表示放i个车的方案数

#include<stdio.h>//Author:summershell
int a[50][50],n,ans[100];
int judge(int x,int y)
{
    for(int i=x-1;i>0&&a[i][y]!=0;--i)
        if(a[x][y]==a[i][y])return 1;//表示发现同类
    for(int i=x+1;i<=n&&a[i][y]!=0;++i)
        if(a[x][y]==a[i][y])return 1;//表示发现同类

    for(int i=y-1;i>0&&a[x][i]!=0;--i)
        if(a[x][y]==a[x][i])return 1;//表示发现同类
    for(int i=y+1;i<=n&&a[x][i]!=0;++i)
        if(a[x][y]==a[x][i])return 1;//表示发现同类
    return 0;
}
void dfs(int deepx,int deepy,int counter,int maxnum)//counter是放置了几个，maxnum是最多几个车
{
    if(counter<=n*n)//能进到本次循环的都是可以放置的
        ans[counter]++;

    for(int i=deepx;i<=n;++i)
    {
        for(int j=i==deepx?deepy:1;j<=n;++j)//保证从刚进入本层dfs时候，从当前坐标往下判断。然后下一层时候j需要从1开始了。
        if(a[i][j]==1)//若能放置棋子
        {
            a[i][j]=10;
            if(judge(i,j)==0)dfs(i,j,counter+1,maxnum);
            a[i][j]=1;
        }

    }
}
int main()//TLE了好几次了。。。。再改下！！！
{//改进：dfs过程的结果可以保存起来，这样避免了许多重复的计算。用ans[100]
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)scanf("%d",&a[i][j]);
    for(int i=0;i<100;i++)ans[i]=0;

    dfs(1,1,0,n*n);//10代表车
    for(int i=1;i<n*n;++i)if(ans[i])printf("%d\n",ans[i]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

如果有问题交流咨询，可以加入QQ群：673852347

18 3000米排名预测

作者: turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
3000米长跑时，围观党们兴高采烈地预测着最后的排名。因为他们来自不同的班，对所有运动员不一定都了解，于是他们分别对自己了解的一些运动员的实力作出了评估，即对部分运动员做了相对排名的预测，并且告诉了可怜留守的班长。因为无聊，于是他们就组团去打Dota去了。比赛结束后他们向班长询问最后的排名，但班长不记得了，只记得他们中哪些人的预测是正确的，哪些人的预测是错误的。他们想知道比赛的排名可能是什么。

输入说明 :
第一行两个整数n， m，n为运动员数量，m为围观党数量。运动员编号从0到n-1。
接下来m行，每行为一个围观党的相对排名预测。每行第一个数c表示他预测的人数，后面跟着c个0~n-1的不同的数，表示他预测的运动员相对排名，最后还有一个数，0表示这个预测是错误的，1表示是正确的。

数据规模和约定
　　1<=n<=10, 2<=c<=n, 1<=m<=10，保证数据合法，且答案中排名可能数不超过20000。对于一个排名序列，一个预测是正确的，当且仅当预测的排名的相对顺序是排名序列的一个子序列。一个预测是错误的，当且仅当这个预测不正确。

输出说明 :
第一行一个数k为有多少种排名的可能。
下面k行，每行一个0~n-1的排列，为某一个可能的排名，每个数字后有一个空格（即：行尾也有一个空格）。所有排名按字典序依次输出。

比如，输入：
3 2
2 0 1 1
2 2 1 0
则输出：
1
0 1 2

#include<stdio.h>//Author:summershell
#include<string.h>//对每种排名都列举出来 然后对其判断 用 C 提交
int n,m,people[15][15],_true[15],ans[20000][15],ansnum=0;
int road[15],top=-1,vis[15];
int judge()
{
    for(int i=0;i<m;++i)
    {
        int pos=1;
        for(int j=0;j<n;++j)//在这里判断是否符合这个预测
        {
            if(road[j]==people[i][pos])
            {
                ++pos;
            }
            if(pos>people[i][0])break;//说明符合这个预测
        }
        if(pos>people[i][0] && _true[i]==0)//若符合预测 且为假的
            return 0;
        if(pos<=people[i][0] && _true[i]==1)//若不符合预测 且为真
            return 0;
    }
    return 1;
}
void DFS(int x)
{
    if(x==n)
    {
        if(judge())//判断
        {
            for(int i=0;i<n;++i)
                ans[ansnum][i]=road[i];
            ansnum++;
        }
        return;
    }
    for(int i=0;i<n;++i)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            road[++top]=i;
            DFS(x+1);
            top--;
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d",&people[i][0]);//0存放预测的长度
        for(int j=1;j<=people[i][0];++j)scanf("%d",&people[i][j]);
        scanf("%d",&_true[i]);
    }
    memset(vis,0,sizeof(vis));
    DFS(0);//开始深搜
    printf("%d\n",ansnum);
    for(int i=0;i<ansnum;++i)
    {
        for(int j=0;j<n;++j)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

19 排队打水问题

作者: Turbo 时间限制: 1S 章节: 其它

问题描述 :
　　有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…………tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入说明 :
　　第一行n，r (n<=500,r<=75)
　　第二行为n个人打水所用的时间Ti (Ti<=100)；
输出说明 :
　　最少的花费时间
输入范例 :

#include<stdio.h>//Author:summershell
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()//所有时间的意思是每个人的等待时间加上接水时间
{//原则就是 谁接水时间最短 就让谁先接水
    int n,r,sum=0,a[2020],b[2020];
    scanf("%d %d",&n,&r);
    for(int i=0;i<n;++i)scanf("%d",&a[i]);
    qsort(a,n,sizeof(a[0]),cmp);

    for(int i=0;i<r;i++)b[i]=a[i];
    for(int i=r;i<n;++i)b[i]=a[i]+b[i-r];//自己的时间等于前面人总时间加上自己接水时间

    for(int i=0;i<n;++i)sum+=b[i];
    printf("%d\n",sum);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

20 产生数

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。
　　规则：
　　一位数可变换成另一个一位数，变换得到的数不能为零。
　　例如：n=234。有规则（k＝2）：
　　2－> 5
　　3－> 6
　　上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
　　234
　　534
　　264
　　564
　　共 4 种不同的产生数
　　问题：
　　给出一个整数 n 和 k 个规则。
　　求出：
　　经过任意次的变换（0次或多次），能产生出多少个不同整数。
　　仅要求输出个数。
输入说明 :
　　n k
　　x1 y1
　　x2 y2
　　… …
　　xn yn
输出说明 :
一个整数（满足条件的个数）

#include<stdio.h>//Author:summershell
#include<string.h>
//给出一个整数 n（n<10^30) 和 k 个变换规则k<=15。虽然题目类别写的dfs。但是直接递归肯定超时，这是一道算法题
int main()//如果找到每位数字可以变换的种类，则把各位可以变换的情况相乘就是最后的结果
{
    char str[2020];
    int swit[10][10],k;//下标表示可以变换的数组，例如swit[x][y]=1;表示x->y成立的
    scanf("%s %d",str,&k);
    memset(swit,0,sizeof(swit));
    for(int i=0;i<k;++i)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        swit[x][y]=1;
    }
    //可能存在1->2和2->3，那么就衍生了1->3。故使用数据结构书中的弗洛伊德算法的小技巧，如下
    for(int i=0;i<10;++i)
        for(int j=0;j<10;++j)
            for(int k=0;k<10;++k)//不断反复的询问才可以达到所有的情况
                if(swit[k][j] && swit[j][i])swit[k][i]=1;
    //我们可以假设不存在变换时候是只有自己向自己的一种变换。这样处理比较方便
    int tag[2020];//tag[x]表示x有多少种变换
    memset(tag,0,sizeof(tag));
    for(int i=0;i<10;++i)
    {
        swit[i][i]=1;//自己向自己转换
        for(int j=0;j<10;++j)if(swit[i][j])tag[i]++;
    }
    //emm数据太大了，30个数相乘，很容易爆，使用大数处理
    int number[2020],numlen=0,stlen=strlen(str);
    memset(number,0,sizeof(number));
    number[0]=1;
    for(int i=0;i<stlen;++i)
    {
        int a=tag[str[i]-'0'],temp=0;//a去乘大数组
        for(int j=0;j<=numlen;++j)
        {
            temp=(temp+a*number[j]);
            number[j]=temp%10;
            temp=temp/10;
        }
        while(temp){number[++numlen]=temp%10;temp/=10;}
    }
    for(int i=numlen;i>=0;--i)printf("%d",number[i]);
    printf("\n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

如果有问题交流咨询，可以加入QQ群：673852347

21 分分钟的碎碎念

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　以前有个孩子，他分分钟都在碎碎念。不过，他的念头之间是有因果关系的。他会在本子里记录每一个念头，并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子，你一定会被互相穿梭的箭头给搅晕，现在他希望你用程序计算出这些念头中最长的一条因果链。
　　将念头从1到n编号，念头i来源于念头from[i]，保证from[i]<i，from[i]=0表示该念头没有来源念头，只是脑袋一抽，灵光一现。

样例输入
8
0
1
0
3
2
4
2
4
样例输出
3
样例说明
　　最长的因果链有：
　　1->2->5 (from[5]=2,from[2]=1,from[1]=0)
　　1->2->7 (from[7]=2,from[2]=1,from[1]=0)
　　3->4->6 (from[6]=4,from[4]=3,from[3]=0)
　　3->4->8 (from[8]=4,from[4]=3,from[3]=0)

输入说明 :
　　第一行一个正整数n表示念头的数量
　　接下来n行依次给出from[1]，from[2]，…，from[n]
1<=n<=1000
输出说明 :
　　共一行，一个正整数L表示最长的念头因果链中的念头数量

#include<stdio.h>//Author:summershell
int countTree(int tree[],int x)//数x往后的念头有几个
{
    int counter=1;
    while(tree[x])
    {
        x=tree[x];
        counter++;
    }
    return counter;
}
int main()//之前做克鲁斯卡尔时候用到过,Easy
{
    int n,tree[2020],maxlen=-10;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&tree[i]);
    for(int i=1;i<=n;++i)
    {
        int temp=countTree(tree,i);
        if(maxlen<temp)maxlen=temp;
    }
    printf("%d\n",maxlen);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

22 现代诗如蚯蚓

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　现代诗如蚯蚓
　　断成好几截都不会死
　　字符串断成好几截
　　有可能完全一样
　　请编写程序
　　输入字符串
　　输出该字符串最多能断成多少截完全一样的子串

样例输入
abcabcabcabc
样例输出
4
样例说明
　　最多能断成四个”abc”，也就是abc重复四遍便是原串
　　同时也能断成两个”abcabc”
　　最坏情况是断成一个原串”abcabcabcabc”

输入说明 :
　　一行，一个字符串
　　字符串长度<=1000
输出说明 :
　　一行，一个正整数表示该字符串最多能断成的截数

#include<stdio.h>//Author:summershell
#include<string.h>
int main()//猛一看觉得有点不知所措，细细想来，不就是字符串匹配吗？
{
    char s[2020];
    gets(s);
    int len=strlen(s);
    for(int n=1;n<=len/2;++n)
    {

        if(len%n==0)//若可以被等分n长度
        {
            int segment=len/n,j;
            char sp1[2020],sp2[2020];
            memcpy(sp1,s,n);
            sp1[n]='\0';
            for(j=1;j<segment;++j)
            {
                memcpy(sp2,s+n*j,n);//把字符串复制过来进行匹配
                sp2[n*(j+1)]='\0';//对cmp有影响，必须加断
                if(strcmp(sp1,sp2)!=0)break;
            }
            if(j>=segment)//若分割成功
            {
                printf("%d\n",segment);
                return 0;
            }
        }
    }
    printf("1\n");//若不可分割
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

23 函数求值

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　设 F(N) 表示正整数 1 到正整数 N 中,数字 1,2 总共出现了多少次。例如 N = 10 时:1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这 10 个数中,数字 1 出现了两次,数字 2 出现了 1 次,所以数字 1, 2 总共出现了 3 次,因此 F (10) = 3。
　　现在给你正整数 N ,请你求出 F(N) 的值。由于 F(N) 可能很大,你仅需输出 F(N) 除以 20123 的余数。
输入说明 :
　　输入数据仅一行,包含一个正整数 N (1 ≤ N ≤ 10100 ),表示函数 F(N)的参数。
输出说明 :
　　输出仅一个整数,为 F(N) 除以 20123 的余数。

/*******************蓝桥杯官方题解********************/
#include<stdio.h>
#include<string.h>
int main()
{
    int ten[1000],z[1000],a[1000],i,len,j,sum=0;
    char s[1000];
    gets(s);
    ten[0]=1;
    z[1]=1;
    for (i=1;i<=100;i++) ten[i]=ten[i-1]*10%20123;
    for (i=2;i<=100;i++)
        z[i]=(z[i-1]+(ten[i-1]+9*ten[i-2]*(i-1))%20123)%20123;
    len=strlen(s);  a[len]=0;
    for (i=len-1;i>=0;i--)
        a[i]=((s[i]-48)*ten[len-i-1]+a[i+1])%20123;
    for (i=0;i<len;i++)
    {
      for (j=0;j<s[i]-48;j++)
      {
        sum=(sum+z[len-i-1]*2)%20123;
        if (j==1||j==2)
            sum=(sum+ten[len-i-1])%20123;
      }
      if (s[i]=='1'||s[i]=='2')
        sum=(sum+a[i+1]+1)%20123;
    }
    printf("%d\n",sum);
    return 0;
}
/**************我的题解TLE了*******规律如下*****
//9   99   999    9999     99999       999999      9999999
//2   40   600    8000     100000      1200000     14000000
#include<stdio.h>//Author:summershell
#include<string.h>
int main()//100位的数，不容小觑啊
{
    char num[2020];
    gets(num);
    int ans=0,len=strlen(num),start=0;
    while(start<len)//让xxxxxx每次循环时候减一，直到0结束
    {
        for(int i=start;i<len;++i)
            if(num[i]=='1' || num[i]=='2')++ans;
   //     ans=ans%20123;
        //开始-1操作
        for(int i=len-1;i>=start;--i)
        {
            if(num[i]=='0')//表示存在借位
                num[i]='9';
            else
            {
                num[i]=num[i]-1;
                break;
            }
        }
        if(num[start]=='0')//若借位给借完了，长度应该减小1
            start++;
    }
    printf("%d\n",ans);
    return 0;
}*/

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

如果有问题交流咨询，可以加入QQ群：673852347

24 密码锁

作者: Turbo 时间限制: 1S 章节: 宽度优先搜索

问题描述 :
　　你获得了一个据说是古代玛雅人制作的箱子。你非常想打开箱子看看里面有什么东西,但是不幸的是,正如所有故事里一样,神秘的箱子出现的时候总是会挂着神秘的锁。
　　这个锁上面看起来有 N 个数字,它们排成一排,并且每个数字都在 0 到 2 之间。你发现你可以通过锁上的机关来交换相邻两个数字的顺序。比如,如果原来有 5 个数字 02120,在一次交换以后你就可以得到 20120,01220,02210 或者 02102。
　　根据你所搜集的情报,这个锁在上面存在某连续四个数字是“2012”的时候会自动打开。现在,你需要计算一下,你至少需要进行多少次交换操作才能打开这把锁?

样例输入
5
02120
样例输出
1
对样例的解释
　　把前两个数字交换以后,锁上的数字是 20120,其中存在连续四个数字2, 0, 1, 2,因此锁会打开。

输入说明 :
　　输入数据的第一行有一个正整数 N。(4 ≤ N ≤ 13) 输入数据的第二行有 N 个数字 a1,a2, …, aN ,其中 ai 表示这个锁上面第 i 个数字的值,满足 0 ≤ ai ≤ 2。这些数字之间没有空格分隔。
输出说明 :
你只需要输出一个数字,即你至少需要的交换次数。如果无论如何都没有希望打开这把锁,输出 -1。

#include<stdio.h>//Author:summershell
#include<iostream>
#include<queue>//BFS比较方便的C++模板
#include<set>//TLE了，需要加上判重才可以，这里使用set
typedef struct node
{
    std::string str;
    int step;
}Node;
int n;
std::set<std::string> different;
int BFS(std::string str)
{
    std::queue<Node>que;
    Node p,q;//构造一个初始结点
    p.str=str;
    p.step=0;
    que.push(p);//初始结点进队
    while(!que.empty())
    {
        q=que.front();//取队头结点，然后出队
        que.pop();
        if(q.str.find("2012")!=std::string::npos)
        return q.step;
        for(int i=0;i<n-1;++i)//否则就进行变换从0到n-1。
        {
            Node r;//要构建新结点进队啊
            r.str=q.str;
            std::swap(r.str[i],r.str[i+1]);
            r.step=q.step+1;
            if(different.find(r.str)==different.end())//若无重复，进队
            {
                different.insert(r.str);
                que.push(r);//进队
            }
        }
    }
    return -1;
}
int main()
{
    std::string str;
    scanf("%d ",&n);
    std::cin>>str;
    std::cout<<BFS(str)<<std::endl;;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

如果有问题交流咨询，可以加入QQ群：673852347

25 超级玛丽

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　大家都知道"超级玛丽"是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,…am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。
　　现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。
输入说明 :
　　第一行为两个整数n,m
　　第二行为m个整数，表示陷阱的位置
　　40>=n>=3,m>=1
　　n>m;
　　陷阱不会位于1及n上
输出说明 :
　　一个整数。表示玛丽跳到n的方案数

#include<stdio.h>//Author:summershell
#include<string.h>
int ans=0,road[2020],n,m,temp;
void dfs(int deep)
{
    if(deep==n)++ans;
    else
    {
        if(road[deep+1]==0)dfs(deep+1);
        if(road[deep+2]==0)dfs(deep+2);
    }
}
int main()//常规dfs
{
    scanf("%d %d",&n,&m);
    memset(road,0,sizeof(road));//0代表有陷阱
    for(int i=0;i<m;++i)
    {
        scanf("%d",&temp);
        road[temp]=1;
    }
    road[n+1]=road[n+2]=1;//把终点堵死
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

26 聪明的美食家

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　如果有人认为吃东西只需要嘴巴，那就错了。
　　都知道舌头有这么一个特性，“由简入奢易，由奢如简难”（据好事者考究，此规律也适合许多其他情况）。具体而言，如果是甜食，当你吃的食物不如前面刚吃过的东西甜，就很不爽了。
　　大宝是一个聪明的美食家，当然深谙此道。一次他来到某小吃一条街，准备从街的一头吃到另一头。为了吃得爽，他大费周章，得到了各种食物的“美味度”。他拒绝不爽的经历，不走回头路而且还要爽歪歪（爽的次数尽量多）。
输入说明 :
　　两行数据。
　　第一行为一个整数n，表示小吃街上小吃的数量
　　第二行为n个整数，分别表示n种食物的“美味度”

美味度为0到100的整数
　　n<1000
输出说明 :
　　一个整数，表示吃得爽的次数

#include<stdio.h>//Author:summershell
#include<iostream>
int main()//不就是找最长递增子序列吗
{//设置一个答案数组length[x]，x表示下标x的最长的子序列长度。
    int n,a[2020],length[2020];
    scanf("%d",&n);//很显然我们在找length[x]时候，会从x到1遍历。
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        length[i]=1;//初始长度是1，再差，自己一个人也是可以的
        for(int j=i-1;j>0;--j)
        {
            if(a[i]>=a[j])//如果小于那就没得谈了啊
            {
                length[i]=std::max(length[i],length[j]+1);//如果遇到合适的且比i大，则就用它
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(ans<length[i])ans=length[i];
    }
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

如果有问题交流咨询，可以加入QQ群：673852347

27 士兵排队问题

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　有Ｎ个士兵(1≤Ｎ≤26)，编号依次为Ａ,Ｂ,Ｃ,…，队列训练时，指挥官要把一些士兵从高到矮一次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“P1比P2高”这样的比较结果(P1、P2∈Ａ,Ｂ,Ｃ,…,Ｚ,记为 P1>P2)，如”Ａ>Ｂ”表示Ａ比Ｂ高。
　　请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。
　　（注：比较结果中没有涉及的士兵不参加排队）
输入说明 :
　　比较结果从文本文件中读入（文件由键盘输入），每个比较结果在文本文件中占一行。
输出说明 :
　　若输入数据无解，打印“No Answer!”信息，否则从高到矮依次输出每一个士兵的编号，中间无分割符，并把结果写入文本文件中，文件由键盘输入：

#include<stdio.h>//Author:summershell
#include<string.h>
#include<queue>//拓扑排序问题，寻找入度为0的点
#include<vector>
#include<algorithm>
using namespace std;
vector<int> edge[30];//用加入结点的先后来对同样入度为0的结点处理时候的排列顺序处理
int visit[30],degree[30];//degree表示入度
char str[100];
vector<int>::iterator it;
int TopSort()
{
    std::queue<int>que;
    int count=0,c=0;//一共多少结点,用于判断拓扑是否成功
    for(int i=0;i<27;++i)
    {
        if(visit[i])
        {
            count++;
            if(degree[i]==0)que.push(i);//把入度为0的点进队
        }
    }
    while(!que.empty())
    {
        int p=que.front();
        que.pop();//出队了
        str[c++]=p+'A';
        for(it=edge[p].begin();it!=edge[p].end() ;++it)
        {
            if(visit[*it])//寻找p的尾结点，减少出度
            {
                if(--degree[*it]==0)
                    que.push(*it);
            }
        }
    }
    str[c]='\0';
    return count-c==0?1:0;
}
int main()
{
    //freopen("in.txt","r",stdin);
    memset(visit,0,sizeof(visit));
    memset(edge,0,sizeof(edge));
    memset(degree,0,sizeof(degree));
    char x,y;
    while(scanf("%c>%c ",&x,&y)!=EOF)
    {
        if(x==y){puts("No Answer!");return 0;}
        visit[x-'A']=visit[y-'A']=1;//代表来比较了
        it=find(edge[x-'A'].begin(),edge[x-'A'].end(),y-'A');
        if(it==edge[x-'A'].end())
        {
            edge[x-'A'].push_back(y-'A');
            degree[y-'A']++;
        }
    }
    printf(TopSort()?"%s\n":"No Answer!\n",str);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

如果有问题交流咨询，可以加入QQ群：673852347

28 师座操作系统

作者: Turbo 时间限制: 1S 章节: 结构体

问题描述 :
　　师座这天在程序设计课上学了指针和结构体以后，觉得自己可以轻松的写出操作系统，为了打败大微软帝国，他给这个系统起了个响亮的名字“师座操作系统”，你是师座手下的首席架构师，被要求写这个操作系统的文件系统部分，要求如下：
　　这个文件系统有的所有文件都有一个独一无二的文件名，除此之外分为两类文件，一类文件是数据存储文件，它可以存储一个字符串信息，另一类文件是快捷方式，它会指向另一个文件，有可能是数据块也有可能是快捷方式。
　　.
　　这个文件系统支持3条命令：
　　1.创建命令：create
　　这个命令的意思是，创建一个文件名为，文件类型为，文件信息为，文件类型为0或者1,0表示数据块，1表示快捷方式，如果是数据块，那么表示储存的字符串，如果这是一个快捷方式，表示指向的文件的名称，如果当前已存在名为的文件，则更新这个文件的信息。
　　.
　　2.打开命令：open
　　这个命令是打开文件名为的文件，如果这是一个快捷方式，则会打开这个快捷方式指向的文件，直到打开一个数据块时，显示这个数据块储存的信息并换行。
　　.
　　3.退出命令：exit
　　得到这个命令以后，你的程序需要安全终止。
输入说明 :
　　若干条命令构成，最后一条命令必然为exit。

总命令条数不超过1000条。
　　保证，，不包含空格和不合法字符，每个长度不超过20个字符。
输出说明 :
　　输出每次使用open命令的显示结果。

#include<stdio.h>//Author:summershell
#include<string.h>
#include<iostream>
#include<map>
using namespace std;
typedef struct node
{
    int type;
    string info;
}Nod;//string类到结构体的映射
int main()//map大法好哇
{
    map<string,Nod>system;
    map<string,Nod>::iterator it;

    char s[30];
    string name;
    Nod temp;
    while(scanf("%s",s)!=EOF && strcmp(s,"exit")!=0)
    {
        if(strcmp(s,"create")==0)
        {
            cin>>name;
            scanf("%d",&(temp.type));
            cin>>temp.info;
            system.erase(name);
            system.insert(pair<string,Nod>(name,temp));//map的插入
        }
        if(strcmp(s,"open")==0)
        {
            cin>>name;
            it=system.find(name);
            while((it->second).type==1)
            {
                it=system.find((it->second).info);
            }
            cout<<(it->second).info<<endl;
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

29 洗牌

作者: Turbo 时间限制: 1S 章节: 基本练习（字符串）

问题描述 :
　　小弱T在闲暇的时候会和室友打扑克，输的人就要负责洗牌。虽然小弱T不怎么会洗牌，但是他却总是输。
　　渐渐地小弱T发现了一个规律：只要自己洗牌，自己就一定会输。所以小弱T认为自己洗牌不够均匀，就独创了一种小弱洗牌法。
　　小弱洗牌法是这样做的：先用传统洗牌法将52张扑克牌（1到K各四张，除去大小王）打乱，放成一堆，然后每次从牌堆顶层拿一张牌放到手中（初始时手中无牌）。如果这张牌的大小是P（1到K的大小分别为1到13），那么就把这张牌插入到当前手中第P张牌的后面。如果当前手中不足P张牌，那么就把这张牌放在最后。
　　现在给你一对已经被打乱的牌，请你用小弱洗牌法进行洗牌，然后输出最后手中牌的序列。
　　注意：小弱可能在第一次洗牌时弄丢了某些牌，这时请你输出一个-1来提醒他牌的数目不够。
输入说明 :
　　测试数据的输入含N个用空格隔开的字符串表示牌堆从顶至底的每张扑克（1到K中的某个）。可能有多行。
输出说明 :
　　如果字符串的个数N为52，则输出用小弱洗牌法洗牌后的序列，每个字符串后都有一个空格。
　　否则请输出一个-1.

#include<stdio.h>//Author:summershell
#include<string.h>
int main()
{
    char str[2020],c[10];//有10,还有JQK，不好办。把10变成*
    int len=0;
    while(scanf("%s",c)!=EOF)
    {
        if(strlen(c)==2)str[len++]='*';
        else str[len++]=c[0];
    }
    str[len]='\0';
    if(len!=52)printf("-1\n");
    else
    {
        char s[2020];
        int lens=0,pos=0,temp;//pos当前在牌堆的第几张牌了
        while(lens<52)//牌堆洗完之前
        {
            if(str[pos]=='J')temp=11;
            else if(str[pos]=='Q')temp=12;
            else if(str[pos]=='K')temp=13;
            else if(str[pos]=='*')temp=10;
            else temp=str[pos]-'0';

            if(temp>=lens)s[lens]=str[pos];
            else//否则就移动元素
            {
                for(int i=lens;i>=temp;--i)s[i+1]=s[i];
                s[temp]=str[pos];
            }
            lens++;
            pos++;
        }
        for(int i=0;i<52;++i)printf(s[i]=='*'?"10 ":"%c ",s[i]);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

如果有问题交流咨询，可以加入QQ群：673852347

30 盾神与砝码称重

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太难了，于是就丢给了你。
注意：砝码可以和物品一起放在天平的同一边。
输入说明 :
　　第一行为两个数，n和m。
　　第二行为n个数，表示这n个砝码的重量。
　　第三行为m个数，表示这m个物品的重量。

  1<=n<=24, 1<=m<=10.

  • 1

输出说明 :
　　输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。

#include<stdio.h>//Author:summershell
#include<algorithm>// 在企图用dp解决这道题的时候 还是DFS香一些
#include<stdlib.h>
int m,n,fama[30],sum[30],temp,flag; 
int DFS(int weight,int num)
{//weight是要称的重量 num是砝码的序号
    if(flag || num<0 || abs(weight)>sum[num])//当已经称出 或者越界
        return 0;//或者接下来的重量肯定无法称出 就回去 因为没那么多了
    if(weight==0 || abs(weight)==sum[num])
    {
        flag=1;
        return 1;
    }//选择放在物品对面 或者不放 或者和物品一边
    return DFS(weight-fama[num],num-1) || DFS(weight,num-1) || DFS(weight+fama[num],num-1);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i) scanf("%d",&fama[i]);
    std::sort(fama,fama+n);
    for(int i=0;i<n;++i) sum[i]=i?fama[i]+sum[i-1]:fama[i];//把砝码的前部分和求出 便于剪枝
    for(int i=0;i<m;++i)
    {
        scanf("%d",&temp);
        flag=0;
        printf("%s\n",DFS(temp,n-1)?"YES":"NO");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
//下面是我的DP版本的代码 留着警醒我自己吧
 

  • 1
  • 2
//第一次的dp代码
#include<stdio.h>//Author:summershell
#include<string.h>
#define max 10000000
int dp[max],dpt[max];//DFS超时了，用dp做一下，由于可以让砝码放在物品的一侧，也就是我们能称出物品-砝码i 也是可以的
int main()// 我尽力了 0.75分 最后一个case
{
    int m,n,temp;
    scanf("%d %d",&n,&m);
    dp[max/2]=1;//由于要先减去一部分砝码 所以可能出现负值 那么加大下限来处理
    for(int i=0;i<n;++i)
	{
		scanf("%d",&temp);
		memcpy(dpt,dp,sizeof(dp));//由于要保证无后效性，所以 把结果分开
		dpt[max/2+temp]=1;
		for(int j=0;j<max;++j)
		{
			if(dp[j])//如果j是已称出来的
			{
				dpt[j+temp]=1;
				if(j-temp>0)dpt[j-temp]=1;//代表放在物品那一侧可以得到的重量
			}
		}
		memcpy(dp,dpt,sizeof(dp));
	}
    for(int i=0;i<m;++i)
    {
        scanf("%d",&temp);
        puts(dp[max/2+temp]||dp[max/2-temp]?"YES":"NO");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
//2次dp 另一个版本的 最后两个case没过
#include<stdio.h>//Author:summershell
#include<vector>
#define max 116777217
using namespace std;
//long long int dp[max],top=-1;//DFS超时了，用dp做一下，由于可以让砝码放在物品的一侧，也就是我们能称出物品-砝码i 也是可以的
long long int top=-1;
vector<long long int>dp;
int main()// 我尽力了 0.75分 最后一个case
{
    int m,n,temp;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i)
	{
		scanf("%d",&temp);
		long long int len=dp.size();
		dp.push_back(temp);
		for(long long int j=0;j<len;j++)
		{
			dp.push_back(dp[j]+temp);
			dp.push_back(dp[j]-temp);
		}
	}
    for(long long int i=0,j;i<m;++i)
    {
        scanf("%d",&temp);
        long long int len=dp.size();
        for(j=0;j<len;++j)
			if(dp[j]==temp || dp[j]+temp==0)break;
		puts(j<len?"YES":"NO");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
//3次dp代码
#include<stdio.h>//Author:summershell
#include<map>
#define max 10000000
using namespace std;
map<int,bool>dp;//DFS超时了，用dp做一下，由于可以让砝码放在物品的一侧，也就是我们能称出物品-砝码i 也是可以的
map<int,bool>dpt;
map<int,bool>::iterator it;
int main()// 我尽力了 0.75分 最后一个case
{
    int m,n,temp;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i)
	{
		scanf("%d",&temp);
		it=dp.begin();
		dpt.clear();
		dpt[temp]=true;
		while(it!=dp.end())
        {
            dpt[it->first +temp]=true;
            dpt[it->first -temp]=true;
            ++it;
        }
		it=dpt.begin();
		while(it!=dpt.end())
        {
            dp[it->first]=true;
            it++;
        }
	}
    for(int i=0;i<m;++i)
    {
        scanf("%d",&temp);
        puts(dp[temp]||dp[-temp]?"YES":"NO");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

如果有问题交流咨询，可以加入QQ群：673852347

31 文化之旅

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
　　现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

样例输入
2 2 1 1 2
1 2
0 1
1 0
1 2 10
样例输出
-1
输入输出样例说明
　　由于到国家2必须要经过国家1，而国家2的文明却排斥国家1的文明，所以不可能到达国家2。

样例输入
2 2 1 1 2
1 2
0 1
0 0
1 2 10
样例输出
10
输入输出样例说明
　　路线为1 -> 2。

输入说明 :
　　第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为1到N），文化种数（文化编号为1到K），道路的条数，以及起点和终点的编号（保证S不等于T）；
　　第二行为N个整数，每两个整数之间用一个空格隔开，其中第i个数Ci，表示国家i的文化为Ci。
　　接下来的K行，每行K个整数，每两个整数之间用一个空格隔开，记第i行的第j个数为aij，aij= 1表示文化i排斥外来文化j（i等于j时表示排斥相同文化的外来人），aij= 0表示不排斥（注意i排斥j并不保证j一定也排斥i）。
　　接下来的M行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u与国家v有一条距离为d的可双向通行的道路（保证u不等于v，两个国家之间可能有多条道路）。
输出说明 :
　　输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。

   2≤N≤100，1≤K≤100，1≤M≤ N^2，1≤ki≤K，1≤u, v≤N，1≤d≤1000，S≠T，1 ≤S, T≤N。

  • 1
#include<stdio.h>//Author:summershell
#include<string.h>
#include<algorithm>
int e[110][110],culture[110][110],country[110],visit[110];//国家和文化的邻接矩阵
int N,K,M,S,T,learn[110],ans;

int judge(int x,int y)//判断学过的文化和x国家有冲突没有
{
    if(culture[ country[y] ][ country[x] ])return 0;
    if(culture[ country[T] ][ country[y] ])return 0;//如果终点国家排斥
    for(int i=1;i<=learn[0];++i)
    {
        if(culture[learn[y]][country[i]])return 0;
    }
    return 1;
}
int dfs(int deep,int dis)
{
    if(ans!=-1 && dis>=ans)return 0;//剪枝操作
    if(deep==T)
    {
        ans=dis;//由于上一句的原因 那么能进来的肯定是比较小的距离
        return 1;
    }
    for(int i=1;i<=N;++i)//遍历的邻边
    {
        if(deep==i)continue;
        if(visit[i]==0 && judge(deep,i))//如果学过的文化和他没有冲突
        {
            visit[i]=1;
            learn[0]++;
            learn[learn[0]]=country[i];
            dfs(i,dis+e[deep][i]);//递归
            learn[0]--;
            visit[i]=0;
        }
    }
    return 1;
}
int main()
{
    scanf("%d %d %d %d %d",&N,&K,&M,&S,&T);
    for(int i=1;i<=N;++i)
        scanf("%d",&country[i]);
    for(int i=1;i<=K;++i)
        for(int j=1;j<=K;++j)
            scanf("%d",&culture[i][j]);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            e[i][j]=9999;//对于题目来说 足够了
    for(int i=1;i<=M;++i)
    {
        int u,v,d;
        scanf("%d %d %d",&u,&v,&d);
        if(!culture[country[v]][country[u]] && country[u]!=country[v])
            e[u][v]=std::min(e[u][v],d);//这个顺序别搞反了，应该是你的国家不排斥我 我就可以过去，尽管 我排斥你
        if(!culture[country[u]][country[v]] && country[u]!=country[v])
            e[v][u]=std::min(e[v][u],d);
    }
    learn[0]=1;//存储已经学过的
    learn[1]=country[S];
    ans=-1;
    memset(visit,0,sizeof(visit));
    visit[S]=1;
    dfs(S,0);
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

32 网络警察

作者: Turbo 时间限制: 1S 章节: 基本练习（字符串）

问题描述 :
作为一名网络警察，你的任务是监视电子邮件，看其中是否有一些敏感的关键词。不过，有些狡猾的犯罪嫌疑人会改变某些单词的字母顺序，以逃避检查。请编写一个程序，发现这种调整过顺序的关键词。
输入说明 :
输入有两行，第一行是关键词列表，第二行是待检查的句子。
单词全部为小写，单词之间以一个空格分隔，每一行的单词个数不限
输出说明 :
输出为在该句子中所找到的经过顺序调整的关键词
按照在关键词列表中的先后顺序输出

#include<stdio.h>//Author:summershell
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *(char *)a - *(char *)b;
}
int main()
{
    char key[2020][20],str[2020],c;
    int i=0,j=0,flag[2020];//表示关键词是否出现过
    while((c=getchar()) && c!='\n')
    {
        if(c==' '){key[i][j]='\0';j=0;i++;}
        else key[i][j++]=c;
    }
    key[i][j]='\0';//录入关键词完毕
    memset(flag,0,sizeof(flag));
    while(scanf("%s",str)!=EOF)
    {//灵光一闪 想到了对比两个单词的好方法
        int len1=strlen(str);
        qsort(str,len1,sizeof(str[0]),cmp);
        for(int k=0;k<=i;k++)
        {
            int len2=strlen(key[k]);
            if(len1==len2)//只有长度一样才可以比较
            {
                char temp[2020];
                strcpy(temp,key[k]);
                qsort(temp,len2,sizeof(temp[0]),cmp);
                if(strcmp(temp,str)==0)flag[k]=1;
            }
        }
    }
    for(int coun=0,j=0;j<=i;j++)
        if(flag[j]==1)printf(coun++==0?"%s":" %s",key[j]);
    printf("\n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

33 线段和点

作者: Turbo 时间限制: 1S 章节: 其它

问题描述 :
　　有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a>=b且a<=c，称点a满足区间[b,c]。
　　求最小的点的子集，使得所有区间都被满足。
输入说明 :
　　第一行两个整数n m
　　以下n行 每行一个整数，代表点的坐标
　　以下m行 每行两个整数，代表区间的范围

1<=n,m<=10000
　　0<=点和区间的坐标<=50000
输出说明 :
　　输出一行，最少的满足所有区间的点数，如无解输出-1。

#include<stdio.h>//Author:summershell
#include<stdlib.h>
#include<string.h>
typedef struct lineNode
{
    int left,right;
}line;
int cmp(const void *a,const void *b)
{
    line x=*(line *)a,y=*(line *)b;
    if(x.left!=y.left)return x.left - y.left;
    else  return x.right - y.right;
}
int main()//将区间排序，然后遍历各段区间，对当前区间的各个坐标遍历，
//遍历时候的原则是尽量包含多的区间，且不能跑出前面的任何一个区间，如果跑出就停止遍历，记录下最大的点的位置
{
    int m,n,ans=0,x,y,temp,dot[51001];//记录点，且把他能包含的最多段区间数记录到其中
    line L[100001];
    memset(L,0,sizeof(L));
    memset(dot,0,sizeof(dot));
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i){
        scanf("%d",&temp);
        dot[temp]=1;
    }
    for(int i=0;i<m;++i){
        scanf("%d %d",&x,&y);
        L[i].left=x;L[i].right=y;
    }
    qsort(L,m,sizeof(L[0]),cmp);
    for(int i=0;i<m;++i){//遍历所有区间段
        int maxnum=-1;
        for(int j=L[i].left;j<=L[i].right;++j){//遍历所有的点
            if(dot[j]){//若存在该点
                dot[j]=1;//一定要重置为1.因为有可能他在上一组的运算中赋值很大
                for(int k=i+1;k<m;k++){
                    if(j>= L[k].left && j<=L[k].right)dot[j]++;
                    else break;
                }
                if(maxnum<dot[j])maxnum=dot[j];
            }
        }
        if(maxnum==-1){printf("-1\n");return 0;}
        ans++;
        i=i-1+maxnum;//若存在 则计数，且过滤掉已经包含的区间
    }
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

如果有问题交流咨询，可以加入QQ群：673852347

34 我们的征途是星辰大海

作者: Turbo 时间限制: 1S 章节: 模拟

问题描述 :
　　最新的火星探测机器人curiosity被困在了一个二维迷宫里，迷宫由一个个方格组成。
　　共有四种方格：
　　‘.’ 代表空地，curiosity可以穿过它
　　‘#’ 代表障碍物，不可穿越，不可停留
　　‘S’ 代表curiosity的起始位置
　　‘T’ 代表curiosity的目的地
　　NASA将会发送一系列的命令给curiosity，格式如下：“LRUD”分别代表向左，向右，向上，向下走一步。由于地球和火星之间最近时也有55000000km！所以我们必须提前判断这一系列的指令会让curiosity最终处在什么样的状态，请编程完成它。
输入说明 :
　　第一行是一个整数T，代表有几个测试样例
　　每个测试样例第一行是一个整数N（1<=N<=50））代表迷宫的大小（N*N）。随后的N行每行由N个字符串组成，代表迷宫。接下来的一行是一个整数Q，代表有多少次询问，接下来的Q行每行是一个仅由“LRUD”四个字母的组成的字符串，字符转长度小于1000.
输出说明 :
　　对于每个询问输出单独的一行：
　　“I get there!”：执行给出的命令后curiosity最终到达了终点。
　　“I have no idea!”：执行给出的命令后curiosity未能到达终点。
　　“I am dizzy!”：curiosity在执行命令的过程中撞到了障碍物。
　　“I am out!”：代表curiosity在执行命令的过程中走出了迷宫的边界。

#include<stdio.h>//Author:summershell
#include<string.h>//简单模拟,直接写吧，把xy控制好就行
int T,N,Q;
char maze[100][100],quest[2020];
void operate(int x,int y)
{
    int len=strlen(quest);
    for(int i=0;i<len;++i)
    {
        if(quest[i]=='R')y++;
        else if(quest[i]=='L')y--;
        else if(quest[i]=='U')x--;
        else if(quest[i]=='D')x++;
        if(x>N || x<1 || y>N || y<1)
        {
            puts("I am out!");
            return;
        }
        else if(maze[x][y]=='#')
        {
            puts("I am dizzy!");
            return;
        }
        else if(maze[x][y]=='T')
        {
            puts("I get there!");
            return;
        }
    }
    puts("I have no idea!");
}
int main()
{
    scanf("%d ",&T);
    while(T--)
    {
        memset(maze,0,sizeof(maze));
        int x=0,y=0;//起始位置的坐标
        scanf("%d ",&N);
        for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=N;++j)
            {
                scanf("%c",&maze[i][j]);
                if(maze[i][j]=='S'){x=i;y=j;}
            }
            getchar();
        }
        scanf("%d ",&Q);
        for(int i=1;i<=Q;++i)
        {
            gets(quest);
            operate(x,y);
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

35 快速幂

作者: Turbo 时间限制: 1S 章节: 数学相关

问题描述 :
　　给定A, B, P，求(A^B) mod P。
输入说明 :
　　输入共一行。
　　第一行有三个数，A, B, P。
A, B为long long范围内的非负整数，P为int内的非负整数。
输出说明 :
　　输出共一行，表示所求。

#include<stdio.h>//Author:summershell
int main()//快速幂有规律
{
    long long a,b,ans;
    int p;
    scanf("%lld %lld %d",&a,&b,&p);
    ans=1;
    a%=p;
    while(b>0)
    {
        if(b&1)ans=ans*a%p;//奇数要多乘一次
        a=a*a%p;
        b>>=1;//b除2
    }
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

36 日历

作者: Turbo 时间限制: 1S 章节: 基本练习（循环）

问题描述 :
　　已知2007年1月1日为星期一。设计一函数按照下述格式打印2007年以后（含）某年某月的日历，2007年以前的拒绝打印。为完成此函数，设计必要的辅助函数也是必要的。
输入说明 :
两个整数，表示年和月，以空格分隔
输出说明 :
按照范例输出
注意各个位置的空格数目，特别是每一行的末尾是否有空格。

#include<stdio.h>//Author:summershell
int RunNian(int year)
{
    return (year%400==0 ||(year%4==0 && year%100!=0));
}
int main()
{
    int yy,mm,x,y,week=1;//0代表周日
    int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    scanf("%d %d",&x,&y);
    for(yy=2007;yy<x;++yy)
    {
        int days=365;
        if(RunNian(yy))days++;
        days=days%7;
        week=(week+days)%7;
    }//已经算得x年开头的星期几
    if(RunNian(x))month[2]=29;
    for(mm=1;mm<y;++mm)
    {
        week=(week+month[mm])%7;
    }//算得mm月开头是星期几
    printf("Calendar %d - %02d\n",yy,mm);//开始打印
    printf("---------------------\n");
    printf("Su Mo Tu We Th Fr Sa\n");
    printf("---------------------\n");
    int count=1;
    for(int i=0;i<7;++i)//打印第一行
        if(i<week)printf("   ");
        else printf("%2d ",count++);
    printf("\n");
    week=0;
    while(count<=month[mm])
    {
        printf("%2d ",count++);
        if(++week%7==0)printf("\n");
    }
    if(week%7!=0)printf("\n");
    printf("---------------------");

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

如果有问题交流咨询，可以加入QQ群：673852347

37 分离度

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　在我们联系日益紧密的世界里，人们推测每个人和其他人的分离度不超过六（六度分离）。在这个问题里，你需要写一个程序来找出人们的关系网络中最大的分离度。
　　对于任意两个人，他们的分离度是联系两个人需要经过的最小的关系数。对于一个关系网络，最大的分离度是网络中任意两人的分离度的最大值。如果一个网络中有两个人没有通过关系链连接起来，这个网络是不连通的。
　　如下图所示，一个网络可以用一些连接两个人的对称关系来描述。一条线段表示两个人之间有联系。网络A描述了一个分离度最大值为2的网络，网络B没有连通。
输入说明 :
　　输入包含多组描述关系网络的数据，对于每组数据，第一行有两个数P，表示网络中人的数目，和R，关系的对数。接下来一行是R个关系。每个关系用两个字符串表示，代表网络中有关系的两个人的名字。每个名字是不同的，并且中间没有空格。因为一个人可能和多个人有联系，一个名字可能在一组数据中出现多次。
　　最后以一行两个0表示结束。

  2<=P<=50，R>=1

  • 1

输出说明 :
　　对于每个网络，输出网络中最大的分离度。如果这个网络是不连通的，输出DISCONNECTED。每一个网络输出后再输出一个回车。按照样例输出中的格式输出。

#include<stdio.h>//Author:summershell
#include<iostream>//直接弗洛伊德吧
#include<string.h>
#include<map>
using namespace std;
map<string,int>people;
int edge[100][100];
int main()
{
    int t=1,x,y;
    char name1[100],name2[100];
    while(scanf("%d %d",&x,&y)!=EOF && x+y)
	{
		people.clear();
		memset(edge,0x3f3f3f3f,sizeof(edge));
		int pos=1;
		for(int i=0;i<y;++i)
		{
			scanf(" %s %s",name1,name2);
			if(people[name1]==0)//如果是新成员
				people[name1]=pos++;
			if(people[name2]==0)//如果是新成员
				people[name2]=pos++;
			edge[people[name1]][people[name2]]=1;
			edge[people[name2]][people[name1]]=1;
		}
		if(pos!=x+1)//人不够那么多 肯定是非连通的
		{
			printf("Network %d: DISCONNECTED\n\n",t++);
			continue;
		}
		for(int k=1;k<=x;k++)
			for(int i=1;i<=x;++i)
				for(int j=1;j<=x;++j)//把自己到自己的情况去掉
				if(i!=j && k!=i && k!=j && edge[i][k]+edge[k][j]<edge[i][j])edge[j][i]=edge[i][j]=edge[i][k]+edge[k][j];
		int flag=1,dis=-1;
		for(int i=1;i<=x && flag;++i)
			for(int j=i+1;j<=x && flag;++j)
			{
				if(edge[i][j]==0x3f3f3f3f)flag=0;
				if(edge[i][j]>dis)dis=edge[i][j];
			}
		if(!flag)printf("Network %d: DISCONNECTED\n\n",t++);
		else printf("Network %d: %d\n\n",t++,dis);
	}
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

38 矩阵翻转

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
Ciel有一个NN的矩阵，每个格子里都有一个整数。
N是一个奇数，设X = (N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个XX的子矩阵，并将这个子矩阵中的所有整数都乘以-1。
现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。

输入说明 :
第一行为一个正整数N。
接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1000。
1 <= N <= 33，且N为奇数。

输出说明 :
输出一个整数，表示操作后矩阵中所有数之和的最大值。

#include<stdio.h>//  借鉴了网上的代码
#include<stdlib.h>
#define max(a,b) a>b?a:b
int n,a[40][40],x,ans=-999999999;
void computing()
{
    int maxnum=0,ta,tb;
    for(int i=0;i<n;++i)maxnum+=a[x-1][i];
    for(int i=0;i<x-1;++i)
    {
        ta=-999999999;
        tb=a[i][x-1]+a[i+x][x-1];
        for(int j=0;j<x-1;++j)tb+=abs(a[i][j]+a[i][j+x]+a[i+x][j]+a[i+x][j+x]);
        ta=max(ta,tb);
        tb=-1*(a[i][x-1]+a[i+x][x-1]);
        for(int j=0;j<x-1;++j)tb+=abs( -1*a[i][j]+a[i][j+x]-a[i+x][j]+a[x+i][j+x] );
        ta=max(ta,tb);
        maxnum+=ta;
    }
    ans=max(maxnum,ans);
}

void solve()
{
    for(int k=0;k<(1<<x-1);++k)//一定得是位运算 不然WA
    {
        for(int j=0;j<x-1;++j)
            if((k&(1<<j))!=0)//位运算
            {
                for(int i=0;i<x;++i)
                {
                    a[i][j]*=-1;
                    a[i][j+x]*=-1;
                }
            }
        computing();
        for(int j=0;j<x-1;++j)
            if((k&(1<<j))!=0)//位运算
            {
                for(int i=0;i<x;++i)
                {
                    a[i][j]*=-1;
                    a[i][j+x]*=-1;
                }
            }
    }
}
int main()
{
    scanf("%d",&n);
    x=(n+1)/2;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)scanf("%d",&a[i][j]);
    solve();
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

39 最大乘积

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？
输入说明 :
　　第一行一个数表示数据组数
　　每组输入数据共2行：
　　第1行给出总共的数字的个数n和要取的数的个数m，1<=n<=m<=15，
　　第2行依次给出这n个数，其中每个数字的范围满足:a[i]的绝对值小于等于4。
输出说明 :
　　每组数据输出1行，为最大的乘积。

#include<stdio.h>
int T,m,n,num[20],ans,flag[20];
void dfs(int sum,int deep)//把结果放到参数里面，省时一点
{
	if(deep>m)return;//剪枝
	if(deep==m)
	{
		ans=ans>sum?ans:sum;
		return;
	}
	for(int i=0;i<n;++i)
	{
		if(flag[i]==0)
		{
			flag[i]=1;
			dfs(sum*num[i],deep+1);
			flag[i]=0;
		}
	}
}

int main()//排列组合的赶脚，无情TLE。加个剪枝
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;++i)
		{
			scanf("%d",&num[i]);
			flag[i]=0;
		}
		ans=-999999999;
		dfs(1,0);//从0开始 计数
		printf("%d\n",ans);
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

如果有问题交流咨询，可以加入QQ群：673852347

40 排列数

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　0、1、2三个数字的全排列有六种，按照字母序排列如下：
　　012、021、102、120、201、210
　　输入一个数n
　　求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入说明 :
　　一行，包含一个整数n
输出说明 :
　　一行，包含一组10个数字的全排列

#include<stdio.h>
int n,num[20],flag[20],pos,ans;
void dfs(int sum,int deep)
{
	if(deep==10)
	{
		ans++;
		if(ans==n)
		{
			for(int i=0;i<=pos;++i)printf("%d",num[i]);
			printf("\n");
		}
		return;
	}
	for(int i=0;i<10;++i)
	{
		if(flag[i]==0)
		{
			flag[i]=1;
			num[++pos]=i;
			dfs(10*sum+i,deep+1);
			--pos;
			flag[i]=0;
		}
	}
}

int main()//排列组合。开整
{
	scanf("%d",&n);
	pos=-1;
	dfs(0,0);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

41 盾神与条状项链

作者: Turbo 时间限制: 1S 章节: 模拟

问题描述 :
　　有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
　　“哇这么恶心的项链你也做得出来！！！”
　　盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
　　“这个嘛首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧”土方一下子说出了m个修改步骤。
　　盾神觉得这个用人工做太麻烦了，于是交给了你。
输入说明 :
　　第一行两个数，分别为n，m。
　　第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
　　接下来m行，为以下形式之一：
　　ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
　　DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
　　输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。

  表示颜色的数字不超过10^5的正数，1<=n<=10^4，1<=m<=10^4。

  • 1

输出说明 :
　　第一行为一个数len，为做完所有操作后，项链的长度。
　　第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。

#include<stdio.h>//Author:summershell
#include<string.h>
#include<stdlib.h>//链表操作
typedef struct nod
{
	int data;
	struct nod *next;
}node;
int n,m,len;

void init(node *&head)
{
	node *p,*r;
	head=(node*)malloc(sizeof(node));
	head->next=NULL;
	r=head;
	len=n;
	for(int i=0;i<n;++i)
	{
		p=(node*)malloc(sizeof(node));
		scanf("%d",&(p->data));
		p->next=NULL;
		r->next=p;
		r=p;
	}
}
void add(node *head,int p,int q)
{
	node *pre=head,*t;
	while(pre->next->data!=p && pre->next)pre=pre->next;//找到p
	t=(node *)malloc(sizeof(node));
	t->data=q;
	t->next=pre->next;
	pre->next=t;
	len++;
}
void del(node *head,int p)
{
	node *pre=head,*t;
	while(pre->next->data!=p)pre=pre->next;
	t=pre->next;//肯定能找到 所以不用担心找不到
	pre->next=pre->next->next;
	free(t);
	len--;
}
int main()
{
	node *head;		//怎能无表头呢
	scanf("%d %d",&n,&m);
	init(head);
	while(m--)
	{
		char str[100];
		int p,q;
		scanf("%s",str);
		if(strcmp(str,"ADD")==0)
		{
			scanf(" %d %d",&p,&q);
			add(head,p,q);
		}
		if(strcmp(str,"DEL")==0)
		{
			scanf(" %d",&p);
			del(head,p);
		}
	}
	printf("%d\n",len);
	while(head->next)
	{
		printf("%d ",head->next->data);
		head=head->next;
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74

如果有问题交流咨询，可以加入QQ群：673852347

42 Cutting Chains

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　什么！Anna Locke最近买了几个链环，并且其中的一些链环连接到了一起。
　　Anna想要把这些链环拼组成连续的一段链。她把这些链环带到一个珠宝商那里，珠宝商告诉她合并这些链环的费用取决于必须打开和关上的环的数目。为了最小化这个费用，她小心地计算为了合并成一个单独的序列所需要打开的最小的环的数目。这个比她想象中更困难。请你为她解决这个问题。
输入说明 :
　　输入包含多组关于链环集合的描述，对于每一组。每个链环集合由一行用一个或多个空格隔开的数字表示。
每个描述由一个n开始，表示链环集合中环的数量。我们把这些环编号为1,2,…,n。
紧接着n后面的整数描述了哪些环连接在一起。每个连接由一对整数i，j（1<=i,j<=n并且i≠j）来描述，代表环i和环j连接，即一个穿过另一个。每个链环集合用一对-1 -1表示结束（-1 -1 不用进行计算）
　　输入用n=0表示结束，并且n=0不用进行计算
1<=n<=15
输出说明 :
　　对于每一个输入的链环集合，输出一行形如
　　Set N: Minimum links to open is M
　　N是测试数据的组号，M是最小需要打开然后关闭的次数来使所有环组成一条单独的链。
　　1<=i,j<=n并且i≠j

#include<stdio.h>//借鉴了网上的代码 用C提交
#include<string.h>
#define min(a,b) a<b?a:b
int n,num,maxn=20,edge[20][20],vis[20];
int branch(int x)//分支数目
{
    for(int i=0;i<n;++i)
    {
        if(x&(1<<i))continue;
        int cnt=0;
        for(int j=0;j<n;++j)
        {
            if(x&(1<<j))continue;//已经打开的环
            if(edge[i][j])++cnt;//若其与其他环相连+1
        }
        if(cnt>2)return 1;//大于0 结束
    }
    return 0;
}
int dfs(int s,int now,int pre)
{//now是当前环 pre是上一个
    vis[now]=1;
    for(int i=0;i<n;++i)
    {
        if((s&(1<<i)) || !edge[now][i] || i==pre)continue;//如果已经打开或者遇见自己就跳过
        if(vis[i]||dfs(s,i,now))return 1;
    }
    return 0;
}
int circle(int x)
{
    for(int i=0;i<n;++i)
    {
        if(x&(1<<i)||vis[i])continue;
        ++num;
        if(dfs(x,i,-1))return 1;
    }
    return 0;
}
int cal(int x)
{//计算要打开的环的数量
    return x==0?0:cal(x/2)+(x&1);
}
int solve()
{
    int ans=n-1;//最多打开的数目
    for(int i=0;i<(1<<n);++i)
    {
        memset(vis,0,sizeof(vis));
        num=0;
        if(branch(i)||circle(i))continue;//若有环或者分支大于2
        //int temp=cal(i);
        if(cal(i)>=num-1)ans=min(ans,cal(i));//如果能够连起来，就更新ans
    }
    return ans;
}
int main()
{
    int cou=0;
    while(scanf("%d",&n) && n)
    {
        memset(edge,0,sizeof(edge));
        int x,y;
        while(scanf("%d %d",&x,&y) && x+y>0)
        {
            edge[x-1][y-1]=1;
            edge[y-1][x-1]=1;
        }
        printf("Set %d: Minimum links to open is %d\n", ++cou, solve());
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72

43 最少操作数

作者: Turbo 时间限制: 1S 章节: 基本练习（数组）

问题描述 :
　　数组A中共有n个元素，初始全为0。你可以对数组进行两种操作：1、将数组中的一个元素加1；2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入说明 :
　　第一行一个正整数n表示数组中元素的个数
　　第二行n个正整数表示目标状态B中的元素
　　n<=50，B[i]<=1000
输出说明 :
　　输出一行表示最少操作数

#include<iostream>//Author:summershell
int a[55],n;//逆向考虑 如果是奇数就-1，方便除2呀，如果全是偶数/2
__int64 ans=0;
int judge()//判断是否全是0
{
    for(int i=0;i<n;++i)
        if(a[i]!=0)return 0;
    return 1;
}
int main()
{
    std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>a[i];
    while(1)
    {
        for(int i=0;i<n;++i)//是奇数就-1
            if(a[i]&1){
                a[i]--;
                ans++;
            }
        if(judge())break;
        for(int i=0;i<n;++i)a[i]/=2;
        ans++;
    }
    std::cout<<ans<<std::endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

44 多项式输出

作者: Turbo 时间限制: 1S 章节: 基本练习（数组）

问题描述 :
　　一元n 次多项式可用如下的表达式表示：

f(x)=a[n]x^n+a[n-1]x^(n-1)+...+a[1]x+a[0], a[n]!=0

  • 1

其中，a[i]x^i称为i 次项， a[i]称为i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
　　1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
　　2. 多项式中只包含系数不为0 的项。
　　3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系数为负，则多项式以“-”号开头。
　　4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。
　　5. 多项式中，多项式的开头、结尾不含多余的空格。
输入说明 :
　　输入共有2 行
　　第一行1 个整数，n，表示一元多项式的次数。
　　第二行有n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空格隔开。
　　1 ≤ n ≤ 100，多项式各次项系数的绝对值均不超过100。
输出说明 :
　　输出共1 行，按题目所述格式输出多项式。

#include<stdio.h>
void printX(int b)
{
	if(b!=0)
	{
		printf("x");
		if(b!=1)printf("^%d",b);
	}
}
int main()
{
	int n,b;
	scanf("%d %d",&n,&b);
	if(b<0)printf("-");
	if(b!=1 && b!=-1)printf("%d",b>0?b:-b);
	printX(n);
	while(--n>=0)
	{
		scanf("%d",&b);
		if(b==0)continue;
		printf(b>0?"+":"-");
		if(n!=0 && b!=1 && b!=-1)printf("%d",b>0?b:-b);
		printX(n);
	}
	if(b!=0)printf("%d",b>0?b:-b);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

如果有问题交流咨询，可以加入QQ群：673852347

45 和最大子序列

作者: Turbo 时间限制: 1S 章节: 枚举

问题描述 :
　　对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。
输入说明 :
　　输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。
　　其中
　　1 <= N <= 100000
　　-10000 <= A[i] <=　　10000
输出说明 :
　　输出仅包含一个整数，表示你算出的答案。

#include<stdio.h>//Author:summershell 问了一个同学 他和我讲 输入不止一组的时候我才知道这个题的坑
int main()//和最大子序列，思路是动态规划，我们尽量使用连续的序列，因为
{//连续的才能遇见更好的（更大的数），那么假设dp[i-1]是i-1及其之前连续的和
	long long int n,temp,max;//有可能a[i-1]是负的，但是没关系，只要加上a[i-1]后dp[i-1]还是正的
	while(scanf("%lld",&n)!=EOF)
    {//那么它这个状态就是一个略好的，我们到最后比较哪个dp[i]最大
        scanf("%lld",&max);
        long long int sum=max;//就是我们想要的结果，结果可能很大 要使用long int 刚刚就wa了
        for(int i=1;i<n;++i)
        {
            scanf("%lld",&temp);
            if(sum>=0)sum+=temp;//sum就是之前i-1个的状态，若他是正的或者0，则可以尽量和后面连续
            else sum=temp;//若实在没办法。就只能从新加和
            if(max<sum)max=sum;
        }
        printf("%lld\n",max);
    }
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

如果有问题交流咨询，可以加入QQ群：673852347

46 邮票面值设计

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
　　给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤13）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。

例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
输入说明 :
　　一行，两个数N、K
输出说明 :
　　两行，第一行升序输出设计的邮票面值，第二行输出“MAX=xx”（不含引号），其中xx为所求的能得到的连续邮资最大值。

#include<stdio.h>//Author:summershell
#define min(a,b) (a<b?a:b)//dfs+动态规划
int n,k,max=-1,ans[20],v[20];
void calculate()//计算当前组合得到的最大值
{
	int dp[300]={0},i=0;//dp[i]是表示i面值 最少需要多少张
	while(dp[i]<=n)//当张数还不满
	{
		++i;
		dp[i]=99999;
		for(int j=0;j<k && i>=v[j];++j)
			dp[i]=min(dp[i],dp[i-v[j]]+1);
	}//当无法连续时候才跳出循环 所以是i-1是答案
	if(i-1>max)
	{
		max=i-1;
		for(int i=0;i<k;++i) ans[i]=v[i];
	}
}
void DFS(int deep)//搜索可能有的组合
{
	if(deep==k-1)//这题很严格 一开始出口是k 就TLE了
	{
		calculate();
		return;
	}
	for(int i=v[deep]+1;i<v[deep]*n+2;++i)//假设 前面是3 则 下一个设计最大是3*n+1 不然断了
	{
		v[deep+1]=i;
		DFS(deep+1);
	}
}
int main()
{
	scanf("%d %d",&n,&k);
	v[0]=1;//第一张肯定是1
	DFS(0);
	for(int i=0;i<k;++i)printf(i==0?"%d":" %d",ans[i]);
	printf("\nMAX=%d\n",max);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

如果有问题交流咨询，可以加入QQ群：673852347

47 数字密码发生器

作者: Turbo 时间限制: 1S 章节: 基本练习（字符串）

问题描述 :
在对银行账户等重要权限设置密码的时候，我们常常遇到这样的烦恼：如果为了好记用生日吧，容易被破解，不安全；如果设置不好记的密码，又担心自己也会忘记；如果写在纸上，担心纸张被别人发现或弄丢了…
这个程序的任务就是把一串拼音字母转换为6位数字（密码）。我们可以使用任何好记的拼音串(比如名字，王喜明，就写：wangximing)作为输入，程序输出6位数字。
变换的过程如下：
第一步. 如果字符串长度超过6，则把字符串6个一组折叠起来并左对齐，比如wangximing则变为：
wangxi
ming
注意：左对齐后，ming的右边无任何字符，可认为都是字符’\0’。
第二步. 把所有垂直在同一个位置的字符的ascii码值相加，得出6个数字，如上面的例子，则得出：
228 202 220 206 120 105
第三步. 再把每个数字“缩位”处理：就是把每个位上的数字相加，得出的数字如果不是一位数，就再缩位，直到变成一位数字为止。例如: 228 => 2+2+8=12 => 1+2=3
上面的数字缩位后变为：344836, 这就是程序最终的输出结果！

输入说明 :
程序从标准输入接收数据，第一行是一个整数n（<100），表示下边有多少输入行，接下来是n行字符串（每个字符串长度<100），就是等待变换的字符串。
输出说明 :
在标准输出上输出结果，输出n行，每行都包含一个变换后的6位密码，无多余空格或空行。

#include<stdio.h>//Author:summershell
#include<string.h>
int convert(int x)
{
	int sum=0;
	while(x)
	{
		sum+=x%10;
		x/=10;
	}
	return sum<10?sum:convert(sum);
}
int main()//好久没见过这种水题了，开心
{
	char str[2020];
	int n,code[6];
	scanf("%d ",&n);
	while(n--)
	{
		gets(str);
		int len=strlen(str),y=0;
		memset(code,0,sizeof(code));
		for(int i=0;i<len;i++)
		{
			code[y]+=str[i];
			y=(y+1)%6;
		}
		for(int i=0;i<6;++i)printf("%d",convert(code[i]));
		printf("\n");
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

48 小计算器

作者: Turbo 时间限制: 1S 章节: 模拟

问题描述 :
模拟程序型计算器，依次输入指令，可能包含的指令有

  1. 数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
  2. 运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
  3. 进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
  4. 输出指令：‘EQUAL’，以当前进制输出结果
  5. 重置指令：‘CLEAR’，清除当前数字

指令按照以下规则给出：
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方

运算过程中中间变量均为非负整数，且小于2^63。
以大写的’A’'Z’表示1035
输入说明 :
第1行：1个n，表示指令数量
第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出说明 :
依次给出每一次’EQUAL’得到的结果

#include<stdio.h>//Author:summershell
#include<string.h>//感觉使用运算时候都转成10进制比较好办
__int64 convert10(char s[],__int64 b)//b进制下的s换成10进制的
{
	__int64 sum=0,temp=1,num;
	int len=strlen(s)-1;
	while(len>=0)
	{
		if(s[len]>='A')num=10+s[len]-'A';
		else num=s[len]-'0';
		sum+=num*temp;
		temp=temp*b;
		len--;
	}
	return sum;
}
void convert(__int64 x, __int64 b)//把10进制的x转换成b进制，除留余数法
{//输出
	if(b==10){
		printf("%I64d\n",x);
		return;
	}
	int sta[5000],pos=-1;
	do
	{
		sta[++pos]=x%b;
		x/=b;
	}while(x);//有效的解决了0的输出问题
	while(pos!=-1)
	{
		if(sta[pos]<10)printf("%d",sta[pos]);
		else printf("%c",sta[pos]-10+'A');
		pos--;
	}
	printf("\n");
}
__int64 cal(__int64 a,__int64 b,__int64 flag)
{
	if(flag==1)return a+b;
	else if(flag==2) return a-b;
	else if(flag==3) return a*b;
	else if(flag==4) return a/b;
	else if(flag==5) return a%b;
}
int main()
{
	char str[2020],s1[2020];
	__int64 n,temp,sum,k=10,flag=1;//flag表示+-...
	scanf("%I64d",&n);
	getchar();
	while(n--)
	{
		scanf("%s",str);
		getchar();
		if(strcmp(str,"CLEAR")==0)
		{
			sum=0;//每次clear之后进制不变
			flag=1;//初始的时候是+ 它不香吗
		}
		if(str[0]=='N' && str[1]=='U' && str[2]=='M')
		{
			scanf("%s",s1);
			getchar();
			temp=convert10(s1,k);
			sum=cal(sum,temp,flag);
		}
		if(strcmp(str,"ADD")==0)flag=1;
		if(strcmp(str,"SUB")==0)flag=2;
		if(strcmp(str,"MUL")==0)flag=3;
		if(strcmp(str,"DIV")==0)flag=4;
		if(strcmp(str,"MOD")==0)flag=5;
		if(str[0]=='C'&&str[1]=='H'&&str[2]=='A')
		{
			scanf("%I64d",&k);
			getchar();
		}
		if(strcmp(str,"EQUAL")==0)convert(sum,k);
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

49 合根植物

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体(也就是说，成为一株合根植物了）。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入说明 :
　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。
　　比如：5 * 4 的小格子，编号：

	1   2   3   4
　　5   6   7   8
　　9   10  11  12
　　13  14  15  16
　　17  18  19  20

  • 1
  • 2
  • 3
  • 4
  • 5

比如输入：
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
其合根情况如下：

因此总共有5株合根植物。

输出说明 :
输出一个整数

#include<stdio.h>//Author:summershell
int tree[1000001],m,n,k,a,b,x,y;//这个题 我想起了克鲁斯卡尔算法。根本不需要深搜
int getroot(int a)
{
    while(tree[a]!=a)
        a=tree[a];
    return a;
}
int main()
{

    for(int i=0;i<1000001;++i)tree[i]=i;
    scanf("%d %d %d",&m,&n,&k);
    for(int i=0;i<k;++i)
    {
        scanf("%d %d",&a,&b);
        x=getroot(a);
        y=getroot(b);
        if(x!=y)tree[x]=y;
    }
    int ans=0;
    for(int i=1;i<=m*n;++i)
    {
        if(tree[i]==i)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

如果有问题交流咨询，可以加入QQ群：673852347

50 分考场

作者: Turbo 时间限制: 1S 章节: 深度优先搜索

问题描述 :
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求至少需要分几个考场才能满足条件。
输入说明 :
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出说明 :
输出一行，包含一个整数，表示最少分几个考场。

#include<iostream>//Author:summershell
#include<algorithm>//深搜
int n,m,e[110][110],ans=10000;
int room[110][110];//room[i][0]表示第i个room里有多少人
void dfs(int deep,int num)//num是有几个屋子，deep表示第几人
{
    if(num>=ans)return;//剪枝
    if(deep==n+1)//第n+1个人，即是n个都安排完了
    {
        ans=std::min(ans,num);
        return;
    }
    for(int i=1,j;i<=num;++i)
    {
        for(j=1;j<=room[i][0];++j)
        {
            if(e[deep][ room[i][j] ]==1)break;
        }
        if(j>room[i][0])//若都不认识，进房子
        {
            room[i][0]++;
            room[i][j]=deep;
            dfs(deep+1,num);
            room[i][0]--;
        }
    }
    //再开一间
    num++;
    room[num][0]++;
    room[num][ room[num][0] ]=deep;
    dfs(deep+1,num);
    room[num][0]--;//回溯
}
int main()
{
    std::cin>>n>>m;;
    for(int i=0;i<m;++i)
    {
        int a,b;
        std::cin>>a>>b;;
        e[a][b]=e[b][a]=1;
    }
    dfs(0,0);
    std::cout<<ans<<std::endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

如果有问题交流咨询，可以加入QQ群：673852347

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/180212
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号