2018蓝桥杯第九届C++语言A组省赛大题题解--第十题

107 阅读 0 评论 71 点赞

我是靠谱客的博主淡淡皮皮虾，最近开发中收集的这篇文章主要介绍2018蓝桥杯第九届C++语言A组省赛大题题解--第十题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

为了准备下次比赛（2019A组C++），这里只写了大题的题解。（一部分原因也是因为要考研，时间不太够）

对于下次比赛很有信心，因为看了下大题基本会做。想起去年看这些题还要思考很久就感慨万分啊，当时以为自己智商不过，哪知道系统的学过算法后能提升这么多思维。所以有的看算法题崩溃的道友们不要担心，慢慢学总是学得会的，多学习算法还是挺有好处的。加油吧！

下面的代码注意：为了简化代码和减少代码错误，我把for循环写成了宏定义。还有代码没有经过严格测试和证明，如果有错误还希望道友或大佬们指出，如果有更灵活，或者更有趣的思路，也希望大家分享交流~

第六题


标题：航班时间
【问题背景】
小h前往美国参加了蓝桥杯国际赛。小h的女朋友发现小h上午十点出发，
上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。
小h对超音速飞行感到十分恐惧。仔细观察后发现飞机的起降时间都是当地时间。
由于北京和美国东部有12小时时差，故飞机总共需要14小时的飞行时间。
不久后小h的女朋友去中东交换。小h并不知道中东与北京的时差。
但是小h得到了女朋友来回航班的起降时间。小h想知道女朋友的航班飞行时间是多少。
【问题描述】
对于一个可能跨时区的航班，给定来回程的起降时间。
假设飞机来回飞行时间相同，求飞机的飞行时间。
【输入格式】
从标准输入读入数据。
一个输入包含多组数据。
输入第一行为一个正整数T，表示输入数据组数。
每组数据包含两行，第一行为去程的 起降 时间，第二行为回程的 起降 时间。
起降时间的格式如下
h1:m1:s1 h2:m2:s2
或
h1:m1:s1 h3:m3:s3 (+1)
或
h1:m1:s1 h4:m4:s4 (+2)
表示该航班在当地时间h1时m1分s1秒起飞，
第一种格式表示在当地时间 当日 h2时m2分s2秒降落
第二种格式表示在当地时间 次日 h3时m3分s3秒降落。
第三种格式表示在当地时间 第三天 h4时m4分s4秒降落。
对于此题目中的所有以 h:m:s 形式给出的时间, 保证 ( 0<=h<=23, 0<=m,s<=59 ).
【输出格式】
输出到标准输出。
对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。
注意，当时间为一位数时，要补齐前导零。如三小时四分五秒应写为03:04:05。
【样例输入】
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)
【样例输出】
04:09:05
12:10:39
14:22:05
【限制与约定】
保证输入时间合法，飞行时间不超过24小时。

思路：题目每组数据的输入是两行，分别是可能跨时区的时间起降时间，所以只需要将两个飞行耗时直接加起来，抵消掉时差，然后除以二即可。

这里我是中间计算按秒数计算，最后在用除法取余得到具体时间。具体格式处理请看代码。

#define LOCAL
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FO freopen("out.txt","w",stdout)
#define FI freopen("in.txt","r",stdin)
#define RI(a) scanf("%d",&a)
#define oarr(aa,ll,rr) _rep(ii,ll,rr)printf("%d ",aa[ii]);printf("n")
#define PP(ddd) printf("%d ",ddd);
using namespace std;
typedef long long LL;
int T,a1,a2,a3,b1,b2,b3;
char buf[100];
int main() {
scanf("%d",&T);
cin.getline(buf,100);
while(T--){
int sum=0;
for(int i=0;i<2;i++){
cin.getline(buf,100);
int n=strlen(buf),t=0;
if(n<=19)
sscanf(buf,"%d:%d:%d %d:%d:%d",&a1,&a2,&a3,&b1,&b2,&b3);
else
sscanf(buf,"%d:%d:%d %d:%d:%d (+%d)",&a1,&a2,&a3,&b1,&b2,&b3,&t);
b1+=t*24;
sum+= (b1-a1)*3600+(b2-a2)*60+b3-a3;
}
sum/=2;
int s=sum%60,m=(sum/60 )%60,h=sum/3600;
printf("%02d:%02d:%02dn",h,m,s);
}
}

第七题


标题：三体攻击
【题目描述】
三体人将对地球发起攻击。为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。
三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 t 轮攻击用 7 个参数 lat, rat, lbt, rbt, lct, rct, ht 描述；
所有满足 i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。
地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。
【输入格式】
从标准输入读入数据。
第一行包括 4 个正整数 A, B, C, m；
第二行包含 A × B × C 个整数，其中第 ((i − 1)×B + (j − 1)) × C + (k − 1)+1 个数为 d(i, j, k)；
第 3 到第 m + 2 行中，第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。
【输出格式】
输出到标准输出。
输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。
【样例输入】
2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2
【样例输出】
2
【样例解释】
在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。
【数据约定】
对于 10% 的数据，B = C = 1；
对于 20% 的数据，C = 1；
对于 40% 的数据，A × B × C, m ≤ 10, 000；
对于 70% 的数据，A, B, C ≤ 200；
对于所有数据，A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。

思路：暴力可以得大部分分（40-70），想得满分这道题花的时间不值，后面还有三道大题呢。所以直接暴力吧。

