签到
#include <bits/stdc++.h> int n; int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); int ans = 0; for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); ans += a * b; } printf("%d\n", ans); } return 0; }
判断所有情况，写丑了。
#include <bits/stdc++.h> const int N = 30; int a[N], b[N]; const int n = 24; bool check() { for (int i = 1; i <= 6; i++) { int j = (i - 1) * 4 + 1; int num = b[j]; for (int cnt = 0; cnt < 4; j++, cnt++) if (b[j] != num) return false; } return true; } int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while (T--) { for (int i = 1; i <= 24; i++) scanf("%d", a + i); memcpy(b, a, sizeof(a)); if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(a)); b[5] = a[1]; b[7] = a[3]; b[9] = a[5]; b[11] = a[7]; b[13] = a[9]; b[15] = a[11]; b[3] = a[15]; b[1] = a[13]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[1] = a[5]; b[3] = a[7]; b[5] = a[9]; b[7] = a[11]; b[9] = a[13]; b[11] = a[15]; b[15] = a[3]; b[13] = a[1]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[6] = a[2]; b[8] = a[4]; b[10] = a[6]; b[12] = a[8]; b[14] = a[10]; b[16] = a[12]; b[4] = a[16]; b[2] = a[14]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[4] = a[8]; b[2] = a[6]; b[6] = a[10]; b[8] = a[12]; b[10] = a[14]; b[12] = a[16]; b[14] = a[2]; b[16] = a[4]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[3] = a[19]; b[4] = a[20]; b[23] = a[3]; b[24] = a[4]; b[9] = a[24]; b[10] = a[23]; b[20] = a[9]; b[19] = a[10]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[3] = a[23]; b[4] = a[24]; b[23] = a[10]; b[24] = a[9]; b[10] = a[19]; b[9] = a[20]; b[19] = a[3]; b[20] = a[4]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[1] = a[21]; b[2] = a[22]; b[21] = a[12]; b[22] = a[11]; b[12] = a[17]; b[11] = a[18]; b[17] = a[1]; b[18] = a[2]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[1] = a[17]; b[2] = a[18]; b[21] = a[1]; b[22] = a[2]; b[11] = a[22]; b[12] = a[21]; b[18] = a[11]; b[17] = a[12]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[5] = a[23]; b[6] = a[21]; b[23] = a[16]; b[21] = a[15]; b[15] = a[20]; b[16] = a[18]; b[20] = a[6]; b[18] = a[5]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[5] = a[18]; b[6] = a[20]; b[23] = a[5]; b[21] = a[6]; b[16] = a[23]; b[15] = a[21]; b[20] = a[15]; b[18] = a[16]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[7] = a[17]; b[8] = a[19]; b[24] = a[7]; b[22] = a[8]; b[13] = a[22]; b[14] = a[24]; b[19] = a[13]; b[17] = a[14]; if (check()) { puts("YES"); continue; } memcpy(b, a, sizeof(b)); b[7] = a[24]; b[8] = a[22]; b[24] = a[14]; b[22] = a[13]; b[13] = a[19]; b[14] = a[17]; b[19] = a[8]; b[17] = a[7]; if (check()) { puts("YES"); continue; } puts("NO"); } return 0; }
[C. Pocky]
当 $n > d$ 时，$f(n) = \dfrac{\int_{d} ^{n} f(x)dx}{n} + 1$
当 $n \leq d$ 时，$f(n) = 0$
解得 $f(n) = ln(\dfrac{n}{d}) + 1$
#include<bits/stdc++.h> const double eps = 1e-10; int dcmp(double x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } int main() { int T; scanf("%d", &T); while (T--) { double a, b; scanf("%lf%lf", &a, &b); if (dcmp(a - b) <= 0) { puts("0.000000"); continue; } double ans = log(a) - log(b) + 1.0; printf("%.6f\n", ans); } return 0; }
每种硬币都是独立的。那么求出第 $i$ 种硬币在第 $j$ 轮之前都被拿掉的概率 $die[i][j] = (1 - p_{i} ^ j)^{cnt_i}$。$alive[i][j] = 1 - die[i][j]$ 表示第 $i$ 种硬币在第 $j$ 轮还存活的概率。
对于第 $i$ 种硬币的答案就是 $\sum_{step} (alive[i][step] - alive[i][step + 1]) * \prod_{j!=i}die[j][step]$。
#include <bits/stdc++.h> const int N = 15; const int step = 105; double qp(double a, int n) { double ans = 1; while (n) { if (n & 1) ans *= a; a *= a; n >>= 1; } return ans; } double alive[N][step], die[N][step], p[N]; int cnt[N], n; void init(int index) { double pp = p[index]; for (int i = 1; i < step; i++) { die[index][i] = qp(1 - pp, cnt[index]); alive[index][i] = 1 - die[index][i]; pp *= p[index]; } } double solve(int index) { double ans = 0; for (int i = 1; i < step - 1; i++) { double temp = alive[index][i] - alive[index][i + 1]; for (int j = 1; j <= n; j++) { if (j == index) continue; temp *= die[j][i]; } ans += temp; } return ans; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%lf", cnt + i, p + i); init(i); } if (n == 1) { puts("1.000000"); continue; } for (int i = 1; i <= n; i++) printf("%.6f%c", solve(i), " \n"[i == n]); } return 0; }
求出最小的崩溃概率，即求最大的未崩溃概率。
转化成二分图。人多于食物的为 $X$，人少于食物的为 $Y$。
概率取对数，跑费用流即可。
#include <bits/stdc++.h> const int N = 500 + 7; const int M = 2e4 + 7; const double inf = 1e12; const int INF = 0x3f3f3f3f; struct E { int v, ne, f; double c; } e[M]; int head[N], cnt; double dis[N]; int path[N], n, m; bool inq[N]; inline void add(int u, int v, int f, double c) { e[cnt].v = v; e[cnt].f = f; e[cnt].c = c; e[cnt].ne = head[u]; head[u] = cnt++; e[cnt].v = u; e[cnt].f = 0; e[cnt].c = -c; e[cnt].ne = head[v]; head[v] = cnt++; } const double eps = 1e-8; int dcmp(double x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } bool spfa(int s, int t) { for (int i = 0; i <= t; i++) dis[i] = inf, inq[i] = 0, path[i] = -1; dis[s] = 0; inq[s] = 1; std::queue<int> que; que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); inq[u] = 0; for (int i = head[u]; ~i; i = e[i].ne) { int v = e[i].v; double c = e[i].c; if (e[i].f && dcmp(dis[v] - dis[u] - c) > 0) { dis[v] = dis[u] + c; path[v] = i; if (!inq[v]) { inq[v] = 1; que.push(v); } } } } return dis[t] != inf; } double mcf(int s, int t) { double ans = 0; while (spfa(s, t)) { int x = INF; for (int i = path[t]; ~i; i = path[e[i ^ 1].v]) x = std::min(x, e[i].f); ans += dis[t] * x; for (int i = path[t]; ~i; i = path[e[i ^ 1].v]) e[i].f -= x, e[i ^ 1].f += x; } return ans; } int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while (T--) { memset(head, -1, sizeof(head)); cnt = 0; scanf("%d%d", &n, &m); int s = 0, t = n + 1; for (int i = 1; i <= n; i++) { int S, B; scanf("%d%d", &S ,&B); if (S > B) add(s, i, S - B, 0); else if(S<B)add(i, t, B - S, 0); } for (int i = 1; i <= m; i++) { int u, v, c; double p; scanf("%d%d%d%lf", &u, &v, &c, &p); add(u, v, 1, 0); if (c > 1) add(u, v, c - 1, -log(1.0 - p)); } printf("%.2f\n", 1.0 - exp(-mcf(s, t))); } return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11706499.html
