[关闭]
@ljt12138 2017-06-09T11:30:46.000000Z 字数 16497 阅读 968

各种OJ刷题记录5.31-6.8

bzoj2733: [HNOI2012]永无乡

以前用启发式合并做的，突然脑补出了线段树合并做法，比启发式合并快到不知哪里去了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. int n, m, k;
  7. int l[MAXN*20], r[MAXN*20], lc[MAXN*20], rc[MAXN*20], dat[MAXN*20];
  8. int top = 0;
  10. int build(int opl, int opr, int pos)
  11. {
  12.     int nd = ++top;
  13.     l[nd] = opl, r[nd] = opr, dat[nd] = 1;
  14.     if (opl < opr) {
  15.         int mid = (opl+opr)/2;
  16.         if (pos <= mid) lc[nd] = build(opl, mid, pos);
  17.         else rc[nd] = build(mid+1, opr, pos);
  18.     }
  19.     return nd;
  20. }
  22. int merge(int a, int b)
  23. {
  24.     if (a==0||b==0) return a+b;
  25.     dat[a] += dat[b];
  26.     lc[a] = merge(lc[a], lc[b]);
  27.     rc[a] = merge(rc[a], rc[b]);
  28.     return a;
  29. }
  31. int kth(int nd, int k)
  32. {
  33.     int l = 1, r = n;
  34.     while (l < r) {
  35.         int dt = dat[lc[nd]];
  36.         if (dt >= k) r = (l+r)/2, nd = lc[nd];
  37.         else k -= dt, l = (l+r)/2+1, nd = rc[nd];
  38.     }
  39.     return l;
  40. }
  42. int tr[MAXN];
  43. int fa[MAXN];
  44. inline int findf(int i)
  45. { return fa[i]?fa[i]=findf(fa[i]):i; }
  46. int atp[MAXN];
  48. int main()
  49. {
  50.     scanf("%d%d", &n, &m);
  51.     for (int i = 1; i <= n; i++) {
  52.         int d; scanf("%d", &d);
  53.         atp[d] = i;
  54.         tr[i] = build(1, n, d);
  55.     }
  56.     for (int i = 1; i <= m; i++) {
  57.         int u, v;
  58.         scanf("%d%d", &u, &v);
  59.         u = findf(u), v = findf(v);
  60.         if (u != v) fa[u] = v, tr[v] = merge(tr[u], tr[v]);
  61.     }
  62.     scanf("%d", &k);
  63.     char str[3];
  64.     int u, v;
  65.     for (int i = 1; i <= k; i++) {
  66.         scanf("%s %d %d", str, &u, &v);
  67.         if (str[0] == 'B') {
  68.             u = findf(u), v = findf(v);
  69.             if (u != v) fa[u] = v, tr[v] = merge(tr[u], tr[v]);
  70.         } else {
  71.             u = findf(u);
  72.             if (dat[tr[u]] < v) puts("-1");
  73.             else printf("%d\n", atp[kth(tr[u], v)]);
  74.         }
  75.     }
  76.     return 0;
  77. }

bzoj3996: [TJOI2015]线性代数

以前觉得挺神的题...推了推发现还是很水的。

容易发现：

