『小白杯』黄冈师范学院程序设计
第三届新生赛题解
:
一般的暴力写法是根据n循环并判断每个数字是否含有9,以此得到第n项,但是n的数据范围是1e9级别,暴力的写法被卡掉了。
由题意可知,含9的数字被删除,在具体的数字上表示为逢9进1,所以对于给定的n,转化成9进制表示即可。 时间复杂度O(log n)
题解代码：
#include<stdio.h>
int res[100];
int main(){
int n;
scanf("%d",&n);
int size=0;
while(n){
res[++size]=n%9;
n/=9;
}
for(int i=size;i;i--)printf("%d",res[i]);
}
:的外卖:
本题的难点就在于对双循环的优化，可以通过预处理的方式来解决，求连续一段区间（l，r）的总和，可以看成求前r项和减去前l-1项和，那么我们就可以提前将前n项和求出来，然后求连续k天的总和就不需要用循环来再求一遍。
当然，也有另一种解法，也是过了的人都用的解法，就是维护一个长度为k的区间，让这个区间不断的向后面移动，每次都加上加入到区间中的数和减去移除区间的数，然后比较更新最大值，从头到尾跑一遍就能得到最大值。
还有就是本题的数据比较大，需要开long long.
题解代码:
解法一：
#include <iostream>
using namespace std;
const int N=1e5+10;
long long a[N],s[N]; //s数组用来记录前n项和
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i]; //s[i]表示前i项和
}
long long sum=0;
for(int i=k;i<=n;i++)
{
sum=max(sum,s[i]-s[i-k]); //s[i]-s[i-k]表式第i-k+1项到第i项之和
}
cout<<sum<<endl;
}
解法二：
#include <iostream>
using namespace std;
const int N=1e5+10;
long long a[N];
int main()
{
int n,k;
cin>>n>>k;
long long sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i<=k)sum+=a[i]; //先计算出前k项
}
long long ans=sum;
for(int i=k+1;i<=n;i++) //从第k+1项开始，加上第i项，减去前面第i-k项，然后比较和之前最大的值，然后更新最大值
{
sum+=a[i];
sum-=a[i-k];
ans=max(sum,ans);
}
cout<<ans<<endl;
}
:谁才是第一名：
本题为此次比赛的签到题，先比较过题数，过题数不相同取直接最大值，过题数相同则比较过题时间，取过题时间更小的即可。
题解代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
int a,b,c;
int x,y,z;
scanf("%d %d %d",&a,&b,&c);
scanf("%d %d %d",&x,&y,&z);
if(a>x)
{
printf("QQLover");
return 0;
}
else if(a<x)
{
printf("VXLover");
}
else if(a==x)
{
if(b+(c-1)*20>y+(z-1)*20)
{
printf("VXLover");
return 0;
}
else
{
printf("QQLover");
return 0;
}
}
return 0;
}
:最长回文子串：
本题介绍其中一种解法：枚举给定字符串的左右端点，如相同则往中间移动（左端点的左指针向右移动，右端点的指针向左移动），直到不相同为止，每次记录一次回文子串的最大长度即可。复杂度O（n^3）。
题解代码：
#include <stdio.h>
#include<string.h>
const int N=1e3+10;
int max(int a , int b)
{
if(a>b) return a;
else return b;
}
int main()
{
char s[N];
scanf("%s",s);
int len = strlen(s);
int mxl = 0;
for(int i=0 ; i<len-1 ;i++)
{
for(int j=i+1 ;j<len ;j++)
{
int l=i , r=j;//左指针指向i，右指针指向j
while(l<r)
{
if(s[l]!=s[r])break;//不同则退出循环
else{
r--;l++;
}
}
if(l>=r)
{
int len = j-i+1;//j-i+1为此时枚举的回文子串长度
mxl = max(mxl , len);
}
}
}
printf("%d\n",mxl);
}
:想当滋崩狗：
检查和原点的曼哈顿距离是否为奇数，如果存在偶数就会被追上。
题解代码
#include<bitsdc++.h>
using namespace std;
int main(){
int n, x, y;
// scanf("%d %d %d", &n, &x, &y);
cin >> n >> x >> y;
int tx, ty;
int judge = 1;
for (int i = 1; i <= n; i ++){
// scanf("%d, %d", &tx, &ty)
cin >> tx >> ty;
int dis = abs(x - tx) + (y - ty);
// abs() 为求绝对值
if(dis % 2 == 0)
judge = 0;
}
cout << (judge ? "YES" : "NO") << endl;
}
:谁才是第一名：
本题为签到题的加强版，先比较过题数，过题数不相同取过题数高的并更新此时的第一名，过题数相同则比较过题时间，取过题时间更小作为第一名并更新即可。
题解代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c;
int max=-1,max2=-1;
int n;
int ans;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b>>c;
if(max2<a)
{
ans=i;
max2=a;
max=b+(c-1)*20;
}
else if(max2==a)
{
if(max>b+(c-1)*20)
{
ans=i;
max=b+(c-1)*20;
}
}
}
printf("%d",ans+1);
}
的签到题:
思路就是读入的是一个字符串，不能用int来读,可以用string 或者char数组来读入。
题解代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
char a;
cin>>a;
int flag=1;
for(int i=0;i<s.size();i++)
{
if(s[i]==a)
{
cout<<i+1<<endl;
flag=0;
break;
}
}
if(flag) cout<<"-1"<<endl;
}
return 0;
}