题意
给定一个期望达到的胜率a/b，n次比赛，每次的输赢有当前的胜率和期望达到的胜率决定。
问n次比赛后能赢多少次。
思考
显然答案是[a*n/b]和[a*n/b]+1中的一个，具体是哪一个。通过打表（或者分析前一步的情况）可以得到，为1 +(n - 1) * a / bz
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
| #include<bits/stdc++.h>
using namespace std;
long long t,n,a,b;
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&a,&b);
double t = 1.0*a/b;
t *= n;
long long tpp = t;
if(n!=1){
double flg = 1.0*tpp/(n-1);
if(flg<=1.0*a/b){
printf("%lld\n",tpp+1);
}else{
printf("%lld\n",tpp);
}
} else{
printf("1\n");
}
}
return 0;
}
|
总结
打表是个好东西
题意
给定一个整数k，要求构造数列满足：把该数列分为一个单调不降子序列和另一个单调不升子序列的方式一共有k种。
注意空集也是一个子序列。
思考
k为0或1的情况特判
对于其余情况：
方法一
只用1和2构造
最前面 a 个1 可以一起贡献 $2^a$ 种分法，后面每切换一次数字，对于该数字，每新增第 x 位就能贡献$2^{x-1}$种方法。
比如 k = 30时，构造结果为1 1 1 1 2 2 2 1 1 1（16+1+2+4+1+2+4）
这是属于试着试着就搞出来的方法。
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
| #include <iostream>
#include <vector>
using namespace std;
long long n;
long long mi[50];
int main()
{
cin>>n;
mi[0]=1;
for(int i=1;i<=32;i++){
mi[i]=mi[i-1]*2;
}
if(n==0){
cout<<"9"<<endl;
cout<<"7 8 9 4 5 6 1 2 3"<<endl;
}else if(n==1){
cout<<"6"<<endl;
cout<<"1 1 4 5 1 4"<<endl;
}else{
vector<int> ans;
int idx=0;
int i;
for(i=1;;i++){
if(n<mi[i]){
idx++;
break;
}
ans.push_back(idx%2+1);
}
n-=mi[i-1];
if(n!=0){
while(n){
for(i=0;;i++){
if(n<mi[i]){
idx++;
break;
}
n-=mi[i];
ans.push_back(idx%2+1);
}
}
}
cout<<ans.size()<<endl;
for(int x:ans){
cout<<x<<" ";
}
}
return 0;
}
|
方法二
这个方法就更加自然了，构造的序列是单调不减的（比如说1 1 1 2 2 2 3 3 ）。这样不管那个子序列都是单调不减的了。
每相同的数组成一块，另外一个单调不升的序列一定只能在同一块中取，对于一个长度为n的块，一共有$2^{n-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
| #include <iostream>
#include <vector>
using namespace std;
long long n;
long long mi[50];
int main()
{
cin>>n;
mi[0]=1;
for(int i=1;i<=32;i++){
mi[i]=mi[i-1]*2;
}
if(n==0){
cout<<"9"<<endl;
cout<<"7 8 9 4 5 6 1 2 3"<<endl;
}else if(n==1){
cout<<"6"<<endl;
cout<<"1 1 4 5 1 4"<<endl;
}else{
vector<int> ans;
int idx=1;
n--;
while(n){
int i;
ans.push_back(idx);
for(i=2;n+1>=mi[i];i++){
ans.push_back(idx);
}
n-=(mi[i-1]-1);
idx++;
}
cout<<ans.size()<<endl;
for(int x:ans){
cout<<x<<" ";
}
}
return 0;
}
|
总结
要么硬着头皮试（方法一），要么找性质（方法二）。
题意
给定一棵树，每个点有点权，在树上找到一条路径，使得这条路径上的点的点权组成的一个式子最大。
经过数学计算化简，这个式子就是这些点的平均值。
思考
路径的长度一定是2或3！
若不然，将这个路径拆分成两条路径，一定有一条是大于等于当前的平均值的
那么直接暴力寻找2或3的路径就行了。
(然而暴力找路径细节很多，并不简单)
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
| #include<bits/stdc++.h>
using namespace std;
vector<int> mp[100010];
double v[100010];
int n;
bool st[100010];
double gettwo(){
queue<int> qu;
qu.push(1);
double res=0;
st[1]=true;
while(!qu.empty()){
int nw=qu.front();
qu.pop();
for(int nx:mp[nw]){
if(st[nx]) continue;
res=max(res,abs(v[nw]+v[nx])/2);
st[nx]=true;
qu.push(nx);
for(int nxx:mp[nx]){
if(st[nxx]==true) continue;
res=max(res,abs(v[nw]+v[nx]+v[nxx])/3);
}
}
double max1=0,max2=0,min1=0,min2=0;
for(int nx:mp[nw]){
if(v[nx]>max1){
max2=max1;
max1=v[nx];
}else if(v[nx]>max2){
max2=v[nx];
}
if(v[nx]<min1){
min2=min1;
min1=v[nx];
}else if(v[nx]<min2){
min2=v[nx];
}
}
if(max2!=0) res=max(res,abs(v[nw]+max1+max2)/3);
if(min2!=0) res=max(res,abs(v[nw]+min1+min2)/3);
}
return res;
}
int main(){
double avg=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&v[i]);
}
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
mp[a].push_back(b);
mp[b].push_back(a);
}
avg= gettwo();
printf("%0.6lf",(avg*avg)/4);
return 0;
}
|
总结
其实枚举两个点的情况在读入的时候就可以进行了。
枚举三个点也不用bfs，for循环遍历一遍所有点，找到最大次大、最小次小的相邻点就行了。
题意
n个球，每个球都有一个被选中的概率。选中过后把这个球移到前面。代价是前面球的个数。
求无限次操作后，进行一步操作的代价期望。
思考
最后的答案是枚举每个球，选中这个球的概率乘以有多少个球在它前面的概率，对每个球求和就可以了。
有多少个球在它前面的概率，可以分开算，用到了概率期望的线性性质。
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;
int n;
double ch[110];
double ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ch[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
ans+=ch[i]*ch[j]/(ch[i]+ch[j]);
}
}
printf("%0.7lf",ans);
}
|
总结
有一说一这个银牌题好像也没这么难，和数据结构和算法没啥关系了，主要是概率论的一些东西。
