第二届全国大学生算法设计与编程挑战赛（冬季赛）题解

@toc

今天下午上课差点把这个比赛忘了，对了6个，应该算一般吧，应该是个铜奖(前百分之30%）排名：824/3043，很垃圾，不过我也就这样了

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

塔

• 题目描述

你在最后那场博弈中败下阵来，却意外穿越到了海拉尔大陆！是你吗林克？ 初来到海拉尔大陆的你，有些许的局促，但当你看到塔，或许一切的一切都迎刃而解。 一个层高为n的字母塔的定义为： 共n行，由字母组成的等腰三角形。 塔顶为第一层，且只有一个大写字母A；下面每一层都比上面一层多两个字母。 每一层都是左右对称。 对于第i层，前i个字母由大写字母表中A~第i个字母顺序组成。 为了稳住局面，样例给出了层高为5的字母塔，请你输出层高2626的字母塔。

• 输入

TIPS：此题是一道程序填空题，下面会给出此题正确代码的挖空版本，选手可以根据提示对代码进行完善。

• 输出

输出高度为 2626 的塔。

在这里插入图片描述

• 题解

观察题目样例给出的高为5层的塔，可以得出以下几个规律 对于一个高为n层的塔而言，首先设最上面一层（顶层）为第一层。 1. 对于第i层而言，其字符的排列规律为：大写字母表中从第1个字符(A)-第i个字符，后又倒序从第i-1个字符~第1个字符(A)。 2. 第1~n-1层每层前都有空格，具体而言，对于第i行，字符前面的空格个数为n-i个。 找出以上规律后，我们就可以根据这些规律构造出答案：层高26的塔。 TIPS: 大写字母'A'为大写字母表第一个字符 对于大写字母表中第i个字符，可以使用'A'+i-1得到。 例如：第5个字符为'E'，亦即为：'A'+5-1

• 代码#include <stdio.h> int main() { char c1; int n = 26; //设定塔的层数为26 int i, j; for (i = 1; i <= n; i++) { //对塔每一层按照规律进行构造。 //首先进行输出空格的操作：对于第i行，字符前面的空格个数为n-i个。 for (j = 1; j <= n-i; j++) printf(" "); for (j = 1; j <= i; j++) { //按照规律1，输出第1~第i个大写字母。 c1 = j + 'A' - 1; //第j个大写字母为'A'+j-1 printf("%c", c1); //输出第j个大写字母 } for (j = i-1; j >= 1; j--) {//按照规律1，输出第i-1~第1个大写字母，注意是倒序 c1 = 'A'+j-1; printf("%c", c1); } printf("\n");//第i行输出结束，进行换行。 } return 0; }
• c语言
• c++

#include<iostream>
using namespace std;

int main()
{
	char c1;
	int n=26; //设定塔的层数为26
	for(int i=1;i<=n;i++){ //对塔每一层按照规律进行构造。
		//首先进行输出空格的操作：对于第i行，字符前面的空格个数为n-i个。
		for(int j = 1;j<=n-i;j++)
			cout<<" ";

		for(int j=1;j<=i;j++){ //按照规律1，输出第1~第i个大写字母。
			c1=j+'A'-1; //第j个大写字母为'A'+j-1
			cout<<c1; //输出第j个大写字母
		}
		for(int j= i-1;j>=1;j--){ //按照规律1，输出第i-1~第1个大写字母，注意是倒序
			c1= 'A'+j-1;
			cout<<c1;
		}
		cout<<endl;//第i行输出结束，进行换行。
	}
	return 0;
}


```--  java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        char c1;
        int n=26;//设定塔的层数为26
        for(int i=1;i<=n;i++){ //对塔每一层按照规律进行构造。
            //首先进行输出空格的操作：对于第i行，字符前面的空格个数为n-i个。
            for(int j = 1;j<= n-i;j++) {
                System.out.print(" ");
            }
            for(int j=1;j<=i;j++){//按照规律1，输出第1~第i个大写字母。
                c1=(char) (j+'A'-1);//第j个大写字母为'A'+j-1
                System.out.print(c1);//输出第j个大写字母
            }
            for(int j= i-1;j>=1;j--){//按照规律1，输出第i-1~第1个大写字母，注意是倒序
                c1= 'A'+j-1;
                System.out.print(c1);
            }
            System.out.println();//第i行输出结束，进行换行。
        }
    }

}

• Python

n=26;# 设定塔的层数为26
i=1

while i<=n:# 对塔每一层按照规律进行构造。
	# 首先进行输出空格的操作：对于第i行，字符前面的空格个数为n-i个。
    j=1
    while j<=n-i #第i层需要输出的空格个数 :#注意这里最右边的分号:为原python语法，不要修改
        print(" ",end="")
        j=j+1

    h=1
    while h<=i:# 按照规律1，输出第1~第i个大写字母。
        c1=chr(h+ord('A')-1)# 第j个大写字母为'A'+j-1
        print(c1,end="")# 输出第j个大写字母
        h=h+1

    k=i-1 #从第i-1个大写字母倒序输出，此处填k的起始位置
    while k>=1:# 按照规律1，输出第i-1~第1个大写字母，注意是倒序
        c2='A'+j-1
        print(c2,end="")
        k=k-1
    print("")# 第i行输出结束，进行换行。
    i=i+1

日记

• 题目描述

看着林林色色的塔，你的心里有些许的安稳，在询问路人时你得知了，你正身处「卡卡利科村」，似乎帕雅也在那里？ 好久没有偷窥帕雅的日记了 你喜欢偷窥帕雅日记一事已广为人知，帕雅特地在日记本上加了密。 加密的方式很简单：对于一串字符串，如果其中有l，i，n，k，e这五个字母当中的任意一个，帕雅都会在这后面加上bt再加上原来的字母已加密，如love就会加密成lbtlovebte。 下面给出帕雅日记的第一页内容，请你根据他的日记内容进行解密。 ibti lbtlovebte lbtlibtinbtnkbtkebtezbas jebte dosadnbtna ovakbtkebtemibtijaxaszxdbtddbtddbtddbtddbtddbtd 注意上面内容为一行内容，没有任何换行，若网页显示多行只是文本显示宽度问题。 但这能拦得住你吗？时间紧迫，快解密吧！

• 输入

这是一道提交答案题，没有任何输入，只需要将问题的解使用输出语句输出即可。

• 输出 输出帕雅日记第一页解密后的内容。
• 样例输出
  

  在这里插入图片描述
  思路分析

先获取字符串长度，依次判断每个字符的后面两个字符是不是b和t，如果是的话，输出字符串往后移动三个输出，不是的话直接输出

• 代码class Main{ public static void main(String[] args){ String s="ibti lbtlovebte lbtlibtinbtnkbtkebtezbas jebte dosadnbtna ovakbtkebtemibtijaxaszxdbtddbtddbtddbtddbtddbtd"; int j=s.length()-1; for(int k=0;k<=j;k++){ System.out.print(s.charAt(k)); if( (s.charAt(k)=='l'&&s.charAt(k+1)=='b'&&s.charAt(k+2)=='t'&&s.charAt(k)=='l')|| (s.charAt(k)=='i'&&s.charAt(k+1)=='b'&&s.charAt(k+2)=='t'&&s.charAt(k)=='i')|| (s.charAt(k)=='n'&&s.charAt(k+1)=='b'&&s.charAt(k+2)=='t'&&s.charAt(k)=='n')|| (s.charAt(k)=='k'&&s.charAt(k+1)=='b'&&s.charAt(k+2)=='t'&&s.charAt(k)=='k')|| (s.charAt(k)=='e'&&s.charAt(k+1)=='b'&&s.charAt(k+2)=='t'&&s.charAt(k)=='e')) { k = k + 3; } } } }神仙爱采药
• java
• 问题描述

您是一个神仙，但您很喜欢采药。 您有一个神奇的背包，背包内有VV个格子。 您所在的空间内有一些药，每个药会占用 11 或 22 个格子。 每天可以进行一次如下操作： 采摘一个药材放入背包中，若此时背包中没有多余的格子来放入新的药材，可以先将背包中的若干药材扔出去，至于扔多少以及扔几个，全都由您决定。当然您也可以选择不去进行采摘操作。 每一天结束前，神奇背包中的每个药材都会产生一个药丸。 作为神仙，您知道每天您可以采摘的药材类型（即占用格子数目），注意，当天的药材如果不采摘，在第二天就会消失（当天药材仅限当天采摘）。 为了获得尽可能多的药丸，请您计算最终能获得的药丸数目最多是多少？

• 输入

给定一个整数 VV 表示背包的格子数量，接下来一行一个由1或2构成的字符串 ss 表示药占用体积的情况。 其中1表示该药占用体积为 11，2表示该药占用体积为 22。 |s|∣s∣表示天数 V≤100000,|s|≤ 100000 ,V≤100000,∣s∣≤100000

• 输出

最多的药丸数目。

• 测试样例
  

  在这里插入图片描述
• 提示

对于第四组样例： 第一天装入了体积为2的药，该天生产药丸数为1。 第二天装入了体积为1的药，该天生产药丸数为2。 第三天取出了体积为2的药，装入了体积为1的药，该天生产药丸数为2。 第四天未操作，生产药丸数为2。 第五天装入体积为1的药，该天生产药丸数为3 故 1+2+2+2+3=10 个

• 代码#include<iostream> #include<string> using namespace std; void work(){ int sum; string t; cin>>sum>>t; long long res=0,one=0,two=0; for(int i=0;i<t.size();i++){ if(t[i]=='2'){ if(sum>=2){ sum-=2; two++; } } else{ if(sum>=1){ sum--; one++; } else{ if(two>0){ two--; one++; sum++; } } } res=res+one+two; } cout<<res<<endl; } int main() { work(); }v = int(input()) s = input() li = list(map(int,s)) res = 0 p = {1:0,2:0} l = 0 for x in li: if x<=v: p[x] += 1 l += 1 v -= x elif x==1 and p[2]>0: p[2] -= 1 p[x] += 1 v += 1 res += l print(res)奇怪的小鸭子也增加了
• c++
• python
• 问题描述

这题是个签到题(这不是签到题。。。)。 有一个 A\times BA×B 的大澡盆，还有若干个 a\times ba×b 的长方形小鸭子，澡盆里最少放几只鸭子后，便无法再向其中放入更多的鸭子？ 鸭子很倔强，不能旋转成 b\times ab×a ，也不能重叠放置。

• 输入

四个整数，分别表示 A,B,a,bA,B,a,b 1<=a<=A<=300001<=a<=A<=30000 1<=b<=B<=300001<=b<=B<=30000

• 输出

最==少==能放几只鸭子。(注意，是最少)

在这里插入图片描述

• 提示
  

  在这里插入图片描述
  这个题如果是最多几只小鸭子就成签到题了#include<iostream> using namespace std; void work() { double whu_cha=1e-7; double A,B,a,b; cin>>A>>B>>a>>b; double bb=b-whu_cha; double aa=a-whu_cha; int t1=1,t2=1; double yy=bb+b; double xx=aa+a; while((B-yy)>=b){ yy+=bb+b; t1++; } while((A-xx)>=a){ xx+=aa+a; t2++; } cout<<t1*t2<<endl; } int main() { work(); }关于哥俩好的数字这件事
• 代码
• c++
• 问题描述

这题是个签到题。(这不是签到题。。。)。 数字 x,yx,y 是个「哥俩好」数字，当且仅当数字 xx 的数位和与数字 yy 的数位和相同。 你需要找 nn 个不同的正整数，使得这 nn 个数字两两之间均为「哥俩好」数字且总和最小。

• 输入

一个整数 n ， 1≤n≤5000

• 输出

最小的「哥俩好」数字总和。

• 样例输出
  

  在这里插入图片描述
  -解题思路

解题思路： 第一眼可能觉得此题有点费解，但是数据范围只有5000。

同时要求找最小的和，所以我们不妨使用for循环逐个枚举，令i从最小值1枚举至无穷大。对于每一个数字i，计算其数位和，设为f(i)。则可以知道每个数字的数位和都不会太大，可以先开一个数组cntx记录：到目前为止数位和为x的数字个数。同时设sumx记录：到目前为止数位和为x的数字之和。因为是从小到大顺序枚举的，所以一定是最小和

经过枚举可以发现，在n最大为5000时，答案的解也在600000范围内，即for循环中i只需要从1枚举到600000即可。这完全可以在1s内得出答案的解。并且数位和也很小，不会超过50。所以上述数组完全开得下。至此，本题通过简单枚举和数组即可解决：在枚举的过程中更新cntx数组和sumx数组在某个cntx的值刚好到n时，用当前的sumx去更新答案。循环结束输出答案即可。需要注意的是：本题sumx和答案会超过c++的int数据范围，故需要开long long。

• 代码
• c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long maxx =1000000;
vector<long long>cun[1500];
void accept(long long a)
{
    long long zhon=a;
    long long s=0;
    while(a)
    {
        s+=a%10;
        a/=10;
    }
    cun[s].push_back(zhon);
}
void work(){
    long long n;
    cin>>n;
    for(long long i=1;i<=maxx;i++)accept(i);
    long long res=1000000000000000;
    for(long long i=0;i<1500;i++)
    {
        if(cun[i].size()>=n)
        {
            long long s=0;
            long long count1=n;
            for(long long j=0;j<cun[i].size();j++)
            {
                s+=cun[i][j];
                count1--;
                if(count1==0)break;
            }
            res=min(res,s);
        }
    }
    cout<<res<<endl;
}
int main() {
    work();
}

出题人说这道题是一个签到题

• 问题描述

比赛前一天，出题人接到了一个电话… 我们都知道2020-2021年度第二届全国大学生算法设计与编程挑战赛（冬季赛）是由中国未来研究会大数据与数学模型专业委员会举办的面向全国高校大学生的学科竞赛，旨在激发学生学习计算机领域专业知识与技能的兴趣，鼓励学生主动灵活地运用计算机知识和技能解决实际问题，有效提升算法设计、逻辑推理、数学建模、编程实现和计算机系统能力，培养团队合作意识、挑战精神和创新能力。 主办单位：全国大学生算法设计与编程挑战赛组委会、中国未来研究会大数据与数学模型专业委员会。 现在，出题人想测试一下你的编程能力！ 出题人有一个人工智能的项目要做，大概是问答相关。但因为明天就要检验了，今天只来得及「新建文件夹」啦。 快帮帮他！他要做一个自动回复的脚本，功能如下： 如果输入的值是1，则回复ADPC。 否则的话，输出12345。 你需要帮助出题人完成这个自动回复的脚本。

• 输入

输入一个整数 NN，NN只会是 {1,2,3,4,5}1,2,3,4,5中的一个。

• 输出

ADPC或12345。

在这里插入图片描述

• 代码#include<stdio.h> int main() { int a=0; scanf("%d",&a); if(a==1) printf("ADPC"); else printf("12345"); }
• c

但更爱字符串

• 题目描述您是一个神仙，您尤其喜欢字符串。

定义一个好词是第一个字母大写，其他字母均小写，且长度大于 11 的单词，例如Akworldfinal、Orzorz、Orz、Nb。好串是由好词构成的，两个好词之间有且只有一个空格，且一个好串至少有两个好词。如：International Collegiate Programming Contest。现在您有一篇文章，想让您将其中的好串进行适当的缩写。如：International Collegiate Programming Contest改写为ICPC (International Collegiate Programming Contest)。注意：好串一定是尽可能长的。如International Collegiate Programming Contest能且仅能被唯一地缩写成ICPC (International Collegiate Programming Contest)。

Input

输入一篇文章，文章是由字母、标点、空格回车构成的。（每行不超过 128128 个字符，总共不会超过 10001000 行）

Output

进行改写过后的文章。

• 样例输出
  

  在这里插入图片描述
• 代码
• c++

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector <string> word;//存放单词和符号

bool bigletter(char c){//判断是不是大写字母
	if(c>='A'&&c<='Z') return true;
	return false;
}
bool smallletter(char c){//判断是不是小写字母
	if (c>='a'&&c<='z') return true;
	return false;
}

bool bigletterword(string s){//判断是不是word
	if (!bigletter(s[0])) return false;
	if (s.size()<=1) return false;
	for (int i=1;i<s.size();i++){
		if (!smallletter(s[i])) return false;
	}
	return true;
}

void work(){//处理每一个单词或符号
	int n=word.size();
	for (int i=0;i<n;i++){
		int inow=i;
		if (!bigletterword(word[i]))//如果不需要缩写则直接输出
			cout<<word[i];
		if (bigletterword(word[i])) {
			if (i!=n-1){//最后一位要么跟着前面的缩写，要么就是只有一个符合的所以不用缩写
				if (word[i+1]==" "&&bigletterword(word[i+2])){
					int j;
					for (j=i;j<n;j++){
						if ((j-i)%2==0){
							if (!bigletterword(word[j])){
								j--; 
								break;
							}
								
							else cout<<word[j][0];
						}
						else if (word[j]!=" ") break;
						
					}//j停在了最后符合要求的word的最后一位的后面一位
					cout<<" (";
					for (int k=i;k<j-1;k+=2)
						cout<<word[k]<<' ';
					cout<<word[j-1]<<')';
					inow=j-1;//i直接跳过缩写的部分
				}
				else cout<<word[i];
			}
			else cout<<word[i];
		}
		i=inow;
	}
} 

int main(){
	string s;
	while(getline(cin,s)){
		if (s.size()==0) break;//如果输入为空就停止
		string w="";//存放单词
		for (int i=0;i<s.size();i++){//循环s
			if (bigletter(s[i])||smallletter(s[i])) w+=s[i];//如果是字母则直接压到s里
			if (!bigletter(s[i])&&!smallletter(s[i])){//否则把单词压到word了，并把符号也压进去
				word.push_back(w);
				w="";
				w+=s[i];
				word.push_back(w);
				w="";
			}
		}
		word.push_back(w);//把最后一个单词压进去
		work();
		word.clear();//清空word
		cout<<endl;
	}
	return 0;//完美结束
}