Top

2019 Wannafly Camp day2


自闭感受

今天上午吉老师吉老师给我们讲了一通数论知识,可以说是醍醐灌顶吧,半懂半懵(简单的懂了,难的n^n脸懵逼),真的是菜的教不来啊 不过吉老师不亏是WF金牌爷,属实强大啊。下午数论自闭专场(好像大部分数论题都没几个做出来的 ),自闭场了就写出2道题AH,有点难受,K题队友T了,B吃饭时候想出了正确的贪心策略。

开始我先开的A题,队友lyy和hxx开了K题,同时写崩,A题写半天发现怼的是div1的B题,K题lyy先T。后来A题瞎几把想了个假的贪心,贪最大值,果断wa了3发,发现是个假策略并算了算复杂度发现直接n方暴力。然后hxx的k也T了,对拍了波两人代码,发现没错误,那就凉了假算法。此时lyy便切到了B题,我开了H题,发现是个求球交体积的题目,取横截面积进行微积分(我有板子自己裸板子过的),在这题还闹了个乌龙,样例完全正确后,我交了H并和队友说了句过了,队友说小心WA,秒回了“样例过了就是过了”,结果CE​ ​ ,有个结构体函数忘了函数类型,改改就A了。H过后便和lyy开始怼B题,因为K题实在不会了,目测是状压DP不会写。B题HACK了好几个YY出来的的假贪心策略之后,就直接去吃饭了,吃饭时候想到了贪长度,可惜已经GG了。

今天虽然是数论专场,但是感觉打脸最多的就是自己的假贪心策略,以后想出的策略觉得要证明正确性再写,一定不要莽

上题解(后期补题会更新其他能力范围内的题解)

A-Erase Numbers II

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
#include<stdio.h>
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn = 6e3 + 10;
ull a[maxn];
void slove(ull &a, ull b){
while(b){
a *= 10;
b /= 10;
}
}

int main(){
int t, t1 = 1;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
cin >> a[i];
ull ans = 0, temp;
for(int i = 0; i < n - 1; ++i){
for(int j = i + 1; j < n; ++j){
temp = a[i];
slove(temp, a[j]);
ans = max(ans, temp + a[j]);
}
}
cout << "Case #" << t1++ << ": " << ans << endl;
}
return 0;
}

H-Cosmic Cleaner

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;
const double PI = acos(-1.0);
typedef long long ll;
const int maxn=120;
struct point {
double x,y,z;
point() {}
void Init(double a, double b,double c){
x = a;
y = b;
z = c;
}
point(double a, double b,double c){
x = a;
y = b;
z = c;
}
point operator -(const point &b)const { //返回减去后的新点
return point(x - b.x, y - b.y,z-b.z);
}
point operator +(const point &b)const { //返回加上后的新点
return point(x + b.x, y + b.y,z+b.z);
}
//数乘计算
point operator *(const double &k)const { //返回相乘后的新点
return point(x * k, y * k,z*k);
}
point operator /(const double &k)const { //返回相除后的新点
return point(x / k, y / k,z/k);
}
double operator *(const point &b)const { //点乘
return x*b.x + y*b.y+z*b.z;
}
};
double dist(point p1, point p2) { //返回平面上两点距离
return sqrt((p1 - p2)*(p1 - p2));
}
struct sphere {//球
double r;
point centre;
};
void SphereInterVS(sphere a, sphere b,double &v) {
double d = dist(a.centre, b.centre);//球心距
if(d>=a.r+b.r)return;
if(a.r-d>=b.r){
v+=PI*4.0/3.0*b.r*b.r*b.r;
return;
}
if(a.r<=b.r-d){
v+=PI*4.0/3.0*a.r*a.r*a.r;
return;
}
double t = (d*d + a.r*a.r - b.r*b.r) / (2.0 * d);//
double h = sqrt((a.r*a.r) - (t*t)) * 2;//h1=h2,球冠的高
double angle_a = 2 * acos((a.r*a.r + d*d - b.r*b.r) / (2.0 * a.r*d)); //余弦公式计算r1对应圆心角,弧度
double angle_b = 2 * acos((b.r*b.r + d*d - a.r*a.r) / (2.0 * b.r*d)); //余弦公式计算r2对应圆心角,弧度
double l1 = ((a.r*a.r - b.r*b.r) / d + d) / 2;
double l2 = d - l1;
double x1 = a.r - l1, x2 = b.r - l2;//分别为两个球缺的高度
double v1 = PI*x1*x1*(a.r - x1 / 3);//相交部分r1圆所对应的球缺部分体积
double v2 = PI*x2*x2*(b.r - x2 / 3);//相交部分r2圆所对应的球缺部分体积
v += v1 + v2;//相交部分体积
}
struct Node{
double x,y,z,r;
}a[maxn];
double x,y,z,r;
int n;
double Solve(){
double v=0;
sphere A,B;
A.r=r;
A.centre.Init(x,y,z);
for(int i=0;i<n;i++){
B.r=a[i].r;
B.centre.Init(a[i].x,a[i].y,a[i].z);
SphereInterVS(A,B,v);
}
return v;
}
int main(){
int t,tt=1;
/*sphere A,B;
A.r=1;
A.centre.Init(0,0,0);
B.r=1;
B.centre.Init(0,0,0);
double v=0;
SphereInterVS(A,B,v);
printf("%lf",v);*/
scanf("%d",&t);
while(tt<=t){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
}
scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
printf("Case #%d: %.10lf\n",tt++,Solve());
}
return 0;
}