190504--2019湘潭大学程序设计大赛重现赛
发现自己真的太菜了，签到题全部wa，所以现根据网上题解和自己的理解做一个题解自己看看
再此顺便感谢网上贴出题解供我理解的大佬们：
阿茶家的庸医(注释和方法都非常清晰！！！)
yjun
守林鸟
ccsu_YangJ
目录
A.Who's matter?(签到题）
B.Number（签到题）
C.Math Problem(签到题)
D.stone(签到题）
F.Black & White
链接：https://ac.nowcoder.com/acm/contest/893/A
来源：牛客网
A.Who's matter?(签到题）
ICPC比赛中，谁通过的题数多，谁排名靠前；在通过题数相同的情况下，谁的罚时少，谁排名靠前；如果前两者都相同，就看最后正确提交的时间，谁早最排名靠前。 现在给你两个队伍的正确通过的题数、罚时和最后正确提交时间，请判断一下，谁的排名更靠前？
输入描述:
只有一组测试样例，两行，每行三个整数n(0≤n≤13),p(1≤p≤1000),s(1≤s≤300)，依次表示两个队的正确通过的题数、罚时和最后正确提交时间。
输出描述:
输出一行（末尾要换行符）。
如果是第1个队排名靠前，输出1；如果是2队，输出2；如果无法分辨，输出"God"。
1 10 10
1 22 2
输出
<pre>1</pre>
示例2
输入
<pre>1 10 10
2 42 20</pre>
输出
<pre>2</pre>
示例3
输入
1 10 10
1 10 10
输出
God
//注意不要超时
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
int a,b,suma=0,sumb=0,ta,tb,sa,sb;
scanf("%d%d%d",&a,&ta,&sa);
scanf("%d%d%d",&b,&tb,&sb);
if(a>b)suma++;
else if(b>a)sumb++;
else {
if(ta<tb)suma++;
else if(ta>tb)sumb++;
else {
if(sa>sb)sumb++;
else if(sa<sb)suma++;
}
}
if(suma>sumb)cout<<"1"<<endl;
else if(suma<sumb)cout<<"2"<<endl;
else cout<<"God"<<endl;
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/893/B
来源：牛客网
B.Number（签到题）
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
Bonnie得到了一个数字n。
现在她想对这个数字不断的做一种操作：
- 如果n的最后一位数码是0，那么她就把n除以10；
- 否则她把这个数加上1；
- 直到n变为一个不大于1的数。
给定n，请问Bonnie需要做多少次操作？
输入描述:
<pre>第一行一个数字T(1≤T≤300000)-样例个数。
每个样例仅一行一个数字n(1≤n≤109)
输出描述:
每个样例输出一行一个数字—Bonnie需要做的操作次数。
示例1
输入
6
9
99
2
11032
1000000000
62
输出
2
3
9
44
9
13
说明
<pre>第一个样例: 9→10→1
第二个样例: 99→100→10→1
//做不出纯粹是我个人理解题目的问题
//我以为判断条件是转化成二进制码的最后一位，没想到n%10暴力AC，orz
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main(){
int n,count,t;
scanf("%d",&t);
while(t--){
count=0;
scanf("%d",&n);
while(n>1){
if(n%10==0)n=n/10;
else n++;
count++;
};
cout<<count<<endl;
}
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/893/C
来源：牛客网
C.Math Problem(签到题)
题目描述
已知整数a,a3，a,a^3除192的余数是1。求区间[L,R]之间满足条件的a的累加和是多少？
输入描述:
<pre>第一行是一个整数T(1≤T≤10000）表示样例的个数。
每个样例包含两个整数L,R,1≤L≤R≤109
输出描述:
每行输出一个样例的结果。
示例1
输入
1
1 10
输出
1
超时代码：
#include<stdio.h>
#include<iostream>
#define ll long long
using namespace std;
ll f(ll l,ll r){
ll sum=0;
for(int i=l;i<=r;i++){
ll m=i*i*i;
if(m%192==1)
sum+=i;
}
return sum;
}
int main(){
ll t,l,r,a;
cin>>t;
while(t--){
scanf("%lld%lld",&l,&r);
printf("%lld\n",f(l,r));
}
}
AC代码1：找规律，复杂度减少
（ak+1)3=a3k3+3a2k2+3ak+1=(a2k3+3a1k^2+3k)a+1=a*x+1;
即（a*k+1）的3次方也是a的倍数+1；
#include<bits/stdc++.h>
using namespace std;
int t,l,r;
int main(){
scanf("%d",&t);
while(t--){
long long ans=0;
scanf("%d%d",&l,&r);
int p=l/192,q=r/192;
if(l%192>1)p++;
if(r%192<1)q--;
for(int i=p;i<=q;i++){
ans=ans+(long long )i*192+1;
}
printf("%lld\n",ans);
}
return 0;
}
AC代码2：
#include<stdio.h>
#include<iostream>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int t;
ll l,r,a;
ll f(ll l,ll r){
ll sum=0;
while(l%192!=1)
l++;
while(r%192!=1)
r--;
a=r/192-l/192+1;
sum=((l+r)/2)*a;
return sum;
}
int main(){
cin>>t;
while(t--){
scanf("%lld%lld",&l,&r);
printf("%lld\n",f(l,r));
}
}
链接：https://ac.nowcoder.com/acm/contest/893/D
来源：牛客网
D.stone(签到题）
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述[](javascript:void(0);)[]
有n堆石子排成一排，第i堆石子有a个石子。
每次，你可以选择任意相邻的两堆石子进行合并，合并后的石子数量为两堆石子的和，消耗的体力等价于两堆石子中石子数少的那个。
请问，将所有的石子合并成一堆，你所消耗的体力最小是多少？
输入描述:
第一行是一个整数T表示样例的个数。
每个样例的第一行是一个整数表示石子堆的数量。
第二行是n个整数ai(1≤ai≤109)
输出描述:
每行输出一个样例的结果。
示例1
输入
2
2
1 2
1
1
输出
1
0
说明
巨大的输入，请使用C风格的输入。
//两两求最大值，然后用总数减最大值
// WA理由：long long必须用在n,a上
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stdlib.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int main(){
ll t,n;
ll a[100000];
scanf("%d",&t);
while(t--){
ll sum=0;
scanf("%d",&n);
ll Max=0;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
Max=max(Max,a[i]);
}
printf("%lld\n",sum-Max);
}
return 0;
}
F.Black & White
题目描述
你有一个长度为 n 的 01 串S，你可以执行最多 m 次操作。
对于每次操作，你可以选择一个位置 i 满足
1≤i≤n，翻转这一位的值，0变成1，1变成0。
定义一个 01 串的价值为其中最长连续0的个数和最长连续1的个数的较大值，求S在经过最多m次操作后的最大价值。
输入描述:
第一行一个整数 T ，表示接下来有 T 个样例。
首先输入n,m，表示S串的长度n和操作次数m，其中
1≤n≤100000，0≤m≤10000；
接下来输入一个长度为n的字符串S。
输出描述:
一个整数，表示题面上描述的最大价值。
示例1
输入
2
5 1
00101
2 1
01
输出
4
2
说明
第一个串翻转第三个位置，00001的价值为4；第二个串翻转第一个位置，11的价值为2。
思路：
- 尺取法（目前还搞不太清楚，故贴出大佬的尺取法的学习地址：尺取法 — 详解 + 例题模板(全)）
- 前缀+二分法：
首先预处理两个数组 pre1 和 pre0，分别代表1～i个位置上1和0的个数
这样就可以在 O(1) 的时间求出 区间内 1或者0 的个数
然后二分答案：最大长度len。
因为 len 是固定的，所以 l=1，r=len 开始 滑动窗口（时间O(n)），每次移动都判断当前方块内 1或者0的个数是否小于 可以改变的次数m，如果小于等于 则 len 可以成立，可以往更大值二分，否则只能往更小值二分。
时间复杂度：每次二分判断需要O(n)的时间，二分需要log2(n)的时间，所以总时间n*lg(n)时间复杂度ok
贴出前缀+二分AC代码：
//大佬（阿茶的庸医）的代码
#include <iostream>
#include <algorithm>
#include <string>
#define N 100010
using namespace std;
string str;
int n, m;
int pre0[N], pre1[N];//0和1的个数数组
//判断是否可以进行转换
//(每次移动都判断当前方块内 1或者0的个数是否小于 可以改变的次数m)
bool judjed(int len){
int l = 1, r = len;
while(r <= n){
if(pre0[r]-pre0[l-1] <= m || pre1[r]-pre1[l-1] <= m)
return true;
++l, ++r;
}
return false;
}
//二分
int get_n(){
int res;
int l=0, r=n;
while(l <= r){
int mid = (l+r)/2;
if(judjed(mid)){//可以往更大值二分
l = mid+1;
res = mid;
}else{
r = mid-1;
}
}
return res;
}
int main(){
int T;
cin >> T;
while(T--){
cin >> n >> m;//n长度，m操作次数
cin >> str;
for(int i=1; i<=n; i++){
if(str[i-1] == '0'){
pre0[i] = pre0[i-1]+1;
pre1[i] = pre1[i-1];
}else{
pre0[i] = pre0[i-1];
pre1[i] = pre1[i-1]+1;
}
}
cout << get_n() << endl;
str.clear();
}
return 0;
}
查看16道真题和解析
锐捷网络股份有限公司公司福利 348人发布