[关闭]
@ljt12138 2017-05-01T22:34:58.000000Z 字数 17151 阅读 975

bzoj刷题记录4.25-5.1

1823: [JSOI2010]满汉全席

2-SAT裸题：a∨b=¬a→b=¬b→a，然后tarjan就行了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 505, MAXM = 10005;
  6. struct node {
  7.     int to, next;
  8. } edge[MAXM];
  9. int head[MAXN], top = 0;
  10. void push(int i, int j)
  11. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  13. int n, m;
  15. int neg(int nd)
  16. { return nd>n?nd-n:nd+n; }
  18. int T;
  20. int dfn[MAXN], low[MAXN], stk[MAXN], instk[MAXN], stop = 0, dftop = 0;
  22. bool tarjan(int nd)
  23. {
  24.     dfn[nd] = low[nd] = ++dftop;
  25.     instk[nd] = 1, stk[++stop] = nd;
  26.     for (int i = head[nd]; i; i = edge[i].next) {
  27.         int to = edge[i].to;
  28.         if (!dfn[to]) {
  29.             if (!tarjan(to)) return 0;
  30.             low[nd] = min(low[nd], low[to]);
  31.         }
  32.         else if (instk[to]) low[nd] = min(low[nd], dfn[to]);
  33.     }
  34.     if (dfn[nd] == low[nd]) {
  35.         int now = 0;
  36.         do {
  37.             now = stk[stop--], instk[now] = 0;
  38.             if (now == neg(nd)) return 0;
  39.         } while (now != nd); 
  40.     }
  41.     return 1;
  42. }
  44. bool fail()
  45. {
  46.     memset(dfn, 0, sizeof dfn);
  47.     for (int i = 1; i <= n*2; i++)
  48.         if (!dfn[i])
  49.             if (!tarjan(i)) return 1;
  50.     return 0;
  51. }
  53. int main()
  54. {
  55.     scanf("%d", &T);
  56.     while (T--) {
  57.         top = 0, memset(head, 0, sizeof head);
  58.         dftop = 0, stop = 0;
  59.         memset(instk, 0, sizeof instk);
  60.         scanf("%d%d", &n, &m);
  61.         for (int i = 1; i <= m; i++) {
  62.             char t1, t2; int n1, n2;
  63.             scanf("\n%c%d %c%d", &t1, &n1, &t2, &n2);
  64.             if (t1 == 'm') n1 = neg(n1);
  65.             if (t2 == 'm') n2 = neg(n2);
  66.             push(neg(n1), n2), push(neg(n2), n1);
  67.         }
  68.         if (fail()) puts("BAD");
  69.         else puts("GOOD");
  70.     }
  71.     return 0;
  72. }

bzoj2756: [SCOI2012]奇怪的游戏

