我是靠谱客的博主 乐观饼干,这篇文章主要介绍2013年ICPC中国大陆区域赛真题,现在分享给大家,希望可以做个参考。

Golden Radio Base 黄金分割进制

题目读了好长时间,大体是要把十进制数字转化成黄金分割进制,当然肯定每个十进制数字的黄金分割进制数字都是唯一的

当时一直没懂large {color{Red} }varphi + 1 = varphi ^{2}  和 large 2 varphi ^{2} = varphi ^{3} + 1是什么意思后来终于才明白

可以推出 large varphi ^{i} = varphi ^{i- 1} + varphi ^{i - 2}  还有 large 2 varphi ^{i} = varphi ^{i+1} + varphi ^{i-2}

以此为根据,暴力把>1的位数上的数字拆开再把相邻的1进位直到没有相邻的且每一位上的数字至多为1

其实数组开100就可以,整数部分对1是斐波那契式的增长,所以最多50位就会超过10^9

复制代码
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
#include<bits/stdc++.h> using namespace std; int ans[210],n; bool f; int main() { while(~scanf("%d",&n)) { memset(ans,0,sizeof(ans)); ans[100] = n; f = 1; while(f) { f = 0; for(int i = 2;i <= 200; ++i) if(ans[i] > 1) { ans[i + 1] += ans[i] / 2; ans[i - 2] += ans[i] / 2; ans[i] %= 2; f = 1; } for(int i = 1;i <= 200; ++i) if(ans[i] && ans[i + 1]) { int x = min(ans[i],ans[i + 1]); ans[i] -= x; ans[i + 1] -= x; ans[i + 2] += x; } } int l,r; for(int i = 200;i >= 1; --i) if(ans[i]) { l = i; break; } for(int i = 1;i <= 200; ++i) if(ans[i]) { r = i; break; } for(int i = l;i >= r; --i) { if(i == 99) printf("."); printf("%d",ans[i]); } printf("n"); } return 0; }

 

Little Tiger vs. Deep Monkey 背包+思维

题目:老虎和猴子比赛,有n道题目,猴子做对每道题的概率都是随机的,作对得分不然不得分,给出n个题目各自的得分,问狮子最少要多少分才能有p的概率不输给猴子

解:因为猴子是否做题目是随机的,可以计算出猴子得到某个得分的概率,求一个最小的x使得猴子得分小于x的概率是>=p

复制代码
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
#include<bits/stdc++.h> using namespace std; int a[50],b[50],n,m,t; double dp[50][40050],p; int main() { scanf("%d",&t); while(t--) { scanf("%d%lf",&n,&p); b[0] = 0; for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); b[i] = b[i - 1] + a[i]; } memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 1;i <= n;i++) for(int j = 0;j <= b[i];j++) { dp[i][j] += dp[i - 1][j] * 0.5; dp[i][j + a[i]] += dp[i - 1][j] * 0.5; } double g = 0; for(int i = 0;i <= b[n];i++) { g += dp[n][i]; if(g >= p) { cout<<i<<'n'; break; } } } return 0; }

 

最后

以上就是乐观饼干最近收集整理的关于2013年ICPC中国大陆区域赛真题的全部内容,更多相关2013年ICPC中国大陆区域赛真题内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(99)

评论列表共有 0 条评论

立即
投稿
返回
顶部