[关闭]
@ljt12138 2017-04-13T23:43:36.000000Z 字数 18066 阅读 818

bzoj刷题记录4.10-4.14

bzoj1093: [ZJOI2007]最大半联通子图

仍然缩点。缩完点之后每个半联通子图就相当于一条带权链（权值是一个scc的点数）。之后dp即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005, MAXM = 2000005;
  5. struct g {
  6.     struct node {
  7.         int to, next;
  8.     } edge[MAXM];
  9.     int head[MAXN], top;
  10.     g(){ top = 0, memset(head, 0, sizeof head); }
  11.     void push(int i, int j)
  12.     { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  13. }g, g1;
  15. int dfn[MAXN], low[MAXN], stk[MAXN], top = 0, dft = 0;
  16. int gp[MAXN], gtop = 0, gsiz[MAXN], vis[MAXN], n, m;
  18. void tarjan(int nd)
  19. {
  20.     dfn[nd] = low[nd] = ++dft;
  21.     stk[++top] = nd, vis[nd] = 1;
  22.     for (int i = g.head[nd]; i; i = g.edge[i].next) {
  23.         int to = g.edge[i].to;
  24.         if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
  25.         else if (vis[to]) low[nd] = min(low[nd], dfn[to]);
  26.     }
  27.     if (dfn[nd] == low[nd]) {
  28.         int now; ++gtop;
  29.         do {
  30.             now = stk[top--], vis[now] = 0, gp[now] = gtop, gsiz[gtop]++;
  31.         } while (now != nd);
  32.     }
  33. }
  35. long long x;
  37. set<pair<int,int> > hst;
  39. int dp[MAXN], cnt[MAXN];
  41. int dfs(int nd)
  42. {
  43.     if (dp[nd] != -1) return dp[nd];
  44.     dp[nd] = gsiz[nd];
  45.     for (int i = g1.head[nd]; i; i = g1.edge[i].next)
  46.         dp[nd] = max(dp[nd], dfs(g1.edge[i].to)+gsiz[nd]);
  47.     return dp[nd];
  48. }
  50. int dfs_cnt(int nd)
  51. {
  52.     if (cnt[nd] != -1) return cnt[nd];
  53.     if (!g1.head[nd]) return 1%x;
  54.     cnt[nd] = 0;
  55.     for (int i = g1.head[nd]; i; i = g1.edge[i].next) {
  56.         int to = g1.edge[i].to;
  57.         if (dp[nd] == dp[to] + gsiz[nd]) (cnt[nd] += dfs_cnt(to)) %= x;
  58.     }
  59.     return cnt[nd];
  60. }
  62. void work()
  63. {
  64.     for (int i = 1; i <= n; i++)
  65.         if (!dfn[i])
  66.             tarjan(i);
  67.     for (int i = 1; i <= n; i++)
  68.         for (int j = g.head[i]; j; j = g.edge[j].next) {
  69.             int to = g.edge[j].to;
  70.             if (gp[i] != gp[to] && !hst.count(make_pair(gp[i], gp[to]))) {
  71.                 hst.insert(make_pair(gp[i], gp[to]));
  72.                 g1.push(gp[to], gp[i]); // G^R
  73.             }
  74.         }
  75.     memset(dp, -1, sizeof dp), memset(cnt, -1, sizeof cnt);
  76.     int ans1; long long ans2; ans1 = ans2 = 0;
  77.     for (int i = 1; i <= gtop; i++)
  78.         ans1 = max(ans1, dfs(i));
  79.     for (int i = 1; i <= gtop; i++)
  80.         if (dfs(i) == ans1)
  81.             (ans2 += dfs_cnt(i)) %= x;
  82.     printf("%d\n%lld\n", ans1, ans2);
  83. }
  84. int main()
  85. {
  86.     scanf("%d%d%lld", &n, &m, &x);
  87.     for (int i = 1; i <= m; i++) {
  88.         int u, v; scanf("%d%d", &u, &v), g.push(u, v);
  89.     }
  90.     work();
  91.     return 0;
  92. }

bzoj2208: [JSOI2010] 联通数

缩点后暴力可过..
但是貌似有更好的算法？？比如在拓扑图上随意dfs一棵生成树然后dfs序维护？？
尚不清楚复杂度是否更优。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 2005, MAXM = MAXN*MAXN;
  5. struct graph {
  6.     struct node {
  7.         int to, next;
  8.     } edge[MAXM];
  9.     int head[MAXN], top;
  10.     graph(){top = 0, memset(head, 0, sizeof head); }
  11.     void push(int i, int j)
  12.     { ++top, edge[top] = (node) {j, head[i]}, head[i] = top; }
  13. } g, g1;
  15. int dfn[MAXN], dft = 0, low[MAXN], vis[MAXN];
  16. int stk[MAXN], top = 0;
  17. int gp[MAXN], gtop = 0, gsiz[MAXN], n;
  19. void tarjan(int nd)
  20. {
  21.     vis[nd] = 1, dfn[nd] = low[nd] = ++dft, stk[++top] = nd;
  22.     for (int i = g.head[nd]; i; i = g.edge[i].next) {
  23.         int to = g.edge[i].to;
  24.         if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
  25.         else if (vis[to]) low[nd] = min(low[nd], dfn[to]);
  26.     }
  27.     if (dfn[nd] == low[nd]) {
  28.         int now; ++gtop; //printf(" -- Group %d --\n", gtop);
  29.         do {
  30.             now = stk[top--];
  31.             gp[now] = gtop, gsiz[gtop]++, vis[now] = 0;
  32.             // cerr << now << " ";
  33.         } while(now != nd); //puts("");
  34.     }
  35. }
  37. int bfstime = 0;
  38. queue<int> que;
  39. int lkt[MAXN][MAXN];
  41. void work()
  42. {
  43.     for (int i = 1; i <= n; i++)
  44.         if (!dfn[i])
  45.             tarjan(i);
  46.     for (int i = 1; i <= n; i++)
  47.         for (int j = g.head[i]; j; j = g.edge[j].next) {
  48.             int to = g.edge[j].to;
  49.             if (gp[to] != gp[i] && !lkt[gp[i]][gp[to]]) {
  50.                 lkt[gp[i]][gp[to]] = 1;
  51.                 g1.push(gp[i], gp[to]);
  52.             }
  53.         }
  54.     int ans = 0;
  55.     memset(vis, 0, sizeof vis);
  56.     for (int i = 1; i <= gtop; i++) {
  57.         ++bfstime;
  58.         que.push(i), vis[i] = bfstime;
  59.         int cnt = 0;
  60.         while (!que.empty()) {
  61.             int t = que.front(); que.pop(), cnt += gsiz[t];
  62.             for (int i = g1.head[t]; i; i = g1.edge[i].next) {
  63.                 int to = g1.edge[i].to;
  64.                 if (vis[to] != bfstime)
  65.                     vis[to] = bfstime, que.push(to);
  66.             }
  67.         }
  68.         ans += cnt*gsiz[i];
  69.     }
  70.     cout << ans << endl;
  71. }
  73. char str[2005];
  74. int main()
  75. {
  76.     scanf("%d", &n);
  77.     for (int i = 1; i <= n; i++) {
  78.         scanf("%s", str+1);
  79.         for (int j = 1; j <= n; j++)
  80.             if (str[j] == '1')
  81.                 g.push(i, j);
  82.     }
  83.     work();
  84.     return 0;
  85. }

4.11 更新

今天来一波字符串。

bzoj3172: [Tjoi2013]单词

这个题就比较神了。首先建出AC自动机，然后先求出每个节点的“顺着路过的总数dp[nd]”，也就是trie树上子树finish标记的总数；然后每个节点表示的串出现的次数就是某个节点fail树的子树中所有dp[nd]的总和。

第一次做反了...
形如

  1. sher
  2. shers
  3. her

的数据可以hack。因为shers不会算入her中去。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 3000005;
  5. int chl[MAXN][26], fail[MAXN], fin[MAXN], top = 0, root = 0;
  6. vector<int> ids[MAXN];
  7. int new_node()
  8. { return ++top, fail[top] = fin[top] = 0, memset(chl[top],0, sizeof chl[top]), top; }
  10. void push(int &nd, const char *str, int id)
  11. {
  12.     if (nd == 0) nd = new_node();
  13.     if (*str == '\0') fin[nd]++, ids[nd].push_back(id);
  14.     else push(chl[nd][*str-'a'], str+1, id);
  15. }
  17. struct node {
  18.     int to, next;
  19. } edge[MAXN];
  20. int head[MAXN], tp_edge = 0;
  21. void push(int i, int j)
  22. { ++tp_edge, edge[tp_edge] = (node) {j, head[i]}, head[i] = tp_edge; }
  23. int siz[MAXN], n;
  25. queue<int> que;
  26. void init()
  27. {
  28.     que.push(root); fail[root] = 0;
  29.     while (!que.empty()) {
  30.         int t = que.front(); que.pop();
  31.         for (int i = 0; i < 26; i++) if (chl[t][i]) {
  32.             int p = fail[t];
  33.             while (p && !chl[p][i]) p = fail[p];
  34.             if (!p) fail[chl[t][i]] = root;
  35.             else fail[chl[t][i]] = chl[p][i];
  36.             que.push(chl[t][i]);
  37.             push(fail[chl[t][i]], chl[t][i]);
  38.         }
  39.     }
  40. }
  42. long long res[MAXN];
  43. long long dp[MAXN];
  45. int dfs(int nd)
  46. {
  47.     if (siz[nd] != -1) return siz[nd];
  48.     siz[nd] = dp[nd];
  49.     for (int i = head[nd]; i; i = edge[i].next) {
  50.         int to = edge[i].to;
  51.         siz[nd] += dfs(to);
  52.     }
  53.     return siz[nd];
  54. }
  56. long long dfs2(int nd)
  57. {
  58.     if (dp[nd] != -1) return dp[nd];
  59.     dp[nd] = fin[nd];
  60.     for (int i = 0; i < 26; i++)
  61.         if (chl[nd][i])
  62.             dp[nd] += dfs2(chl[nd][i]);
  63.     return dp[nd];
  64. }
  66. char str[MAXN];
  68. int main()
  69. {
  70.     scanf("%d", &n);
  71.     for (int i = 1; i <= n; i++) {
  72.         scanf("%s", str);
  73.         push(root, str, i);
  74.     }
  75.     init();
  76.     memset(siz, -1, sizeof siz);
  77.     memset(dp, -1, sizeof dp);
  78.     dfs2(root);
  79.     dfs(root);
  80.     for (int i = 1; i <= top; i++)
  81.         for (int j = 0; j < fin[i]; j++)
  82.             res[ids[i][j]] = siz[i];
  83.     for (int i = 1; i <= n; i++)
  84.         printf("%lld\n", res[i]);
  85.     return 0;
  86. }

bzoj1090: [SCOI2003]字符串折叠

首先|S|≤100告诉我们必然不是什么高端结构...

区间dp是正解，方程容易想到，唯一的字符串trick就是用hashk判断相等。

特别注意取某一区间hash的小技巧。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 105;
  5. char str[MAXN];
  6. int n;
  7. unsigned long long hash_tab[MAXN], pwr[MAXN];
  9. unsigned long long hash_val(int i, int j)
  10. { return hash_tab[j]-hash_tab[i-1]*pwr[j-i+1]; }
  12. int dp[MAXN][MAXN];
  14. int len(int num)
  15. { return num <= 9 ? 1 : (num <= 99 ? 2 : 3); }
  17. int dfs(int i, int j)
  18. {
  19.     if (dp[i][j] != -1) return dp[i][j];
  20.     if (i == j) return 1;
  21.     dp[i][j] = INT_MAX;
  22.     for (int k = i; k < j; k++)
  23.         dp[i][j] = min(dp[i][j], dfs(i,k)+dfs(k+1,j));
  24.     for (int k = 1; k <= j-i+1; k++) { // 枚举每一块长度
  25.         if ((j-i+1)%k != 0) continue;
  26.         int flag = 1; unsigned long long val = 0;
  27.         for (int p = 0; p < (j-i+1)/k; p++) {
  28.             if (p == 0) val = hash_val(i+p*k, i+(p+1)*k-1);
  29.             else if (val != hash_val(i+p*k, i+(p+1)*k-1)) { flag = 0; break; }
  30.         }
  31.         if (flag) dp[i][j] = min(dp[i][j], dfs(i, i+k-1)+2+len((j-i+1)/k));
  32.     }
  33.     return dp[i][j];
  34. }
  35. int main()
  36. {
  37.     scanf("%s", str+1), n = strlen(str+1);
  38.     pwr[0] = 1;
  39.     for (int i = 1; i <= n; i++) pwr[i] = pwr[i-1]*31;
  40.     for (int i = 1; i <= n; i++) hash_tab[i] = hash_tab[i-1]*31+(str[i]-'A'+1);
  41.     memset(dp, -1, sizeof dp);
  42.     cout << dfs(1, n) << endl;
  43.     return 0;
  44. }

bzoj2124: 等差子序列

乍一看和字符串毫无关系...
事实上，存在一个等差数列当且仅当存在三个点i<j<k，满足：

ai=aj+d,ak=aj−d

然后对于这种对称的处理思路就两种：

  1. FFT
  2. 回文串

FFT貌似不太好处理，但回文串很兹瓷啊。用线段树记录每个点是否存在1/2并维护区间哈希，然后正反算哈希判断是不是相等即可。如果在某一时刻i，ai两侧不对称，就必然有一段回文串，也就有等差数列。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 10005;
  5. unsigned long long hash_tab[MAXN*4], hash_rev[MAXN*4], power[MAXN];
  6. int lc[MAXN*4], rc[MAXN*4], l[MAXN*4], r[MAXN*4], top = 0, root = 0;
  7. int n, a[MAXN];
  9. inline int siz(int nd) { return r[nd]-l[nd]+1; }
  10. void build(int &nd, int opl, int opr)
  11. {
  12.     nd = ++top, hash_tab[nd] = hash_rev[nd] = 1, lc[nd] = rc[nd] = 0, l[nd] = opl, r[nd] = opr;
  13.     if (opl < opr) {
  14.         build(lc[nd], opl, (opl+opr)/2), build(rc[nd], (opl+opr)/2+1, opr);
  15.         hash_tab[nd] = hash_tab[lc[nd]]+power[siz(lc[nd])]*hash_tab[rc[nd]];
  16.         hash_rev[nd] = hash_rev[rc[nd]]+power[siz(rc[nd])]*hash_rev[lc[nd]];
  17.     }
  18. }
  19. void modify(int nd, int pos)
  20. {
  21.     if (l[nd] == r[nd]) hash_tab[nd] = hash_rev[nd] = 2;
  22.     else {
  23.         modify(pos<=(l[nd]+r[nd])/2?lc[nd]:rc[nd], pos);
  24.         hash_tab[nd] = hash_tab[lc[nd]]+power[siz(lc[nd])]*hash_tab[rc[nd]];
  25.         hash_rev[nd] = hash_rev[rc[nd]]+power[siz(rc[nd])]*hash_rev[lc[nd]];
  26.     }
  27. }
  28. unsigned long long query(int nd, int opl, int opr)
  29. {
  30.     if (l[nd] == opl && r[nd] == opr) return hash_tab[nd];
  31.     else {
  32.         int mid = (l[nd]+r[nd])/2;
  33.         if (opr <= mid) return query(lc[nd], opl, opr);
  34.         else if (opl > mid) return query(rc[nd], opl, opr);
  35.         else return query(lc[nd], opl, mid)+power[mid-opl+1]*query(rc[nd], mid+1, opr);
  36.     }
  37. }
  38. unsigned long long query_reversed(int nd, int opl, int opr)
  39. {
  40.     if (l[nd] == opl && r[nd] == opr) return hash_rev[nd];
  41.     else {
  42.         int mid = (l[nd]+r[nd])/2;
  43.         if (opr <= mid) return query_reversed(lc[nd], opl, opr);
  44.         else if (opl > mid) return query_reversed(rc[nd], opl, opr);
  45.         else return power[opr-mid]*query_reversed(lc[nd], opl, mid)+query_reversed(rc[nd], mid+1, opr);
  46.     }
  47. }
  48. void init()
  49. {
  50.     scanf("%d", &n);
  51.     top = root = 0;
  52.     build(root, 1, n);
  53.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  54. }
  55. int main()
  56. {
  57.     int T; scanf("%d", &T);
  58.     power[0] = 1;
  59.     for (int i = 1; i <= 10000; i++) power[i] = power[i-1]*31;
  60.     while (T--) {
  61.         init();
  62.         int flag = 0;
  63.         for (int i = 1; i <= n; i++) {
  64.             // cerr << query(root, 1, 3) << "--" << query_reversed(root, 1, 3) << endl;
  65.             if (a[i] <= n-a[i]+1) {
  66.                 if (i >= 2 && i < n && query(root, 1, 2*a[i]-1) != query_reversed(root, 1, 2*a[i]-1)) {
  67.                     flag = 1; break;
  68.                 }
  69.             } else {
  70.                 int k = 2*(n-a[i]+1)-1;
  71.                 if (i >= 2 && i < n && query(root, n-k+1, n) != query_reversed(root, n-k+1, n)) {
  72.                     flag = 1; break;
  73.                 }
  74.             }
  75.             modify(root, a[i]);
  76.         }
  77.         if (flag) puts("Y");
  78.         else puts("N");
  79.     }
  80.     return 0;
  81. }

bzoj3207: 花神的嘲讽计划Ⅰ

首先k≤20就可以暴力算出来每个块的哈希，然后就变成一个在区间内有没有某个值的问题了。莫队可解，O(nn√)但跑比谁都快。

注意：hash一定要用ull...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 400005, lgn = 20;
  5. int n, m, k, bas, sqr;
  7. unsigned long long hash_val(int a[], int l, int r)
  8. {
  9.     unsigned long long ans = 0;
  10.     for (int i = l; i <= r; i++)
  11.         ans = ans*bas+a[i];
  12.     return ans;
  13. }
  15. struct query {
  16.     int l, r, dat, id, ans;
  17.     friend bool operator < (const query &a, const query &b)
  18.     { return a.l/sqr != b.l/sqr ? a.l < b.l : a.r < b.r; }
  19. } q[MAXN];
  21. bool cmp(const query &a, const query &b)
  22. { return a.id < b.id; }
  23. int a[MAXN], tmp[30];
  24. unsigned long long d[MAXN], dx[MAXN], qu[MAXN], top = 0;
  25. void dx_init()
  26. {
  27.     memcpy(dx, d, sizeof d);
  28.     sort(dx+1, dx+top+1);
  29. }
  30. int dx_num(unsigned long long dat)
  31. { return lower_bound(dx+1, dx+top+1, dat)-dx; }
  33. int tab[MAXN];
  35. int main()
  36. {
  37.     scanf("%d%d%d", &n, &m, &k), bas = n+1;
  38.     sqr = sqrt(n); // 分块大小
  39.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  40.     for (int i = 1; i+k-1 <= n; i++) d[++top] = hash_val(a, i, i+k-1);
  41.     for (int i = 1; i <= m; i++) {
  42.         scanf("%d%d", &q[i].l, &q[i].r); q[i].r = q[i].r-k+1;
  43.         for (int j = 1; j <= k; j++) scanf("%d", &tmp[j]);
  44.         qu[i] = hash_val(tmp, 1, k);
  45.         d[++top] = qu[i], q[i].id = i;
  46.     }
  47.     dx_init(); // 离散化
  48.     for (int i = 1; i+k-1 <= n; i++) a[i] = dx_num(d[i]);
  49.     for (int i = 1; i <= m; i++) q[i].dat = dx_num(qu[i]);
  50.     sort(q+1, q+m+1);
  51.     memset(tab, 0, sizeof tab);
  52.     int L = q[1].l, R = q[1].r;
  53.     for (int i = L; i <= R; i++) tab[a[i]]++; q[1].ans = tab[q[1].dat];
  54.     for (int i = 2; i <= m; i++) {
  55.         if (q[i].l > q[i].r) continue;
  56.         while (L < q[i].l) tab[a[L++]]--;
  57.         while (L > q[i].l) tab[a[--L]]++;
  58.         while (R < q[i].r) tab[a[++R]]++;
  59.         while (R > q[i].r) tab[a[R--]]--;
  60.         q[i].ans = tab[q[i].dat];
  61.     }
  62.     sort(q+1, q+m+1, cmp);
  63.     for (int i = 1; i <= m; i++)
  64.         if (q[i].ans) puts("No");
  65.         else puts("Yes");
  66.     return 0;
  67. }

bzoj1103: [POI2007]大都市meg

看题解dfs序+树状数组就水过去了，O(nlgn)。
但是写了链剖O(nlg2n)也水过去了。
然而O(nlgn)的lct却死超死超的...
玄学啊...当然也可能我写跪了...

链剖

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 250005;
  6. int C[MAXN], n, dstop = 0;
  7. int lowbit(int i) { return i&(-i); }
  8. void modify(int pos, int dt)
  9. { for (int i = pos; i <= n; i += lowbit(i)) C[i] += dt; }
  10. int sum(int pos)
  11. {
  12.     int ans = 0;
  13.     for (int i = pos; i > 0; i -= lowbit(i)) { ans += C[i];}
  14.     return ans;
  15. }
  16. int sum(int l, int r)
  17. { return sum(r)-sum(l-1); }
  19. struct node {
  20.     int to, next;
  21. } edge[MAXN*2];
  22. int head[MAXN], top;
  23. void push(int i, int j)
  24. { ++top, edge[top] = (node){j, head[i]}, head[i] = top; }
  26. int siz[MAXN], id[MAXN], ind[MAXN], fa[MAXN];
  28. void dfs1(int nd)
  29. {
  30.     siz[nd] = 1;
  31.     for (int i = head[nd]; i; i = edge[i].next)
  32.         dfs1(edge[i].to), siz[nd] += siz[edge[i].to], fa[edge[i].to] = nd;
  33. }
  35. void dfs2(int nd, int from = 0)
  36. {
  37.     id[nd] = ++dstop, ind[nd] = from, modify(id[nd], 1);
  38.     int hev = 0;
  39.     for (int i = head[nd]; i; i = edge[i].next)
  40.         if (siz[edge[i].to] > siz[hev])
  41.             hev = edge[i].to;
  42.     if (!hev) return;
  43.     dfs2(hev, from);
  44.     for (int i = head[nd]; i; i = edge[i].next)
  45.         if (edge[i].to != hev)
  46.             dfs2(edge[i].to, edge[i].to);
  47. }
  49. void change(int nd)
  50. { modify(id[nd], -1); }
  52. int ask(int nd)
  53. {
  54.     int ans = 0;
  55.     while (nd) {
  56.         // cout << nd << endl;
  57.         ans += sum(id[ind[nd]], id[nd]), nd = fa[ind[nd]];
  58.     }
  59.     return ans;
  60. }
  62. int main()
  63. {
  64.     scanf("%d", &n);
  65.     for (int i = 1; i < n; i++) {
  66.         int u, v; scanf("%d%d", &u, &v);
  67.         if (u > v) swap(u,v);
  68.         push(u, v);
  69.     }
  70.     dfs1(1), dfs2(1);
  71.     int m; scanf("%d", &m);
  72.     for (int i = 1; i <= m+n-1; i++) {
  73.         char s; int u, v;
  74.         scanf("\n%c", &s);
  75.         if (s == 'A') { scanf("%d%d", &u, &v), change(max(u,v)); }
  76.         else if (s == 'W') {scanf("%d", &u), printf("%d\n", ask(u)-1); }
  77.         else throw;
  78.     }
  79.     return 0;
  80. }

LCT（TLE）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 250005;
  5. int chl[MAXN][2], dat[MAXN], hv[MAXN], stk[MAXN], stktop = 0, fa[MAXN];
  6. int rev[MAXN], n, m;
  8. bool is_rt(int nd)
  9. { return nd != chl[fa[nd]][0] && nd != chl[fa[nd]][1]; }
  11. void update(int nd)
  12. { dat[nd] = dat[chl[nd][0]] + dat[chl[nd][1]] + hv[nd];}
  14. void pdw(int nd)
  15. {
  16.     if (!rev[nd]) return;
  17.     int &lc = chl[nd][0], &rc = chl[nd][1]; rev[nd] = 0;
  18.     if (lc) rev[lc] ^= 1;
  19.     if (rc) rev[rc] ^= 1;
  20.     swap(lc, rc);
  21. }
  23. void zig(int nd)
  24. {
  25.     int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  26.     int son = chl[nd][tp^1];
  27.     if (!is_rt(p)) chl[g][tg] = nd; chl[nd][tp^1] = p, chl[p][tp] = son;
  28.     fa[son] = p, fa[p] = nd, fa[nd] = g;
  29.     update(p), update(nd);
  30. }
  32. void splay(int nd)
  33. {
  34.     stk[stktop = 1] = nd;
  35.     for (int i = nd; !is_rt(i); i = fa[i]) stk[++stktop] = fa[i];
  36.     while (stktop) pdw(stk[stktop--]);
  37.     while (!is_rt(nd)) {
  38.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  39.         if (is_rt(p)) { zig(nd); break; }
  40.         else if (tp == tg) zig(p), zig(nd);
  41.         else zig(nd), zig(nd);
  42.     }
  43. }
  45. void access(int x)
  46. {
  47.     for (int y = 0; x; x = fa[y = x])
  48.         splay(x), chl[x][1] = y, update(x);
  49. }
  51. void make_rt(int x)
  52. { access(x), splay(x), rev[x] ^= 1; }
  54. void link(int i, int j)
  55. { make_rt(j), fa[j] = i, access(j); }
  57. void change(int nd)
  58. { make_rt(nd), splay(nd), hv[nd]--, update(nd); }
  60. int ask(int nd)
  61. { make_rt(1), access(nd), splay(nd); return hv[nd]+dat[chl[nd][0]]; }
  63. int main()
  64. {
  65.     scanf("%d", &n);
  66.     for (int i = 2; i <= n; i++) hv[i] = 1;
  67.     for (int i = 1; i < n; i++) {
  68.         int u, v; scanf("%d%d", &u, &v);
  69.         if (u > v) swap(u, v);
  70.         link(u, v);
  71.     }
  72.     scanf("%d", &m);
  73.     for (int i = 1; i <= n+m-1; i++) {
  74.         char c; int u, v;
  75.         scanf("\n%c", &c);
  76.         if (c == 'W') { scanf("%d", &u), printf("%d\n", ask(u)); }
  77.         else if (c == 'A') { scanf("%d%d", &u, &v), change(max(u, v)); }
  78.     }
  79.     return 0;
  80. }

dfn&BIT

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 250005;
  5. int C[MAXN], n, dstop = 0;
  6. int lowbit(int i) { return i&(-i); }
  7. void modify(int pos, int dt)
  8. { for (int i = pos; i <= n; i += lowbit(i)) C[i] += dt; }
  9. int sum(int pos)
  10. {
  11.     int ans = 0;
  12.     for (int i = pos; i > 0; i -= lowbit(i)) { ans += C[i];}
  13.     return ans;
  14. }
  16. struct node {
  17.     int to, next;
  18. } edge[MAXN];
  19. int head[MAXN], top = 0;
  20. void push(int i, int j)
  21. { ++top, edge[top] = (node){j, head[i]}, head[i] = top; }
  23. int depth[MAXN], dfi[MAXN], dfo[MAXN], dft = 0;
  25. void dfs(int nd)
  26. {
  27.     dfi[nd] = ++dft;
  28.     for (int i = head[nd]; i; i = edge[i].next) {
  29.         int to = edge[i].to;
  30.         depth[to] = depth[nd]+1;
  31.         dfs(to);
  32.     }
  33.     dfo[nd] = dft;
  34. }
  36. void change(int nd)
  37. { modify(dfi[nd], 1), modify(dfo[nd]+1, -1); }
  39. int ask(int nd)
  40. { return depth[nd]-sum(dfi[nd]); }
  42. int main()
  43. {
  44.     scanf("%d", &n);
  45.     for (int i = 1; i < n; i++) {
  46.         int u, v; scanf("%d%d", &u, &v);
  47.         if (u > v) swap(u,v);
  48.         push(u, v);
  49.     }
  50.     depth[1] = 0, dfs(1);
  51.     int m; scanf("%d", &m);
  52.     for (int i = 1; i <= n+m-1; i++) {
  53.         char s; int u, v;
  54.         scanf("\n%c", &s);
  55.         if (s == 'A') { scanf("%d%d", &u, &v), change(max(u,v)); }
  56.         else if (s == 'W') {scanf("%d", &u), printf("%d\n", ask(u)); }
  57.         else throw;
  58.     }
  59.     return 0;
  60. }

4.13

bzoj3506: [Cqoi2014]排序机械臂

题面传送门

就是splay维护最小值和最小值位置，加上反转操作即可。
然而debug能力是硬伤...
注意重复元素的处理，就是xi→xi(n+1)+i

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. int chl[MAXN][2], fa[MAXN], rev[MAXN], stk[MAXN], stktop = 0;
  6. int top = 0, min_pos[MAXN], siz[MAXN], root = 0;
  7. long long min_val[MAXN], dat[MAXN];
  9. void update(int nd)
  10. {
  11.     min_val[nd] = min(dat[nd], min(min_val[chl[nd][0]], min_val[chl[nd][1]]));
  12.     min_pos[nd] = min_val[nd] == min_val[chl[nd][0]] ? min_pos[chl[nd][0]] : (min_val[nd] == dat[nd] ? nd : min_pos[chl[nd][1]]);
  13.     siz[nd] = siz[chl[nd][0]] + siz[chl[nd][1]] + 1;
  14. }
  16. inline int new_node(long long d) { return ++top, dat[top] = d, update(top), top;}
  18. void pdw(int nd)
  19. {
  20.     if (!rev[nd]) return;
  21.     int &lc = chl[nd][0], &rc = chl[nd][1];
  22.     if (lc) rev[lc] ^= 1;
  23.     if (rc) rev[rc] ^= 1;
  24.     swap(lc, rc), rev[nd] ^= 1;
  25. }
  27. void zig(int nd)
  28. {
  29.     int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  30.     int son = chl[nd][tp^1];
  31.     fa[son] = son==0?0:p, fa[p] = nd, fa[nd] = g;
  32.     chl[g][tg] = g==0?0:nd, chl[nd][tp^1] = p, chl[p][tp] = son;
  33.     root = g?root:nd;
  34.     update(p), update(nd);
  35. }
  37. void splay(int nd, int tar = 0)
  38. {
  39.     stk[stktop = 1] = nd;
  40.     for (int i = nd; fa[i]; i = fa[i]) stk[++stktop] = fa[i];
  41.     for (; stktop; stktop--) pdw(stk[stktop]);
  42.     while (fa[nd] != tar) {
  43.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  44.         if (g == tar) {zig(nd); break; }
  45.         else if (tp == tg) zig(p), zig(nd);
  46.         else zig(nd), zig(nd);
  47.     }
  48. }
  50. void dfs(int nd)
  51. {
  52.     if (!nd) return;
  53.     pdw(nd);
  54.     dfs(chl[nd][0]);
  55.     cerr << dat[nd] << " ";
  56.     dfs(chl[nd][1]);
  57. }
  59. void insert(long long nd)
  60. {
  61.     if (root == 0) root = new_node(nd);
  62.     else {
  63.         chl[root][1] = new_node(nd), fa[top] = root;
  64.         splay(top), update(top);
  65.         // dfs(top);
  66.     }
  67. }
  69. int get_min()
  70. {
  71.     splay(min_pos[root]);
  72.     int ans = siz[chl[root][0]]+1;
  73.     return ans;
  74. }
  76. int get_by_order(int k)
  77. {
  78.     int nd = root; k--; // have k element on left
  79.     while (nd) {
  80.         pdw(nd), update(nd);
  81.         if (siz[chl[nd][0]] == k) break;
  82.         nd = siz[chl[nd][0]]>k?chl[nd][0]:(k -= siz[chl[nd][0]]+1, chl[nd][1]);
  83.     }
  84.     return nd;
  85. }
  87. int get_segment(int l, int r)
  88. {
  89.     if (l == 1 && r == siz[root]) return root;
  90.     if (l == 1) return splay(get_by_order(r+1)), chl[root][0];
  91.     if (r == siz[root]) return splay(get_by_order(l-1)), chl[root][1];
  92.     return splay(get_by_order(l-1)), splay(get_by_order(r+1), root), chl[chl[root][1]][0];
  93. }
  95. void del_root()
  96. {
  97.     int t = get_segment(siz[chl[root][0]]+1, siz[chl[root][0]]+1);
  98.     int tp = chl[fa[t]][0] != t; chl[fa[t]][tp] = 0;
  99.     for (int i = fa[t]; i; i = fa[i]) update(i);
  100.     fa[t] = 0;
  101. }
  103. void reverse(int l, int r)
  104. {
  105.     int t = get_segment(l, r);
  106.     rev[t] ^= 1;
  107. }
  109. int ans()
  110. {
  111.     int ret = get_min();
  112.     reverse(1, ret);
  113.     splay(min_pos[root]), del_root();
  114.     return ret;
  115. }
  117. int n;
  119. int main()
  120. {
  121.     memset(min_val, 127/3, sizeof min_val);
  122.     scanf("%d", &n);
  123.     for (int i = 1; i <= n; i++) {
  124.         int u; scanf("%d", &u); insert((long long)u*(n+1)+i);
  125.     }
  126.     for (int i = 1; i <= n; i++) printf("%d ", ans()+i-1);
  127.     return 0;
  128. }

bzoj3530: [Sdoi2014]数数

大爷题解：http://blog.csdn.net/aarongzk/article/details/50472209#

就是AC自动机上dp，然而数位dp仍然跪烂...要注意前导零的处理。
AC自动机忘记push儿子调试1h...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXL = 1505;
  6. int vis[MAXL];
  7. struct ACM {
  8.     struct node {
  9.         int chl[10];
  10.         int finished, fail;
  11.         node() { memset(chl, 0, sizeof chl), finished = fail = 0; }
  12.     } tree[MAXL];
  13.     int top, root;
  14.     ACM() { top = root = 0; }
  15.     inline int new_node() { return ++top; }
  16.     void insert(int &nd, const char *str)
  17.     {
  18.         if (!nd) nd = new_node();
  19.         if (*str == '\0') tree[nd].finished = 1, vis[nd] = 1;
  20.         else insert(tree[nd].chl[*str-'0'], str+1);
  21.     }
  22.     queue<int> que;
  23.     void init()
  24.     {
  25.         tree[root].fail = 0, que.push(root);
  26.         while (!que.empty()) {
  27.             int nd = que.front(); que.pop(); vis[nd] |= vis[tree[nd].fail];
  28.             for (int i = 0; i < 10; i++) {
  29.                 if (!tree[nd].chl[i]) continue;
  30.                 int p = tree[nd].fail;
  31.                 while (p && !tree[p].chl[i]) p = tree[p].fail;
  32.                 if (!p) tree[tree[nd].chl[i]].fail = root;
  33.                 else tree[tree[nd].chl[i]].fail = tree[p].chl[i];
  34.                 que.push(tree[nd].chl[i]);
  35.             }
  36.         } ;
  37.     }
  38.     int trans(int nd, int ths)
  39.     {
  40.         if (tree[nd].chl[ths]) return tree[nd].chl[ths];
  41.         int p = tree[nd].fail;
  42.         while (p && !tree[p].chl[ths]) p = tree[p].fail;
  43.         if (!p) return root;
  44.         else return tree[p].chl[ths];
  45.     }
  46. } ac;
  48. long long dp[1500][MAXL][3]; // 1 随意 0 不随意
  49. char str[MAXL]; int s[MAXL];
  50. long long mod = 1e9+7;
  51. int n, m;
  53. int main()
  54. {
  55.     memset(vis, 0, sizeof vis);
  56.     scanf("%s", str+1); n = strlen(str+1);
  57.     for (int i = 1; i <= n; i++) s[i] = str[i]-'0';
  58.     scanf("%d", &m);
  59.     for (int i = 1; i <= m; i++) {
  60.         scanf("%s", str);
  61.         ac.insert(ac.root, str);
  62.     }
  63.     long long ans = 0;
  64.     ac.init();
  65.     memset(dp, 0, sizeof dp);
  66.     for (int i = 1; i < 10; i++) if (!vis[ac.trans(ac.root, i)]) dp[2][ac.trans(ac.root, i)][0]++;
  67.     for (int i = 2; i < n; i++)
  68.         for (int j = 1; j <= ac.top; j++)
  69.             for (int k = 0; k < 10; k++) if (!vis[ac.trans(j, k)])
  70.                 (dp[i+1][ac.trans(j, k)][0] += dp[i][j][0]) %= mod;
  71.     for (int i = 2; i <= n; i++)
  72.         for (int j = 1; j <= ac.top; j++)
  73.             (ans += dp[i][j][0]) %= mod; // 前导0
  74.     memset(dp, 0, sizeof dp);
  75.     for (int i = 1; i <= s[1]; i++)
  76.         if (!vis[ac.trans(ac.root, i)])
  77.             dp[2][ac.trans(ac.root, i)][i == s[1]]++;
  78.     for (int i = 2; i <= n; i++) {
  79.         for (int j = 1; j <= ac.top; j++)
  80.             for (int k = 0; k < 10; k++) {
  81.                 if (vis[ac.trans(j, k)]) continue;
  82.                 (dp[i+1][ac.trans(j, k)][0] += dp[i][j][0]) %= mod;
  83.                 if (k < s[i]) (dp[i+1][ac.trans(j, k)][0] += dp[i][j][1]) %= mod;
  84.                 else if (k == s[i]) (dp[i+1][ac.trans(j, k)][1] += dp[i][j][1]) %= mod;
  85.             }
  86.     }
  87.     for (int i = 1; i <= ac.top; i++)
  88.         (ans += dp[n+1][i][0]+dp[n+1][i][1]) %= mod;
  89.     cout << ans << endl;
  90.     return 0;
  91. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注