网络流。http://hzwer.com/5992.html

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 50*51, MAXM = 50*50*50;
  5. struct node {
  6.     int to, next;
  7.     long long flow;
  8.     int neg;
  9. } edge[MAXM];
  10. int head[MAXN], top = 0;
  11. void push(int i, int j, long long f)
  12. {
  13.     ++top, edge[top] = (node){j, head[i], f, top+1}, head[i] = top;
  14.     ++top, edge[top] = (node){i, head[j], 0, top-1}, head[j] = top;
  15. }
  17. int S = 2531, T = 2532;
  18. long long inf = 233333333333ll;
  20. int vis[MAXN], bfstime = 0, lev[MAXN];
  21. queue<int> que;
  23. bool bfs()
  24. {
  25.     vis[S] = ++bfstime, lev[S] = 0, que.push(S);
  26.     while (!que.empty()) {
  27.         int f = que.front(); que.pop();
  28.         for (int i = head[f]; i; i = edge[i].next) {
  29.             int to = edge[i].to;
  30.             long long fl = edge[i].flow;
  31.             if (!fl || vis[to] == bfstime) continue;
  32.             lev[to] = lev[f] + 1, vis[to] = bfstime, que.push(to);
  33.         }
  34.     }
  35.     return vis[T] == bfstime;
  36. }
  38. long long dfs(int nd, long long mf = inf)
  39. {
  40.     if (nd == T || !mf) return mf;
  41.     long long t, ans = 0;
  42.     for (int i = head[nd]; i; i = edge[i].next) {
  43.         int to = edge[i].to; long long f = edge[i].flow;
  44.         if (!f || lev[to] != lev[nd]+1) continue;
  45.         t = dfs(to, min(mf, f));
  46.         ans += t, mf -= t;
  47.         edge[i].flow -= t, edge[edge[i].neg].flow += t;
  48.     }
  49.     if (mf) lev[nd] = -1;
  50.     return ans;
  51. }
  53. long long dinic()
  54. {
  55.     long long ans = 0;
  56.     while (bfs()) ans += dfs(S);
  57.     return ans;
  58. }
  60. long long chess_board[55][55];
  61. int n, m, Tp;
  62. long long x[2] = {0,0}, sx[2] = {0,0};
  64. inline int number(int i, int j)
  65. { return (i-1)*m+j;}
  67. int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};
  69. bool judge(long long z)
  70. {
  71.     bfstime = 0, top = 0, memset(head, 0, sizeof head);
  72.     for (int i = 1; i <= n; i++)
  73.         for (int j = 1; j <= m; j++) {
  74.             if (z-chess_board[i][j] < 0) return 0;
  75.             if ((i+j)&1) push(S, number(i, j), z-chess_board[i][j]);
  76.             else push(number(i, j), T, z-chess_board[i][j]);
  77.         }
  78.     for (int i = 1; i <= n; i++)
  79.         for (int j = 1; j <= m; j++) {
  80.             if (!((i+j)&1)) continue;
  81.             for (int k = 0; k < 4; k++) {
  82.                 int nx = i+dx[k], ny = j+dy[k];
  83.                 if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
  84.                     push(number(i, j), number(nx, ny), inf);
  85.             }
  86.         }
  87.     long long fl = dinic();
  88.     return fl == z*x[0]-sx[0];
  89. }
  91. int main()
  92. {
  93.     scanf("%d", &Tp);
  94.     while (Tp--) {
  95.         scanf("%d%d", &n, &m);
  96.         x[0] = x[1] = sx[0] = sx[1] = 0;
  97.         for (int i = 1; i <= n; i++)
  98.             for (int j = 1; j <= m; j++) {
  99.                 scanf("%lld", &chess_board[i][j]);
  100.                 x[(i+j)&1]++, sx[(i+j)&1] += chess_board[i][j];
  101.             }
  102.         if (x[0] != x[1]) {
  103.             if ((sx[0]-sx[1])%(x[0]-x[1]) != 0) puts("-1");
  104.             else {
  105.                 long long val = (sx[0]-sx[1])/(x[0]-x[1]);
  106.                 if (judge(val)) printf("%lld\n", val*x[0]-sx[0]);
  107.                 else puts("-1");
  108.             }
  109.         } else {
  110.             if (sx[0] != sx[1]) puts("-1");
  111.             else {
  112.                 long long l = 0, r = inf, mid;
  113.                 while (l <= r) {
  114.                     mid = (l+r)>>1;
  115.                     if (!judge(mid)) l = mid+1;
  116.                     else r = mid-1;
  117.                 }
  118.                 printf("%lld\n", l*x[0]-sx[0]);
  119.             }
  120.         }
  121.     }
  122.     return 0;
  123. }

bzoj2809: [Apio2012]dispatching

第一反应是可并堆.
然而可并堆的空间会不会爆炸呢..后来发现是不会炸的..每个元素至多只入一次堆，删除一次，总复杂度还是O(nlgn)的。