由于是向量，有贡献当且仅当，而则在为时为负权，因此可以构造最大权闭合子图：为正权点，为负权点，依赖，然后套板子就好了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 501*501+1005;
  5. struct node {
  6.     int to, next, flow, neg;
  7. } edge[MAXN*10];
  8. int head[MAXN], top = 0;
  9. inline void push(int i, int j, int f)
  10. {
  11.     ++top, edge[top] = (node){j, head[i], f, top+1}, head[i] = top;
  12.     ++top, edge[top] = (node){i, head[j], 0, top-1}, head[j] = top;
  13. }
  15. int vis[MAXN], bfstime = 0;
  16. int lev[MAXN];
  17. int S = MAXN-3, T = MAXN-2;
  18. queue<int> que;
  20. bool bfs()
  21. {
  22.     vis[S] = ++bfstime, lev[S] = 0, que.push(S);
  23.     while (!que.empty()) {
  24.         int nd = que.front(); que.pop();
  25.         for (int i = head[nd]; i; i = edge[i].next) {
  26.             int to = edge[i].to, f = edge[i].flow;
  27.             if (vis[to] == bfstime || !f) continue;
  28.             vis[to] = bfstime, que.push(to), lev[to] = lev[nd]+1;
  29.         }
  30.     }
  31.     return vis[T] == bfstime;
  32. }
  34. int dfs(int nd, int flow)
  35. {
  36.     if (nd == T || !flow) return flow;
  37.     int ans = 0, t;
  38.     for (int i = head[nd]; i; i = edge[i].next) {
  39.         int to = edge[i].to, f = edge[i].flow;
  40.         if (lev[to] != lev[nd]+1 || !f) continue;
  41.         t = dfs(to, min(flow, f));
  42.         ans += t, edge[i].flow -= t;
  43.         edge[edge[i].neg].flow += t, flow -= t;
  44.     }
  45.     if (flow) lev[nd] = -1;
  46.     return ans;
  47. }
  49. int dinic()
  50. {
  51.     int ans = 0;
  52.     while (bfs()) ans += dfs(S, 233333333);
  53.     return ans;
  54. }
  56. int B[505][505], n, c[MAXN];
  58. int main()
  59. {
  60.     scanf("%d", &n);
  61.     int ans = 0;
  62.     for (int i = 1; i <= n; i++)
  63.         for (int j = 1; j <= n; j++)
  64.             scanf("%d", &B[i][j]), ans += B[i][j];
  65.     for (int i = 1; i <= n; i++)
  66.         scanf("%d", &c[i]);
  67.     for (int i = 1; i <= n; i++)
  68.         for (int j = 1; j <= n; j++) {
  69.             int dat = (i-1)*n+j;
  70.             push(S, dat, B[i][j]);
  71.             push(dat, n*n+i, 233333333);
  72.             push(dat, n*n+j, 233333333);
  73.         }
  74.     for (int i = 1; i <= n; i++)
  75.         push(n*n+i, T, c[i]);
  76.     cout << ans-dinic() << endl;
  77.     return 0;
  78. }

LYOI#158. 「上下界网络流」有源汇最小流

向Orz stdcall学习了一个上下界最大最小流的姿势：

  1. 上下界最小流：先求不加入的最大流，记录为，再在残量网络上加入，求最大流为。设辅助边容量和，则则无解，否则就是结果。
  2. 上下界最大流：先加入，跑一个的最大流；跑不满辅助边就无解。然后跑的最大流。结果就是上的流量。

这题需要当前弧一下，跑得比香港记者还快。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 50010, MAXM = 100227*10;
  5. struct node {
  6.     int to, next, flow, neg;
  7. } edge[MAXM];
  8. int head[MAXN], top = 0;
  9. inline void push(int i, int j, int f)
  10. {
  11.     ++top, edge[top] = (node){j, head[i], f, top+1}, head[i] = top; 
  12.     ++top, edge[top] = (node){i, head[j], 0, top-1}, head[j] = top;
  13. }
  15. int SS = 50007, ST = 50008;
  16. int inf = 2147483647;
  17. int lev[MAXN], vis[MAXN], bfstime = 0;
  18. queue<int> que;
  19. int n, m, s, t;
  21. bool bfs()
  22. {
  23.     lev[SS] = 1, vis[SS] = ++bfstime;
  24.     que.push(SS);
  25.     while (!que.empty()) {
  26.         int nd = que.front(); que.pop();
  27.         for (int i = head[nd]; i; i = edge[i].next) {
  28.             int to = edge[i].to, f = edge[i].flow;
  29.             if (vis[to] == bfstime || !f) continue;
  30.             lev[to] = lev[nd]+1, que.push(to), vis[to] = bfstime;
  31.         }
  32.     }
  33.     return vis[ST] == bfstime;
  34. }
  36. int cur[MAXN];
  38. long long dfs(int nd, int maxf)
  39. {
  40.     if (nd == ST || !maxf) return maxf;
  41.     long long ans = 0;
  42.     int t;
  43.     for (register int &i = cur[nd]; i; i = edge[i].next) {
  44.         int to = edge[i].to, f = edge[i].flow;
  45.         if (lev[to] != lev[nd]+1 || !f) continue;
  46.         t = dfs(to, min(f, maxf));
  47.         ans += t, maxf -= t;
  48.         edge[i].flow -= t, edge[edge[i].neg].flow += t;
  49.         if (!maxf) break;
  50.     }
  51.     if (maxf) lev[nd] = -1;
  52.     return ans;
  53. }
  55. long long dinic()
  56. {
  57.     long long ans = 0;
  58.     while (bfs()) {
  59.         for (int i = 1; i <= n; i++) cur[i] = head[i];
  60.         cur[SS] = head[SS], cur[ST] = head[ST];
  61.         ans += dfs(SS, inf);//, printf("%lld\n", ans);
  62.     }
  63.     return ans;
  64. }
  66. int main()
  67. {
  68.     scanf("%d%d%d%d", &n, &m, &s, &t);
  69.     long long cnt = 0;
  70.     for (int i = 1; i <= m; i++) {
  71.         int u, v, l, r;
  72.         scanf("%d%d%d%d", &u, &v, &l, &r);
  73.         push(u, v, r-l), push(SS, v, l), push(u, ST, l);
  74.         cnt += l;
  75.     }
  76.     long long k = dinic();
  77.     push(t, s, inf);
  78.     long long ans = dinic();
  79.     if (k+ans < cnt) puts("please go home to sleep");
  80.     else cout << ans << endl;
  81.     return 0;
  82. }

