“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛) 原创
- B题
我觉得这应该是一道模拟题，就照题目的意思进行模拟就好了。
每一次先找出不是1的数，从这个不是1的数开始寻找一个最小的数，当碰到1的时候退出这个寻找的循环，然后将找出的最小的数都减去在这个范围内的数。累加这个最小的数。一直重复着，一直到找不到不是1 的数的时候退出循环。
代码：
#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int INF=0x7f7f7f7f;
int num[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int minn=0,a=1;
ll sum=0;
while(1)
{
int b=0;
for(int i=a;i<=n;i++)
{
if(num[i]==1) break;
if(num[i]!=1) num[i]-=minn;
}
for(int i=a;i<=n;i++)
{
if(num[i]!=1)
{
b=i;
break;
}
}
if(b==0) break;
a=b;
minn=INF;
for(int i=a;i<=n;i++)
{
if(num[i]==1) break;
minn=min(minn,num[i]);
}//printf("%d %d %d \n",minn,a,sum);
minn--;
sum+=minn;
}
printf("%lld\n",sum);
}
return 0;
} - c题
是一道签到题，但是我却做了好久，因为我使用double，输出以lf输出，这样写是没有问题的，有问题的是我提交的是第一个，所以一直错误，第一个应该是c99的，我下面的代码要提交的是第二个，才能通过。
代码：
#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(0),cin.tie(0)
#define PI 3.14
using namespace std;
typedef long long ll;
const int N= 10000;
const int INF=0x7f7f7f7f;
int mp[N][N],vis[N][N];
int d[][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,cnt=INF;
int main()
{
cin>>T;
while(T--)
{
double a,b;
scanf("%lf",&a);
b=2.0*PI*(a/2.0)*(a/2.0)+a*a*1.0;
printf("%.2lf\n",b);
}
return 0;
}- E题
这题可以使用二分查找，但是呢，强大的STL中有一个函数就是二分查找的函数，所以就不能这么麻烦的手写二分啦。要记得使用这个函数的时候，查找的数要自加1，为了以防找到一个和自己一样的数，找到的数要进行标记，我这里的是将找出的数全部改为-1，我想的是应该没有哪一个数要比-1小了吧，而且输出的都是正整数，O(∩_∩)O哈哈~，不要忘记每一次查询都要sort一遍哦，(* ^▽^)，*（小声逼逼，我看了一下，好像没有那个人和我一样呢，用STL，嘿嘿，可能是我没有仔细看）
代码：
#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int N= 100000+5;
const int INF=0x7f7f7f7f;
//int mp[N][N],vis[N][N];
int d[][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,cnt=INF;
ll num[N],vis[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld",&num[i]);
sort(num,num+n);
ll cnt=0;
for(int i=0;i<n;i++)
{
ll x;
scanf("%lld",&x);
ll pj=lower_bound(num,num+n,x+1)-num;
if(num[pj]>x)
{
cnt++;
num[pj]=-1;
sort(num,num+n);
}
}
printf("%lld\n",cnt);
}
return 0;
}- F题
这题大家应该都知道的一个定理：三角形两边之和大于第三边，两边之差小于第三边。并且这两个条件缺一不可。既然这样，我们可以找出1,1,2，3,4,5......这样的分段长度，因为两边之和不能大于第三，又要尽可能的取多，所以只好这样取了。因此可以发现，这是斐波那契数列，所以公式也可以很快的得出，限定的条件就是取出的这些分段的和要是原木棒的和，因此要把这些数相加小于或者等于小木棒的长度。
#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=100+1;
ull f[N];
void fun()
{
f[1]=1,f[2]=1;
for(int i=3;i<=101;i++)
f[i]=f[i-1]+f[i-2];
}
int main()
{
IO ;
int t;
cin>>t;
fun();
while(t--)
{
ull n;
cin>>n;
ull i=1,cnt=0;
while(1)
{ //cout<<n<<' '<<f[i]<<endl;
if(n<f[i]) break;
n-=f[i];
cnt++;
i++;
}
cout<<cnt<<endl;
}
return 0;
}- H 题
这也是一道有关数学的题，要是知道这个定理的肯定知道要怎么做了，重要的是要知道高精度怎么写。
平面内有n条直线，其中没有两条互相平行，也没有三条交于一点，一共有n*(n-1)/2个交点
就是这样的定理。（这是我查百度的呢，因为我只知道公式是什么，不知道这怎么表述，哎）这题我是当长度大于10的时候，我才使用了高精度，如果每一个都是使用高精度的话，时间复杂度会很大的。所以在这个地方我进行了判断。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int a[N],b[N],c[N],res[N];
string s;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
cin>>s;
int len=s.length();
if(len<=10)
{
long double a=0,b;
int x=0;
for(int i=len-1;i>=0;i--)
a+=pow(10,x)*(s[i]-'0'),x++;
printf("%.0Lf\n",a*(a-1)/2);
}
else
{
memset(c,0,sizeof c);
memset(res,0,sizeof res);
int ma=0,mb=0;
for(int i=len-1;i>=0;i--)
a[ma++]=s[i]-'0',b[mb++]=s[i]-'0';
int up=-1;//b减去1
for(int i=0;i<mb;i++)
{
b[i]=b[i]+up;
if(b[i]<0)
{
b[i+1]-=1;
b[i]+=10;
}
up=0;
}
if(b[mb-1]==0) mb--;
up=0;//两数相乘
for(int i=0;i<ma;i++)
{
up=0;
for(int j=0;j<mb;j++)
{
c[i+j]+=a[i]*b[j]+up;
up=c[i+j]/10;
c[i+j]%=10;
}
c[mb+i]=up;
}
int lenc=max(ma,mb)*2-1;
while(c[lenc]==0&&lenc>0)
lenc--;
up=0;//除法
for(int i=lenc;i>=0;i--)
{
res[i]=(up*10+c[i])/2;
up=(up*10+c[i])%2;
}
int lenres=lenc;
while(res[lenres]==0&&lenres>0)
lenres--;
for(int i=lenres;i>=0;i--)
printf("%d",res[i]);printf("\n");
}
s.clear();
}
return 0;
}- J 题
这题我是暴力的，没有想到竟然过了。我的字符串的下标的是从0开始的，因此我从1开始寻找一个和s[0]相同的字符，如果出现的话就从这个字符开始找后面有没有与s[1]相同的，如果有就计数，如果没有就退出寻找的循环。回到刚刚找到s[0]的地方继续向后查找一个与s[0]相同的字符，如果有则重复着刚刚的操作。就一直这样的找出一个最长的。
代码：
#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=100+1;
ull f[N];
string s,temp;
int main()
{
IO;
int t;
cin>>t;
while(t--)
{
cin>>s;
temp=s;
int len=s.length(),res=0;
for(int i=1;i<len;i++)
{
if(temp[i]==s[0])
{
int cnt=0;
for(int j=i,k=0;j<len;j++,k++)
{
if(temp[j]!=s[k]) break;
cnt++;
}
res=max(res,cnt);
}
}
cout<<res<<endl;
}
return 0;
}
上海得物信息集团有限公司公司福利 716人发布
投递美团等公司7个岗位
查看13道真题和解析