结果写了可持久化权值线段树..离散化，找出dfn序用可持久化线段树维护区间内有值的点数和总和，然后二分就好，复杂度也是O(nlgn).

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005, lgn = 20;
  5. int lc[MAXN*20], rc[MAXN*20], l[MAXN*20];
  6. int r[MAXN*20], top = 0;
  7. long long dat[MAXN*20], sum[MAXN*20], siz[MAXN*20], dx[MAXN];
  8. int root[MAXN];
  9. int n;
  10. long long m;
  12. inline void update(int nd)
  13. {
  14.     sum[nd] = sum[lc[nd]] + sum[rc[nd]] + dat[nd];
  15.     if (l[nd] == r[nd]) siz[nd] = dat[nd] != 0;
  16.     else siz[nd] = siz[lc[nd]] + siz[rc[nd]];
  17. }
  19. void build(int &nd, int opl, int opr)
  20. {
  21.     nd = ++top, l[nd] = opl, r[nd] = opr;
  22.     if (opl < opr)
  23.         build(lc[nd], opl, (opl+opr)/2), build(rc[nd], (opl+opr)/2+1, opr);
  24. }
  26. void push(int prev, int &nd, int pos)
  27. {
  28.     nd = ++top, l[nd] = l[prev], r[nd] = r[prev];
  29.     if (l[prev] == r[prev]) dat[nd] = dx[pos]/(n+1), update(nd);
  30.     else {
  31.         int mid = (l[prev]+r[prev])/2;
  32.         if (pos <= mid) push(lc[prev], lc[nd], pos), rc[nd] = rc[prev], update(nd);
  33.         else push(rc[prev], rc[nd], pos), lc[nd] = lc[prev], update(nd);
  34.     }
  35. }
  37. int answer(int lpos, int rpos, long long sm)
  38. {
  39.     lpos--;
  40.     int i = 1, j = n, mid, lr = root[lpos], rr = root[rpos];
  41.     int ans = 0;
  42.     while (i < j) {
  43.         mid = (i+j)>>1;
  44.         int lp = lc[lr], rp = lc[rr];
  45.         if (sum[rp]-sum[lp] >= sm) lr = lp, rr = rp, j = mid;
  46.         else sm -= sum[rp]-sum[lp], ans += siz[rp]-siz[lp], lr = rc[lr], rr = rc[rr], i = mid+1;
  47.     }
  48.     if (sm >= sum[rr]-sum[lr]) ans += siz[rr]-siz[lr];
  49.     return ans;
  50. }
  52. struct node {
  53.     int to, next;
  54. } edge[MAXN];
  55. int head[MAXN], tp = 0;
  56. void push(int i, int j)
  57. { edge[++tp] = (node){j, head[i]}, head[i] = tp; }
  59. int fa[MAXN], in[MAXN], out[MAXN], dfn = 0;
  60. long long money[MAXN], leader[MAXN];
  62. int dx_num(long long num, int i)
  63. { return lower_bound(dx+1, dx+n+1, num*(n+1)+i)-dx; }
  65. void dx_init()
  66. {
  67.     for (int i = 1; i <= n; i++) dx[i] = money[i]*(n+1)+i;
  68.     sort(dx+1, dx+n+1);
  69. }
  71. void dfs(int nd)
  72. {
  73.     in[nd] = ++dfn;
  74.     push(root[dfn-1], root[dfn], dx_num(money[nd], nd));
  75.     for (int i = head[nd]; i; i = edge[i].next)
  76.         dfs(edge[i].to);
  77.     out[nd] = dfn;
  78. }
  80. long long query(int nd)
  81. { return leader[nd]*answer(in[nd], out[nd], m); }
  83. int main()
  84. {
  85.     scanf("%d%lld", &n, &m);
  86.     int master = 0;
  87.     for (int i = 1; i <= n; i++)
  88.         scanf("%d%lld%lld", &fa[i], &money[i], &leader[i]);
  89.     build(root[0], 1, n);
  90.     dx_init();
  91.     for (int i = 1; i <= n; i++) {
  92.         if (!fa[i]) master = i;
  93.         else push(fa[i], i);
  94.     }
  95.     dfs(master);
  96.     long long ans = 0;
  97.     for (int i = 1; i <= n; i++)
  98.         ans = max(ans, query(i));
  99.     printf("%lld\n", ans);
  100.     return 0;
  101. }

bzoj3206: [Apio2013]道路费用

没过...
用国内数据和hzwer及几分其他std拍都拍过了，然而bzoj上还是WA...奇特的是我们拿那份Te数据都WA一个点且结果一样。

