【题解】中南林业科技大学2019年校赛
CSUFT 2019年校赛题解
A. 链表的合并
现在有两个长度相等且为15的有序链表(都为升序)，现在需要你将两个链表合成一个，并且保证两个链表合并完后依旧是升序(链表值相等并不影响最后的输出结果)
输入
每个测试数据输入共2行
第1行:为第1个升序链表
第2行:为第2个升序链表
题意
将两个数字序列合并成一个序列
并且成上升序列
思路
因为输入文件只包含一组数据，所以我们可以直接将所有数据直接输入进来存放在一个数组里面然后排序，直接输出即可
代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[20000];
int main()
{
while(cin>>a[0])
{
for(int i = 1; i < 30; ++i)
cin>>a[i];
sort(a,a+30);
for(int i = 0; i < 30; ++i)
cout<<a[i]<<(i == 29 ? '\n' : ' ');
}
return 0;
}
B. 兑换零钱
现有N元钱，兑换成小额的零钱，有多少种换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。
(由于结果可能会很大，输出Mod 10^9 + 7的结果)
题意
将一个数N用1，2，5，10，20，50，100，200，,500，1000，2000，5000，10000，分解看有多少种分解的方法
思路
背包问题，状态转移方程
%25mod&preview=true)
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1e9+7;
const int maxn = 100000+10;
int coin[13] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
int dp[maxn];
int main()
{
int n;
scanf("%d",&n);
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i=0;i<13;i++){
for(int j=coin[i];j<=n;j++){
dp[j] = (dp[j]+dp[j-coin[i]])%mod;
}
}
printf("%d\n",dp[n]);
return 0;
}
C. 神奇的进制转换
描述
给出一个m进制下的数a，现在请输出a在n进制下的表示。
输入
一行有3个整数，分别表示m，n，a，其中2=<m<=62，2=<n<=62，a的位数不超过350位且a>=0，样例个数不超过400。（每一位数表示方法从小到大分别为'0''9', 'A''Z', 'a'~'z'）
输出
输出上述问题的答案，每个答案占一行。
思路
大数模拟题
代码
//c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000+100;
char hashch[maxn];
int hashnum[maxn];
void init()
{
char ch;
for(int i=0;i<62;i++){
if(i<10) ch=i+'0';
else if(i>=10&&i<36) ch='A'+i-10;
else ch='a'+i-36;
hashch[i]=ch;
hashnum[ch]=i;
}
}
string change(int m,int n,string str)
{
bool flag;
string ans="";
int tmp,quotient,remainder;
while(true)
{
flag=false;
remainder=0;
string div="";
int len=str.length();
for(int i=0;i<len;i++){
tmp=remainder*m+hashnum[str[i]];
quotient=tmp/n;
remainder=tmp%n;
if(flag){
div+=hashch[quotient];
}
else{
if(quotient!=0){
flag=true;
div+=hashch[quotient];
}
}
}
ans=hashch[remainder]+ans;
str=div;
if(flag==false) break;
}
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
init();
int m,n;
string str;
while(cin>>m>>n>>str)
{
string ans=change(m,n,str);
cout<<ans<<endl;
}
return 0;
}
# Python
find = []
for i in range(10):
find.append(i)
for a in range(26):
find.append(chr(a+ord('A')))
for a in range(26):
find.append(chr(a+ord('a')))
T = int(input())
while T>0:
num1, num2, num3 = input().split(' ')
a = int(num1)
b = int(num2)
ans, index = 0, 0
for e in num3[::-1]:
num = 0
if ord(e)>=ord('0') and ord(e)<=ord('9'):
num = int(e)
elif ord(e)>=ord('A') and ord(e)<=ord('Z'):
num = 10 + (ord(e)-ord('A'))
else:
num = 36 + (ord(e)-ord('a'))
tmp = num * (a**index)
ans = ans + tmp
index = index + 1
res = []
if ans==0:
res.append(0)
while ans != 0:
res.append(ans % b)
ans = ans // b
for e in res[::-1]:
print(find[e], end="")
print()
T = T-1
D. 最大的湖
农场主约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度害怕水的消息而恶化。
然而，他的保险公司只会根据他农场最大的“湖”的大小来偿还他一笔钱。
农场表示为一个矩形网格，有N（1≤N≤100）行和M（1≤M≤100）列。网格中的每个格子要么是干的，
要么是被淹没的，而恰好有K（1≤K≤N×M）个格子是被淹没的。正如人们所期望的，一个“湖”有一个
中心格子，其他格子通过共享一条边（只有四个方向，对角线不算的意思）与之相连。任何与***格子共享一条边或与***格
子相连的格子共享一条边的格子都将成为湖的一部分。
输入
第一行有三个整数N,M,K，分别表示这个矩形网格有N行，M列，K个被淹没的格子。
接下来K行，每一行有两个整数R,C。表示被淹没的格子在第R行，第C列。
输出
输出最大的“湖”所包含的格子数目
题意
输出最大的湖的大小
思路
利用DFS就可以找出最大的湖
代码
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int flag,pic[102][102],bj[102][102],N,M;
void dfs (int r,int c) {
if(r<1||r>N||c<1||c>M)
return;
if(bj[r][c]==1||pic[r][c]!=1)
return ;
flag++;
bj[r][c]=1;
for(int dr=-1; dr<=1; dr++) {
if(dr!=0) {
dfs(r+dr,c);
dfs(r,c+dr);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
int K,x,y,sum;
cin>>N>>M>>K;
sum=0;
memset(pic,0,sizeof(pic));
memset(bj,0,sizeof(bj));
for(int i=1; i<=K; i++) {
cin>>x>>y;
pic[x][y]=1;
}
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) {
flag=0;
if(bj[i][j]==0&&pic[i][j]==1) {
dfs(i,j);
if(flag>sum)
sum=flag;
}
}
cout<<sum<<endl;
return 0;
}
E. 砝码与天枰
现在有很多砝码，质量为w的0次方、1次方……n次方，每个砝码都只有一个。还有一个天平，可以在两端放置砝码和重物。现在要用这些砝码搭配出相等于重物的质量m，也可以把若干个砝码和重物一起放在天平的一侧，来平衡这个天平。
输入：
单组测试数据。
第一行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。
输出：
如果能，输出YES，否则输出NO。
思路
将m转化成w进制，然后从小的位数开始遍历一遍如果为0或1不进行操作，如果为w-1则加上一个数使得当前位数变成0，如果为其他数着就可以直接输出NO，如果没有输出NO 则最后输出YES
代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<sstream>
#include<string.h>
#include<set>
using namespace std;
int main()
{
long long n,m;
int t,x;
long long a[100];
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&m);
x=0;
int flag=0;
memset(a,0,sizeof(a));
while(m>0)
{
a[x++]=m%n;
m/=n;
}
int win=0;
for(int i=0;i<x;i++)
{
if(a[i]==0||a[i]==1)continue;
else if(a[i]==n-1)
{
int k=i+1;
int s=1;
while(s)
{
a[k]+=s;
s=a[k]/n;
a[k]%=n;
k++;
if(x<k)x=k;
}
}
else
{
flag=1;
break;
}
}
if(flag)printf("NO\n");
else printf("YES\n");
}
}
F. 得分
给出T 个由O 和X 组成的字符串，统计所有字符的得分和。每个O 的得分为目前连续出现的O 的个数，X 的得分为0 。例如，OOXXOXXOOO 的得分1+2+0+0+1+0+0+1+2+3=10
现给你一个OX字符串输出总得分。
思路
定义一个X变量存储当前分数，初始化为0，再定义一个sum变量存储总分数，初始化为0，循环一遍字符串，当字符为O时x++，当字符为X时x赋值为0，每次sun+=x;
代码
#include <iostream>
#include <string>
using namespace std;
string s;
int main()
{
int len, pos = 0, ans = 0;
while(cin>>s){
len = s.length();
pos = ans = 0;
for(int i = 0; i < len; ++i){
if(s[i] == 'O')
++pos;
else
pos = 0;
ans += pos;
}
cout<<ans<<'\n';
}
return 0;
}
G. 5和0
给出任意多的5和0，合成一个整数，要求没有前导零且能被90整除
思路
保证最后一位为0，剩余位数数字和加起来为9的倍数。为保证尽量大且没有前导零，将5堆到前面，0堆到后面。
代码
int n;
while(~scanf("%d",&n))
{
int t=0,x;
for(int i=0;i<n;i++) {
scanf("%d",&x);
if(x==5)t++;
}
int flag=0;
if(t==n) {
printf("-1\n");
continue;
}
int s=0;
while(s+9<=t)s+=9;
if(s==0) {
printf("0\n");
continue;
}
for(int i=0;i<s;i++) printf("5");
for(int i=n-t;i>0;i--) printf("0");
printf("\n");
return 0;
}
投递中国科学技术大学等公司7个岗位