#define LOCAL
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FO freopen("out.txt","w",stdout)
#define FI freopen("in.txt","r",stdin)
#define RI(a) scanf("%d",&a)
#define oarr(aa,ll,rr) _rep(ii,ll,rr)printf("%d ",aa[ii]);printf("n")
#define PP(ddd) printf("%d ",ddd);
using namespace std;
typedef long long LL;
int A,B,C,m;
int a[202][202][202];
int main() {
scanf("%d%d%d%d",&A,&B,&C,&m);
_rep(i,1,A)_rep(j,1,B)_rep(k,1,C)
scanf("%d",&a[i][j][k]);
_for(x,0,m){
int l1,r1,l2,r2,l3,r3,ht;
scanf("%d%d%d%d%d%d%d",&l1,&r1,&l2,&r2,&l3,&r3,&ht);
_rep(i,l1,r1)_rep(j,l2,r2)_rep(k,l3,r3){
if((a[i][j][k]-=ht)<0){
printf("%dn",x+1);
return 0;
}
}
}
}

第八题全球变暖

你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。  
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。  
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。  
【输入格式】
 
第一行包含一个整数N。  (1 <= N <= 1000)  
 
以下N行N列代表一张海域照片。  
 
 
 
照片保证第1行、第1列、第N行、第N列的像素都是海洋。  
【输出格式】
一个整数表示答案。
【输入样例】
7 
.......
.##....
.##....
....##.
..####.
...###.
.......  
【输出样例】
1  
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
思路：

把'.'当做0，把'#'当做-1（化作整数方便标记连通分量）

1.dfs一次，并在dfs的过程中标连通分量（每个岛给一个编号p，p从1开始）

2.在1的过程中，把会被淹没的陆地（如果周围存在海）给予特殊编号-2

3.最后统计非特殊编号个数cnt, 答案就是p-cnt;

#define LOCAL
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FO freopen("out.txt","w",stdout)
#define FI freopen("in.txt","r",stdin)
#define RI(a) scanf("%d",&a)
#define oarr(aa,ll,rr) _rep(ii,ll,rr)printf("%d ",aa[ii]);printf("n")
#define PP(ddd) printf("%d ",ddd);
using namespace std;
typedef long long LL;
int n,a[1111][1111],p=0;
int hf(int i,int j){
return i>=0&&j>=0&&i<n&&j<n;
}
void dfs(int i,int j){
a[i][j]=p;
//先给岛屿编号
_rep(di,-1,1)_rep(dj,-1,1)
if(abs(di)+abs(dj)==1&&hf(i+di,j+dj)){
if(a[i+di][j+dj]==-1) dfs(i+di,j+dj);
else if(!a[i+di][j+dj]) a[i][j]=-2;
// 用-2标记会被淹没的岛屿
}
}
int main() {
scanf("%d",&n);
_for(i,0,n){
char buf[1111];
scanf("%s",&buf);
_for(j,0,n) if(buf[j]=='#')a[i][j]=-1;
}
_for(i,0,n)_for(j,0,n) if(a[i][j]==-1){++p;dfs(i,j);}
set<int> st;
_for(i,0,n)_for(j,0,n) if(a[i][j]>0)st.insert(a[i][j]);
printf("%dn",p-st.size());
}

第九题倍数问题


标题：倍数问题
【题目描述】
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，
使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。
【输入格式】
从标准输入读入数据。
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
【输出格式】
输出到标准输出。
输出一行一个整数代表所求的和。
【样例入】
4 3
1 2 3 4
【样例输出】
9
【样例解释】
选择2、3、4。
【数据约定】
对于 30% 的数据，n <= 100。
对于 60% 的数据，n <= 1000。
对于另外 20% 的数据，K <= 10。
对于 100% 的数据，1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗
< 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。

思路：(a+b+c)%k==0 等价于 (a%k+b%k+c%k)==0,所以只要找到三个数，这三个数模k余数相加等于0即可

所以保存每个输入数据的%K取余，保存到a[x%k][]里面，a数组开1000*3空间，只保存x%k最大的三个x数即可。

然后就是两个for循环找a，b然后c=k-a-b.时间复杂度(k^2);

#define LOCAL
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
#define FO freopen("out.txt","w",stdout)
#define FI freopen("in.txt","r",stdin)
#define RI(a) scanf("%d",&a)
#define oarr(aa,ll,rr) _rep(ii,ll,rr)printf("%d ",aa[ii]);printf("n")
#define PP(ddd) printf("%d ",ddd);
using namespace std;
typedef long long LL;
int n,k,a[1003][3],ans=0;
void inser(int i,int x){//插入
if(a[i][0]<x)swap(a[i][0],x);
if(a[i][1]<a[i][0])swap(a[i][1],a[i][0]);
if(a[i][2]<a[i][1])swap(a[i][2],a[i][1]);
}
int pop(int i){//取出
int t=a[i][2];
a[i][2]=0;
swap(a[i][2],a[i][1]);
swap(a[i][1],a[i][0]);
return t;
}
int main() {
scanf("%d%d",&n,&k);
_for(i,0,n){
int x;RI(x);
inser(x%k,x);
}
_for(a,0,k){
int t1=pop(a);
if(t1)_for(b,a,k){
int t2=pop(b);
if(t2){
int c=k-a-b,t3=pop(c);
if(t3)ans=max(ans,t1+t2+t3);
inser(c,t3);
}
inser(b,t2);
}
inser(a,t1);
}
cout<<ans<<endl;
}