然而hzwer代码bzoj可过而这份不可过...

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  7. const int MAXN = 100005, MAXM = 300105;
  8. int fa[MAXN];
  9. inline int findf(int nd)
  10. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  11. int gp[MAXN];
  12. long long siz[MAXN];
  13. inline int findgp(int nd)
  14. { return gp[nd]?gp[nd]=findgp(gp[nd]):nd; }
  15. void link(int i, int j)
  16. {
  17.     int a = findgp(i), b = findgp(j);
  18.     if (a != b)
  19.         gp[a] = b, siz[b] += siz[a];
  20. }
  22. struct edge {
  23.     int x, y;
  24.     long long c;
  25.     int on_eg;
  26.     edge(){ on_eg = 1; }
  27.     friend bool operator < (const edge &a, const edge &b)
  28.     { return a.c < b.c; }
  29. } edge[MAXM], knew[105], inp[MAXM];
  30. int n, m, k;
  31. const long long INF = 1234567891011ll;
  33. struct node {
  34.     int to, next;
  35.     long long dis;
  36. } graph[105];
  37. int head[MAXN], top = 0;
  38. int stk[50], t = 0;
  39. inline void push(int i, int j, long long dis)
  40. { //printf("%d--%lld-->%d\n", i, dis, j);
  41.  graph[++top] = (node){j, head[i], dis}, head[i] = top; }
  43. void mst(int eg, int flag = 0, int p = 0)
  44. {
  45.     // cout << eg << endl;
  46.     sort(edge+1, edge+eg+1);
  47.     if (!p) memset(fa, 0, sizeof fa);
  48.     else {
  49.         for (int i = 1; i <= t; i++)
  50.             fa[stk[i]] = 0;
  51.     }
  52.     for (int i = 1; i <= eg; i++) {
  53.         int a = findf(findgp(edge[i].x)), b = findf(findgp(edge[i].y));
  54.         if (a != b) {
  55.             fa[a] = b;
  56.             // printf("On MST --- %d, %d, %lld\n", a, b, edge[i].c);
  57.             if (flag) {
  58.                 push(findgp(edge[i].x), findgp(edge[i].y), edge[i].c);
  59.                 push(findgp(edge[i].y), findgp(edge[i].x), edge[i].c);
  60.             }
  61.         } else {
  62.             if (!p)edge[i].c = INF;
  63.             edge[i].on_eg = 0;
  64.         }
  65.     }
  66. }
  68. void cut1()
  69. {
  70.     memcpy(edge, inp, sizeof inp);
  71.     int tp = m;
  72.     for (int i = 1; i <= k; i++)
  73.         edge[++tp] = knew[i], edge[tp].c = -INF;
  74.     mst(tp);
  75.     for (int i = 1; i <= tp; i++)
  76.         if (abs(edge[i].c) != INF)
  77.             link(edge[i].x, edge[i].y);
  78. }
  80. void cut2()
  81. {
  82.     memcpy(edge, inp, sizeof inp);
  83.     mst(m);
  84.     int tp = m;
  85.     m = 0;
  86.     for (int i = 1; i <= tp; i++)
  87.         if (edge[i].c != INF) {
  88.             inp[++m] = edge[i], inp[m].on_eg = 1;
  89.             // printf("Cut2 %d--%lld--%d\n", edge[i].x, edge[i].c, edge[i].y);
  90.         }
  91. }
  93. int depth[MAXN], par[MAXN];
  94. long long peo[MAXN];
  95. long long lim[MAXN];
  97. void dfs(int nd, int f)
  98. {
  99.     depth[nd] = depth[f]+1;
  100.     par[nd] = f, lim[nd] = INF;
  101.     peo[nd] = siz[nd];
  102.     for (int i = head[nd]; i; i = graph[i].next) {
  103.         int to = graph[i].to;
  104.         if (to != f) dfs(to, nd), peo[nd] += peo[to];
  105.     }
  106. }
  108. void push_lim(int x, int y, long long l)
  109. {
  110.     while (x != y) {
  111.         if (depth[x] >= depth[y]) {
  112.             lim[x] = min(lim[x], l);
  113.             x = par[x];
  114.         } else {
  115.             lim[y] = min(lim[y], l);
  116.             y = par[y];
  117.         }
  118.     }
  119. }
  122. long long deal(int S)
  123. {
  124.     memcpy(edge, inp, k*16*sizeof(int));
  125.     top = 0;
  126.     int tp = m;
  127.     // cout << "---" <<edge[1].c << endl;
  128.     for (int i = 1; i <= t; i++)
  129.         head[stk[i]] = 0;
  130.     for (int i = 1; i <= k; i++)
  131.         if (S&(1<<(i-1))) {
  132.             edge[++tp] = knew[i], edge[tp].c = -INF, edge[tp].on_eg = 1;
  133.             if (findgp(knew[i].x) == findgp(knew[i].y)) return 0ll;
  134.         }
  135.     // for (int i = 1; i <= tp; i++)
  136.         // if (edge[i].on_eg != 1)
  137.             // throw;
  138.     mst(tp, 1, 1);
  139.     // printf("     tp = %d    \n", tp);
  140.     dfs(findgp(1), 0);
  141.     long long ans = 0;
  142.     for (int i = 1; i <= tp; i++) {
  143.         int x = findgp(edge[i].x), y = findgp(edge[i].y);
  144.         if (edge[i].on_eg == 0) {
  145.             push_lim(x, y, edge[i].c);
  146.             // printf("Pushlim %d,%d -- %lld\n", x, y, edge[i].c);
  147.             // edge[i].on_eg = 1;
  148.         } //else printf("Lk %d -- %lld -- %d\n", x, edge[i].c, y);
  149.     }
  150.     for (int i = 1; i <= k; i++)
  151.         if (S&(1<<(i-1))) {
  152.             int x = findgp(knew[i].x), y = findgp(knew[i].y);
  153.             if (depth[x] < depth[y]) swap(x, y);
  154.             long long l = lim[x];
  155.             ans += l*peo[x];
  156.             // cout << x << " " << y << " " << l << " " << peo[x] << endl;
  157.         }
  158.     // cout << ans << endl;
  159.     return ans;
  160. }
  162. int main()
  163. {
  164.     freopen("toll.in", "r", stdin);
  165.     freopen("toll.out", "w", stdout);
  166.     scanf("%d%d%d", &n, &m, &k);
  167.     for (int i = 1; i <= m; i++)
  168.         scanf("%d%d%lld", &inp[i].x, &inp[i].y, &inp[i].c), inp[i].on_eg = 1;
  169.     for (int i = 1; i <= k; i++)
  170.         scanf("%d%d", &knew[i].x, &knew[i].y);
  171.     for (int i = 1; i <= n; i++)
  172.         scanf("%lld", &siz[i]);
  173.     cut1();
  174.     cut2();
  175.     for (int i = 1; i <= n; i++)
  176.         if (gp[i] == 0)
  177.             stk[++t] = i;
  178.     long long ans = 0;
  179.     for (int i = 0; i < (1<<k); i++) {
  180.         ans = max(ans, deal(i));
  181.     }
  182.     cout << ans << endl;
  183.     return 0;
  184. }

