2016 ACM/ICPC亚洲区青岛站现场赛(部分题解)-程序员宅基地

技术标签: 数据结构与算法  c/c++  

摘要

  本文主要列举并求解了2016 ACM/ICPC亚洲区青岛站现场赛的部分真题,着重介绍了各个题目的解题思路,结合详细的AC代码,意在熟悉青岛赛区的出题策略,以备战2018青岛站现场赛。


 

HDU 5984 Pocky

题意

  给出一根棒子(可以吃的)的长度x和切割过程中不能小于的长度d,每次随机的选取一个位置切开,吃掉左边的一半,对右边的棒子同样操作,直至剩余的长度不大于d时停止。现在给出x和d,问切割次数的数学期望是多少。

解题思路

  当看到第二个样例2 1时,结果是1.693147,联想到ln(2) = 0.693147,可猜测当x > d时,答案是ln(x/d) + 1。

详细解法:

  设长度为x、限制长度是d的棒切割次数的数学期望是f(x),首先当x < d时,f(x) = 0(直接结束,切割次数为0);当x >= d时,f(x) 应该是任选一点后,右边部分切割次数的数学期望加上1。设t是切割的位置,即,其中后面的式子表示切割点t的数学期望(积分0到x,取到这一点的概率乘上t的概率密度,也就是长度为t的切割次数的数学期望),进而又可以写成(积分中,系数可以自由进出),也即将f(x)写成如下形式

   由此可得f(x) = ln(x) + c,当x = d时,f(d) = ln(d) + c = 1得,c = 1 - ln(d),代入f(x) = ln(x) - ln(d) + 1,也即f(x) = ln(x/d) + 1;

综上所述

代码如下:

  其中涉及C语言中对数的表示方法,C中只定义两log(double x)和log10(double x),分别表示数学中的ln和lg,至于如何表示loga(b)呢?使用换底公式log(b)/log(a)即可。

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 int main()
 5 {
 6     double x, d;
 7     int T;
 8     scanf("%d", &T);
 9     while(T--) {
10         scanf("%lf%lf", &x, &d);
11         if(x <= d) 
12             printf("0.000000\n");
13         else
14             printf("%.6lf\n", log(x) - log(d) + 1);
15     }
16     return 0;
17 }

 HDU 5983 Pocket Cube

题意

  输入一个二阶魔方的状态,问能否一步将其复原。

解题思路

  需要细心和耐心,考虑每一种拧法,操作的时候,先顺时针改变一个面的数,然后改变四周的数,写出操作模板。要特别注意输入状态的次序,哪个面先,以及哪个角先。