bzoj1492: [NOI2007]货币兑换Cash

好好做一个斜率优化...

首先是一个贪心性质，每次交易一定是的。

然后可以设为第天手上最多，为，为第天最多的钱，根据题目有：

然后找递推关系：

有：

后面的，对于一大堆点要最大化轴截距，则要维护一个上凸壳。然而这次斜率不随单调，因此不能用单调队列，而要用维护凸包。

考虑用分治解决这个问题。首先按斜率排序询问。过程用来求解内所有，并将按横坐标排序。考虑先划分成和；递归处理。然后得到了左边所有节点排好序的结果，用一个单调栈维护上凸壳。右边所有询问按斜率排序过了，直接扫一遍更新。然后就可以递归处理右边。

最后只剩一个问题，就是按排序。这里只要用归并两个区间就可以了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. int n, m;
  7. double f[MAXN];
  8. const double eps = 1e-7, inf = 1e9;
  10. struct query {
  11.     double a, b, r;
  12.     int pos;
  13.     inline double slop()
  14.     {
  15.         return -a/b; 
  16.     }
  17. } q[MAXN], tmp[MAXN];
  19. struct point {
  20.     double x, y;
  21.     friend bool operator < (const point &a, const point &b)
  22.     { return b.x-a.x>eps||(abs(b.x-a.x)<=eps && b.y-a.y > eps); }
  23. } stk[MAXN], p[MAXN], tmp_p[MAXN];
  24. int top;
  26. inline double slop(const point &a, const point &b)
  27. {
  28.         if (abs(a.x-b.x)<=eps) return -inf; 
  29.     return (a.y-b.y)/(a.x-b.x); 
  30. }
  32. bool cmp(query a, query b)
  33. { return a.slop() > b.slop(); }
  35. void solve(int l, int r)
  36. {
  37.     if (l == r) {
  38.         f[l] = max(f[l], f[l-1]);
  39.         p[l].y = f[l]/(q[l].a*q[l].r+q[l].b), p[l].x = q[l].r*p[l].y;
  40.         return;
  41.     }
  42.     int mid = (l+r)>>1, l1 = l, l2 = mid+1;
  43.     for (int i = l; i <= r; i++) {
  44.         if (q[i].pos <= mid) tmp[l1++] = q[i];
  45.         else tmp[l2++] = q[i];
  46.     }
  47.     for (int i = l; i <= r; i++)
  48.         q[i] = tmp[i];
  49.     solve(l, mid);
  50.     top = 0;
  51.     for (int i = l; i <= mid; i++) {
  52.         while (top >= 2 && slop(stk[top-1], stk[top]) < slop(stk[top], p[i])-eps) top--;
  53.         stk[++top] = p[i];
  54.     }
  55.     int lp = 1;
  56.     for (int i = mid+1; i <= r; i++) {
  57.         while (lp+1 <= top && slop(stk[lp], stk[lp+1]) > q[i].slop()-eps) lp++;
  58.         f[q[i].pos] = max(f[q[i].pos], stk[lp].x*q[i].a+stk[lp].y*q[i].b);
  59.     }
  60.     solve(mid+1, r);
  61.     int tp = l, a = l, b = mid+1;
  62.     while (a <= mid && b <= r) {
  63.         if (p[a] < p[b]) tmp_p[tp++] = p[a++];
  64.         else tmp_p[tp++] = p[b++];
  65.     }
  66.     while (a <= mid) tmp_p[tp++] = p[a++];
  67.     while (b <= r) tmp_p[tp++] = p[b++];
  68.     for (int i = l; i <= r; i++)
  69.         p[i] = tmp_p[i];
  70. }
  72. int main()
  73. {
  74.     // freopen("cash.in", "r", stdin);
  75.     // freopen("cash.out", "w", stdout);
  76.     scanf("%d%lf", &n, &f[0]);
  77.     for (int i = 1; i <= n; i++) {
  78.         scanf("%lf%lf%lf", &q[i].a, &q[i].b, &q[i].r);
  79.         q[i].pos = i;
  80.     }
  81.     sort(q+1, q+n+1, cmp);
  82.     solve(1, n);
  83.     printf("%.3f\n", f[n]);
  84.     return 0;
  85. }

