首先声明:我是被选拔的人,不是选拔的人,本人目前没参加过任何CCF的考试或者比赛,没系统地学过数据结构和算法的相关知识,我也只是稍微稍微地了解那么一点点,水平较差,这些题对于大佬来说非常简单,本人就在这里做一点做题之后的总结而已

A – Dress’em in Vests!

#include<stdio.h>
#define MAX 100000
int a[MAX];
int b[MAX];
int c[MAX];
int d[MAX];
int ans=0;

int main(){
    int n,m,x,y;
    scanf("%d %d %d %d",&n,&m,&x,&y);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&b[i]);
    }
    int b_t=1;
    for(int i=0,j=0;j<m&&i<n;){
        if(a[i]-x<=b[j]&&b[j]<=a[i]+y){
            ans++;
            j++;
            i++;
            c[b_t]=i;
            d[b_t]=j;
            b_t++;
        }else if(b[j]<a[i]){
            j++;
        }else{
            i++;
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++){
        printf("%d %d\n",c[i],d[i]);
    }
    return 0;
}

这道题就是贪心,ai数组和bi数组排序后挨个比较,如果可以穿进去,存进c和d这两个数组里面,假如说是士兵个头小了,那就换一个高一点的,如果是衣服小了,就换个大点的衣服,挨个排就行了,就像配比,这个不行就顺序下来,跟高考报志愿一个理儿

B – Vanya and Books

#include<stdio.h>
long long int number[100]={0, 9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000, 8100000000, 90000000000};
long long int count(long long int a, long long int b)
{
    if(b==0)
        return 1;
    long long int sum=1;
    for(int i=0; i<b; i++)
        sum*= a;
    return sum;
}
int main()
{
    long long int n;
    scanf("%lld", &n);
    long long int sum =0;
    int cnt =0;
    long long int num1=n;
    while(n)
    {
        if(n <= 9) break;
        long long int num2=n;
        if(num2/10 != 0){
            sum +=number[++cnt];
            n/=10;
            continue;
        }
    }
    long long int dig= cnt+1;
    sum= sum+(num1-count(10, cnt)+1)*dig;
    printf("%lld\n", sum);
    return 0;
}

本质上就是一个数学题,打个表计数就好了,
分位数来讨论书字符的总数,算出输入的位数,以及到上一位的总数字和,就好比被除数=除数*商+余数

C – Petya and Java

#include<stdio.h>
#include<string.h>
int main()
{
    int len;
    char a[101];
    scanf("%s",a);
    len=strlen(a);
    if(len<3||(len==3&&strcmp(a,"127")<=0)){
        printf("byte\n");
    }
    else if(len<5||(len==5&&strcmp(a,"32767")<=0))
    {
        printf("short\n");
    }
    else if(len<10||(len==10&&strcmp(a,"2147483647")<=0))
    {
        printf("int\n");
    }
    else if(len<19||(len==19&&strcmp(a,"9223372036854775807")<=0))
    {
        printf("long\n");
    }
    else
    {
        printf("BigInteger\n");
    }
    return 0;
}

位数比较:这里建议不要使用数字,因为这里没有啥运算,单纯的大小比较,不如使用字符串省点空间

D – 滑雪

#include <stdio.h>
//#include<iostream>
//#include<cstring>
//using namespace std;

#define MAX 101
int n,m;
int dp[MAX][MAX];
int baocun[MAX][MAX];
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};

int yuejiemei(int x,int y)
{
    if(x < 1 || x > n || y < 1 || y > m)
        return 0;
    return 1;
}
int max(int x,int y){
    if(x>y) return x;
    else return y;
}
int dfs(int i,int j)
{
    if(dp[i][j])
        return dp[i][j];
    else{
//    cout<<i<<" "<<j<<endl; 
    int result = 1;
    for(int k = 0; k < 4; k++)
    {
        int xx = i + dir[k][0];
        int yy = j + dir[k][1];
        if(yuejiemei(xx,yy) && baocun[i][j] > baocun[xx][yy])
            result = max(dfs(xx,yy)+1, result);
    }
    dp[i][j] = result;
    return result;
    }
}

