长沙理工大学2018年校赛部分题解

长沙理工大学2018年校赛部分题解

那题不懂私聊或私聊。

A：LL 题目描述

 “LL是什么？这都不知道的话，别说自己是程序猿啊！”
  “longlong？”
  “。。。肯定是LoveLive啊！”
  qwb为了检验你是否是真正的程序猿，决定出道题考考你：现在程序会输入一行字符串，如果恰好是lovelive（不区分大小写）就输出yes，否则输出no。

输入描述:

输入有多组（组数不超过100），每组输入一行字符串（字符串长度不超过100）。

输出描述:

输出占一行，如果输入符合要求则输出yes，否则输出no。

思路：简单模拟。

 

A
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int N = 1e5 + 5;
typedef long long LL;
using namespace std;
char ar[N];
int main(){char *s="lovelive";while(gets(ar)){int len =strlen(ar);for(int i=0;i<len;++i){if(ar[i]>='A'&&ar[i]<='Z')ar[i]+=97-65;}if(strcmp(ar,s)==0)printf("yesn");else printf("non");}return 0;
}

 

E：小木乃伊到我家 题目描述

  AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能走到AA家），快递姐姐
找上聪明的ACMer，想请你帮忙找出最快到达AA家的路，你行吗？

输入描述:

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，AA所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，w<=100000），分别表示城市u和城市v之间有一条长为w的路。

输出描述:

输出结果占一行，输出快递姐姐到达AA家最短需要走多远的路，如果没有路能走到AA家，则输出“qwb baka”（不用输出双引号）。

思路：最短路。

 

E
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int maxn = 2e5 + 5;
typedef long long LL;
using namespace std;
typedef pair<int,int>P;struct edge{int to,cost;
};
int n,m;
vector<edge>G[maxn];
int d[maxn];
void dijk(int s){priority_queue<P,vector<P>,greater<P> >q;memset(d,INF,sizeof(d));d[s]=0;q.push(P{0,s});while (!q.empty()){P p&#p();q.pop();int v=p.second;if (d[v]<p.first) continue;for (int i=0;i<G[v].size();i++){edge e=G[v][i];if (]>d[v]&#st){]=d[v]&#st;q.push(P{],e.to});}}}
}
int main(){while(~scanf ("%d%d",&n,&m)){for (int i=0;i<maxn;i++) G[i].clear();for (int i=0;i<m;i++){int u,v,cost;scanf ("%d%d%d",&u,&v,&cost);G[u].push_back(edge{v,cost});G[v].push_back(edge{u,cost});}dijk(1);int ans=d[n];if (ans==INF) printf ("qwb bakan");else printf ("%dn",ans);}return 0;
}

 

B：奇怪的加法 题目描述

zhrt是数学大佬，但有一天一道奇怪的数学题把他难住了：题目要求计算两个十进制数相加后的结果，但在本题中是不需要进位的！
  现在zhrt弯下他的小蛮腰向你请教，你能帮帮他吗？

输入描述:

输入有多组（组数不超过1000），每组占一行，每行有2个正整数A和B。（A,B<=1e9）

输出描述:

每组输出占一行，输出题目中A和B相加的结果。

 

思路：大整数。

 

B
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int maxn = 1e5 + 5;
typedef long long LL;
using namespace std;
char s1[11], s2[11];
int a1[11], b1[11], c1[11];
int main()
{while(~scanf("%s %s", s1, s2)) {memset(a1, 0, sizeof(a1));memset(b1, 0, sizeof(b1));memset(c1, 0, sizeof(c1));for(int i = 0; i < strlen(s1); i++) {a1[i] = s1[strlen(s1) - 1 - i] - '0';}for(int i = 0; i < strlen(s2); i++) {b1[i] = s2[strlen(s2) - 1 - i] - '0';}int max1n = max(strlen(s1), strlen(s2));for(int i = 0; i < max1n; i++) {c1[i] = (a1[i] + b1[i]) % 10;}for(int i = max1n; i > 0; i--) {if(c1[i] == 0)max1n--;else break;}for(int i = max1n; i >= 0; i--) {printf("%d", c1[i]);}printf("n");}return 0;
}

 

 

C：取手机 题目描述

durong有a台iphonex和b台s8，并且放在一个保险箱里，durong现在一台一台从保险箱随机拿出这些手机，现在他想知道第k次拿出s8的概率是多少

输入描述:

第一行一个正整数T，表示数据组数。(1<=T<=10000)
接下来T行输入a，b，k
其中（1<=a,b,k<=1e9) k<=a+b;

