北京师范大学第十六届程序设计竞赛决赛-重现赛

本文主要是介绍北京师范大学第十六届程序设计竞赛决赛-重现赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 塞特斯玛斯塔

链接：https://www.nowcoder.com/acm/contest/117/A
来源：牛客网

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

题目描述

quailty是一名狂热的ACM音游选手，沉迷各种音乐游戏，比如Lunatic Rave 2，osu!之类的。

今天，quailty玩的是国内游戏厂商雷亚（并不是赞助商）出品的一款音乐游戏Cytus。

游戏中，玩家需要随着游戏界面中上下移动的扫描线来适时演奏对应音符。

当上下移动的黑色线（扫描线）与圆形的物体（音符）的圆心重合时点击音符。

普通音符（图中第一种）只需点击即可。

锁链音符（图中第二种）将带箭头的音符（滑块）按下后不要松开，并将滑块沿着斜线和圆点组成的路径拖动，直至拖动到最后一个圆点处方可松开。注意拖动过程中应保持滑块圆心始终与扫描线重合。

长按音符（图中第三种）按下后不要松开，原地不动，等扫描线到达其末端并显示判定结果后方可松开。

Cytus共有五种判定，从好到坏依次为：彩PERFECT、黑PERFECT、GOOD、BAD、MISS。

得分中包括了90%的“判定分”和10%的“连击分”，而连击分是累进计算的，断COMBO对其影响很大，往往只要有1个MISS就会损失几万的连击分。

彩PERFECT和黑PERFECT在计算得分时一视同仁，只要全部PERFECT即可获得满分，满分为1000000，被称为MILLION Master。

quailty真的很严格，如果打完一把没有拿到MILLION Master，他就认为自己是NAIVE Noob。

现在给你quailty打出的判定序列，请你输出这次游戏的评价是MILLION Master还是NAIVE Noob。

输入描述:

第一行是一个正整数T ( 1 ≤ T ≤ 5 )，表示测试数据的组数，
每组测试数据，第一行是一个正整数n ( 1 ≤ n ≤ 100000 )，表示该组测试数据包含的判定数。接下来的n行，每行包含"PERFECT"、"GOOD"、"BAD"、"MISS"之中的一个字符串，表示quailty打出的一个判定。

输出描述:

对于每组数据，输出一行，包含一个字符串，表示这次游戏的评价。

示例1

输入

2
5
PERFECT
PERFECT
PERFECT
PERFECT
PERFECT
10
PERFECT
MISS
PERFECT
BAD
BAD
GOOD
BAD
GOOD
GOOD
MISS

输出

MILLION Master
NAIVE Noob

思路：签到题目，前面全是废话。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;string str;bool flag = false;for(int i=1;i<=n;i++){cin>>str;if(str!="PERFECT"){flag = true;}}if(flag)cout<<"NAIVE Noob"<<endl;elsecout<<"MILLION Master"<<endl;}return 0;
}

C 萌萌哒身高差

思路；

（1）多写几个样例，找规律。2的时候3/3；3的时候8/3；4的时候15/3；5的时候24/3；6的时候35/3，可以发现n的时候就是((n*n)-1)/3即n方减一

代码：

#include <iostream>
#include <iomanip>2
using namespace std;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;cout<<fixed<<setprecision(12)<<((n*n)-1.0)/3.0<<endl;}return 0;
}

（2）另一种思考方式，由于是全排列，对于n个数，总共有n*(n-1)/2种形式的差，且每种差出现次数相同，两重for循环即可求出所有形式的差出现一次的和sum，那么求出每种差出现的次数就可以求出差的总和。由于每一种顺序有n-1种差，有n！种序列，所以每次出现的次数为：n!*(n-1)/(n*(n-1)/2)=2*(n-1)!所以和即为：(sum*2*(n-1)!)/n! = sum*2/n即为答案。