代码如下:

  1 #include <cstdio>
  2 
  3 struct Magic2{
  4     int f[5], b[5], u[5], d[5], l[5], r[5];
  5     void get_u() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &u[i]);}}
  6     void get_d() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &d[i]);}}
  7     void get_f() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &f[i]);}}
  8     void get_b() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &b[i]);}}
  9     void get_l() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &l[i]);}}
 10     void get_r() {
    for(int i = 1 ; i <= 4; i++) {scanf("%d", &r[i]);}}
 11     void L(int cnt) {
 12         for(; cnt > 0; cnt--) {
 13             int a[5];
 14             for(int i = 1; i <= 4; i++) a[i] = l[i];
 15             l[2] = a[1];l[1] = a[3];
 16             l[3] = a[4];l[4] = a[2];
 17 
 18             int x = b[3], y = b[1];
 19             b[3] = d[3], b[1] = d[1];
 20             d[3] = f[3], d[1] = f[1];
 21             f[3] = u[3], f[1] = u[1];
 22             u[3] = x, u[1] = y;
 23         }
 24     }
 25     void R(int cnt) {
 26         for(; cnt > 0; cnt--) {
 27             int a[5];
 28             for(int i = 1; i <= 4; i++) a[i] = r[i];
 29             r[1] = a[3], r[2] = a[1];
 30             r[3] = a[4], r[4] = a[2];
 31 
 32             int x = b[2], y = b[4];
 33             b[2] = u[2], b[4] = u[4];
 34             u[2] = f[2], u[4] = f[4];
 35             f[2] = d[2], f[4] = d[4];
 36             d[2] = x, d[4] = y;
 37         }
 38     }
 39     void U(int cnt) {
 40             for(; cnt > 0; cnt--) {
 41             int a[5];
 42             for(int i = 1; i <= 4; i++) a[i] = u[i];
 43             u[1] = a[3], u[2] = a[1];
 44             u[3] = a[4], u[4] = a[2];
 45 
 46             int x = b[3], y = b[4];
 47             b[3] = l[4], b[4] = l[2];
 48             l[4] = f[2], l[2] = f[1];
 49             f[2] = r[1], f[1] = r[3];
 50             r[1] = x, r[3] = y;
 51         }
 52     }
 53     void D(int cnt) {
 54         for(; cnt > 0; cnt--) {
 55             int a[5];
 56             for(int i = 1; i <= 4; i++) a[i] = d[i];
 57             d[2] = a[1], d[1] = a[3];
 58             d[4] = a[2], d[3] = a[4];
 59 
 60             int x = b[1], y = b[2];
 61             b[1] = r[4], b[2] = r[2];
 62             r[4] = f[3], r[2] = f[4];
 63             f[3] = l[1], f[4] = l[3];
 64             l[1] = x, l[3] = y;
 65         }
 66     }
 67     void F(int cnt) {
 68         for(; cnt > 0; cnt--) {
 69             int a[5];
 70             for(int i = 1; i <= 4; i++) a[i] = f[i];
 71             f[1] = a[3], f[2] = a[1];
 72             f[3] = a[4], f[4] = a[2];
 73 
 74             int x = u[3], y = u[4];
 75             u[3] = l[3], u[4] = l[4];
 76             l[3] = d[1], l[4] = d[2];
 77             d[1] = r[3], d[2] = r[4];
 78             r[3] = x, r[4] = y;
 79         }
 80     }
 81     void B(int cnt) {
 82         for(; cnt > 0; cnt--) {
 83             int a[5];
 84             for(int i = 1; i <= 4; i++) a[i] = u[i];
 85             u[1] = a[3], u[3] = a[4];
 86             u[2] = a[1], u[4] = a[2];
 87 
 88             int x = u[1], y = u[2];
 89             u[1] = r[1], u[2] = r[2];
 90             r[1] = d[4], r[2] = d[3];
 91             d[4] = l[1], d[3] = l[2];
 92             l[1] = x, l[2] = y;
 93         }
 94     }
 95     bool ok() {
 96         for(int i = 2; i <= 4; i++) {
 97             if(u[i] != u[1] || d[i] != d[1]
 98             || l[i] != l[1] || r[i] != r[1]
 99             || f[i] != f[1] || b[i] != b[1])
100                 return 0;
101         }
102         return 1;
103     }
104     bool operate(char ch) {
105         if(ch == 'u') {
106             U(1);
107             if(ok())
108                 return 1;
109             else {
110                 U(3);
111                 U(3);
112                 if(ok())
113                     return 1;
114                 else{
115                     U(1);
116                     return 0;
117                 }
118             }
119         }
120         if(ch == 'd') {
121             D(1);
122             if(ok())
123                 return 1;
124             else{
125                 D(3);
126                 D(3);
127                 if(ok())
128                     return 1;
129                 else{
130                     D(1);
131                     return 0;
132                 }
133             }
134         }
135         if(ch == 'f') {
136             F(1);
137             if(ok())
138                 return 1;
139             else{
140                 F(3);
141                 F(3);
142                 if(ok())
143                     return 1;
144                 else{
145                     F(1);
146                     return 0;
147                 }
148             }
149         }
150         if(ch == 'b') {
151             B(1);
152             if(ok())
153                 return 1;
154             else{
155                 B(3);
156                 B(3);
157                 if(ok())
158                     return 1;
159                 else{
160                     B(1);
161                     return 0;
162                 }
163             }
164         }
165         if(ch == 'l') {
166             L(1);
167             if(ok())
168                 return 1;
169             else{
170                 L(3);
171                 L(3);
172                 if(ok())
173                     return 1;
174                 else{
175                     L(1);
176                     return 0;
177                 }
178             }
179         }
180         if(ch == 'r') {
181             R(1);
182             if(ok())
183                 return 1;
184             else{
185                 R(3);
186                 R(3);
187                 if(ok())
188                     return 1;
189                 else{
190                     R(1);
191                     return 0;
192                 }
193             }
194         }
195     }
196     void print() {
197         puts("###");
198         for(int i = 1; i <= 4; i++) printf("%d ", u[i]); puts("");
199         for(int i = 1; i <= 4; i++) printf("%d ", f[i]); puts("");
200         for(int i = 1; i <= 4; i++) printf("%d ", d[i]); puts("");
201         for(int i = 1; i <= 4; i++) printf("%d ", b[i]); puts("");
202         for(int i = 1; i <= 4; i++) printf("%d ", l[i]); puts("");
203         for(int i = 1; i <= 4; i++) printf("%d ", r[i]); puts("");
204     }
205 }m2;
206 
207 int main()
208 {
209     int T;
210     scanf("%d", &T);
211     while(T--) {
212         m2.get_u();
213         m2.get_f();
214         m2.get_d();
215         m2.get_b();
216         m2.get_l();
217         m2.get_r();
218         if(m2.ok() || m2.operate('u') || m2.operate('d') || m2.operate('l')
219         || m2.operate('r') || m2.operate('f') || m2.operate('b'))
220             printf("YES\n");
221         else
222             printf("NO\n");
223     }
224     return 0;
225 }