bzoj1912: [Apio2010]patrol 巡逻

第一反应是先找最长链，然后缩成一个点再找最长链，然而只有55分。
后来反应过来两个链相交会有损耗，于是看到了大爷题解中把环上边权设为-1再走最长链的方法..
APIO神题好多..知识水平不超过NOIP但是思维难度很大..

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. struct node {
  6.     int to, next, dis, neg;
  7. } edge[MAXN*2];
  8. int head[MAXN], top = 0;
  9. void push(int i, int j)
  10. {
  11.     top++, edge[top] = (node){j, head[i], 1, top+1}, head[i] = top;
  12.     top++, edge[top] = (node){i, head[j], 1, top-1}, head[j] = top;
  13. }
  14. int n, K;
  15. int gp[MAXN], siz[MAXN];
  17. int stk[MAXN], stop = 0;
  18. int ans = 0;
  19. int depth[MAXN], maxl[MAXN], secl[MAXN], maxps[MAXN], secps[MAXN];
  20. int fa[MAXN];
  21. void dfs(int nd, int f = 0)
  22. {
  23.     maxl[nd] = secl[nd] = maxps[nd] = secps[nd] = 0;
  24.     for (int i = head[nd]; i; i = edge[i].next) {
  25.         int to = edge[i].to;
  26.         if (to == f) continue;
  27.         fa[to] = i;
  28.         depth[to] = depth[nd]+1, dfs(to, nd);
  29.         if (maxl[to]+edge[i].dis >= maxl[nd]) secl[nd] = maxl[nd], secps[nd] = maxps[nd], maxl[nd] = maxl[to]+edge[i].dis, maxps[nd] = to;
  30.         else if (maxl[to]+edge[i].dis > secl[nd]) secl[nd] = maxl[to]+edge[i].dis, secps[nd] = to;
  31.     }
  32. }
  34. void deal()
  35. {
  36.     memset(depth, 0, sizeof depth);
  37.     dfs(1, 0);
  38.     //puts("---");
  39.     int len = 0, nd;
  40.     for (int i = 1; i <= n; i++)
  41.         if (maxl[i] + secl[i] > len) len = maxl[i]+secl[i], nd = i;
  42.     //puts("---");
  43.     ans -= len*2, ans += len+1;
  44.     for (int i = maxps[nd]; i; i = maxps[i])
  45.         edge[fa[i]].dis = -1, edge[edge[fa[i]].neg].dis = -1;
  46.     for (int i = secps[nd]; i; i = maxps[i])
  47.         edge[fa[i]].dis = -1, edge[edge[fa[i]].neg].dis = -1;
  48.     //puts("---");
  49. }
  51. int main()
  52. {
  53.     scanf("%d%d", &n, &K);
  54.     memset(gp, 0, sizeof gp);
  55.     for (int i = 1; i <= n; i++) siz[i] = 1;
  56.     for (int i = 1; i < n; i++) {
  57.         int u, v; scanf("%d%d", &u, &v);
  58.         push(u, v);
  59.     }
  60.     ans = (n-1)*2;
  61.     deal();
  62.     if (K == 2) deal();
  63.     cout << ans << endl;
  64.     return 0;
  65. }

bzoj1076: [SCOI2008]奖励关

