浙江中医药大学第十二届大学生程序设计竞赛部分题解

本文主要是介绍浙江中医药大学第十二届大学生程序设计竞赛部分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem A. Jhadgre的C语言程序

helle 直接复制

Problem B. Wpremig的AH之战

博弈问题还没有学，待补

Problem C. Wpremig的三角形

没看这题，这题人出的也少，待补

Problem D. Jhadgre的梯子

链接：https://ac.nowcoder.com/acm/contest/333/D
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

陶陶摘了这么多年苹果，Jhadgre他也很想摘苹果。

这天Jhadgre趁着陶陶还没起床，决定先去把苹果摘了，现在Jhadgre知道树上有N个苹果以及每个苹果离地面的高度，当然机智的Jhadgre不会像陶陶一样只带一个30厘米的板凳，聪明的Jhadgre决定带一架梯子！这样就可以摘到所有苹果了。

现在Jhadgre告诉你他把手伸直的时候能够到达的最大高度，请你帮他算一下他需要带一架至少多高的梯子才能摘到所有苹果。假设他碰到苹果苹果就会掉下来。

输入描述:

第一行两个个整数N,L(1<=N，L<=100000)表示有N个苹果和Jhadgre把手伸直的时候能够到达的最大高度L。
接下去N个正整数a1,a2,...an,表示每个苹果离地面的高度。(1<=ai<=2147484649)

输出描述:

输出Jhadgre需要带的梯子的高度。若不需要梯子Jhadgre就能摘到所有苹果则输出0.

示例1

输入

复制

5 50
10 20 30 40 100

输出

复制

水题，注意long long 就行

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define N 100000+5
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
typedef long long ll;
const ll mod=1e6;
ll a[N];
bool vis[N];
char c[]={'6','7','8','9','T','J','Q','K','A'};
int main(){ll n,l;cin>>n>>l;ll ans = l;for (int i = 0 ; i < n ; ++i){ll x;cin>>x;if (x >ans)ans = x;}cout<<ans-l<<endl;return 0;
}

Problem E. Jhadgre的合唱队形

不会，好像是树状数组+一些东西，待补

Problem F. Jhadgre的伤心地

链接：https://ac.nowcoder.com/acm/contest/333/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Jhadgre为了他的女神，准备了一场盛大的告白，可惜却被女神毫不留情的拒绝。于是Jhadgre决定离开这个伤心之地。但是钱都被Jhadgre拿去准备告白了，剩下的钱并不够他买车票，只够他坐公交车。

Jhadgre所在城市的所有公交车站总体来说都在一条直线上，在这里有两种公交车，一种是全城公交，这种公交车在城市的任何一站都可以上下车，付了车费后，从当前站开始，最多可以向后坐5站（即从第i站上车，可以选择在第i+1,i+2,i+3,i+4,i+5站下车）。还有一种是区间公交，也就是可以在第X站上车，直到第Y站(X<Y)，中途每一站都可以下车但不可以上车。所有公交车的上车费都是2元。

现在Jhadgre为了最快的逃离这个伤心地，他决定不管上哪种公交车，只要上去了，就一定坐到底再下车，中途不会下车，并且他现在所在的地点为第1站，他认为要到第N站以后的站，他才算彻底逃离这个伤心地。

现在Jhadgre想知道他手里的钱够不够逃离这个伤心地，你可以帮他计算一下他最少需要花多少钱才能离开这个伤心地吗？

输入描述:

只包含一组数据。
第一行一个整数N，意义如题（10<=N<=100）
接下去一行中共N个整数a1,a2,a3...aN，由空格隔开,ai表示第i站的区间公交能到达第ai站，保证(i<ai)

输出描述:

Jhadgre最少需要花的钱

示例1

输入

复制

10
7 11 4 5 6 7 8 9 10 11

输出

复制

说明

以下给出两种乘车方案：(1) Jhadgre在第1站选择上全城公交，到达第6站，付2元钱，接着在第6站选择上全城公交，到达第11站，共付4元钱。(2) Jhadgre在第1站选择上区间公交，到达第7站，付2元钱，接着在第7站选择上全城公交，到达第12站，共付4元钱。

分析：这题一开始以为是DP，但后面的状态不好由前面所推出，所以直接递归就可以，从前面往后推（f【i】——》f【a【i】】或f【i+5】），推出哪一个先到就ok了

 
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define N 100000+5
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
typedef long long ll;
const ll mod=1e6;
ll a[N];
bool vis[N];
ll n;
char c[]={'6','7','8','9','T','J','Q','K','A'};
int f(int x)
{if(x>n) return 0;return min(f(a[x]),f(x+5))+2;}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cout<<f(1)<<endl;return 0;
}