int main()
{
//    while(scanf("%d %d", &n, &m))
//    {
 scanf("%d %d",&n,&m); 
        memset(dp,0,sizeof(dp));
        memset(baocun,0,sizeof(baocun));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d", &baocun[i][j]);
        int ans = 0;
        for(int i = 1;  i <= n; i++)
            for(int j = 1; j <= m; j++)
                ans = max(dfs(i,j), ans);
        printf("%d\n", ans);
//    }
    return 0;
}

首先声明一下,这里面出现了C++的语法的原因:我这道题老是T,我就咨询了一下我朋友,他跟我说是输入的问题,在这里我附一下我原来写的T的代码

#include<stdio.h>

#define MAX 100
int move_dir[4][2] ={{1,0},{-1,0},{0,1},{0,-1}};
int dp[MAX][MAX];
int baocun[MAX][MAX];
int n,m;//n行数,m列数
int yuejiemei(int x,int y){
    if(x<0||x>=n||y<0||y>=m) return 0;
    else return 1;
}
int max(int x,int y){
    if(x>y) return x;
    else return y;
}
int dfs (int i,int j){
    if(dp[i][j])
        return dp[i][j];//如果这个点被搜索过了,就输出即可
    int result = 1;
    for(int i = 0;i<4;i++){
        int next_i = i+move_dir[i][0];
        int next_j = j+move_dir[i][1];
        if(yuejiemei(next_i,next_j)==0){
            continue;
        }
        if(baocun[i][j]>baocun[next_i][next_j]){
            result = max(dfs(next_i,next_j)+1,result);
        }
    }
    dp[i][j]=result;
    return result;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0;i < n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&baocun[i][j]);
        }
    }
    int final = 0;
    for(int i = 0;i < n;i++){
        for(int j=0;j<m;j++){
            final=max(dfs(i,j),final);
        }
    }
    printf("%d\n",final);
}

这道题就是典型的搜索问题,比较类似于C语言实验数组的那道选做题
这道题的dfs函数我说一下作用吧,dfs函数有两个参数,传进去的的是n和m(就是我要从n行m列开始搜索),这里还用了dp这个数组来记住我每个点搜索的结果,我不是很内行,我尝试用数据结构的玩意儿解释一下这个搜索,这个搜索大概类似于一个树,这个树每个节点存了一个高度,这个指向就是高的指向低的,两个节点之间有指向应该是他们俩相邻才有指向,我们构建这样一棵树,然后层数就是我们要求的步数,叶结点就是最矮的(旁边四个都比它高),然后这个递归就是一层一层地嵌套下去,我们就依次遍历每个节点,找到我们的根结点,dp数组存的就是每个节点层数,根结点到叶结点层数差最大的,所以就可以求出来

max(dfs(next_i,next_j)+1,result);

这个语句就是递归遍历求节点的层数,下一个节点是该节点的子节点,层数得加个一

E – John

先来科普一下啥叫尼姆博弈
source:https://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html

有三堆各若干个物品,两个人轮流从某一堆取任意多的
物品,规定每次至少取一个,多者不限,最后取光者得胜。 

这种情况下是颇为复杂的。我们用(ak,bk,ck)(ak ≤ bk ,k=0,1,2,…,n)表示三堆物品的数量并称其为局势,如果甲面对(0,0,0),那么甲已经输了,这种局势我们称为奇异局势

它与二进制有密切关系,我们用(a,b,c)表示某种局势,首
先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情形。

