摘要
本文主要列举并求解了 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)即可.
- #include <cstdio>
- #include <cmath>
- int main()
- {
- double x, d;
- int T;
- scanf("%d", &T);
- while(T--) {
- scanf("%lf%lf", &x, &d);
- if(x <= d)
- printf("0.000000\n");
- else
- printf("%.6lf\n", log(x) - log(d) + 1);
- }
- return 0;
- }
- HDU 5983 Pocket Cube
题意
输入一个二阶魔方的状态, 问能否一步将其复原.
解题思路
需要细心和耐心, 考虑每一种拧法, 操作的时候, 先顺时针改变一个面的数, 然后改变四周的数, 写出操作模板. 要特别注意输入状态的次序, 哪个面先, 以及哪个角先.
代码如下:
- #include <cstdio>
- struct Magic2{
- int f[5], b[5], u[5], d[5], l[5], r[5];
- void get_u() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &u[i]);}}
- void get_d() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &d[i]);}}
- void get_f() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &f[i]);}}
- void get_b() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &b[i]);}}
- void get_l() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &l[i]);}}
- void get_r() {for(int i = 1 ; i <= 4; i++) {scanf("%d", &r[i]);}}
- void L(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = l[i];
- l[2] = a[1];l[1] = a[3];
- l[3] = a[4];l[4] = a[2];
- int x = b[3], y = b[1];
- b[3] = d[3], b[1] = d[1];
- d[3] = f[3], d[1] = f[1];
- f[3] = u[3], f[1] = u[1];
- u[3] = x, u[1] = y;
- }
- }
- void R(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = r[i];
- r[1] = a[3], r[2] = a[1];
- r[3] = a[4], r[4] = a[2];
- int x = b[2], y = b[4];
- b[2] = u[2], b[4] = u[4];
- u[2] = f[2], u[4] = f[4];
- f[2] = d[2], f[4] = d[4];
- d[2] = x, d[4] = y;
- }
- }
- void U(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = u[i];
- u[1] = a[3], u[2] = a[1];
- u[3] = a[4], u[4] = a[2];
- int x = b[3], y = b[4];
- b[3] = l[4], b[4] = l[2];
- l[4] = f[2], l[2] = f[1];
- f[2] = r[1], f[1] = r[3];
- r[1] = x, r[3] = y;
- }
- }
- void D(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = d[i];
- d[2] = a[1], d[1] = a[3];
- d[4] = a[2], d[3] = a[4];
- int x = b[1], y = b[2];
- b[1] = r[4], b[2] = r[2];
- r[4] = f[3], r[2] = f[4];
- f[3] = l[1], f[4] = l[3];
- l[1] = x, l[3] = y;
- }
- }
- void F(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = f[i];
- f[1] = a[3], f[2] = a[1];
- f[3] = a[4], f[4] = a[2];
- int x = u[3], y = u[4];
- u[3] = l[3], u[4] = l[4];
- l[3] = d[1], l[4] = d[2];
- d[1] = r[3], d[2] = r[4];
- r[3] = x, r[4] = y;
- }
- }
- void B(int cnt) {
- for(; cnt> 0; cnt--) {
- int a[5];
- for(int i = 1; i <= 4; i++) a[i] = u[i];
- u[1] = a[3], u[3] = a[4];
- u[2] = a[1], u[4] = a[2];
- int x = u[1], y = u[2];
- u[1] = r[1], u[2] = r[2];
- r[1] = d[4], r[2] = d[3];
- d[4] = l[1], d[3] = l[2];
- l[1] = x, l[2] = y;
- }
- }
- bool ok() {
- for(int i = 2; i <= 4; i++) {
- if(u[i] != u[1] || d[i] != d[1]
- || l[i] != l[1] || r[i] != r[1]
- || f[i] != f[1] || b[i] != b[1])
- return 0;
- }
- return 1;
- }
- bool operate(char ch) {
- if(ch == 'u') {
- U(1);
- if(ok())
- return 1;
- else {
- U(3);
- U(3);
- if(ok())
- return 1;
- else{
- U(1);
- return 0;
- }
- }
- }
- if(ch == 'd') {
- D(1);
- if(ok())
- return 1;
- else{
- D(3);
- D(3);
- if(ok())
- return 1;
- else{
- D(1);
- return 0;
- }
- }
- }
- if(ch == 'f') {
- F(1);
- if(ok())
- return 1;
- else{
- F(3);
- F(3);
- if(ok())
- return 1;
- else{
- F(1);
- return 0;
- }
- }
- }
- if(ch == 'b') {
- B(1);
- if(ok())
- return 1;
- else{
- B(3);
- B(3);
- if(ok())
- return 1;
- else{
- B(1);
- return 0;
- }
- }
- }
- if(ch == 'l') {
- L(1);
- if(ok())
- return 1;
- else{
- L(3);
- L(3);
- if(ok())
- return 1;
- else{
- L(1);
- return 0;
- }
- }
- }
- if(ch == 'r') {
- R(1);
- if(ok())
- return 1;
- else{
- R(3);
- R(3);
- if(ok())
- return 1;
- else{
- R(1);
- return 0;
- }
- }
- }
- }
- void print() {
- puts("###");
- for(int i = 1; i <= 4; i++) printf("%d", u[i]); puts("");
- for(int i = 1; i <= 4; i++) printf("%d", f[i]); puts("");
- for(int i = 1; i <= 4; i++) printf("%d", d[i]); puts("");
- for(int i = 1; i <= 4; i++) printf("%d", b[i]); puts("");
- for(int i = 1; i <= 4; i++) printf("%d", l[i]); puts("");
- for(int i = 1; i <= 4; i++) printf("%d", r[i]); puts("");
- }
- }m2;
- int main()
- {
- int T;
- scanf("%d", &T);
- while(T--) {
- m2.get_u();
- m2.get_f();
- m2.get_d();
- m2.get_b();
- m2.get_l();
- m2.get_r();
- if(m2.ok() || m2.operate('u') || m2.operate('d') || m2.operate('l')
- || m2.operate('r') || m2.operate('f') || m2.operate('b'))
- printf("YES\n");
- else
- printf("NO\n");
- }
- return 0;
- }
- 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 种硬币, 故完整的式子是:
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- using namespace std;
- const int maxn = 15;
- int n;
- double num[maxn], p[maxn], ans[maxn];
- double dead[maxn][110], alive[maxn][110];
- void cdead() {
- for(int k = 1; k <= 100; k++) {
- for(int i = 0; i < n; i++) {
- dead[i][k] = pow(1.0 - pow(p[i], k), num[i]);
- }
- }
- }
- void calive() {
- for(int k = 1; k <= 100; k++) {
- for(int i = 0; i < n; i++) {
- alive[i][k] = 1.0 - dead[i][k];
- }
- }
- }
- int main()
- {
- int T;
- scanf("%d", &T);
- while(T--) {
- scanf("%d", &n);
- for(int i = 0; i < n; i++) {
- scanf("%lf%lf", &num[i], &p[i]);
- }
- if(n == 1) {
- printf("1.000000\n");
- continue;
- }
- cdead();
- calive();
- memset(ans, 0, sizeof(ans));
- for(int k = 1; k <= 100; k++) {
- for(int i = 0; i < n; i++) {
- double tmp = 1;
- for(int j = 0; j < n; j++) {
- if(j == i) continue;
- tmp *= dead[j][k];
- }
- ans[i] += tmp * (alive[i][k] - alive[i][k + 1]);
- }
- }
- for(int i = 0; i < n; i++) {
- printf("%.6lf%c", ans[i], i == n - 1 ? '\n' : ' ');
- }
- }
- return 0;
- }
可以看出青岛站的题目还是有难度的, 主要侧重的是数学推理, 准备时应该多以数学推理为主, 大战在即, 加油!
来源: https://www.cnblogs.com/wenzhixin/p/9854395.html