学习一个期望dp..
设f(k,S)为第k关，吃掉的情况为S之后的期望得分。如果prev[i]⊆S,f(k,S)=max{f(k+1,S),f(k+1,S∪i)+v[i]}，否咋f(k,S)=f(k+1,S)。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. double dp[105][(1<<16)+1];
  5. int k, n;
  6. int rp[105], st[105];
  8. int main()
  9. {
  10.     scanf("%d%d", &k, &n);
  11.     for (int i = 1; i <= n; i++) {
  12.         int t, u;
  13.         scanf("%d", &rp[i]);
  14.         st[i] = 0;
  15.         while (scanf("%d", &u), u != 0)
  16.             st[i] |= (1<<(u-1));
  17.     }
  18.     for (int i = 0; i < (1<<n); i++) dp[k+1][i] = 0;
  19.     for (int i = k; i >= 1; i--) {
  20.         for (int j = 0; j < (1<<n); j++) {
  21.             dp[i][j] = 0;
  22.             for (int p = 1; p <= n; p++) {
  23.                 if ((j&st[p])==st[p])
  24.                     dp[i][j] += max(dp[i+1][j], dp[i+1][j|(1<<(p-1))]+rp[p]*1.0);
  25.                 else
  26.                     dp[i][j] += dp[i+1][j];
  27.             }
  28.             dp[i][j] /= n;
  29.         }
  30.     }
  31.     printf("%.6f\n", dp[1][0]);
  32.     return 0;
  33. }

bzoj2134: 单选错位

分别计算贡献，令a0=an，则第i个题正确的期望是：p(i)=min{ai,ai−1}/(aiai−1)，总和即为所求。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, A, B, C;
  5. int a[10000005];
  6. int main()
  7. {
  8.     scanf("%d%d%d%d%d", &n, &A, &B, &C, a+1);
  9.     for (int i=2;i<=n;i++) a[i] = ((long long)a[i-1] * A + B) % 100000001;
  10.     for (int i=1;i<=n;i++) a[i] = a[i] % C + 1;
  11.     // for (int i = 1; i <= n; i++) cout << a[i] << " "; puts("");
  12.     double now = 0;
  13.     a[0] = a[n];
  14.     for (int i = 1; i <= n; i++) {
  15.         now = min(a[i],a[i-1])*1.0/a[i]/a[i-1]+now;
  16.     }
  17.     printf("%.3f\n", now);
  18.     return 0;
  19. }

bzoj4318: OSU!

大力递推可以O(n3)并优化至O(n2)。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. double p[100005];
  5. int n;
  6. double dp[100005];
  8. int main()
  9. {
  10.     scanf("%d", &n);
  11.     for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);
  12.     for (int i = 1; i <= n; i++) {
  13.         dp[i] = 0;
  14.         for (int k = 0; k <= i; k++) {
  15.             if (k+1 <= i) {
  16.                 double tmp = 1-p[k];
  17.                 for (int j = k+1; j <= i; j++)
  18.                     tmp *= p[j];
  19.                 dp[i] += tmp*((i-k)*(i-k)*(i-k)+dp[k-1]);
  20.             } else dp[i] += dp[k-1]*(1-p[k]);
  21.         }
  22.     }
  23.     cout << dp[n] << endl;
  24.     return 0;
  25. }

然而这个做法没有很好地利用期望的线性性质，即E(aX+bY)=aE(X)+bE(Y)。考虑这个元素之前期望的连续1长度为E(x)，连续1长度的平方为E(x2)，每个元素的贡献为：

(x+1)3−x3=3x2+3x+1=3E(x2)+3E(x)+1

注意：E(x2)≠E2(x)。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. double p[100005];
  5. int n;
  7. int main()
  8. {
  9.     scanf("%d", &n);
  10.     for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);
  11.     double x, x2, ans; x = x2 = 0, ans = 0;
  12.     for (int i = 1; i <= n; i++) {
  13.         ans += (x2*3+3*x+1)*p[i];
  14.         x2 = (x2+2*x+1)*p[i];
  15.         x = (x+1)*p[i];
  16.     }
  17.     printf("%.1f\n", ans);
  18.     return 0;
  19. }

bzoj3036: 绿豆蛙的归宿

例如有1→2,2→3,1→3,2→4,4→3，那么1→3的公式为：

1d1c13+1d11d2(c12+c23)+1d11d21d4(c12+c24+c43)

