Codeforces Round #618 (Div. 2)全题解(A-E)

Codeforces Round #618 (Div. 2)全题解(A-E)

比赛题目地址:https://codeforces.com/contest/1300

# Name
A Non-zero standard input/output1 s, 256 MB Submit Add to favourites img x10972
B Assigning to Classes standard input/output2 s, 256 MB Submit Add to favourites img x9480
C Anu Has a Function standard input/output1 s, 256 MB Submit Add to favourites img x4802
D Aerodynamic standard input/output1 s, 256 MB Submit Add to favourites img x2146
E Water Balance standard input/output3 s, 256 MB Submit Add to favourites img x839

A.Non-zero

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=100000+7;
int a[106];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
int ans=0;
if(sum>0)
{
for(int i=1;i<=n;i++)
{
if(a[i]==0) ans++;
}
printf("%d\n",ans);
}
else if(sum<=0)
{
int k=-1*sum;
for(int i=1;i<=n;i++)
{
if(a[i]==0) ans++;
}
if(ans==k)
{
printf("%d\n",ans+1);
}
else printf("%d\n",ans);
}
}

return 0;
}

B.Assigning to Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=300000+7;
int a[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+2*n);
int minn=abs(a[n+1]-a[n]);
printf("%d\n",minn);
}
return 0;
}

C.Anu Has a Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=300000+7;
int a[maxn];
int main()
{
int n,c,t,flag=-1;;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=32;~i;i--)
{
t=-1;
c=0;
for(int j=0;j<n;j++)
{
if(a[j]&(1ll<<i))
{
t=j;
c++;
}
}
if(c==1)
{
flag=t;
break;
}
}
if(~flag) printf("%d ",a[flag]);
for(int i=0;i<n;i++)
{
if(flag==i) continue;
printf("%d ",a[i]);
}
return 0;
}

D.Aerodynamic

多画几个图形,不难发现只需要判断该图形是否为中心对称图形即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=100000+7;
int x[maxn],y[maxn];
int cnt=0;

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
if(n%2==1) {printf("NO\n");return 0;}
int j=n/2+1;
double ansx=(x[1]+x[j])/2.0;
double ansy=(y[1]+y[j])/2.0;
int flag=1;
for(int i=1;i<=n/2;i++)
{
double ansxx=(x[i]+x[j])/2.0;
double ansyy=(y[i]+y[j])/2.0;
if(ansxx!=ansx||ansy!=ansyy) flag=0;
j++;
}
if(flag==0) printf("NO\n");
else printf("YES\n");
return 0;
}

E.Water Balance

维护凸包的写法看了一个红名的方法,写起来很简洁,也很容易理解。

1vwjLF.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=1000000+7;

int n;
double a[maxn],s[maxn];
int top,q[maxn];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
s[i]=s[i-1]+a[i];
}
for (int i=n;i>=1;i--)
{
q[++top]=i;
while (top >= 2&&(s[q[top]]-s[i-1])/(q[top]-(i-1))>(s[q[top-1]]-s[q[top]])/(q[top-1]-q[top]))
{
top--;
}
}
q[top+1]=0;
for (int i=top; i>=1; i--)
{
double avg=(s[q[i]]-s[q[i+1]])/(q[i]-q[i+1]);
for (int j = q[i + 1] + 1; j <= q[i]; j++)
printf("%.10f\n",avg);
}
return 0;
}