Golden Radio Base 黄金分割进制
题目读了好长时间,大体是要把十进制数字转化成黄金分割进制,当然肯定每个十进制数字的黄金分割进制数字都是唯一的
当时一直没懂 和
是什么意思后来终于才明白
可以推出 还有
以此为根据,暴力把>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中国大陆区域赛真题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复