cf717G. Underfail

题意：给定主串和模式串，每个模式串有权值，在某个位置匹配一次可以获取权值。主串每个位置最多被匹配次，问最大权值和。

首先用自动机找出所有的匹配位置（记录所有经过的位置，他在树上的祖先即是所有匹配位置），然后就变成了一个区间最大权覆盖的模型。

然后就是网络流套路（类似志愿者招募那个模型）了：

  1. 从，之间表示第个位置，容量为。
  2. 对于一个覆盖，，流量为，费用为

考虑增广路的形态，显然由于从左向右连，不会有相交环干扰，每一条增广路都是不相交的环组成的。而流量则限制了跨越他的环最多只有个，而下面的流量，所以存在一个的割，根据最大流最小割定理，，满足了最多被覆盖次的限制。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, m, p[105], x;
  5. int len[105];
  6. char str[505], s[505];
  8. const int MAXN = 500*100;
  10. struct node {
  11.     int to, next, flow, cost, neg;
  12. } edge[500*500];
  13. int head[MAXN], tp = 0;
  14. inline void push(int i, int j, int f, int c)
  15. {
  16.     ++tp, edge[tp] = (node){j, head[i], f, c, tp+1}, head[i] = tp;
  17.     ++tp, edge[tp] = (node){i, head[j], 0, -c, tp-1}, head[j] = tp;
  18. }
  20. int dis[MAXN], vis[MAXN];
  21. queue<int> q;
  22. int pre[MAXN], pre_edge[MAXN];
  23. int S = MAXN-3, T = MAXN-2;
  25. bool spfa(int &flow, int &cost)
  26. {
  27.     memset(dis, 127/3, sizeof dis);
  28.     dis[S] = 0, q.push(S), vis[S] = 1;
  29.     while (!q.empty()) {
  30.         int nd = q.front(); q.pop(); vis[nd] = 0;
  31.         // cerr << nd << endl;
  32.         for (int i = head[nd]; i; i = edge[i].next) {
  33.             int f = edge[i].flow, c = edge[i].cost;
  34.             int to = edge[i].to;
  35.             if (!f || dis[to] <= dis[nd]+c) continue;
  36.             dis[to] = dis[nd]+c, pre[to] = nd, pre_edge[to] = i;
  37.             if (!vis[to]) vis[to] = 1, q.push(to);
  38.         }
  39.     }
  40.     if (dis[T] >= 233333333) return 0;
  41.     int mf = INT_MAX;
  42.     for (int i = T; i != S; i = pre[i]) mf = min(mf, edge[pre_edge[i]].flow);
  43.     for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].flow -= mf, edge[edge[pre_edge[i]].neg].flow += mf;
  44.     flow += mf, cost += mf*dis[T];
  45.     return 1;
  46. }
  48. void mcf(int &flow, int &cost)
  49. { 
  50.     flow = cost = 0;
  51.     while (spfa(flow, cost));// printf("...%d\n", cost);
  52. }
  54. void push_edge(int l, int r, int v)
  55. {
  56.     push(l, r+1, 1, -v);
  57. }
  59. void push_init()
  60. {
  61.     for (int i = 1; i <= n; i++)
  62.         push(i, i+1, x, 0);
  63.     push(S, 1, x, 0), push(n+1, T, x, 0); 
  64. }
  66. int fail[MAXN], chl[MAXN][26], fin[MAXN];
  67. vector<int> pos[MAXN];
  68. int root = 0, top = 0;
  70. void push(int &nd, const char *str, int id)
  71. {
  72.     if (!nd) nd = ++top;
  73.     if (*str == '\0') fin[nd] = id;
  74.     else push(chl[nd][*str-'a'], str+1, id);
  75. }
  77. queue<int> que;
  79. void init()
  80. {
  81.     fail[root] = 0, que.push(root);
  82.     while (!que.empty()) {
  83.         int nd = que.front(); que.pop();
  84.         for (int i = 0; i < 26; i++) {
  85.             if (!chl[nd][i]) continue;
  86.             int p = fail[nd];
  87.             while (p && !chl[p][i]) p = fail[p];
  88.             if (p) fail[chl[nd][i]] = chl[p][i];
  89.             else fail[chl[nd][i]] = root;
  90.             que.push(chl[nd][i]);
  91.         }
  92.     }
  93. }
  95. void match(int nd, const char *str, int ps)
  96. {
  97.     for (int i = nd; i; i = fail[i]) 
  98.         if (fin[i]) push_edge(ps-len[fin[i]]+1, ps, p[fin[i]]);
  99.     if (*str == '\0') return;
  100.     while (nd && !chl[nd][*str-'a']) nd = fail[nd];
  101.     if (!nd) match(root, str+1, ps+1);
  102.     else match(chl[nd][*str-'a'], str+1, ps+1);
  103. }
  105. int main()
  106. {
  107.     scanf("%d", &n);
  108.     scanf("%s", str);
  109.     scanf("%d", &m);
  110.     for (int i = 1; i <= m; i++) {
  111.         scanf("%s %d", s, &p[i]), len[i] = strlen(s);
  112.         push(root, s, i);
  113.     }
  114.     scanf("%d", &x);
  115.     push_init();
  116.     init();
  117.     match(root, str, 0);
  118.     int flow = 0, cost = 0;
  119.     mcf(flow, cost);
  120.     cout << -cost << endl;
  121.     return 0;
  122. }