令dpi为1→i所有路径上点出度倒数乘积乘上路径长的和，fi为路径上所有点出度倒数乘积的和，然后发现有递推关系：

  1. f[to] += f[nd]/d[tp];
  2. dp[to] += dp[nd]/cd[tp]+c(nd,to)*f[nd]/cd[nd];
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. struct node {
  6.     int to, next, dis;
  7. } edge[MAXN*2];
  8. int head[MAXN], top = 0, rd[MAXN], cd[MAXN];
  9. void push(int i, int j, int d)
  10. { edge[++top] = (node){j, head[i], d}, head[i] = top, rd[j]++, cd[i]++; }
  12. int stk[MAXN], stop = 0;
  13. int n, m;
  14. double dp[MAXN], f[MAXN];
  16. int main()
  17. {
  18.     scanf("%d%d", &n, &m);
  19.     for (int i = 1; i <= m; i++) {
  20.         int u, v, d;
  21.         scanf("%d%d%d", &u, &v, &d);
  22.         push(u, v, d);
  23.     }
  24.     stk[++stop] = 1;
  25.     dp[1] = 0, f[1] = 1;
  26.     while (stop) {
  27.         int tp = stk[stop--];
  28.         for (int i = head[tp]; i; i = edge[i].next) {
  29.             int to = edge[i].to;
  30.             f[to] += f[tp]/cd[tp], dp[to] += dp[tp]/cd[tp]+edge[i].dis*f[tp]/cd[tp];
  31.             rd[to]--;
  32.             if (rd[to] == 0) stk[++stop] = to;
  33.         }
  34.     }
  35.     printf("%.2f\n", dp[n]);
  36.     return 0;
  37. }

bzoj4720: [Noip2016]换教室

终于来填坑了...

考场上设计的状态f[i][j][0/1]表示前i门课，能换j次，这次在哪个教室。然而无论怎么调都有后效性，只能记录路径上概率乘积变爆搜了..

正确的思路应该是f[i][j][0/1]表示前i门课，能换j次，这次提不提出申请，那么转移方程就是：

f[i][j][0]=max{f[i−1][j][0]+dis(ci−1,ci),(1−p[i−1])(f[i−1][j][1]+dis(ci−1,ci))+p[i−1](f[i−1][j][1]+dis(di−1,ci))}

i,j,1同理枚举四种可能情况即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, m, v, e;
  5. int g[505][505];
  6. int c[2005][2];
  7. double k[2005];
  8. double f[2005][2005][2];
  9. int main()
  10. {
  11.     scanf("%d%d%d%d", &n, &m, &v, &e);
  12.     for (int i = 1; i <= n; i++) scanf("%d", &c[i][0]);
  13.     for (int i = 1; i <= n; i++) scanf("%d", &c[i][1]);
  14.     for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
  15.     memset(g, 127/3, sizeof g);
  16.     for (int i = 1; i <= v; i++) g[i][i] = 0;
  17.     for (int i = 1; i <= e; i++) {
  18.         int u, v, d; scanf("%d%d%d", &u, &v, &d);
  19.         g[u][v] = g[v][u] = min(g[u][v], d);
  20.     }
  21.     for (int k = 1; k <= v; k++)
  22.         for (int i = 1; i <= v; i++)
  23.             for (int j = 1; j <= v; j++)
  24.                 g[j][i] = g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
  25.     for (int i = 0; i <= m; i++) f[1][i][0] = f[1][i][1] = 1e10;
  26.     f[1][0][0] = f[1][1][1] = f[1][1][0] = 0;
  27.     for (int i = 2; i <= n; i++) {
  28.         for (register int j = 0; j <= m; j++) {
  29.             f[i][j][0] = f[i][j][1] = 1e10;
  30.             f[i][j][0] = min(f[i-1][j][0]+g[c[i-1][0]][c[i][0]],
  31.                 f[i-1][j][1]+k[i-1]*g[c[i-1][1]][c[i][0]]+(1-k[i-1])*g[c[i-1][0]][c[i][0]]);
  32.             if (j != 0) {
  33.                 f[i][j][1] = min(f[i-1][j-1][0]+k[i]*g[c[i-1][0]][c[i][1]]+(1-k[i])*g[c[i-1][0]][c[i][0]],
  34.                     f[i-1][j-1][1]+k[i]*k[i-1]*g[c[i-1][1]][c[i][1]]+(1-k[i-1])*(1-k[i])*g[c[i-1][0]][c[i][0]]
  35.                     +k[i]*(1-k[i-1])*g[c[i-1][0]][c[i][1]]+k[i-1]*(1-k[i])*g[c[i-1][1]][c[i][0]]);
  36.                 f[i][j][0] = min(f[i][j][0], f[i][j-1][0]);
  37.                 f[i][j][1] = min(f[i][j][1], f[i][j-1][1]);
  38.             }
  39.         }
  40.     }
  41.     double ans = f[n][0][0];
  42.     for (int i = 1; i <= m; i++) ans = min(f[n][i][1], f[n][i][0]);
  43.     printf("%.2f\n", ans);
  44.     return 0;
  45. }

