摘要
本文主要列举并求解了2016 ACM/ICPC亚洲区青岛站现场赛的部分真题，着重介绍了各个题目的解题思路，结合详细的AC代码，意在熟悉青岛赛区的出题策略，以备战2018青岛站现场赛。
题意
给出一根棒子（可以吃的）的长度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) + );
}
return ;
}
题意
输入一个二阶魔方的状态，问能否一步将其复原。
解题思路
需要细心和耐心，考虑每一种拧法，操作的时候，先顺时针改变一个面的数，然后改变四周的数，写出操作模板。要特别注意输入状态的次序，哪个面先，以及哪个角先。
代码如下：
#include <cstdio>
struct Magic2{
int f[], b[], u[], d[], l[], r[];
void get_u() {for(int i = ; i <= ; i++) {scanf("%d", &u[i]);}}
void get_d() {for(int i = ; i <= ; i++) {scanf("%d", &d[i]);}}
void get_f() {for(int i = ; i <= ; i++) {scanf("%d", &f[i]);}}
void get_b() {for(int i = ; i <= ; i++) {scanf("%d", &b[i]);}}
void get_l() {for(int i = ; i <= ; i++) {scanf("%d", &l[i]);}}
void get_r() {for(int i = ; i <= ; i++) {scanf("%d", &r[i]);}}
void L(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = l[i];
l[] = a[];l[] = a[];
l[] = a[];l[] = a[];
int x = b[], y = b[];
b[] = d[], b[] = d[];
d[] = f[], d[] = f[];
f[] = u[], f[] = u[];
u[] = x, u[] = y;
}
}
void R(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = r[i];
r[] = a[], r[] = a[];
r[] = a[], r[] = a[];
int x = b[], y = b[];
b[] = u[], b[] = u[];
u[] = f[], u[] = f[];
f[] = d[], f[] = d[];
d[] = x, d[] = y;
}
}
void U(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = u[i];
u[] = a[], u[] = a[];
u[] = a[], u[] = a[];
int x = b[], y = b[];
b[] = l[], b[] = l[];
l[] = f[], l[] = f[];
f[] = r[], f[] = r[];
r[] = x, r[] = y;
}
}
void D(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = d[i];
d[] = a[], d[] = a[];
d[] = a[], d[] = a[];
int x = b[], y = b[];
b[] = r[], b[] = r[];
r[] = f[], r[] = f[];
f[] = l[], f[] = l[];
l[] = x, l[] = y;
}
}
void F(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = f[i];
f[] = a[], f[] = a[];
f[] = a[], f[] = a[];
int x = u[], y = u[];
u[] = l[], u[] = l[];
l[] = d[], l[] = d[];
d[] = r[], d[] = r[];
r[] = x, r[] = y;
}
}
void B(int cnt) {
for(; cnt > ; cnt--) {
int a[];
for(int i = ; i <= ; i++) a[i] = u[i];
u[] = a[], u[] = a[];
u[] = a[], u[] = a[];
int x = u[], y = u[];
u[] = r[], u[] = r[];
r[] = d[], r[] = d[];
d[] = l[], d[] = l[];
l[] = x, l[] = y;
}
}
bool ok() {
for(int i = ; i <= ; i++) {
if(u[i] != u[] || d[i] != d[]
|| l[i] != l[] || r[i] != r[]
|| f[i] != f[] || b[i] != b[])
return ;
}
return ;
}
bool operate(char ch) {
if(ch == 'u') {
U();
if(ok())
return ;
else {
U();
U();
if(ok())
return ;
else{
U();
return ;
}
}
}
if(ch == 'd') {
D();
if(ok())
return ;
else{
D();
D();
if(ok())
return ;
else{
D();
return ;
}
}
}
if(ch == 'f') {
F();
if(ok())
return ;
else{
F();
F();
if(ok())
return ;
else{
F();
return ;
}
}
}
if(ch == 'b') {
B();
if(ok())
return ;
else{
B();
B();
if(ok())
return ;
else{
B();
return ;
}
}
}
if(ch == 'l') {
L();
if(ok())
return ;
else{
L();
L();
if(ok())
return ;
else{
L();
return ;
}
}
}
if(ch == 'r') {
R();
if(ok())
return ;
else{
R();
R();
if(ok())
return ;
else{
R();
return ;
}
}
}
}
void print() {
puts("###");
for(int i = ; i <= ; i++) printf("%d ", u[i]); puts("");
for(int i = ; i <= ; i++) printf("%d ", f[i]); puts("");
for(int i = ; i <= ; i++) printf("%d ", d[i]); puts("");
for(int i = ; i <= ; i++) printf("%d ", b[i]); puts("");
for(int i = ; i <= ; i++) printf("%d ", l[i]); puts("");
for(int i = ; i <= ; 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 ;
}
题意
给出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 = ;
int n;
double num[maxn], p[maxn], ans[maxn];
double dead[maxn][], alive[maxn][]; void cdead() {
for(int k = ; k <= ; k++) {
for(int i = ; i < n; i++) {
dead[i][k] = pow(1.0 - pow(p[i], k), num[i]);
}
}
}
void calive() {
for(int k = ; k <= ; k++) {
for(int i = ; 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 = ; i < n; i++) {
scanf("%lf%lf", &num[i], &p[i]);
}
if(n == ) {
printf("1.000000\n");
continue;
} cdead();
calive();
memset(ans, , sizeof(ans));
for(int k = ; k <= ; k++) {
for(int i = ; i < n; i++) {
double tmp = ;
for(int j = ; j < n; j++) {
if(j == i) continue;
tmp *= dead[j][k];
}
ans[i] += tmp * (alive[i][k] - alive[i][k + ]);
}
} for(int i = ; i < n; i++) {
printf("%.6lf%c", ans[i], i == n - ? '\n' : ' ');
}
}
return ;
}
可以看出青岛站的题目还是有难度的，主要侧重的是数学推理，准备时应该多以数学推理为主，大战在即，加油！