2018CCPC吉林站部分题解

前几天在刷知乎的时候看到吉老师对这套题赞誉有加,因此特来做做试试。水平有限,能力一般。

A.The Fool

题目大意为:求$\sum_{i=1}^{n}{\frac{n}{i}}$ 的值。$(n\leq 1e9)$

这道题还算简单,直接按照$\frac{n}{i}$的值分块计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll t,n;
scanf("%lld",&t);
for(ll q=1;q<=t;q++){
scanf("%lld",&n);
ll sum=0;
for(ll i=1;i<=n;){
sum+=(n/i)*(n/(n/i)-i+1);
i=n/(n/i)+1;
}
printf("Case %lld: ",q);
if(sum&1) printf("odd\n");
else printf("even\n");
}
return 0;
}

B.The World

题目大意为:给你一个地区的时间,让你求另一个地区的时间。

不算很难的题目,直接模拟计算即可。细节比较多,需要多处理处理。

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

char s[10][100];
int a[30];

int main(){
int t;scanf("%d",&t);
int cas=0;
a['L'-'A']=0;
a['M'-'A']=3;
a['W'-'A']=-5;
a['B'-'A']=8;
while(t--){
for(int i=0;i<4;i++){
scanf("%s",s[i]);
}
printf("Case %d: ",++cas);
int hour=0,minu=0;
int flag=1;
for(int j=0;s[0][j];j++){
if(s[0][j]==':'){flag=0;continue;}
if(flag){
hour=hour*10+s[0][j]-'0';
}
else {
minu=minu*10+s[0][j]-'0';
}
}
int x=a[s[3][0]-'A']-a[s[2][0]-'A'];
int tmp=hour;
if(tmp==12)tmp=0;
hour=(hour+x+12)%12;
if(hour==0)hour=12;
if(x==0){
printf("Today %s %s\n",s[0],s[1]);
}
else if(x>0){
if(tmp+x<12){
printf("Today %d:%02d %s\n",hour,minu,s[1]);
}
else{
if(s[1][0]=='A'){
if(tmp+x<24)printf("Today %d:%02d PM\n",hour,minu);
else printf("Tomorrow %d:%02d AM\n",hour,minu);
}
else{
if(tmp+x==24)printf("Tomorrow %d:%02d PM\n",hour,minu);
else printf("Tomorrow %d:%02d AM\n",hour,minu);
}
}
}
else{
if(tmp+x>=0){
printf("Today %d:%02d %s\n",hour,minu,s[1]);
}
else{
if(s[1][0]=='A'){
if(tmp+x>=-12)printf("Yesterday %d:%02d PM\n",hour,minu);
else printf("Yesterday %d:%02d AM\n",hour,minu);
}
else{
if(tmp+12+x>=0)printf("Today %d:%02d AM\n",hour,minu);
else{
printf("Yesterday %d:%02d PM\n",hour,minu);
}
}
}
}
}
return 0;
}

C.Justice

题目大意为,给你一堆数字,每个数字代表一个值$\frac{1}{2^x}$,问能否将其分成两堆,使得每堆值之和大于等于$\frac{1}{2}$ 。

一个稍微复杂一点的题目,首先我们需要判断所有数的和是否超过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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
struct node{
int x,pos;
}a[maxn];
int res[maxn];
int T,n,u;
bool cmp(node i,node j){return i.x<j.x;}
bool check(){
int x,y;
priority_queue<int>que;
for(int i=1;i<=n;i++) que.push(a[i].x);
while(!que.empty()){
if(que.top()==0) return true;

x=que.top();que.pop();
if(!que.empty()){
y=que.top();
que.pop();
}
else return false;

if(x==y) que.push(x-1);
else que.push(y);
}
return false;
}
void solve(){
sort(a+1,a+n+1,cmp);
if(!check()) printf("NO\n");
else{
printf("YES\n");
ll sum=0;
for(int i=1;i<=n;i++){
if(a[i].x-a[i-1].x>17 || abs(sum)>=1e6) break;
if(sum>0) sum=min(1e9,sum*pow(2,a[i].x-a[i-1].x));
else sum=max(-1e9,sum*pow(2,a[i].x-a[i-1].x));
if(sum<=0){
sum+=1;
res[a[i].pos]=1;
}
else sum-=1;
}
for(int i=1;i<=n;i++) printf("%d",res[i]);
printf("\n");
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].x);
a[i].pos=i;
res[i]=0;
}
printf("Case %d: ",t);
solve();
}
return 0;
}