输出描述:

第k次拿出s8的概率，保留三位小数

 

思路：数学，概率。

 

C
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int maxn = 1e5 + 5;
typedef long long LL;
using namespace std;int t;
int a,b,k;
int main(){scanf ("%d",&t);while(t--){scanf ("%d%d%d",&a,&b,&k);double ans=b*1.0/(a+b);printf ("%.3lfn",ans);}return 0;
}

 

G：逃离迷宫 题目描述

给你一个n*m的图，地图上'.'代表可以走的地方，而'#'代表陷阱不能走，
'P'代表人物位置，'K'代表钥匙，'E'代表出口。人物一个，钥匙有多个，
（'K'的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。

输入描述:

第一行一个整数T(T <= 50)，代表数据的组数
接下来一行n,m(n<=500,m<=500),代表地图的行和列
接下来n行，每行一个长度为m的字符串，组成一个图。

输出描述:

如果可以出去，输出所花费的最少时间。
如果不能出去，输出一行"No solution"。

思路：bfs。

G
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int N = 500 + 5;
typedef long long LL;
using namespace std;
int vis[N][N][3];
char ar[N][N];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m;
int s1,t1;
int flag;
struct lp{int x,y,ip,step;lp(){}lp(int a,int b,int c,int d):x(a),y(b),ip(c),step(d){}
}now,t;;
int bfs(){flag=0;queue<lp>Q;t.x=s1;t.y=t1;t.ip=0;t.step=0;Q.push(t);memset(vis,0,sizeof(vis));vis[s1][t1][0]=1;while(!Q.empty()){now=Q.front();Q.pop();for(int i=0;i<4;++i){int px=now.x+dir[i][0],py=now.y+dir[i][1];if(px<0||py<0||px>=n||py>=m)continue;int ip=now.ip;if(vis[px][py][ip])continue;if(ar[px][py]=='#')continue;vis[px][py][ip]=1;if(ar[px][py]=='E'&&ip==1){flag=1;return now.step+1;}if(ar[px][py]=='E')continue;if(ar[px][py]=='K')ip=1;vis[px][py][ip]=1;t.x=px,t.y=py,t.ip=ip,t.step=now.step+1;Q.push(t);}}return -1;
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;++i){scanf("%s",ar[i]);for(int j=0;j<m;++j){if(ar[i][j]=='P')s1=i,t1=j;}}int ans=bfs();if(flag==1)printf("%dn",ans);else printf("No solutionn");}return 0;
}

 

 

L：仓鼠养殖计划 题目描述

集训队暑训的时候，是睡在机房的，有几个小伙子不甘寂寞，带了仓鼠来机房。有的还不止带了一只！
为此，贴心的集训队刘队长买了一大一小两种放仓鼠笼子的架子，大的可以放两个仓鼠笼 小的只能放一个。
要注意的是仓鼠是领地动物，一般来讲 仓鼠笼与仓鼠笼之间是不能贴在一起的，
但同一个人带来的仓鼠的仓鼠笼可以被放在一起（既两个仓鼠笼如果属于同一个人，那么这两个仓鼠笼就可以被放在同一个大架子上）
现在告诉你现有的两种架子的数量和多少人带了仓鼠以及每个人带的仓鼠的数量，问你是否能将这些仓鼠放下。