bzoj4008: [HNOI2015]亚瑟王

huzecong dalao的神题...
直接dp会发现无论怎么设计状态都不可能消除后效性。
然后就比较神了，分别计算每个卡牌的贡献，如果我们知道了这个卡牌i获得k次发动机会的概率f[i][k]，那么其贡献就为：

∑kf[i][k]×(1−(1−p[i])k)×di

也就是至少发动一次的概率（即一次也不发动的反面）。而在哪一次发动则对于这个卡牌的贡献是等价的，我们已经通过计算f[i][k]将每个卡牌独立，也就消除了哪一次发动对贡献的影响。然后只要列f[i][k]的方程：

f[i][k]=f[i−1][k]×(1−p[i−1])k+f[i−1][k+1]×(1−(1−p[i−1])k+1)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int T, n, r;
  5. double dp[225][140];
  6. double p[225], d[225];
  8. int main()
  9. {
  10.     scanf("%d", &T);
  11.     while (T--) {
  12.         scanf("%d%d", &n, &r);
  13.         double tmp = 1;
  14.         for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i], &d[i]), tmp *= p[i];
  15.         double ans = 0;
  16.         memset(dp, 0, sizeof dp);
  17.         dp[0][r] = 1;
  18.         for (int i = 1; i <= n; i++)
  19.             for (int j = 0; j <= r; j++) {
  20.                 dp[i][j] = dp[i-1][j]*pow(1-p[i-1], j)+dp[i-1][j+1]*(1-pow(1-p[i-1], j+1));
  21.                 ans += dp[i][j]*(1-pow(1-p[i], j))*d[i];
  22.             }
  23.         printf("%.10f\n", ans);
  24.     }
  25.     return 0;
  26. }

bzoj3270: 博物馆

和《游走》那个题套路一样。
把一个有序对看成状态列转移矩阵A，结果向量就是：

∑λ=0∞Aλx0=x0II−A

然后就完了。
脑残的我把E−A看成−A大概需要治疗

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. double A[405][805];
  5. int g[25][25], n, m, u, v, a, b;
  6. double p[25], eps = 1e-10;
  7. inline int num(int i, int j)
  8. { return (i-1)*n+j; }
  10. void inverse()
  11. {
  12.     for (int i = 1; i <= n*n; i++) A[i][i+n*n] = 1;
  13.     for (int i = 1; i <= n*n; i++) {
  14.         int k = i;
  15.         while (abs(A[k][i]) <= eps) k++;
  16.         swap(A[i], A[k]);
  17.         for (int j = 1; j <= n*n; j++) {
  18.             if (j == i) continue;
  19.             double tmp = -A[j][i]/A[i][i];
  20.             for (int k = 1; k <= 2*n*n; k++)
  21.                 A[j][k] += A[i][k]*tmp;//, printf("%f ",A[j][k]);
  22.         }
  23.     }
  24.     for (int i = 1; i <= n*n; i++)
  25.         for (int j = n*n+1; j <= n*n*2; j++)
  26.             A[i][j] /= A[i][i];
  27.     for (int i = 1; i <= n*n; i++)
  28.         for (int j = 1; j <= n*n; j++)
  29.             A[i][j] = A[i][j+n*n];
  30. }
  32. int main()
  33. {
  34.     scanf("%d%d%d%d", &n, &m, &a, &b);
  35.     for (int i = 1; i <= m; i++)
  36.         scanf("%d%d", &u, &v), g[u][v] = g[v][u] = 1, g[v][v]++, g[u][u]++;
  37.     for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);
  38.     for (int i = 1; i <= n; i++)
  39.         for (int j = 1; j <= n; j++)
  40.             for (int k = 1; k <= n; k++)
  41.                 for (int l = 1; l <= n; l++) { // (i,j)-->(k,l)
  42.                     if ((i == k || g[i][k]) && (g[j][l] || j==l)) {
  43.                         double ti = i==k?p[i]:(1-p[i])*1.0/g[i][i];
  44.                         double tj = j==l?p[j]:(1-p[j])*1.0/g[j][j];
  45.                         A[num(k,l)][num(i,j)] = -ti*tj;
  46.                     }
  47.                     if (i == j)
  48.                         A[num(k,l)][num(i,j)] = 0;
  49.                 }
  50.     for (int i = 1; i <= n*n; i++) A[i][i] += 1;
  51.     inverse();
  52.     for (int i = 1; i <= n; i++)
  53.         printf("%.6f ", A[num(i,i)][num(a,b)]);
  54.     return 0;
  55. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注