D.The Moon

题目大意为:你在玩一个游戏,获胜的概率为p%,然后给你游戏的操作:

step0: 初始中奖率为q=2%;
step1: 玩家以p%的获胜率玩一局游戏;
step2: 玩家获胜转到step3,否则转到step4;
step3: 玩家抽奖,如果没中奖,获奖率提高2%,上限100%,转到step1;
step4: 获奖概率提高1.5%,转到step1;

问抽中奖时玩的游戏的局数的期望。

这个题是个比较简单的概率dp,$dp[i]$表示在获胜概率为$i\%$时的期望局数,由于1.5%不是一个整数,所以将所有的值扩大二倍,初始$dp[200]=\frac{1}{p}$然后就可以写出转移方程:
$$
dp[i]=p*(1-\frac{1}{i})*dp[min(i+4,200)]+(1-p)*dp[min(i+3,200)]+1;
$$
其中前一部分表示获胜没抽中奖的期望,后一部分表示没获胜的期望,最后需要+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
double dp[300];
int main()
{
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
double p;
scanf("%lf",&p);
p/=100;
dp[200]=1/p;
for(int i=199;i>=4;i--){
dp[i]=p*(1.0-i/200.0)*dp[min(200,i+4)]+(1.0-p)*dp[min(200,i+3)]+1;
}
printf("Case %d: %.10lf\n",t,dp[4]);
}
return 0;
}

E.The Tower

题目大意为:已知底面半径为$r$,高为$h$的圆锥,给你一个点$(x_0,y_0,z_0)$,它的速度为$(v_x,v_y,v_z)$ ,问这个点与圆锥相交的最短时间为多少。

几何题,首先知道圆锥的方程为$x^2+y^2=r^2\frac{(h-z)^2}{h^2}$ ,然后假设点与圆锥相交的点为$(x_0+v_xt,y_0+v_yt,z_0+v_zt)$,然后带入方程求解即可:
$$
x^2+y^2=r^2\frac{(h-z)^2}{h^2} \\
(x_0+v_xt)^2+(y_0+v_yt)^2=r^2\frac{(h-z_0-v_zt)^2}{h^2} \\
x_0^2+2x_0v_xt+v_x^2t^2+y_0^2+2y_0v_yt+v_y^2t^2=r^2\frac{h^2+z_0^2+v_z^2t^2-2hz_0-2hv_zt+2z_0v_zt}{h^2} \\
h^2x_0^2+2h^2x_0v_xt+h^2v_x^2t^2+h^2y_0^2+2h^2y_0v_yt+h^2v_y^2t^2=r^2h^2+r^2z_0^2+r^2v_z^2t^2-2r^2hz_0-2r^2hv_zt+2r^2z_0v_zt \\
(h^2v_x^2+h^2v_y^2-r^2v_z^2)t^2+(2h^2x_0v_x+2h^2y_0v_y+2r^2hv_z-2r^2z_0v_z)t+(h^2x_0^2+h^2y_0^2-r^2h^2-r^2z_0^2+2r^2hz_0)=0
$$
解完以后就可以按照一元二次方程组的方式进行求解。

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;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
double dp[300];
int main()
{
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
double r,h,x0,y0,z0,vx,vy,vz;
scanf("%lf %lf",&r,&h);
scanf("%lf %lf %lf",&x0,&y0,&z0);
scanf("%lf %lf %lf",&vx,&vy,&vz);
double a=h*h*vx*vx+h*h*vy*vy-r*r*vz*vz;
double b=2*h*h*x0*vx+2*h*h*y0*vy+2*r*r*h*vz-2*r*r*z0*vz;
double c=h*h*x0*x0+h*h*y0*y0-r*r*h*h-r*r*z0*z0+2*r*r*h*z0;
double t1=(-b+sqrt(b*b-4*a*c))/(2.0*a);
double t2=(-b-sqrt(b*b-4*a*c))/(2.0*a);
printf("Case %d: ",t);
if(t2>0) printf("%.10lf\n",t2);
else printf("%.10lf\n",t1);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------