HDU 5985 Lucky Coins

题意

  给出n个硬币和每个硬币的数量和正面朝上的概率,问每个硬币成为幸运硬币的概率是多少。成为幸运硬币的条件是每投一次将所有背面朝上的硬币去掉,继续抛掷,直至剩下一种或者一个都剩下,那最后一种留下的硬币就是幸运硬币。

解题思路

  概率DP,我们定义dead[i][j]表示第i种硬币在前j步以内全部被抛弃的概率,显然

化简可得 .

  那么我们定义aliv[i][j] 表示第i种硬币在前j步以内至少有一个没有被抛弃的概率是 1 - dead[i][j],那么第i个硬币成为幸运硬币的概率大概等于(应为当k = 30的时候0.5的三十次方就很小),其实际意义就是第i种硬币成为幸运硬币的概率等于模拟投掷100次,而每次让第1到n种硬币在k步全部被抛弃的概率乘上第i种硬币在第k步至少还有一个而第k+1步全部被抛弃的概率,当然前面的第1到第n种硬币全部被抛弃不包括第i种硬币,故完整的式子是:

代码如下:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 15;
 9 int n;
10 double num[maxn], p[maxn], ans[maxn];
11 double dead[maxn][110], alive[maxn][110];
12 
13 void cdead() {
14     for(int k = 1; k <= 100; k++) {
15         for(int i = 0; i < n; i++) {
16             dead[i][k] = pow(1.0 - pow(p[i], k), num[i]);
17         }
18     }
19 }
20 void calive() {
21     for(int k = 1; k <= 100; k++) {
22         for(int i = 0; i < n; i++) {
23             alive[i][k] = 1.0 - dead[i][k];
24         }
25     }
26 }
27 
28 int main()
29 {
30     int T;
31     scanf("%d", &T);
32     while(T--) {
33         scanf("%d", &n);
34         for(int i = 0; i < n; i++) {
35             scanf("%lf%lf", &num[i], &p[i]);
36         }
37         if(n == 1) {
38             printf("1.000000\n");
39             continue;
40         }
41 
42         cdead();
43         calive();
44         memset(ans, 0, sizeof(ans));
45         for(int k = 1; k <= 100; k++) {
46             for(int i = 0; i < n; i++) {
47                 double tmp = 1;
48                 for(int j = 0; j < n; j++) {
49                     if(j == i)  continue;
50                     tmp *= dead[j][k];
51                 }
52                 ans[i] += tmp * (alive[i][k] - alive[i][k + 1]);
53             }
54         }
55 
56         for(int i = 0; i < n; i++) {
57             printf("%.6lf%c", ans[i], i == n - 1 ? '\n' : ' ');
58         }
59     }
60     return 0;
61 }

   可以看出青岛站的题目还是有难度的,主要侧重的是数学推理,准备时应该多以数学推理为主,大战在即,加油!

转载于:https://www.cnblogs.com/wenzhixin/p/9854395.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/aisebu7819/article/details/101517037

智能推荐

笔记本电脑插入耳机只能外放,耳机没声音_耳机连到笔记本电脑后只有输入没有输出-程序员宅基地

文章浏览阅读5.4w次,点赞6次,收藏14次。通常的一些做法,请参考http://jingyan.baidu.com/article/64d05a0267a80ede55f73b14.html不过我的耳机没声音是这么解决的,感觉比较坑爹,曾一度以为耳机坏了,谁知是驱动的问题。不吐槽了,请看下面:(1)_耳机连到笔记本电脑后只有输入没有输出

windows下redis安装+phpredis扩展_php redis-x64-2.8.2104.msi-程序员宅基地

文章浏览阅读236次。准备工作:Redis-x64-2.8.2104.zip(可根据自己的操作系统进行选择,这里使用的是64位)php_redis.dll(根据php版本,选择对应的扩展版本)操作: 1.解压Redis-x64-2.8.2104.zip,打开其中的redis-server.exe,出现如下图: 2.打开redis-cli.exe,出现如下图:_php redis-x64-2.8.2104.msi

k8s部署redis有状态服务statefulset-程序员宅基地

文章浏览阅读1k次。apiVersion: v1kind: ConfigMapmetadata: name: redis-conf namespace: dmgeo-libdata: redis.conf: | bind 0.0.0.0 port 6379 requirepass 123456 pidfile .pid appendonly yes cluster-config-file nodes-6379.c.