bzoj3622: 已经没有什么好害怕的了

广义容斥原理...
http://www.cnblogs.com/candy99/p/6617195.html

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 2005;
  5. int sug[MAXN], med[MAXN], n, k;
  6. int cnt[MAXN], fac[MAXN];
  7. const int mod = 1e9+9;
  8. int f[MAXN][MAXN], a[MAXN];
  10. int power(int a, int n)
  11. {
  12.     int b = a, ans = 1;
  13.     for (int i = 0; i <= 30; i++) {
  14.         if (n&(1<<i)) ans = (long long)ans*b%mod;
  15.         b = (long long)b*b%mod;
  16.     }
  17.     return ans;
  18. }
  20. int inv(int a)
  21. { return power(a, mod-2); }
  23. int choose(int n, int k)
  24. { return (long long)fac[n]*inv(fac[k])%mod*inv(fac[n-k])%mod; }
  26. int main()
  27. {
  28.     scanf("%d%d", &n, &k);
  29.     if ((n+k)&1) { printf("0\n"); return 0; }
  30.     else k = (n+k)>>1;
  31.     for (int i = 1; i <= n; i++) scanf("%d", &sug[i]);
  32.     for (int i = 1; i <= n; i++) scanf("%d", &med[i]);
  33.     fac[0] = 1;
  34.     for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i-1]*i%mod;
  35.     sort(sug+1, sug+n+1), sort(med+1, med+n+1);
  36.     int l = 0;
  37.     for (int i = 1; i <= n; i++) {
  38.         while (l < n && med[l+1] < sug[i]) l++;
  39.         cnt[i] = l;
  40.     }
  41.     f[0][0] = 1;
  42.     for (int i = 1; i <= n; i++) {
  43.         for (int j = 0; j <= n; j++) {
  44.             f[i][j] = f[i-1][j];
  45.             if (j>0)
  46.                 f[i][j] = (f[i][j]+(long long)f[i-1][j-1]*max(cnt[i]-j+1, 0)%mod)%mod;
  47.         }
  48.     }
  49.     for (int i = 0; i <= n; i++) a[i] = (long long)f[n][i]*fac[n-i]%mod;
  50.     int ans = 0;
  51.     for (int i = k; i <= n; i++) 
  52.         ans = (ans+(((i-k)&1)?-1:1)*(long long)choose(i, k)*a[i]%mod)%mod;
  53.     cout << (ans%mod+mod)%mod << endl;
  54.     return 0;
  55. }

bzoj3339: Rmq Problem

常规方法不太好处理。
hzwer给出了一个思路：将询问按排序，用数据结构维护当前左端点下各个右端点的结果。然后计算每次移动左区间对后面值的影响。

