A. Insomnia cure
哎 只能说英语太差，一眼题我看了三分钟。
题意：给5个数k, l, m, n 和 d，求1~d中能被k, l, m, n 至少一个整除的数的个数。
题解：……
代码：
#include <iostream> using namespace std; int main() { int a, b, c, d, n; cin >> a >> b >> c >> d >> n; int ans = 0; for (int i = 1; i <= n; ++i) if (i % a && i % b && i % c && i % d) ++ans; cout << n - ans; return 0; }
B. Escape
题意：还是5个数，vp, vd, t, f and c，公主的速度是vp，龙的速度是vd，公主先跑时间t，龙开始追公主，追到的时候，公主扔一个宝物，龙拿起回到起点然后花时间f把宝物藏起来，问最少扔多少个宝物公主才能跑距离c。
题解：模拟吧，有一个算是trick吧，就是如果vp>=vd直接输出0。
代码：
#include <iostream> using namespace std; int main() { int vp, vd, t, f, c; cin >> vp >> vd >> t >> f >> c; double a = vp * t; double d = vd - vp; int ans = 0; double t1 = a / d; a += t1 * vp; if (vp >= vd) { cout << '0'; return 0; } while (a < c) { ans++; a += vp * (f + a / vd); t1 = a / d; a += t1 * vp; } cout << ans; return 0; }
C. Terse princess
题意：傻逼公主选夫君，n个候选人，每个人有一个财富值，当看到一个人比前面所有的人都富有，公主就喊“Oh”，当看到一个人的财富比前面所有的人的财富和都多，公主就喊“Wow”（此时不喊“Oh”），一共n个人，喊a次“Oh”和b次“Wow”，让你构造一个财富值顺序，构造不出就输出-1。
题解：大概想一下就能知道，先一个1，然后b个“Wow”，然后a个“Oh”，然后全是1。有个Trick，如果b=0，那么构造的数组是1 2 。。。的话，2是要“Wow”的。（div2的C题我都不会做了，弱的不行……
代码（写的比较挫）：
#include <iostream> #include <cstdio> using namespace std; int main() { int a, b, n; cin >> n >> a >> b; int i = 0; int ans[200]; ans[0] = 1; if (b) { for (i = 1; i <= b; ++i) { ans[i] = ans[i-1] * 2; if (ans[i] > 50000) { printf("-1"); return 0; } } for (; i <= b+a; ++i) { ans[i] = ans[i-1] + 1; } for (; i < n; ++i) { ans[i] = 1; } } else { if (a && a >= n-1) { printf("-1"); return 0; } ans[1] = 1; for (i = 2; i <= a+1; ++i) { ans[i] = ans[i-1] + 1; } for(; i < n; ++i) ans[i] = 1; } printf("%d", ans[0]); for (int i = 1; i < n; ++i) printf(" %d", ans[i]); return 0; }
D. Bag of mice
题意：还是傻逼公主，和龙玩游戏。有一个口袋，里面有w个白老鼠和b个黑老鼠，俩人轮流抓老鼠，第一个抓到白老鼠的人赢，龙抓一次之后会吓跑一只老鼠，吓跑的老鼠不算抓到的。公主先抓，如果没有人抓到白老鼠就是龙赢。求公主赢的概率。
题解：比较简单的概率DP。从初态正推。
代码：
#include <iostream> #include <cstdio> using namespace std; const int N = 1005; double dp[N][N][2]; int main() { int a, b; cin >> a >> b; dp[a][b][1] = 1; for (int i = a; i >= 0; --i) { for (int j = b; j >= 0; --j) { if (j) dp[i][j-1][2] += dp[i][j][1] * j / (i+j); if (j > 1) dp[i][j-2][1] += dp[i][j][2] * j / (i+j) * (j-1) / (i+j-1); if (i && j) dp[i-1][j-1][1] += dp[i][j][2] * j / (i+j) * i / (i+j-1); } } double ans = 0; for (int i = a; i >= 0; --i) for (int j = b; j >= 0; --j) if (i) ans += dp[i][j][1] * i / (i+j); printf("%.9f", ans); return 0; }
E. Porcelain
题意：N个架子，每个架子上有一些瓷器，对于每个架子只能从旁边拿一个（左边或右边），求问M次最多拿总价值多少的瓷器。
题解：类似01背包。预处理出每个架子拿1~c（假设该架子一共有C个瓷器）个瓷器的最大值。每个架子只能选择一次。具体看代码吧。
代码：
#include <iostream> #include <cstdio> using namespace std; const int N = 105; int a[N], c[N]; int v[N][N]; int dp[10005]; int l[N], r[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> c[i]; for (int j = 1; j <= c[i]; ++j) cin >> a[j]; for (int j = 1; j <= c[i]; ++j) { l[j] = l[j-1] + a[j]; r[j] = r[j-1] + a[c[i]-j+1]; } for (int j = 1; j <= c[i]; ++j) for (int k = 0; k <= j; ++k) v[i][j] = max(v[i][j], l[k] + r[j-k]); } for (int i = 1; i <= n; ++i) for (int j = m; j >= 0; --j) for (int k = 0; k <= c[i] && k <= j; ++k) dp[j] = max(dp[j], dp[j-k] + v[i][k]); cout << dp[m]; return 0; }