代码：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N=1000010;
const int mod=1e9+7;
const int Max=0x3f3f3f3f;ll ans[N];
char ch[N];int main()
{int T;cin>>T;while(T--){int i,j;ll sum=0;int n;cin>>n;for(i=n;i>=1;i--){for(j=1;j<=n;j++){if(i>j)sum+=(i-j);}}double ans=(2.0*sum)/n;cout<<fixed<<setprecision(12)<<ans<<endl;}return 0;
}

D 雷电爆裂之力

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

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

题目描述

听说导体切割磁感线可以发电？

今天，zhuaiballl想要做切割磁感线运动，感受雷电的力量。

南北方向有四条马路，从西到东依次是京师路，木铎路，金声路和新街口外大街，可以看成是四条平行的数轴，且相邻的两条数轴之间距离为1m。东西走向有许多小道连接了相邻的马路。假设地磁南极和地理北极重合，地磁北极和地理南极重合。现在zhuaiballl位于京师路的某个位置，想要出发前往新街口外大街，速度为1m/s。由于可能没有一条路径从西到东一直连向新街口外大街，所以每次遇到丁字路口时，zhuaiballl需要选择是往左走还是往右走，样例如下图所示。

zhuaiballl想要感受尽可能强的雷电力量，所以希望从他开始往东走时开始，到他到达新街口外大街所需要的时间尽可能短。

现在，给你附近的地图，你能否求出从zhuaiballl开始往东走时开始，到他到达新街口外大街的最短时间？

输入描述:

第一行是一个正整数T(≤ 20)，表示测试数据的组数，对于每组测试数据，第一行是一个整数n,m,k(1≤ n,m,k ≤ 100000)，分别表示连接京师路与木铎路，木铎路与金声路，金声路与新街口外大街的道路个数，第二行包含n个以空格分隔的整数a₁,a₂,...,a_n，表示连接京师路与木铎路的各个小道的南北方向坐标（单位：m），第三行包含m个以空格分隔的整数b₁,b₂,...,b_m，表示连接木铎路与金声路的各个小道的南北方向坐标（单位：m），第四行包含k个以空格分隔的整数c₁,c₂,...,c_k，表示连接金声路与新街口外大街的各个小道的南北方向坐标（单位：m），保证每行坐标按严格递增的顺序给出，并且坐标绝对值不超过10⁹。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示答案（单位：s）。

示例1

输入

输出

思路：

如果直接求需要三重循环，很明显是会超时，所以就要想办法优化，如何优化呢？首先，我们可以以中间路为一个分割点，求出左边到中间所需的距离，然后再求从右到中间的距离，这样就变成了两个for循环，减少时间。然后两者的和再加上3即为答案。那么如何求最小值呢？首先由于坐标值是递增的，所以我们以一个序列（b）遍历另一个序列(a)，找最小的办法就是a从左往右找，只要比以前的最小值小就更新最小值，否则判断两个序列的值的大小，因为如果a序列的数大于b的，就没必要继续找下去了，记录当前a的位置，接着继续b的下一个位置。详见代码：