Problem G. Wpremig的称球问题

这题在我看完所有题的都不会的情况下，尝试写了写，多谢百度的公式，

需要写一个大数，但我又犯了不认真看题的毛病了，输出Yes我输出YES了哎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.StringTokenizer;public class Main {static Scanner in = new Scanner(System.in);public static void main(String args[])throws IOException  {while(in.hasNext()){int n=in.nextInt();int m=in.nextInt();if(n<=2){System.out.println("NO");continue;}BigDecimal x=new BigDecimal(n);BigDecimal a=new BigDecimal(3);BigDecimal b=new BigDecimal(2);BigDecimal bd = new BigDecimal(3);bd = bd.pow(m); bd=bd.subtract(a);bd=bd.divide(b);if(bd.compareTo(x)>=0){System.out.println("YES");}elseSystem.out.println("NO");}}}

一种不需要大数的写法：我们最后比较次数，我们发现3^15=14 348 907，超过了数据范围了，所以我们只要枚举次数即可

#include<bits/stdc++.h>
using namespace std;
int n,m,ans1,ans2;
int main()
{while(scanf("%d%d",&n,&m)!=-1){if(n==2) {cout<<"No"<<endl;continue;}   long long k=3;int j=1;for(j=2;j<=15;j++){k=k*3;if((k-3)/2>=n) break;}if(j<=m) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;}

Problem H. Jhadgre的回家之路

链接：https://ac.nowcoder.com/acm/contest/333/H
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Jhadgre作为一个热(xiang)爱(dang)学(xian)习(yu)的好同学，每天都在掰着手指头等周末。

今天终于到了周五，等到下午六点他就又可以在寝室做两天咸鱼了。但是Jhadgre上午上完课把钥匙丢在了教室，被Wpremig捡到了，所以他必须先去Wpremig手里取得钥匙才能回寝室。

于是机智的Wpremig为了方便Jhadgre拿钥匙，他去配了好多把Jhadgre的钥匙，分别放在不同的地方 (厉害了小老弟)。

现在Jhadgre想要尽快的回到寝室中，他需要取得任意一把钥匙才能够回寝室，请你帮他计算出回寝室的最短路程。

学校可以背看做是一个n * n的网格，其中一些路有障碍，钥匙和家所在的地方也可以看做是道路，可以通过。Jhadgre可以在任意一条道路中选择上下左右四个方向移动，一次移动算作一步。

输入描述:

多组数据，T<=50,对于每组数据有:
第一行有两个整数n,m。
接下去n行每行m个字符，代表学校地图。
其中, '.'表示道路，'#'表示障碍物，'L'表示Jhadgre所在的位置,'W'表示钥匙的位置，'Q'表示寝室的位置。题目保证最少有一条路可以拿到钥匙并且回到寝室。

输出描述:

Jhadgre回寝室需要走的最少步数。

示例1

输入

复制

8 10
W....#.#W#
..#..#...#
...Q##.#.#
##........
..##.#..##
..........
##..#...##
###..L....

输出

复制

分析：

L->W->Q,一开始想遍历bfs全部Q->L和Q->W，但是超时，然后优化了一下，一L和Q为起点两次bfs全部的图，得到每一次到达w的距离，枚举全部比较即可

#include<bits/stdc++.h>
using namespace std;
int n,m,ans1,ans2;
char mapp[2005][2005];
int vis[2005][2005]={0};
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
int dis1[2005][2005];
int dis2[2005][2005];
struct node
{int x,y,step;
}a,b;
int bfs1(int x1,int y1)
{memset(vis,0,sizeof(vis));queue<node>q;a.x=x1;a.y=y1;vis[a.x][a.y]=1;a.step=0;q.push(a);int i=0;while(!q.empty()){a=q.front();q.pop();for(int i=0;i<4;i++){b.x=a.x+dx[i];b.y=a.y+dy[i];if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&mapp[b.x][b.y]!='#'&&!vis[b.x][b.y]){vis[b.x][b.y]=1;dis1[b.x][b.y]=a.step+1;b.step=a.step+1;q.push(b);}}}return 0;}
int bfs2(int x1,int y1)
{memset(vis,0,sizeof(vis));queue<node>q;a.x=x1;a.y=y1;vis[a.x][a.y]=1;a.step=0;q.push(a);while(!q.empty()){a=q.front();q.pop();for(int i=0;i<4;i++){b.x=a.x+dx[i];b.y=a.y+dy[i];if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&mapp[b.x][b.y]!='#'&&!vis[b.x][b.y]){vis[b.x][b.y]=1;b.step=a.step+1;dis2[b.x][b.y]=b.step;q.push(b);}}}return 0;}vector<node>v;
int main()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF){int x,y;int sx1,sy1,sx2,sy2;for(i=0;i<n;i++){scanf("%s",&mapp[i]);for(int j=0;j<m;j++){if(mapp[i][j]=='L'){sx1=i;sy1=j;}else if(mapp[i][j]=='Q'){sx2=i;sy2=j;}else if(mapp[i][j]=='W'){node t;t.x=i;t.y=j;v.push_back(t);}}}int minn3=1e9;;memset(dis1,0,sizeof(dis1));memset(dis2,0,sizeof(dis2));bfs1(sx1,sy1);bfs2(sx2,sy2);for(int i=0;i<v.size();i++){minn3=min(dis1[v[i].x][v[i].y]+dis2[v[i].x][v[i].y],minn3);}v.clear();cout<<minn3<<endl;}return 0;}