具体到这道题，首先用并查集或者树状数组上二分求出初始时的，并预处理出每个值下一个这种值的位置。考虑更新到的影响就是将中所有大于的变成，也就是取。这显然可以用线段树维护。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005, inf = 233333333;
  6. int fa[MAXN];
  7. inline int findf(int nd)
  8. { return fa[nd]!=nd?fa[nd]=findf(fa[nd]):nd; }
  9. void link(int i, int j)
  10. {
  11.     int a = findf(i), b = findf(j);
  12.     if (a != b) fa[a] = b;
  13. }
  14. int a[MAXN], nxt[MAXN], now[MAXN];
  15. int n, q;
  16. int mex[MAXN];
  18. struct tree {
  19.     int l[MAXN*4], r[MAXN*4], lc[MAXN*4], rc[MAXN*4], tag[MAXN*4], dat[MAXN*4];
  20.     int top, root;
  21.     void clear()
  22.     { top = root = 0; }
  23.     void build(int &nd, int opl, int opr)
  24.     {
  25.         nd = ++top, l[nd] = opl, r[nd] = opr, tag[nd] = inf;
  26.         if (opl < opr)
  27.             build(lc[nd], opl, (opl+opr)>>1), build(rc[nd], ((opl+opr)>>1)+1, opr);
  28.         else dat[nd] = mex[opl];
  29.     }
  30.     void pdw(int nd)
  31.     {
  32.         if (tag[nd] == inf) return;
  33.         if (lc[nd]) tag[lc[nd]] = min(tag[lc[nd]], tag[nd]), tag[rc[nd]] = min(tag[rc[nd]], tag[nd]), tag[nd] = inf;
  34.         else dat[nd] = min(dat[nd], tag[nd]), tag[nd] = inf;
  35.     }
  36.     void modify(int nd, int opl, int opr, int dt) // 区间内大于dt的变为dt
  37.     {
  38.         if (opl > opr) return;
  39.         pdw(nd);
  40.         if (l[nd] == opl && r[nd] == opr) tag[nd] = min(tag[nd], dt);
  41.         else {
  42.             int mid = (l[nd]+r[nd])>>1;
  43.             if (opr <= mid) modify(lc[nd], opl, opr, dt);
  44.             else if (opl > mid) modify(rc[nd], opl, opr, dt);
  45.             else modify(lc[nd], opl, mid, dt), modify(rc[nd], mid+1, opr, dt);
  46.         }
  47.     }
  48.     int query(int nd, int dt)
  49.     {
  50.         pdw(nd);
  51.         if (l[nd] == r[nd]) return dat[nd];
  52.         else {
  53.             int mid = (l[nd]+r[nd])>>1;
  54.             if (dt <= mid) return query(lc[nd], dt);
  55.             else return query(rc[nd], dt);
  56.         }
  57.     }
  58. } seg;
  60. int last[MAXN];
  62. struct qy {
  63.     int l, r, id, ans;
  64.     friend bool operator < (const qy &a, const qy &b)
  65.     { return a.l < b.l; }
  66. } qs[MAXN];
  68. int ans[MAXN];
  69. int main()
  70. {
  71.     scanf("%d%d", &n, &q);
  72.     for (int i = 0; i <= n; i++) fa[i] = i;
  73.     for (int i = 1; i <= n; i++) 
  74.         scanf("%d", &a[i]);
  75.     for (int i = 1; i <= n; i++) {
  76.         now[a[i]] = 1;
  77.         if (a[i]-1>=0&&now[a[i]-1]) link(a[i]-1, a[i]);
  78.         if (now[a[i]+1]) link(a[i], a[i]+1);
  79.         mex[i] = now[0]?findf(0)+1:0;
  80.     } // 并查集维护初始mex
  81.     for (int i = 1; i <= n; i++) {
  82.         if (last[a[i]]) nxt[last[a[i]]] = i;
  83.         last[a[i]] = i;
  84.     }
  85.     for (int i = 1; i <= n; i++)
  86.         if (nxt[i] == 0) nxt[i] = n+1;
  87.     seg.build(seg.root, 1, n); // 初始值
  88.     for (int i = 1; i <= q; i++) scanf("%d%d", &qs[i].l, &qs[i].r), qs[i].id = i;
  89.     sort(qs+1, qs+q+1);
  90.     int now = 1;
  91.     for (int i = 1; i <= n; i++) {
  92.         while (now <= q && qs[now].l == i) {
  93.             ans[qs[now].id] = seg.query(seg.root, qs[now].r);
  94.             now++;
  95.         }
  96.         seg.modify(seg.root, i, nxt[i]-1, a[i]);
  97.     }
  98.     for (int i = 1; i <= q; i++)
  99.         printf("%d\n", ans[i]);
  100.     return 0;
  101. }

