集训队圣诞之战总结

清理电脑文件找到了圣诞时比赛的代码,就来写写。

比赛一共出了两道水题,第三道坑了好久,但总体来说还是可以的,第三道题虽然没有Ac,但是它确实对了,编译器差异。。

当时的题挂在学校OJ(http://219.218.128.149/JudgeOnline/)上了1628-1632。

Problem A:

一开始没考虑<0的情况,改了之后对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
long long l=0,k;
while(m--){
cin>>k;
l+=n-k;
}
cout<<(n-l>0?n-l:0)<<endl;
}
return 0;
}

Problem B:

简单几何。

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
double R,r;
while(cin>>r>>R)
printf("%.2lf %.2lf\n",(R-r)/r,(R+r)/r);
return 0;
}

Problem C:

排列组合,求概率。不是很难,但是杭电貌似不认%Lf,比赛时没出。。

学校OJ上改成%lf过了。

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
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
double n,m,x,y,p,p0;
double get_p(double i0){
double k=1.0,i=i0;
int l=i0;
k*=pow(p,i0);
if(i>n-i) i=n-i;
for(int j=n;l>0;--j,--l)
k*=j,k/=l;
k*=pow(1.0-p,n-i0);
return k;
}
int main(){
while(cin>>n>>m>>x>>y>>p){
p0=0.0;
for(int i=0;i<=n;++i){
if(i*x-(n-i)*y>m) p0+=get_p((double)i);
}
printf("%.2lf\n",p0);
}
return 0;
}

Problem D:

也是排列组合,求全排列。比赛时没去做,但那一阵子正好在看紫书第十章,于是后来就把这道题做了做。

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
#include<iostream>
#include<vector>
using namespace std;
const int mod=1000000007;
const int maxn=1010;
vector<int> num;
long long modn[maxn]={1};
int search(int k){
int top=(int)num.size()-1,bott=0,mid=0;
while(top>=bott){
mid=bott+(top-bott)/2;
if(k==num[mid]) return mid;
if(k>num[mid]) bott=mid+1;
else top=mid-1;
}
return mid;
}
int main(){
for(int i=1;i<maxn;i++)
modn[i]=modn[i-1]*i%mod;
int n,k;
while(cin>>n){
long long sum=1;
for(int i=1;i<=n;i++)
num.push_back(i);
for(int i=1;i<=n;i++){
cin>>k;
int p=search(k);
sum+=modn[n-i]*p%mod;
sum%=mod;
num.erase(num.begin()+p);
}
cout<<sum<<endl;
}
return 0;
}

Problem E:

当时写了超时,至今没有再去做。不过比赛结束后学长提示过用vector存路径之后暴搜。。

本文迁移自我的 CSDN博客 ,格式可能有所偏差。