计算机算法里面有一种叫做按位模2加,也叫做异或的运算,我们用符号(+)表示
这种运算。这种运算和一般加法不同的一点是1+1=0。先看(1,2,3)的按位模2加的结果
1 =二进制01
2 =二进制10
3 =二进制11 (+)
0 =二进制00 (注意不进位)
对于奇异局势(0,n,n)也一样,结果也是0。
任何奇异局势(a,b,c)都有a(+)b(+)c =0。
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b< c,我们只要将 c 变为 a(+)b,即可,因为有如下的运算结果: a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0。要将c 变为a(+)b,只要从 c中减去 c-(a(+)b)即可
例1(14,21,39),14(+)21=27,39-27=12,所以从39中拿走12个物体即可达到奇异局势(14,21,27)
例2(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品,就形成了奇异局势(55,81,102)
例3(29,45,58),29(+)45=48,58-48=10,从58中拿走10个,变为(29,45,48)

例4 我们来实际进行一盘比赛看看:
        甲:(7,8,9)->(1,8,9)奇异局势
        乙:(1,8,9)->(1,8,4)
        甲:(1,8,4)->(1,5,4)奇异局势
        乙:(1,5,4)->(1,4,4)
        甲:(1,4,4)->(0,4,4)奇异局势
        乙:(0,4,4)->(0,4,2)
        甲:(0.4,2)->(0,2,2)奇异局势
        乙:(0,2,2)->(0,2,1)
        甲:(0,2,1)->(0,1,1)奇异局势
        乙:(0,1,1)->(0,1,0)
        甲:(0,1,0)->(0,0,0)奇异局势
        甲胜。

从n堆里面拿东西,每次至少拿一个,先拿完者输,是一个典型的尼姆博弈。
除了全为一的情况判断n的奇偶;其他情况按位异或看看能否必胜。

#include<stdio.h>
#define MAX 1000
int main()
{
    int t,n,c,a[MAX],k,i;
    scanf("%d",&t);
    while(t--)
    {
        k=0;c=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]); c^=a[i];
            if(a[i]>1) k=1;
        }
       if(c&&k||!k&&n%2==0)
        printf("John\n");
        else printf("Brother\n");
    }
}
c^=a[i]

F – 最小拦截系统

#include<stdio.h>
#include<string.h>
#define MAX 1001
int height[MAX];
int dp[MAX];
int pick[MAX];
int max(int x,int y){
    if(x>y) return x;
    else return y;
}
int main(void){
    int n,i;
    int missnum,sysnum;
    while(scanf("%d",&n)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(pick,0,sizeof(pick));
        for(i=1;i<=n;i++)
            scanf("%d",&height[i]);
        int he;
        missnum=n;
        sysnum=0;
        while(missnum){
            sysnum++;
            he=9999999;
            for(i=1;i<=n;i++){
                if(!pick[i]){
                    if(he>height[i]){
                        he=height[i];
                        pick[i]=1;
                        missnum--;
                    }
                }
    
            }
        }
        printf("%d\n",sysnum);
    }
    return 0;
}

贪心算法:先把第一个最长的连续子列存进第一个制导系统里面,然后依次存第二个,第三个…,这么依次地轮下去,下面我在这做个注释吧,因为我这个代码换过算法,所以说改动比较严重2333,出现了很多奇奇怪怪的东西,就是贪心一下,我想让每个系统发挥最大的作用,榨干它的价值,求出最大的离散子列和

#include<stdio.h>
#include<string.h>
#define MAX 1001
int height[MAX];
//int dp[MAX];
int pick[MAX];
//int max(int x,int y){
//    if(x>y) return x;
//    else return y;
//}
int main(void){
    int n,i;
    int missnum,sysnum;//miss代表导弹,sys代表系统
    while(scanf("%d",&n)!=EOF){
        //memset(dp,0,sizeof(dp));
        memset(pick,0,sizeof(pick));
        for(i=1;i<=n;i++)
            scanf("%d",&height[i]);
        int he;//定义了目前为止最大的高度
        missnum=n;//导弹的数量是n个
        sysnum=0;//一开始需要的系统数为0,初始化
        while(missnum){//看看还有没有导弹欠收拾
            sysnum++;//征用新的系统,系统数加加
            he=9999999;//定义一个非常高的高度
            for(i=1;i<=n;i++){
                if(!pick[i]){//如果这个导弹还没被收拾,那就看看
                    if(he>height[i]){//这个系统能收拾,得了,收拾掉它
                        he=height[I];//目前导弹系统最高能收拾怎样的导弹?
                        pick[i]=1;//标记一下,我这个导弹收拾掉了
                        missnum--;//剩下的导弹加加
                    }
                }
    
            }
        }
        printf("%d\n",sysnum);
    }
    return 0;
}
最后修改日期:2020年5月14日