输入描述:

第一行为一个数T 表示测试样例组数

对于每组测试数据

第1行输入a,b,n; 分别为小架子的数量，大架子的数量，带了仓鼠的人数

第2行有n个数字P1-Pn，分别表示每个人带的仓鼠的数量

输出描述:

如果放得下 则输出"Yes" 否则输出"No"

思路：贪心。

L
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int N = 1e3 + 5;
typedef long long LL;
using namespace std;
int ar[N];
int main(){int a,b,n;int tt;scanf("%d",&tt);while(tt--){scanf("%d%d%d",&a,&b,&n);int tmp=0,sum=0;for(int i=0;i<n;++i){scanf("%d",&ar[i]);int t=ar[i]/2;if(b>0){if(b>=t&&t){b-=t;tmp+=2*t;ar[i]-=(2*t);}else if(t){ar[i]-=(2*b);tmp+=2*b;b=0;}}sum+=ar[i];}int ans=a+b;if(ans>=sum)printf("Yesn");else printf("Non");}return 0;
}

 

 

H：数学考试 题目描述

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

输入描述:

第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）

输出描述:

输出一个整数，qwb能获得的最大分数

思路：线段树记录区间最值。

#include<bits/stdc++.h>
#define INF 1e16
#define I64d lld
#define lson rt<<1
#define rson rt<<1|1
#define lsonl rt<<1,l,m
#define rsonr rt<<1|1,m+1,r
const int maxn = 2e5 + 5;
typedef long long LL;
using namespace std;
LL ar[maxn],a[maxn];
struct lp{int l,r;LL sum;
}tree[maxn<<2];
LL ma(LL a,LL b){if(a<b)a=b;return a;
}
void push_up(int rt){tree[rt].sum=max(tree[lson].sum,tree[rson].sum);
}
void build(int rt,int l,int r){tree[rt].l=l;tree[rt].r=r;if(l==r){tree[rt].sum=a[l];//printf("*%lldn",a[l]);return;}int m=(l+r)>>1;build(lsonl);build(rsonr);push_up(rt);
}
LL query(int rt,int l,int r){if((l<=tree[rt].l)&&(tree[rt].r<=r)){//printf("*%lldn",tree[rt].sum);return tree[rt].sum;}int m=(tree[rt].l+tree[rt].r)/2;if(l>m)return query(rson,l,r);else if(r<=m)return query(lson,l,r);else{LL ans=query(lsonl);ans=max(ans,query(rsonr));return ans;}/*LL ans=-INF;if(l<=m)ans=ma(ans,query(lson,l,r));if(r>m)ans=ma(ans,query(rson,l,r));return ans;*/
}
int main(){int t;scanf("%d",&t);int tim=0;while(t--){int n,k;memset(a,0,sizeof(a));scanf("%d%d",&n,&k);for(int i=1;i<=n;++i){scanf("%lld",&ar[i]);}/*if(n==8&&k==2){printf("7n");continue;}*/int p=2;for(int i=1;i<=n;++i){if(i<=k)a[1]+=ar[i];else{a[p]=a[p-1]+ar[i]-ar[i-k];p++;}}for(int i=1;i<=n;++i){//printf("%lld ",a[i]);}//printf("n");int m=p-1;build(1,1,m);LL ans=-INF;//printf("%lldn",query(1,4,5));for(int i=1;i<=m;++i){LL x=-INF,y;if(i+k>m)break;y=query(1,i+k,m);ans=max(ans,y+a[i]);}printf("%lldn",ans);}return 0;
}

 

#include <unordered_map>
#include <unordered_set>
std::unordered_map<int, std::unordered_set<int> > V;
int solve() {for(int i=0; i<n; i++) {int nu = fa[e[i].u], nv = fa[e[i].v];if(nu != nv) {if(!V[nu].count(nv)) {du[nu]++;du[nv]++;V[nu].insert(nv);V[nv].insert(nu);}}}
}