COGS2648.[IOI2011]Race

1A了...感慨万千...

OI中摩尔定律：知识量随时间以指数增长，题目难度随时间以指数降低。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005;
  5. struct node {
  6.     int to, next, dis;
  7. } edge[MAXN*2];
  8. int head[MAXN], top = 0;
  9. void push(int i, int j, int d)
  10. { edge[++top] = (node){j, head[i], d}, head[i] = top; }
  12. int siz[MAXN], vis[MAXN];
  14. void dfs_siz(int nd, int f)
  15. {
  16.     siz[nd] = 1;
  17.     for (int i = head[nd]; i; i = edge[i].next) {
  18.         int to = edge[i].to;
  19.         if (to == f || vis[to]) continue;
  20.         dfs_siz(to, nd), siz[nd] += siz[to];
  21.     }
  22. }
  24. void dfs_sel(int nd, int f, const int totsiz, int &ans, int &maxl)
  25. {
  26.     int maxs = 0;
  27.     if (f) maxs = totsiz-siz[nd];
  28.     for (int i = head[nd]; i; i = edge[i].next) {
  29.         int to = edge[i].to;
  30.         if (to == f || vis[to]) continue;
  31.         maxs = max(maxs, siz[to]);
  32.     }
  33.     if (maxs < maxl) maxl = maxs, ans = nd;
  34.     for (int i = head[nd]; i; i = edge[i].next) {
  35.         int to = edge[i].to;
  36.         if (to == f || vis[to]) continue;
  37.         dfs_sel(to, nd, totsiz, ans, maxl);
  38.     }
  39. }
  41. int sig[1000005];
  42. int n, k, pans = 233333333, cnt = 233333333;
  43. void dfs_calc(int nd, int f, int dep, int now_len)
  44. {
  45.     if (now_len > k) return;
  46.     cnt = min(cnt, sig[k-now_len]+dep);
  47.     for (int i = head[nd]; i; i = edge[i].next) {
  48.         int to = edge[i].to;
  49.         if (to == f || vis[to]) continue;
  50.         dfs_calc(to, nd, dep+1, now_len+edge[i].dis);
  51.     }
  52. }
  54. void dfs_mod(int nd, int f, int dep, int now_len)
  55. {
  56.     if (now_len > k) return;
  57.     sig[now_len] = min(sig[now_len], dep);
  58.     for (int i = head[nd]; i; i = edge[i].next) {
  59.         int to = edge[i].to;
  60.         if (to == f || vis[to]) continue;
  61.         dfs_mod(to, nd, dep+1, now_len+edge[i].dis);
  62.     }
  63. }
  65. void dfs_dec(int nd, int f, int dep, int now_len)
  66. {
  67.     if (now_len > k) return;
  68.     sig[now_len] = 233333333;
  69.     for (int i = head[nd]; i; i = edge[i].next) {
  70.         int to = edge[i].to;
  71.         if (to == f || vis[to]) continue;
  72.         dfs_dec(to, nd, dep+1, now_len+edge[i].dis);
  73.     }
  74. }
  76. void calc(int nd)
  77. {
  78.     dfs_siz(nd, 0);
  79.     int center = 0, ans = 233333333;
  80.     dfs_sel(nd, 0, siz[nd], center, ans);
  81.     // cerr << center << endl;
  82.     vis[center] = 1, cnt = 233333333, sig[0] = 0;
  83.     for (int i = head[center]; i; i = edge[i].next) {
  84.         int to = edge[i].to, d = edge[i].dis;
  85.         if (vis[to]) continue;
  86.         dfs_calc(to, 0, 1, d), dfs_mod(to, 0, 1, d);
  87.         // cerr << to << endl;
  88.         // for (int j = 1; j <= k; j++)
  89.         //  cerr << sig[j] << " ";
  90.         // cerr << endl << cnt << endl;
  91.     }
  92.     pans = min(pans, cnt);
  93.     // cerr << "gg" << ans << endl;
  94.     dfs_dec(center, 0, 0, 0);
  95.     for (int i = head[center]; i; i = edge[i].next) {
  96.         int to = edge[i].to;
  97.         if (vis[to]) continue;
  98.         calc(to);
  99.     }
  100. }
  102. int main()
  103. {
  104.     freopen("ioi2011-race.in", "r", stdin);
  105.     freopen("ioi2011-race.out", "w", stdout);
  106.     int size = 128 << 20;
  107.     char *p = (char*)malloc(size) + size;  
  108.     __asm__("movl %0, %%esp\n" :: "r"(p));
  109.     memset(sig, 127/3, sizeof sig);
  110.     scanf("%d%d", &n, &k);
  111.     for (int i = 1; i < n; i++) {
  112.         int u, v, d;
  113.         scanf("%d%d%d", &u, &v, &d), u++, v++;
  114.         push(u, v, d), push(v, u, d);
  115.     }
  116.     calc(1);
  117.     if (pans < 2333333)
  118.         cout << pans << endl;
  119.     else puts("-1");
  120.     return 0;
  121. }

