Codeforces Round #280 (Div. 二) 解题报告 A.B.C.D.E
Codeforces Round #280 (Div. 2) 解题报告 A.B.C.D.E.
B - Vanya and *s
C - Vanya and Exams
D - Vanya and Computer Game
E - Vanya and Field
不知道到底是我的水平提高了还是CF的题目变水了。。。。。。
A - Vanya and Cubes
水题。。暴力枚举就可以。。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int s[100], sum[100];
int main()
{
int n, i;
s[1]=1;
sum[i]=1;
scanf("%d",&n);
for(i=2;i<=10000;i++){
s[i]=s[i-1]+i;
sum[i]=sum[i-1]+s[i];
if(sum[i]>=n)break;
}
printf("%d\n",i-1);
return 0;
}
B - Vanya and *s
水题。。暴力找两个相邻之间的最短距离/2，然后再与边界的比较找最长距离。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int a[2000];
int main()
{
int n, l, i, j;
double d, max1=-1;
scanf("%d%d",&n,&l);
a[0]=0;
a[n+1]=l;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n+2);
for(i=2;i<=n;i++){
max1=max(max1,(a[i]-a[i-1])/2.0);
}
max1=max(max1,a[1]-0.0);
max1=max(max1,l*1.0-a[n]);
printf("%.10lf\n",max1);
return 0;
}
C - Vanya and Exams
贪心。
从所需论文少的开始累加。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
struct node
{
LL f, e;
}fei[110000];
int cmp(node x, node y)
{
return x.e<y.e;
}
int main()
{
int i;
LL n, r, ave, s, sum, ss, ans=0;
scanf("%I64d%I64d%I64d",&n,&r,&ave);
sum=n*ave;
s=0;
for(i=0;i<n;i++){
scanf("%I64d%I64d",&fei[i].f,&fei[i].e);
s+=fei[i].f;
}
ss=sum-s;
if(ss<=0)
{
printf("0\n");
return 0;
}
sort(fei,fei+n,cmp);
//printf("%d\n",ss);
for(i=0;i<n;i++){
if(fei[i].f>=r) continue ;
if(ss-(r-fei[i].f)<=0){
ans+=ss*fei[i].e;
break;
}
else{
ss-=r-fei[i].f;
ans+=fei[i].e*(r-fei[i].f);
}
//printf("%d\n",ss);
}
printf("%I64d\n",ans);
return 0;
}
D - Vanya and Computer Game
比赛的时候想到了二分时间，找到时间后怎么判断是谁的一直没想出来。。第二天才恍然大悟。。只要判断是否整除就可以了。。。。当时为啥没想到呢。。。郁闷。。
先放大时间轴，1/x和1/y秒放大到y和x，然后二分时间，找到时间后，判断是否整除即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int main()
{
LL n, x, y, i, z, low, high, mid, ans;
scanf("%I64d%I64d%I64d",&n, &x, &y);
while(n--) {
scanf("%I64d",&z);
low=1;
high=1e16;
while(low<=high) {
mid=low+high>>1;
if(mid/x+mid/y>=z) {
high=mid-1;
ans=mid;
}
else low=mid+1;
}
if(ans%x==0&&ans%y==0) puts("Both");
else if(ans%x==0) puts("Vova");
else puts("Vanya");
}
return 0;
}
E - Vanya and Field
感觉这次的E题好水。。。首先因为gcd为1，所以可以保证n个数都可以访问到而且不会重复。所以可以默认让他从横坐标为0的某点出发的。然后当纵坐标为0时，可以找到x坐标与y坐标的一个映射关系，保存下来。然后每输入一个坐标，就可以用公式来判断出是从哪个点出发的。然后找到最多的那个出发点就可以了。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int _hash[1100000], a[1100000];
int main()
{
int n, m, dx, dy, i, j, x, y, pos, max1;
scanf("%d%d%d%d",&n,&m,&dx,&dy);
x=y=0;
for(i=0;i<n;i++){
a[x]=y;
x=(x+dx)%n;
y=(y+dy)%n;
}
memset(_hash,0,sizeof(_hash));
while(m--){
scanf("%d%d",&x,&y);
_hash[(y+n-a[x])%n]++;
}
max1=-1;
for(i=0;i<n;i++){
if(max1<_hash[i]){
max1=_hash[i];
pos=i;
}
}
printf("0 %d\n",pos);
return 0;
}