（注意一个坑，inf一开始初始化为1e9)*3+10;结果一直是wa，无意中改了一下，结果AC了，真的是坑。。。）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX = 100010;
const LL INF = (1e9)*300+10;
LL a[MAX],b[MAX],c[MAX];
LL ma[MAX],mc[MAX];  ///ma是中间到左边最小，mc是中间到右边最小
int main()
{int t;LL n,m,k;cin>>t;while(t--){cin>>n>>m>>k;for(LL i=1;i<=n;i++){cin>>a[i];}for(LL i=1;i<=m;i++){cin>>b[i];ma[i] = INF;mc[i] = INF;}for(LL i=1;i<=k;i++){cin>>c[i];}LL pre = 1; ///记录上次找到那个位置，下次继续接着从此处寻找for(LL i=1;i<=m; i++){LL minn = INF;if(pre>n) pre=n;for(LL j=pre;j<=n;j++){if(fabs(b[i]-a[j])<minn)   {minn = fabs(b[i]-a[j]);pre = j;}else  //注意，此种情况就没必要再继续找下去{if(a[j]>b[i])break;}}ma[i] = minn;}pre =1;for(LL i=1;i<=m;i++){LL minn = INF;if(pre>k) pre = k;for(LL j= pre;j<=k;j++){if(fabs(b[i]-c[j])<minn){minn = fabs(b[i]-c[j]);pre = j;}else{if(c[j]>b[i])break;}}mc[i] = minn;}LL ans=INF;for(LL i=1;i<=m;i++){if(ans>(ma[i]+mc[i]))ans=ma[i]+mc[i];}ans+=3;cout<<ans<<endl;}return 0;
}

E 可以来拯救吗

思路：

简单的dfs即可，注意将k以n/2为界分成21部分，即小于等于n/2和大于n/2，然后利用Ck n 的性质来求解即可。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 100005;
int n,k;
int T;
int a[maxn];
LL ans,sum;
void dfs1(int i,int len,int cnt)  ///处理小于等于n/2
{if(len>k) return;for(LL j=i+1;j<=n;j++){cnt+= a[j];if(len==k){ans = ans^(cnt * cnt);}else{dfs1(j,len+1,cnt);}cnt-=a[j];  //回溯}
}void dfs2(int i,int  len,int cnt)  ///处理大于n/2时的情况
{if(len>k) return;for(int j=i+1;j<=n;j++){cnt+=a[j];if(len == k){LL temp = sum-cnt;  //此处需要注意ans = ans^(temp * temp);}else{dfs2(j,len+1,cnt);}cnt-=a[j];}
}
int main()
{cin>>T;while(T--){cin>>n>>k;sum=0;for(int i=1; i<=n ; i++){cin>>a[i];sum+=a[i];}ans=0;if(k<=n/2){if(k==1){for(int i=1;i<=n;i++){ans = ans^(a[i] * a[i]);}}else{for(int i=1;i<=n-k+1;i++){dfs1(i,2,a[i]);}}}else        ///当k大于n/2时{k = n-k;if(k==0) ///特殊处理等于n的情况{ans = sum*sum;}else if(k==1){for(int i=1;i<=n;i++){ans=ans^((sum-a[i])*(sum-a[i]));  ///也就是当k=n-1时的情况}}else{for(int i=1;i<=n-k+1;i++){dfs2(i,2,a[i]);}}}cout<<ans<<endl;}return 0;
}

G 命名规范问题

链接：https://www.nowcoder.com/acm/contest/117/G
来源：牛客网

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

题目描述

驼峰命名法是起变量名的一种规范，大致来说是用混合的大小写字母来构成变量名，在这个问题里你可以假设具体规则如下：

1.每个变量名由至少2个单词拼接构成，且每个单词长度至少为2；

2.每个单词的首字母必须大写，其他位置必须小写（除了变量名的第一个单词允许全部小写外）。

但是SK同学的英语很差，看到长长的变量名就很难脑补出是由哪些单词组成的，因此看驼峰命名法的代码十分头疼。

还有一种下划线命名法，规则比较简单，即各个单词之间用下划线'_'连接，且字母全部小写。

现在给你一些变量名，你能将其中符合驼峰命名法规范的变量转换成下划线命名法吗？

输入描述:

第一行是一个正整数T(≤ 20000)，表示测试数据的组数，
每组测试数据只有一行，包含一个仅包含大小写英文字母且长度不超过20的变量名，
保证所有测试数据变量名长度总和不超过200000。

输出描述:

对于每组测试数据，输出一行，包含一个字符串，如果变量名符合驼峰命名法规范则将其改为下划线命名法，否则不变。

示例1

输入

10
mystring
myString
String
SS
my
mySString
mString
STRING
StrinG
IndexOfString

输出

mystring
my_string
String
SS
my
mySString
mString
STRING
StrinG
index_of_string

思路：

根据给的条件，模拟一遍即可

代码：

#include <iostream>
#include <cstring>
using namespace std;
char s[200005];void print(char *s)
{int len = strlen(s);for(int i=0;i<len;i++){cout<<s[i];}cout<<endl;
}int main()
{int t;cin>>t;while(t--){int num_upp=0;cin>>s;int len = strlen(s);for(int i=0;i<len;i++){if(s[i]<='Z' && s[i] >= 'A'){num_upp++;}}if(num_upp==0||(num_upp==1&&s[0]>='A'&&s[0]<='Z'))   ///当不满足（1）即1个变量至少两个单词的条件时直接输出{print(s);continue;}int num_low=0;bool flag=true;for(int i=0;i<len;i++){if(s[i]<='Z' && s[i]>='A'){if(i!=0 && num_low<2)   ///当不满足（2）每个单词至少由2个字母组成的条件时直接输出{flag=false;break;}num_low = 1;}else{num_low++;}}if(num_low<2) flag = false;///别忘记比较最后一个if(!flag){print(s);continue;}///以上两者均满足是进行下面string str="";for(int i=0;i<len;i++){if(s[i]>='A' && s[i]<='Z'){if(i!=0){str+="_";}str+='a'+(s[i]-'A');}else{str+=s[i];}}cout<<str<<endl;}return 0;
}

I 如何办好比赛

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

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

题目描述

又到了一年一度的程序设计大赛了~

现在参赛选手在机房前排起了一列长队，这里面有萌新也有大佬，萌新都很仰慕大佬，由于大佬们的参赛，萌新们对这次比赛的精彩程度格外期待。对于每个萌新来说，他/她/它对本次的比赛的期待度为排在他/她/它前面的大佬的数量，而这次比赛的总期待度等于每个萌新的期待度之和。

SK同学作为本次比赛的组织者，希望比赛的期待度能够刚刚好，太低的话会让大家兴致不高，太高的话会被喷不满足预期。

现在SK同学可以交换任意相邻的两名参赛选手，但是比赛马上就要开始了，SK同学想知道最少要进行多少次交换才能使得这次比赛的总期待度刚好为k，你能帮帮他吗？

输入描述:

第一行是一个正整数T(≤ 10)，表示测试数据的组数，
对于每组测试数据，
第一行是两个正整数n(≤ 1000000)和k(≤ 1000000000)，分别表示队列长度和最终的比赛总期待度，
接下来一行包含n个字符，表示这个队列，第i个字符表示队列里的第i个人，'D'表示大佬，'M'表示萌新，保证不会出现其它字符。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示最少的交换次数，无解输出-1。

示例1

输入

2
3 1
DMM
3 3
DMM

输出

1
-1

思路：

首先过一遍数据，求出当前序列的期待值，然后判断是比k大还是k小，因为当D发生左移时，其实是每左移一位就加一，相反，右移减一，那么判断能否有加减得到k即可

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1000005];
int main()
{int t;cin>>t;while(t--){ll n,k;cin>>n>>k;cin>>s;ll n_d=0;ll num=0;for(int i=0; i<n; i++){if(s[i]=='D')n_d++;elsenum+=n_d;}if(num>=k)  //需要进行右移{ll sum=0;ll cnt=0;for(int i=n-1; i>=0; i--)  //注意从后往前看{if(s[i] == 'M' ) sum++;else  cnt+=sum;}if(num-cnt<=k) cout<<num-k<<endl;else cout<<-1<<endl;}else{ll sum=0;ll cnt=0;for(int i=0;i<=n-1;i++){if(s[i]=='M') sum++;else cnt+=sum;}if(num+cnt>=k) cout<<k-num<<endl;else cout<<-1<<endl;}}return 0;
}