bzoj2879: [Noi2012]美食节

学习了一个动态加边。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 40+80*100+5;
  5. struct node {
  6.     int to, next, flow, cost, neg;
  7. } edge[MAXN*20];
  8. int head[MAXN], top = 0;
  9. void push(int i, int j, int f, int c)
  10. {
  11.     // printf("%d--%d,%d-->%d\n", i, f, c, j);
  12.     ++top, edge[top] = (node){j, head[i], f, c, top+1}, head[i] = top;
  13.     ++top, edge[top] = (node){i, head[j], 0, -c, top-1}, head[j] = top;
  14. }
  16. int dis[MAXN], vis[MAXN], pre[MAXN], pre_edge[MAXN];
  17. queue<int> que;
  18. int S = MAXN-5, T = MAXN-4;
  19. int inf = 23333333;
  21. bool spfa(int &flow, int &cost)
  22. {
  23.     memset(dis, 127/3, sizeof dis);
  24.     memset(vis, 0, sizeof vis);
  25.     vis[S] = 1, que.push(S), dis[S] = 0;
  26.     while (!que.empty()) {
  27.         int nd = que.front(); que.pop(); vis[nd] = 0;
  28.         // cerr << nd << endl;
  29.         for (int i = head[nd]; i; i = edge[i].next) {
  30.             int to = edge[i].to, f = edge[i].flow, c = edge[i].cost;
  31.             if (!f || dis[to] <= dis[nd]+c) continue;
  32.             dis[to] = dis[nd]+c;
  33.             pre[to] = nd, pre_edge[to] = i;
  34.             if (!vis[to]) 
  35.                 vis[to] = 1, que.push(to);
  36.         }
  37.     }
  38.     // cerr << dis[T] << endl;
  39.     if (dis[T] > inf) return 0;
  40.     int maxf = inf;
  41.     for (int i = T; i != S; i = pre[i]) maxf = min(maxf, edge[pre_edge[i]].flow);
  42.     for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].flow -= maxf, edge[edge[pre_edge[i]].neg].flow += maxf;
  43.     flow += maxf, cost += maxf*dis[T];
  44.     return 1;
  45. }
  47. int id[MAXN], k[MAXN], dish[MAXN], n, m;
  48. int top_tp = 0;
  49. int t[45][505], p[45];
  51. void mcf(int &flow, int &cost)
  52. {
  53.     flow = cost = 0;
  54.     while (spfa(flow, cost)) {
  55.         int x = pre[T];
  56.         // cerr << "id " << x << endl;
  57.         x = id[x];
  58.         k[x]++, id[++top_tp] = x;
  59.         for (int i = 1; i <= n; i++)
  60.             push(dish[i], top_tp, 1, k[x]*t[i][x]);
  61.         push(top_tp, T, 1, 0);
  62.         // printf("---%d\n", flow);
  63.     } 
  64. }
  66. int main()
  67. {   
  68.     scanf("%d%d", &n, &m);
  69.     for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  70.     for (int i = 1; i <= n; i++) 
  71.         for (int j = 1; j <= m; j++)
  72.             scanf("%d", &t[i][j]);
  73.     for (int i = 1; i <= n; i++) dish[i] = ++top_tp;
  74.     for (int i = 1; i <= n; i++) push(S, dish[i], p[i], 0);
  75.     for (int i = 1; i <= m; i++) {
  76.         id[++top_tp] = i, k[i]++;
  77.         for (int j = 1; j <= n; j++)
  78.             push(dish[j], top_tp, 1, k[i]*t[j][i]);
  79.         push(top_tp, T, 1, 0);
  80.     }
  81.     int flow, cost;
  82.     // puts("---");
  83.     mcf(flow, cost);
  84.     cout << cost << endl;
  85.     return 0;
  86. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注