20200115 VJ训练赛

FylSeA

愉快的Virtual Judge假期训练赛第一场题解报告

重新复盘一下QAQ

A. Mezo Playing Zoma

题目描述

给你一串字符串只包含L和R,从0位置开始可以向左向右走也可以不走,问你最多能到达多少个位置。

题目解读

如果给字符串是“L L L”,那么可以选择每一步走或者不走就是-3 -2 -1 0 共4种

如果给字符串是“R R R”,同理 0 1 2 3 共4种

如果给字符串是“R L R”,有-1 0 1 2 共4种

…所以这道题也就是判断LR的数量单独加和最后+1

B. Just Eat It!

题目描述

给你一个数组,数组和为A,一串连续最大字串和为B,问A>=B即输出YES,否则输出NO

题目解读

问题就是求解 数组内连续子段最大和 是多少

首先看看情况都会有哪几种:

第一种:1 2 3 4 5,连续子段最大和为2+3+4+5

第二种:1 2 3 4 -1,连续子段最大和为1+2+3+4

第三种:1 2 3 -1 5,连续子段最大和为2+3+(-1)+5

第四种:1 1 -2 3 4,连续最大子段和为3+4

可以看出,如果要寻找[1,n-1]和[2,n]范围内的最大子段和,需要判断x位置之前的和是否小于0,如果小于0那么就要从x+1位置重新开始,两个范围都跑一遍就好了。

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
long long max(long long a,long long b){
if(a<b)return b;
return a;
}
int main(){
int t,n,a[100005];
cin>>t;
while(t--){
cin>>n;
long long k=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
k+=a[i];
}
long long x=0,maxx=-1;
for(int i=1;i<=n-1;i++){
x+=a[i];
if(x<0) x=0;
maxx=max(maxx,x);
}
x=0;
for(int i=2;i<=n;i++){
x+=a[i];
if(x<0) x=0;
maxx=max(maxx,x);
}
if(maxx<k) printf("YES\n");
else printf("NO\n");
}
return 0;
}

C.Fadi and LCM

题目描述:求一组数的最小公倍数是X,且这一组数的最大值最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
long long gcd(long long a,long long b){
if(b==0)return a;
return gcd(b,a%b);
}
int main(){
long long x;
cin>>x;
for(long long i=sqrt(x);i>=1;i--){
if(x/i*i==x&&gcd(i,x/i)==1){
cout<<i<<" "<<x/i<<endl;
break;
}
}
return 0;
}

Dr. Evil Underscores

异或问题一般都是字典树

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
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int x;
int slove(vector<int> a,int k)
{
if(a.size()==0||k<0) return 0; //当没有位数了
vector<int> p1,p2;
for(int i=0;i<a.size();i++)
{
if((a[i]>>k)&1) p1.push_back(a[i]); //每个数的每位。是1的存在p1,是0的存在p2
else p2.push_back(a[i]);
}
if(p1.size()==0) return slove(p2,k-1);
if(p2.size()==0) return slove(p1,k-1);
return (1<<k)+min(slove(p1,k-1),slove(p2,k-1)); //当前的贡献值+左右子树的最小贡献值。
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a.push_back(x);
}
cout<<slove(a,30)<<endl;
}

E. Deadline

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
#include<cstdio>
#include<iostream>

using namespace std;
int f(int x,int y){
if((x/y)*y<x){
return x/y+1;
}else{
return x/y;
}
}
int main()
{
int t;
cin>>t;
while(t--){
int n,d;
cin>>n>>d;
bool k=false;
for(int i=0;i*i<=d;i++){
if((i+f(d,i+1))<=n){
k=true;
}
}
if(k)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}

F. Yet Another Meme Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long a,b;
cin>>a>>b;
long long x=9,num=0;
while(x<=b){
x=x*10+9;
num++;
}
long long ans=num*a;
cout<<ans<<endl;
}
return 0;
}

G. HQ9+

就注意“+”是无用信息就可以了

H. Rolling The Polygon

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
struct node{//point
int x;
int y;
double z;
double l;
}a[55];

double find(node p,node q){
return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

int main(){
int t;
cin>>t;
int k=t;
node q;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
cin>>q.x>>q.y;
double aa,bb,cc;
for(int i=1;i<=n;i++){
a[i].l=find(a[i],q);
if(i==1){
bb=find(a[1],a[2]);
aa=find(a[2],a[n]);
cc=find(a[n],a[1]);
a[1].z=acos((bb*bb+cc*cc-aa*aa)/(2*bb*cc));
}else if(i==n){
bb=find(a[n],a[1]);
aa=find(a[1],a[n-1]);
cc=find(a[n],a[n-1]);
a[n].z=acos((bb*bb+cc*cc-aa*aa)/(2*bb*cc));
}else{
bb=find(a[i],a[i+1]);
aa=find(a[i+1],a[i-1]);
cc=find(a[i],a[i-1]);
a[i].z=acos((bb*bb+cc*cc-aa*aa)/(2*bb*cc));
}


a[i].z=3.1415926535-a[i].z;



}
double ans=0.0;
for(int i=1;i<=n;i++){
ans+=a[i].z*a[i].l;
}
printf("Case #%d: %.3f\n",k-t,ans);

}
}