Problem I. Jhadgre的小饼干

链接：https://ac.nowcoder.com/acm/contest/333/I
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

最近Jhadgre拿到了一个系列表情包，他很高兴，于是他给每个关系好的女性好友都送了一盒饼干外带这一套表情包。

结果让他惊呆了，竟然真的有女孩子答应他........再来一盒（不然你以为？）

当然也有人回复一些其他的消息...唯独没有答应做他女朋友的人。

Jhadgre很伤心，但是作为一个有原则的人，既然答应了送别人小饼干，那就必须要给！

所有人的回复都由大写字母,小写字母与','组成，占一行，Jhadgre认为只要其中包含了连续的10个小写字母"zailaiyihe"就意味着这个人想要再来一盒。

现在Jhadgre准备给每一个想要“再来一盒”的人买一盒小饼干，他想知道总共需要买几盒小饼干？

输入描述:

第一行一个整数N，表示有N个人回复(1<=N<=1000)
接下去N行每行都是一个人的回复，由大写字母，小写字母与','组成。
(数据保证每行字符不超过1000个)

输出描述:

一个整数表示Jhadgre需要买几盒小饼干

示例1

输入

复制

3
Bu,xing
wokeyizailaiyihe
no

输出

复制

水题

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define N 100000+5
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
typedef long long ll;
const ll mod=1e6;
ll a[N];
bool vis[N];
char c[]={'6','7','8','9','T','J','Q','K','A'};
int main(){ll n;cin>>n;int m=0;while(n--){string s;cin>>s;if(s.find("zailaiyihe")!=-1){m++;}}cout<<m<<endl;return 0;
}

Problem J. Jhadgre爬楼梯

链接：https://ac.nowcoder.com/acm/contest/333/J
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

继上次Jhadgre在楼梯上跳台阶玩了很久之后，他获得了一个很强(la)力(ji)的能力，那就是上楼梯的时候可以跨任意偶数级台阶....

今天上完课,Jhadgre又开始了他的跳台阶之旅，现在他想知道跳到第N级台阶有多少种方案数。

P.S.Jhadgre从楼梯外也就是第0级开始跳，并且依旧可以选择跳一级

输入描述:

多组数据(<=100组)，每组数据包含一个整数N(2<=N<=10000)

输出描述:

对于每组数据包含一个整数表示跳到第N级台阶的方案数（答案对100000007取模）

示例1

输入

复制

3
4

输出

复制

3
6

分析：递归题，不过我一开始看错题了，以为它可以跳到任意偶数位置，然后就自闭了，后来发现他是跨越偶数阶台阶，

递归就行，每一个位置可以由他的前一个，和前面相差偶数个位置得来。

 
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define N 100000+5
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
typedef long long ll;
const ll mod=100000007;
ll a[N];
bool vis[N];
int dp[N];
int main(){int n;dp[0]=1;for(int i=1;i<=10005;i++) {dp[i]=(dp[i]+dp[i-1])%mod;for(int j=i-2;j>=0;j-=2)dp[i]=(dp[i]+dp[j])%mod;}while(scanf("%d",&n)!=-1){cout<<dp[n]<<endl;}return 0;
}