444项国家标准3月1日起实施-程序员宅基地

文章浏览阅读1.6k次。2022年3月1日起,10项强制性国家标准和434项推荐性国家标准开始实施。标准君根据国家标准委官方发布信息,对2022年3月1日起正式实施的国家标准进行了整理汇编,供大家参考,具体标准名单如下:10项强制性国家标准序号 标准号 是否采标 标准名称 实施日期 1 GB 40070-2021 儿童青少年学习用品近视防控卫生要求 2022/3/1 2 GB 14391-2021 卫星紧急无线电示位标性能要求 .

python实现多线程-程序员宅基地

文章浏览阅读6.1k次,点赞12次,收藏53次。本文转载于上面的链接.文章目录1 线程基本概念1.1 线程是什么?1.2 线程和进程关系?2 Python线程模块3 线程间同步4 线程池4.1 传统多线程问题?4.2 线程池基本原理:5 协程5.2 Send来了6. python 进行并发编程6.1 使用asyncio6.2 使用async/await7 小结1 线程基本概念1.1 线程是什么?线程是指进程内的一个执行单元..._python实现多线程

物联网 长连接 服务器_为什么物联网还有很长的路要走-程序员宅基地

文章浏览阅读417次。物联网 长连接 服务器It’s IoT Week at SitePoint! All week we’re publishing articles focused on the intersection of the internet and the physical world, so keep checking the IoT tag for the latest updates. 这是Si..._长连接 物联网

随便推点

Nginx绑定域名 nginx绑定多个域名-程序员宅基地

文章浏览阅读1k次。nginx绑定域名方法很简单我们只要在nginx中servers中加入server然后把server_name写上你的域名就实现域名绑定了。Server 名称使用 “server_name” 指令来定义,并决定用哪一个 server 区块来处理请求一、每个域名一个文件的写法首先打开nginx域名配置文件存放目录:/usr/local/nginx/conf/ser_nginx绑定域名

MySql - 数据库连接池_public void close(connection conn, statement stat,-程序员宅基地

文章浏览阅读175次。数据库连接池负责分配、管理和释放数据库连接,它允许应用程序重复使用一个现有的数据库连接,而不是再重新建立一个;释放空闲时间超过最大空闲时间的数据库连接来避免因为没有释放数据库连接而引起的数据库连接遗漏。这项技术能明显提高对数据库操作的性能。 --- 百度百科C3P0连接池使用步骤;1、导入相关jar包 2、编写c3p0-config.xml文件 -- 自动加..._public void close(connection conn, statement stat, resultset rs) { if (rs

IDEA如何显示左侧的project和右侧的maven 工具栏并固定位置折叠不会隐藏每次都要调出_idea maven 如何折叠-程序员宅基地

文章浏览阅读2.9w次,点赞18次,收藏27次。file->settings在Appearance&Behavior在选择Appearance在右边window options下选择show tool windowsbars点击apply,ok就搞定了效果:_idea maven 如何折叠

依赖注入那些事儿_并利用spring ioc容器实现模块功能。 有一个叫igame的游戏公司,正在开发一款arpg-程序员宅基地

文章浏览阅读933次。目录目录1 IGame游戏公司的故事 1.1 讨论会 1.2 实习生小李的实现方法 1.3 架构师的建议 1.4 小李的小结2 探究依赖注入 2.1 故事的启迪 2.2 正式定义依赖注入3 依赖注入那些事儿 3.1 依赖注入的类别 3.1.1 Setter注入 3.1.2 Co_并利用spring ioc容器实现模块功能。 有一个叫igame的游戏公司,正在开发一款arpg

数据库中查询结果去重_数据库查询列的值去重-程序员宅基地

文章浏览阅读1.7k次。有重复数据主要有一下几种情况:1.存在两条完全相同的纪录这是最简单的一种情况,用关键字distinct就可以去掉example: select distinct * from table(表名) where (条件)2.存在部分字段相同的纪录(有主键id即唯一键)如果是这种情况的话用distinct是过滤不了的,这就要用到主键id的唯一性特点及group by分组example:s..._数据库查询列的值去重

C语言参数传递二维数组—保持城市天际线-程序员宅基地

文章浏览阅读217次。今天做了LeetCode上的一道题,原理较简单,很容易相处解法,但是在编写代码过程中传递二维数组时总是会发生错误,因此总结了下如何传递:参考博客 http://www.cnblogs.com/yangxi/archive/2012/03/22/2411452.html题目 :在二维数组grid中,grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量(不同建..._c 语言城市天际线可以表示为二维列表,其中 1 表示建筑物。在下面的示例中,最高建

推荐文章

热门文章

相关标签