[关闭]
@ljt12138 2017-07-02T11:52:22.000000Z 字数 29642 阅读 922

各种OJ刷题记录6.27-7.6

6175. 「美团 CodeM 初赛 Round B」黑白树

之前一道题的增强版...

考虑所有都相等，则可以从深度由深到浅贪心，如果还没有被覆盖就从这个节点覆盖上去。

但对于不同是有反例的：

http://blog.csdn.net/mengxiang000000/article/details/73718867

考虑先用一边dfs记录子树中覆盖当前节点最浅到哪里，计为。考虑到一个未被覆盖的节点时，覆盖掉中所有的节点，并即可。

没太看懂神犇们的高端写法...只好大力树剖+树状数组维护了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. struct node {
  7.     int to, next;
  8. } edge[MAXN];
  9. int head[MAXN], top = 0;
  10. inline void push(int i, int j)
  11. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  13. int siz[MAXN], id[MAXN], ind[MAXN], id_in_ds = 0;
  14. int c[MAXN];
  15. int n;
  17. int ki[MAXN];
  19. int depth[MAXN], fa[MAXN][20];
  20. int low_dep[MAXN];
  22. int dfn[MAXN], dfn_top = 0;
  24. inline int lowbit(int i)
  25. { return i&(-i); }
  26. void modify(int i, int dt)
  27. {
  28.     for (; i <= n; i += lowbit(i))
  29.         c[i] += dt;
  30. }
  31. void cover(int i, int j)
  32. { modify(i, 1), modify(j+1, -1); }
  33. int dat(int i)
  34. {
  35.     int ans = 0;
  36.     for (; i; i -= lowbit(i))
  37.         ans += c[i];
  38.     return ans;
  39. }
  42. int kth_ans(int nd, int k)
  43. {
  44.     if (k >= depth[nd]) k = depth[nd];
  45.     for (register int i = 0; i < 20; i++)
  46.         if (k&(1<<i))
  47.             nd = fa[nd][i];
  48.     return nd;
  49. }
  51. void dfs_init(int nd)
  52. {
  53.     siz[nd] = 1;
  54.     for (register int i = 1; i < 20; i++)
  55.         fa[nd][i] = fa[fa[nd][i-1]][i-1];
  56.     low_dep[nd] = kth_ans(nd, ki[nd]-1);
  57.     for (int i = head[nd]; i; i = edge[i].next) {
  58.         depth[edge[i].to] = depth[nd]+1;
  59.         dfs_init(edge[i].to), siz[nd] += siz[edge[i].to];
  60.         if (depth[low_dep[edge[i].to]] < depth[low_dep[nd]])
  61.             low_dep[nd] = low_dep[edge[i].to];
  62.     }
  63.     dfn[++dfn_top] = nd;
  64. }
  66. inline bool cmp(int a, int b)
  67. { return depth[a] > depth[b]; }
  69. void dfs_build(int nd, int from)
  70. {
  71.     id[nd] = ++id_in_ds, ind[nd] = from;
  72.     int hev = -1;
  73.     for (int i = head[nd]; i; i = edge[i].next) {
  74.         int to = edge[i].to;
  75.         if (hev == -1 || siz[to] > siz[hev]) hev = to;
  76.     }
  77.     if (hev == -1) return;
  78.     dfs_build(hev, from);
  79.     for (int i = head[nd]; i; i = edge[i].next) {
  80.         int to = edge[i].to;
  81.         if (to != hev) dfs_build(to, to);
  82.     }
  83. }
  85. void cover_point(int nd, int pt)
  86. {
  87.     while (depth[ind[nd]] > depth[pt]) {
  88.         cover(id[ind[nd]], id[nd]);
  89.         nd = fa[ind[nd]][0];
  90.     }
  91.     if (depth[nd] >= depth[pt]) cover(id[pt], id[nd]);
  92. }
  94. int main()
  95. {
  96.     scanf("%d", &n);
  97.     for (int i = 2; i <= n; i++) 
  98.         scanf("%d", &fa[i][0]), push(fa[i][0], i);
  99.     for (int i = 1; i <= n; i++) scanf("%d", &ki[i]);
  100.     dfs_init(1);
  101.     dfs_build(1, 1);
  102.     int cnt = 0;
  103.     for (int i = 1; i <= n; i++) {
  104.         int pt = dfn[i];
  105.         if (dat(id[pt]) != 0) continue;
  106.         int anc = low_dep[pt];
  107.         cover_point(pt, anc), cnt++;
  108.     }
  109.     printf("%d\n", cnt);
  110.     return 0;
  111. }

loj#112. 三维偏序

填坑...

不知道为什么印象特别深刻去年一次NOIP模拟赛建出二维数点模型，然后Too Naive，并不会做...一直向转化成逆序对...学习了一个偏序那套理论才知道Too Simple..

经典题，一维排序，二维归并，三维树状数组。

注意check一下相同的情况。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. inline int read()
  5. {
  6.     int a = 0, c;
  7.     do c = getchar(); while(!isdigit(c));
  8.     while (isdigit(c)) {
  9.         a = a*10+c-'0';
  10.         c = getchar();
  11.     }
  12.     return a;
  13. }
  15. const int MAXN = 100005;
  16. struct pt {
  17.     int x, y, z, id;
  18. } pts[MAXN], tmp[MAXN];
  20. int n, k;
  22. inline bool cmp_x(const pt &a, const pt &b)
  23. { return a.x < b.x; }
  24. inline bool cmp_y(const pt &a, const pt &b)
  25. { return a.y < b.y; }
  27. int ans[MAXN];
  29. int c[MAXN*2];
  31. inline int lowbit(int i)
  32. { return i&(-i); }
  33. void modify(int i, int dt)
  34. {
  35.     for (; i <= k; i += lowbit(i))
  36.         c[i] += dt;
  37. }
  38. int sum(int i)
  39. {
  40.     int ans = 0;
  41.     for (; i; i -= lowbit(i))
  42.         ans += c[i];
  43.     return ans;
  44. }
  46. void solve(int l, int r, int L, int R)
  47. {
  48.     if (l >= r) return;
  49.     L = pts[l].x, R = pts[r].x;
  50.     if (L == R) {
  51.         sort(pts+l, pts+r+1, cmp_y);
  52.         int lp = l, rp = l;
  53.         while (lp <= r) {
  54.             while (rp+1 <= r && pts[rp+1].y == pts[lp].y) rp++;
  55.             for (int i = lp; i <= rp; i++) 
  56.                     modify(pts[i].z, 1);
  57.             for (int i = lp; i <= rp; i++)
  58.                 ans[pts[i].id] += sum(pts[i].z)-1;
  59.             lp = rp = rp+1;
  60.         }
  61.         for (int i = l; i <= r; i++) modify(pts[i].z, -1);
  62.         return;
  63.     }
  64.     int MID = (L+R)>>1;
  65.     int lp = l, rp = r;
  66.     for (int i = l; i <= r; i++) {
  67.         if (pts[i].x <= MID) tmp[lp++] = pts[i];
  68.         else tmp[rp--] = pts[i];
  69.     }
  70.     int mid = lp-1;
  71.     for (int i = l; i <= r; i++)
  72.         pts[i] = tmp[i];
  73.     solve(l, mid, L, MID), solve(mid+1, r, MID+1, R);
  74.     lp = l, rp = mid+1;
  75.     int tmp_l = l;
  76.     while (lp <= mid && rp <= r) {
  77.         if (pts[lp].y <= pts[rp].y) {
  78.             modify(pts[lp].z, 1);
  79.             tmp[tmp_l++] = pts[lp++];
  80.         } else {
  81.             ans[pts[rp].id] += sum(pts[rp].z);
  82.             tmp[tmp_l++] = pts[rp++];
  83.         }
  84.     }
  85.     while (lp <= mid) {
  86.         modify(pts[lp].z, 1);
  87.         tmp[tmp_l++] = pts[lp++];
  88.     }
  89.     while (rp <= r) {
  90.         ans[pts[rp].id] += sum(pts[rp].z);
  91.         tmp[tmp_l++] = pts[rp++];
  92.     }
  93.     for (int i = l; i <= mid; i++) modify(pts[i].z, -1);
  94.     for (int i = l; i <= r; i++) pts[i] = tmp[i];
  95. }
  97. int d[MAXN];
  98. int main()
  99. {
  100.     scanf("%d%d", &n, &k);
  101.     for (int i = 1; i <= n; i++)
  102.         pts[i].x = read(), pts[i].y = read(), pts[i].z = read(), pts[i].id = i;
  103.     sort(pts+1, pts+n+1, cmp_x);
  104.     solve(1, n, 1, k);
  105.     for (int i = 1; i <= n; i++)
  106.         d[ans[i]]++;
  107.     for (int i = 0; i < n; i++)
  108.         printf("%d\n", d[i]);
  109.     return 0;
  110. }

NOIP2016 天天爱跑步

填一下这个坑....

考虑向上的路径，一个观测点观测到的条件是：

也就是。因而一个向上的路径的贡献就是其路径上为定值的点。可以在打一个标记，打一个标记。反过来看，对于一个观测点，查询的其实就是子树中所有标记个数减去标记个数。这可以用序+可持久化数组来维护，后者可以使用可持久化线段树或者可持久化平衡树实现(rope也可以)，复杂度，理论能拿到95分，然而在Cogs只80...后面还是RE...

  3. #include <bits/stdc++.h>
  4. #include <ext/rope>
  6. using namespace __gnu_cxx;
  7. using namespace std;
  9. const int MAXN = 300005;
  11. struct node {
  12.     int to, next;
  13. } edge[MAXN*2];
  14. int head[MAXN], top = 0;
  15. inline void push(int i, int j)
  16. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  18. int depth[MAXN], W[MAXN];
  20. int u[MAXN*2], v[MAXN*2], id[MAXN*2];
  21. int n, m;
  22. int lca[MAXN], vis[MAXN];
  23. int fa[MAXN], father[MAXN], ans[MAXN];
  24. inline int findf(int nd)
  25. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  27. inline int read()
  28. {
  29.     int a = 0, c;
  30.     do c = getchar(); while(!isdigit(c));
  31.     while (isdigit(c)) {
  32.         a = a*10+c-'0';
  33.         c = getchar();
  34.     }
  35.     return a;
  36. }
  38. vector<int> pt[MAXN];
  40. struct tag {
  41.     int dat;
  42.     int tp;
  43. };
  44. vector<tag> tag_up[MAXN], tag_down[MAXN];
  46. void dfs_init(int nd, int f)
  47. {
  48.     vis[nd] = 1, father[nd] = f;
  49.     for (vector<int>::iterator i = pt[nd].begin(); i != pt[nd].end(); ++i)
  50.         if (vis[v[*i]]) {
  51.             lca[id[*i]] = findf(v[*i]);
  52.         }
  53.     for (int i = head[nd]; i; i = edge[i].next) {
  54.         int to = edge[i].to;
  55.         if (to == f) continue;
  56.         depth[to] = depth[nd]+1, dfs_init(to, nd);
  57.     }
  58.     fa[nd] = f;
  59. }
  61. void put_tag()
  62. {
  63.     for (int i = 1; i <= m; i++) {
  64.         int c = lca[i], s = u[i], t = v[i];
  65.         if (c == t) {
  66.             tag_up[s].push_back((tag){depth[s], 1});
  67.             tag_up[father[c]].push_back((tag){depth[s], -1});
  68.         } else if (c == s) {
  69.             tag_down[t].push_back((tag){-depth[s], 1});
  70.             tag_down[father[c]].push_back((tag){-depth[s], -1});
  71.         } else {
  72.             tag_up[s].push_back((tag){depth[s], 1});
  73.             tag_up[father[c]].push_back((tag){depth[s], -1});
  74.             int beg = depth[s]-depth[c];
  75.             tag_down[t].push_back((tag){beg-depth[c], 1});
  76.             tag_down[c].push_back((tag){beg-depth[c], -1});
  77.         }
  78.     }
  79. }
  81. int dfn[MAXN], dfn_top = 0, out[MAXN];
  83. struct my_array {
  84.     rope<int> *arr[MAXN];
  85.     int range_l, range_r, lev;
  86.     void build()
  87.     {
  88.         arr[0] = new rope<int>;
  89.         lev = 0;
  90.         for (int i = range_l; i <= range_r; i++)
  91.             arr[0]->push_back(0);
  92.     }
  93.     inline void new_lev()
  94.     { ++lev, arr[lev] = new rope<int>(*arr[lev-1]); }
  95.     inline void add_pos(int pos, int dt)
  96.     {
  97.         pos = pos-range_l;
  98.         int dat = arr[lev]->at(pos)+dt;
  99.         arr[lev]->replace(pos, dat);
  100.     }
  101.     inline int segment_sum(int l, int r, int pos)
  102.     { return arr[r]->at(pos-range_l)-arr[l-1]->at(pos-range_l); }
  103. } arr_up, arr_down;
  105. void dfs_travel(int nd)
  106. {
  107.     dfn[nd] = ++dfn_top;
  108.     arr_up.new_lev(), arr_down.new_lev();
  109.     for (register vector<tag>::iterator i = tag_up[nd].begin(); i != tag_up[nd].end(); ++i) 
  110.         arr_up.add_pos(i->dat, i->tp);
  111.     for (register vector<tag>::iterator i = tag_down[nd].begin(); i != tag_down[nd].end(); ++i)
  112.         arr_down.add_pos(i->dat, i->tp);
  113.     for (register int i = head[nd]; i; i = edge[i].next) 
  114.         if (edge[i].to != father[nd]) dfs_travel(edge[i].to);
  115.     out[nd] = dfn_top;
  116. }
  118. int main()
  119. {
  120.     freopen("runninga.in", "r", stdin);
  121.     freopen("runninga.out", "w", stdout);
  122.     int size = 128 << 20;
  123.     char *p = (char*)malloc(size) + size;  
  124.     __asm__("movl %0, %%esp\n" :: "r"(p));
  125.     n = read(), m = read();
  126.     for (register int i = 1; i < n; i++) {
  127.         int x = read(), y = read();
  128.         push(x, y), push(y, x);
  129.     }
  130.     for (register int i = 1; i <= n; i++) W[i] = read();
  131.     for (register int i = 1; i <= m; i++) {
  132.         u[i] = read(), v[i] = read();
  133.         u[m+i] = v[i], v[m+i] = u[i], id[m+i] = id[i] = i;
  134.         pt[u[i]].push_back(i), pt[v[i]].push_back(i+m);
  135.     }
  136.     dfs_init(1, 0);
  137.     put_tag();
  138.     arr_up.range_l = 0, arr_up.range_r = 2*n+1, arr_down.range_l = -n-1, arr_down.range_r = n+1;
  139.     arr_up.build(), arr_down.build();
  140.     dfs_travel(1);
  141.     for (register int i = 1; i <= n; i++) {
  142.         ans[i] += arr_up.segment_sum(dfn[i], out[i], depth[i]+W[i]);
  143.         ans[i] += arr_down.segment_sum(dfn[i], out[i], W[i]-depth[i]);
  144.     }
  145.     for (register int i = 1; i <= n; i++)
  146.         printf("%d ", ans[i]);
  147.     puts("");
  148.     return 0;
  149. }

然而这题就是典型“会的越多得分越低”型题目...这个可持久化维护的特别鸡肋。由于答案具有可减性，我们在dfs的过程中维护一个数组，进入时记录一下答案，退出时记录一下，差值就是所求了...

  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  4. using namespace __gnu_cxx;
  5. using namespace std;
  7. const int MAXN = 300005;
  9. struct node {
  10.     int to, next;
  11. } edge[MAXN*2];
  12. int head[MAXN], top = 0;
  13. inline void push(int i, int j)
  14. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  16. int depth[MAXN], W[MAXN];
  18. int u[MAXN*2], v[MAXN*2], id[MAXN*2];
  19. int n, m;
  20. int lca[MAXN], vis[MAXN];
  21. int fa[MAXN], father[MAXN], ans[MAXN];
  22. inline int findf(int nd)
  23. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  25. inline int read()
  26. {
  27.     int a = 0, c;
  28.     do c = getchar(); while(!isdigit(c));
  29.     while (isdigit(c)) {
  30.         a = a*10+c-'0';
  31.         c = getchar();
  32.     }
  33.     return a;
  34. }
  36. vector<int> pt[MAXN];
  38. struct tag {
  39.     int dat;
  40.     int tp;
  41. };
  42. vector<tag> tag_up[MAXN], tag_down[MAXN];
  44. void dfs_init(int nd, int f)
  45. {
  46.     vis[nd] = 1, father[nd] = f;
  47.     for (vector<int>::iterator i = pt[nd].begin(); i != pt[nd].end(); ++i)
  48.         if (vis[v[*i]]) {
  49.             //cerr << *i << " " << id[*i] << " " << v[*i] << endl;
  50.             lca[id[*i]] = findf(v[*i]);
  51.         }
  52.     for (int i = head[nd]; i; i = edge[i].next) {
  53.         int to = edge[i].to;
  54.         if (to == f) continue;
  55.         depth[to] = depth[nd]+1, dfs_init(to, nd);
  56.     }
  57.     fa[nd] = f;
  58. }
  60. void put_tag()
  61. {
  62.     for (int i = 1; i <= m; i++) {
  63.         int c = lca[i], s = u[i], t = v[i];
  64.         // cerr << "LCA(" << s << "," << t << ") = " << c << endl;
  65.         if (c == t) {
  66.             tag_up[s].push_back((tag){depth[s], 1});
  67.             tag_up[father[c]].push_back((tag){depth[s], -1});
  68.         } else if (c == s) {
  69.             tag_down[t].push_back((tag){-depth[s], 1});
  70.             tag_down[father[c]].push_back((tag){-depth[s], -1});
  71.         } else {
  72.             tag_up[s].push_back((tag){depth[s], 1});
  73.             tag_up[father[c]].push_back((tag){depth[s], -1});
  74.             int beg = depth[s]-depth[c];
  75.             tag_down[t].push_back((tag){beg-depth[c], 1});
  76.             tag_down[c].push_back((tag){beg-depth[c], -1});
  77.         }
  78.     }
  79. }
  81. int arr_up[MAXN*4], arr_down[MAXN*4], beg = 600000;
  82. void dfs_travel(int nd)
  83. {
  84.     int pre = arr_up[depth[nd]+W[nd]+beg] + arr_down[W[nd]-depth[nd]+beg];
  85.     for (register int i = head[nd]; i; i = edge[i].next) 
  86.         if (edge[i].to != father[nd]) dfs_travel(edge[i].to);
  87.     for (register vector<tag>::iterator i = tag_up[nd].begin(); i != tag_up[nd].end(); ++i) 
  88.         arr_up[i->dat+beg] += i->tp;
  89.     for (register vector<tag>::iterator i = tag_down[nd].begin(); i != tag_down[nd].end(); ++i)
  90.         arr_down[i->dat+beg] += i->tp;
  91.     ans[nd] = arr_up[depth[nd]+W[nd]+beg] + arr_down[W[nd]-depth[nd]+beg]-pre;
  92. }
  94. int main()
  95. {
  96.     n = read(), m = read();
  97.     for (register int i = 1; i < n; i++) {
  98.         int x = read(), y = read();
  99.         push(x, y), push(y, x);
  100.     }
  101.     for (register int i = 1; i <= n; i++) W[i] = read();
  102.     for (register int i = 1; i <= m; i++) {
  103.         u[i] = read(), v[i] = read();
  104.         u[m+i] = v[i], v[m+i] = u[i], id[m+i] = id[i] = i;
  105.         pt[u[i]].push_back(i), pt[v[i]].push_back(i+m);
  106.     }
  107.     dfs_init(1, 0);
  108.     put_tag();
  109.     dfs_travel(1);
  110.     for (register int i = 1; i <= n; i++)
  111.         printf("%d ", ans[i]);
  112.     puts("");
  113.     return 0;
  114. }

NOIP2015 运输计划

继续填古代坑计划...

当时用SPFA水了25...

现在看来很水啊..二分后随便树剖就行了。也可以树上差分搞。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  6. struct node {
  7.     int to, next, dis;
  8. } edge[MAXN*2];
  9. int head[MAXN], top = 0;
  10. inline void push(int i, int j, int d)
  11. { edge[++top] = (node) {j, head[i], d}, head[i] = top; }
  13. int fa[MAXN];
  14. inline int findf(int a)
  15. { return fa[a]?fa[a] = findf(fa[a]):a; }
  17. int u[MAXN*2], v[MAXN*2], id[MAXN*2], lca[MAXN], vis[MAXN], father[MAXN];
  18. int dis[MAXN];
  19. int n, m;
  20. vector<int> pt[MAXN];
  21. int depth[MAXN], len[MAXN];
  23. inline int read()
  24. {
  25.     int a = 0, c;
  26.     do c = getchar(); while (!isdigit(c));
  27.     while (isdigit(c)) {
  28.         a = a*10+c-'0';
  29.         c = getchar();
  30.     }
  31.     return a;
  32. }
  34. void dfs_init(int nd, int f)
  35. {
  36.     vis[nd] = 1, father[nd] = f;
  37.     for (vector<int>::iterator i = pt[nd].begin(); i != pt[nd].end(); ++i)
  38.         if (vis[v[*i]])
  39.             lca[id[*i]] = findf(v[*i]);
  40.     for (int i = head[nd]; i; i = edge[i].next) {
  41.         int to = edge[i].to;
  42.         if (to == f) continue;
  43.         depth[to] = depth[nd]+1, len[to] = len[nd]+edge[i].dis;
  44.         dfs_init(to, nd);
  45.     }
  46.     fa[nd] = f;
  47. }
  49. int tag[MAXN], max_able = 0;
  51. void dfs_collect(int nd)
  52. {
  53.     for (int i = head[nd]; i; i = edge[i].next) {
  54.         int to = edge[i].to;
  55.         if (to == father[nd]) continue;
  56.         dfs_collect(to), tag[nd] += tag[to];
  57.     }
  58. }
  60. bool check(int ans)
  61. {
  62.     memset(tag, 0, sizeof tag);
  63.     int max_val = 0, cnt = 0;
  64.     max_able = 0;
  65.     for (int i = 1; i <= m; i++)
  66.         if (dis[i] > ans) {
  67.             max_val = max(max_val, dis[i]);
  68.             cnt++;
  69.             // cerr << u[i] << " " << v[i] << " " << lca[i] << endl;
  70.             tag[u[i]]++, tag[v[i]]++, tag[father[lca[i]]]--, tag[lca[i]]--;
  71.         }
  72.     if (cnt == 0) return 1;
  73.     //cerr << cnt << endl;
  74.     dfs_collect(1);
  75.         for (int i = 1; i <= n; i++) {
  76.         if (tag[i] != cnt) continue;
  77.         //cerr << tag[i] << endl;
  78.         for (int j = head[i]; j; j = edge[j].next) {
  79.             int to = edge[j].to;
  80.             // if (to == father[i]) continue;
  81.             if (tag[to] == cnt)
  82.                 max_able = max(max_able, edge[j].dis);
  83.         }
  84.     }
  85.     //cerr << max_val << " " << max_able << " " << ans << endl;
  86.     return max_val-max_able <= ans; 
  87. }
  89. int main()
  90. {
  91.     //freopen("transport.in", "r", stdin);
  92.     //freopen("transport.out", "w", stdout);
  93.     n = read(), m = read();
  94.     for (int i = 1; i < n; i++) {
  95.         int l = read(), r = read(), d = read();
  96.         push(l, r, d), push(r, l, d);
  97.     }
  98.     for (int i = 1; i <= m; i++) {
  99.         u[i] = read(), v[i] = read();
  100.         v[i+m] = u[i], u[i+m] = v[i], id[i] = id[i+m] = i;
  101.         pt[u[i]].push_back(i), pt[v[i]].push_back(i+m);
  102.     }
  103.     dfs_init(1, 0);
  104.     for (int i = 1; i <= m; i++)
  105.         dis[i] = len[u[i]]+len[v[i]]-len[lca[i]]*2;
  106.     int l = 0, r = 300000ll*1000, mid;
  107.     while (l <= r) {
  108.         mid = (l+r)>>1;
  109.         if (check(mid)) r = mid-1;
  110.         else l = mid+1;
  111.     }
  112.     printf("%d\n", r+1);
  113.     return 0;
  114. }

loj#6066. 「2017 山东一轮集训 Day3」第二题

我SX....原来括号序列就是dfs序啊..

二分答案，维护括号序列hash，考虑对于节点，以其为根的子树恰好被删去即是在其个祖先处，打一个标记，然后对于每个节点大力计算就好了。复杂度，如果祖先用长链剖分、排序用基数排序，可以做到

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. struct node {
  6.     int to, next;
  7. } edge[MAXN];
  8. int head[MAXN], top = 0;
  9. void push(int i, int j)
  10. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  12. int hash_dat[MAXN*2], dfn_top = 0;
  13. vector<pair<int, int> > forbidden[MAXN];
  14. int fa[MAXN][20], n;
  15. int dfn_in[MAXN], dfn_out[MAXN];
  17. typedef unsigned long long ull;
  19. ull hash_tab[MAXN*2], bs = 19260817, power[MAXN*2];
  20. int height[MAXN];
  21. // --- hash ---
  23. void hash_init()
  24. {
  25.     power[0] = 1;
  26.     for (int i = 1; i <= n*2; i++) power[i] = power[i-1]*bs;
  27.     for (int i = 1; i <= n*2; i++)
  28.         hash_tab[i] = hash_tab[i-1]*bs+hash_dat[i];
  29. }
  31. ull hash_val(int l, int r)
  32. { return hash_tab[r]-hash_tab[l-1]*power[r-l+1]; }
  34. // --- hash ---
  36. int kth_anc(int nd, int k)
  37. {
  38.     for (int i = 0; i < 20; i++)
  39.         if (k&(1<<i))
  40.             nd = fa[nd][i];
  41.     return nd;
  42. }
  44. void dfs_init(int nd)
  45. {
  46.     height[nd] = 0;
  47.     ++dfn_top, hash_dat[dfn_top] = 1;
  48.     dfn_in[nd] = dfn_top;
  49.     for (int i = 1; i < 20; i++)
  50.         fa[nd][i] = fa[fa[nd][i-1]][i-1];
  51.     for (int i = head[nd]; i; i = edge[i].next) {
  52.         fa[edge[i].to][0] = nd, dfs_init(edge[i].to);
  53.         height[nd] = max(height[nd], height[edge[i].to]+1);
  54.     }
  55.     ++dfn_top, hash_dat[dfn_top] = 2;
  56.     dfn_out[nd] = dfn_top;
  57. }
  59. set<ull> st;
  61. bool calc(int k)
  62. {
  63.     for (int i = 1; i <= n; i++) forbidden[i].clear();
  64.     st.clear();
  65.     for (int i = 1; i <= n; i++) {
  66.         int nd = kth_anc(i, k+1);
  67.         forbidden[nd].push_back(make_pair(dfn_in[i], dfn_out[i]));
  68.     }
  69.     for (int i = 1; i <= n; i++) {
  70.         sort(forbidden[i].begin(), forbidden[i].end());
  71.         forbidden[i].push_back(make_pair(dfn_out[i]+1, dfn_out[i]+1));
  72.     }
  73.     for (int i = 1; i <= n; i++) {
  74.         if (height[i] < k) continue;
  75.         ull hash_v = 0;
  76.         int l = dfn_in[i];
  77.         for (int j = 0, sz = forbidden[i].size(); j < sz; j++) {
  78.             int r = forbidden[i][j].first-1;
  79.             if (l <= r) 
  80.                 hash_v = hash_v*power[r-l+1]+hash_val(l, r);
  81.             l = forbidden[i][j].second+1;
  82.         }
  83.         if (st.count(hash_v)) return 1;
  84.         st.insert(hash_v);
  85.     }
  86.     return 0;
  87. }
  89. inline int read()
  90. {
  91.     int a = 0, c;
  92.     do c = getchar(); while (!isdigit(c));
  93.     while (isdigit(c)) {
  94.         a = a*10+c-'0';
  95.         c = getchar();
  96.     }
  97.     return a;
  98. }
  100. int rd[MAXN], rt;
  102. int main()
  103. {
  104.     n = read();
  105.     for (int i = 1; i <= n; i++) {
  106.         int x, v;
  107.         x = read();
  108.         for (int j = 1; j <= x; j++)
  109.             v = read(), push(i, v), rd[v]++;
  110.     }
  111.     for (int i = 1; i <= n; i++)
  112.         if (rd[i] == 0) {
  113.             rt = i;
  114.             break;
  115.         }
  116.     dfs_init(rt), hash_init();
  117.     int l = 0, r = n, mid;
  118.     while (l <= r) {
  119.         mid = (l+r)>>1;
  120.         if (calc(mid)) l = mid+1;
  121.         else r = mid-1;
  122.     }
  123.     printf("%d\n", l-1);
  124.     return 0;
  125. }

loj #6173. Samjia和矩阵

这个命题思路在哪里见过....当时是kmp，现在用SAM就好了。

考虑枚举矩形的高度，则高度为的矩形可以看成以维向量为字符集的长度为的字符串。

人话就是，把一列看成一个字符。

然后就可以用广义后缀自动机大法了。由于字符集太大，需要hash+map<ull>。

ps : std貌似是后缀数组，复杂度少一个，速度快到不知哪里去了...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef unsigned long long ull;
  6. int n, m;
  7. char A[115][115];
  8. const int MAXN = 30005;
  9. const ull bas = 19260817;
  11. struct SAM {
  12.     map<ull,int> chl[MAXN];
  13.     int fa[MAXN], maxl[MAXN], top, root;
  14.     void clear()
  15.     { top = root = 1, maxl[1] = 0; }
  16.     int push(int nd, ull dat)
  17.     {
  18.         int p = nd, np = ++top; maxl[np] = maxl[p]+1, chl[np].clear();
  19.         while (p && !chl[p][dat]) chl[p][dat] = np, p = fa[p];
  20.         if (!p) fa[np] = root;
  21.         else {
  22.             int q = chl[p][dat];
  23.             if (maxl[q] == maxl[p]+1) fa[np] = q;
  24.             else {
  25.                 int nq = ++top; chl[nq] = chl[q], maxl[nq] = maxl[p]+1;
  26.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  27.                 while (p && chl[p][dat] == q) chl[p][dat] = nq, p = fa[p];
  28.             }
  29.         }
  30.         return np;
  31.     }
  32. } sam_main;
  34. struct trie {
  35.     map<ull, int> tree[MAXN];
  36.     int top, root;
  37.     trie()
  38.     { top = root = 1; }
  39.     void clear()
  40.     {
  41.         for (int i = 1; i <= top; i++) tree[i].clear();
  42.         top = root = 1;
  43.     }
  44.     void push(vector<ull> &str)
  45.     {
  46.         int nd = root;
  47.         for (auto i : str) {
  48.             if (!tree[nd].count(i)) tree[nd][i] = ++top;
  49.             nd = tree[nd][i];
  50.         }
  51.     }
  52. } trie_main;
  54. queue<int> que;
  55. int st[MAXN];
  57. void bfs_build_sam()
  58. {
  59.     sam_main.clear();
  60.     que.push(trie_main.root);
  61.     st[trie_main.root] = sam_main.root;
  62.     while (!que.empty()) {
  63.         int nd = que.front(); que.pop();
  64.         for (auto i : trie_main.tree[nd]) {
  65.             st[i.second] = sam_main.push(st[nd], i.first);
  66.             que.push(i.second);
  67.         }
  68.     }
  69. }
  71. int solve()
  72. {
  73.     bfs_build_sam();
  74.     int ans = 0;
  75.     for (int i = 2; i <= sam_main.top; i++)
  76.         ans += sam_main.maxl[i]-sam_main.maxl[sam_main.fa[i]];
  77.     return ans;
  78. }
  80. ull hash_val[120][120]; // i, j 第i列前j项哈希
  81. ull power[120];
  82. inline ull hash_seg(int i, int l, int r)
  83. { return hash_val[i][r]-hash_val[i][l-1]*power[r-l+1]; }
  85. int main()
  86. {
  87.     scanf("%d%d", &n, &m);
  88.     power[0] = 1;
  89.     for (int i = 1; i <= n; i++) power[i] = power[i-1]*bas;
  90.     for (int i = 1; i <= n; i++)
  91.         scanf("%s", A[i]+1);
  92.     for (int i = 1; i <= m; i++) {
  93.         for (int j = 1; j <= n; j++)
  94.             hash_val[i][j] = hash_val[i][j-1]*bas+A[j][i]-'A'+1;
  95.     }
  96.     vector<ull> vec;
  97.     int ans = 0;
  98.     for (int i = 1; i <= n; i++) {
  99.         trie_main.clear();
  100.         for (int j = 1; j+i-1 <= n; j++) {
  101.             vec.clear();
  102.             for (int k = 1; k <= m; k++)
  103.                 vec.push_back(hash_seg(k, j, j+i-1));
  104.             trie_main.push(vec);
  105.         }
  106.         ans += solve();
  107.     }
  108.     cout << ans << endl;
  109.     return 0;
  110. }

loj#2098. 「CQOI2015」多项式

看不懂神犇五行代码系列qwq...

考虑展开右边级数第项，发现：

然后就py直接做了...

  1. import math
  3. def choose(n, k):
  4.     ans = 1
  5.     for i in range(k):
  6.         ans = ans*(n-i)
  7.     for i in range(1, k+1):
  8.         ans = ans/i
  9.     return ans
  11. n = int(raw_input())
  12. t = int(raw_input())
  13. m = int(raw_input())
  15. def mul(a, b):
  16.     c = {}
  17.     for i in range(2):
  18.         for j in range(2):
  19.             c[i, j] = 0
  20.             for k in range(2):
  21.                 c[i, j] = (c[i, j]+a[i, k]*b[k, j])%3389
  22.     return c
  24. def power(a, n):
  25.     ans = {(0,0):1, (1,1):1, (1, 0):0, (0,1):0}
  26.     for i in range(10000):
  27.         if (((n>>i)&1) != 0):
  28.             ans = mul(ans, a)
  29.         a = mul(a, a)
  30.     return ans
  32. def get_A(n):
  33.     c = {}
  34.     c[0, 0], c[0, 1], c[1, 0], c[1, 1] = 1234, 5678, 0, 1
  35.     c = power(c, n)
  36.     return (c[0, 0]+c[0, 1])%3389
  39. b = {}
  40. b[0] = get_A(n)
  42. for i in range(1, 6):
  43.     tmp, flag, tt = n-i, 1, t
  44.     b[i] = get_A(n-i)
  45.     for j in range(1, i+1):
  46.         b[i] = b[i]+b[i-j]*choose(tmp+j, j)*t**j*flag
  47.         flag, tt = -flag, tt*t
  48.     # print(b[i])
  50. print(b[n-m])

「NOI2016」优秀的拆分

补题计划continue...

首先考场是肯定写85-95的...后面的性价比不高..

正解其实也(看过题解后)比较简单。考虑求的个数只要求出形如的结尾位置和开头位置，然后即为所求。考虑枚举的长度，并将作为关键点。对于一个方案可以转化成求两个关键点和。如果，说明存在一个拆分，在对应的位置区间加1。求lcp和lcs可以用后缀数组或者二分哈希（单哈希会被卡..双哈希在uoj貌似TLE...但loj和bzoj过了）。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  5. typedef unsigned long long ull;
  7. char str[MAXN];
  8. int n, T;
  9. ull hash_tab[MAXN], bas = 31;
  10. long long hash_tab2[MAXN], bas2 = 97, mod = 1e9+7;
  11. ull power[MAXN];
  12. long long power2[MAXN];
  14. void hash_init()
  15. {
  16.     for (register int i = 1; i <= n+n; i++)
  17.         hash_tab[i] = hash_tab[i-1]*bas+str[i]-'a'+1;
  18.     for (register int i = 1; i <= n+n; i++)
  19.         hash_tab2[i] = (hash_tab2[i-1]*bas2%mod+str[i]-'a'+1)%mod;
  20. }
  22. inline ull hash_val1(int l, int r)
  23. { return l <= r ? hash_tab[r]-hash_tab[l-1]*power[r-l+1] : 0; }
  25. inline ull hash_val2(int l, int r)
  26. { return l <= r ? ((hash_tab2[r]-hash_tab2[l-1]*power2[r-l+1]%mod)%mod+mod)%mod : 0; }
  29. int tag_after[MAXN], tag_bef[MAXN];
  30. int pos[MAXN], top = 0;
  32. int max_len_lr(int a, int b, int upp)
  33. {
  34.     register int l = 0, r = upp, mid;
  35.     while (l <= r) {
  36.         mid = (l+r)>>1;
  37.         if (hash_val1(a, a+mid-1) == hash_val1(b, b+mid-1)
  38.             && hash_val2(a, a+mid-1) == hash_val2(b, b+mid-1)) l = mid+1;
  39.         else r = mid-1;
  40.     }
  41.     return l-1;
  42. }
  44. int max_len_rl(int a, int b, int upp)
  45. {
  46.     register int l = 0, r = upp, mid;
  47.     while (l <= r) {
  48.         mid = (l+r)>>1;
  49.         if (hash_val1(a-mid+1, a) == hash_val1(b-mid+1, b)
  50.             && hash_val2(a-mid+1, a) == hash_val2(b-mid+1, b)) l = mid+1;
  51.         else r = mid-1;
  52.     }
  53.     return l-1;
  54. }
  56. int main()
  57. {
  58.     scanf("%d", &T);
  59.     while (T--) {
  60.         scanf("%s", str+1);
  61.         memset(tag_bef, 0, sizeof tag_bef);
  62.         memset(tag_after, 0, sizeof tag_after);
  63.         n = strlen(str+1);
  64.         power[0] = power2[0] = 1;
  65.         for (register int i = 1; i <= n; i++) power[i] = power[i-1]*bas;
  66.         for (register int i = 1; i <= n; i++) power2[i] = power2[i-1]*bas2%mod;
  67.         for (register int i = n+1; i <= n+n; i++) str[i] = int('z')+1;
  68.         hash_init();
  69.         for (register int i = 1; i <= n; i++) {
  70.             top = 0;
  71.             do {
  72.                 ++top, pos[top] = pos[top-1]+i;
  73.             } while (pos[top] < n);
  74.             register int a, b, lr, rl;
  75.             for (register int j = 1; j < top; j++) {
  76.                 a = pos[j], b = pos[j+1];
  77.                 lr = max_len_lr(a, b, i), rl = max_len_rl(a, b, i);
  78.                 if (lr+rl-1 < i) continue;
  79.                 tag_after[b+i-rl]++, tag_after[b+lr]--;
  80.                 tag_bef[a-(i-lr)+1]--, tag_bef[a-rl+1]++;
  81.             }
  82.         }
  83.         for (register int i = 1; i <= n+n; i++) tag_after[i] += tag_after[i-1], tag_bef[i] += tag_bef[i-1];
  84.         long long ans = 0;
  85.         for (register int i = 1; i <= n; i++) 
  86.             ans += (long long)tag_after[i]*tag_bef[i+1];
  87.         printf("%lld\n", ans);
  88.     }
  89.     return 0;
  90. }

「NOI2016」循环之美

好神啊....感觉在考场上最多推出84...

首先打个表发现所求其实就是：

然后交换求和顺序并莫比乌斯大力算，得出：

设，考虑这样一个序列：

由辗转相除法可以得出，因此这段和这段对答案的贡献是一样的。所以：

这样就可以大力拿到84了.

剩下的比较有构造性...设。如果能快速求出这个就可以喜闻乐见下底函数分块了。

考虑最小的因子，令为最大的，则考虑。则：

由可知。而，因此：

大功告成...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXK = 2005, MAXN = 1000005;
  6. const int MOD = 1000007, bas = 2333;
  7. int cnt = 0;
  9. struct hash_table {
  10.     long long tab[MOD];
  11.     int n[MOD], k[MOD];
  12.     inline int hash_val(int n, int k)
  13.     { return ((long long)n*bas%MOD+k)%MOD; }
  14.     inline long long val(int __n, int __k)
  15.     {
  16.         int val = hash_val(__n, __k);
  17.         while (n[val] != __n || k[val] != __k) (val += 1) %= MOD;
  18.         return tab[val];
  19.     }
  20.     inline void insert(int __n, int __k, long long dat)
  21.     {
  22.         int val = hash_val(__n, __k);
  23.         while (k[val] != 0 || n[val] != 0) val++;
  24.         n[val] = __n, k[val] = __k, tab[val] = dat;
  25.     }
  26.     inline bool count(int __n, int __k)
  27.     {
  28.         int val = hash_val(__n, __k);
  29.         while (n[val] != __n || k[val] != __k) {
  30.             if (n[val] == 0 && k[val] == 0) return 0;
  31.             val++;
  32.         }
  33.         return 1;
  34.     }
  35. };
  37. inline int gcd(int a, int b)
  38. { return b == 0 ? a : gcd(b, a%b); }
  40. int prime[MAXN], not_prime[MAXN], mu[MAXN], top = 0;
  41. int M[MAXN];
  42. int n, m, k;
  43. int p[MAXK], q[MAXK]; // 拿出的第一个素因子; 剩余
  44. int f[MAXK];
  46. void get_prime(int n)
  47. {
  48.     mu[1] = 1, not_prime[1] = 1;
  49.     for (int i = 2; i <= n; i++) {
  50.         if (!not_prime[i]) prime[++top] = i, mu[i] = -1;
  51.         for (int j = 1; j <= top && i*prime[j] <= n; j++) {
  52.             not_prime[i*prime[j]] = 1;
  53.             if (i%prime[j] == 0) {
  54.                 mu[i*prime[j]] = 0;
  55.                 break;
  56.             }
  57.             mu[i*prime[j]] = -mu[i];
  58.         }
  59.     }
  60.     for (int i = 1; i <= n; i++)
  61.         M[i] = M[i-1]+mu[i];
  62. }
  64. hash_table hash_M;
  66. long long get_M(int N)
  67. {
  68.     if (N < MAXN) return M[N];
  69.     if (hash_M.count(N, 0)) return hash_M.val(N, 0);
  70.     long long ans = 1;
  71.     int last;
  72.     for (int i = 2; i <= N; i = last+1) {
  73.         last = N/(N/i);
  74.         ans -= (last-i+1)*get_M(N/i);
  75.     }
  76.     hash_M.insert(N, 0, ans);
  77.     return ans;
  78. }
  80. hash_table hash_s;
  82. long long get_G(int n, int k)
  83. {
  84.     // cerr << n << " " << k << endl;
  85.     if (n == 0) return 0;
  86.     if (k == 1) return get_M(n);
  87.     if (hash_s.count(n, k)) return cnt++, hash_s.val(n, k);
  88.     long long tmp = get_G(n, q[k])+get_G(n/p[k], p[k]*q[k]);
  89.     hash_s.insert(n, k, tmp);
  90.     return tmp;
  91. }
  93. void init_pq()
  94. {
  95.     for (int i = 2; i <= k; i++) {
  96.         if (!not_prime[i]) p[i] = i, q[i] = 1;
  97.         else {
  98.             int fac, pp = 1;
  99.             for (int j = 1; j <= top; j++)
  100.                 if (i%prime[j] == 0) {
  101.                     fac = prime[j];
  102.                     break;
  103.                 }
  104.             while (i%(pp*fac) == 0) pp *= fac;
  105.             p[i] = fac, q[i] = i/pp;
  106.         }
  107.     }
  108. }
  110. void init_f()
  111. {
  112.     f[0] = 0;
  113.     for (int i = 1; i <= k; i++) 
  114.         f[i] = f[i-1]+(gcd(i, k) == 1);
  115. }
  117. inline int get_F(int n)
  118. { return n/k*f[k]+f[n%k]; }
  120. int main()
  121. {
  122.     cin >> n >> m >> k;
  123.     get_prime(MAXN-1);
  124.     init_pq();
  125.     init_f();
  126.     int last;
  127.     long long ans = 0;
  128.     for (register int i = 1; i <= n && i <= m; i = last+1) {
  129.         last = min(min(n/(n/i), m/(m/i)), n);
  130.         ans += (get_G(last, k)-get_G(i-1, k))*(n/i)*get_F(m/i);
  131.     }
  132.     cout << ans << endl;
  133.     return 0;
  134. }

「NOI2016」区间

可能是NOI2016唯一一道水题吧......

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 500005;
  6. struct segm {
  7.     int l, r, len;
  8.     friend bool operator < (const segm &a, const segm &b)
  9.     { return a.len < b.len; }
  10. } seg[MAXN];
  11. int n, m;
  13. int dx[MAXN*2], dx_top = 0;
  15. void dx_init()
  16. {
  17.     for (int i = 1; i <= n; i++)
  18.         dx[++dx_top] = seg[i].l, dx[++dx_top] = seg[i].r;
  19.     sort(dx+1, dx+dx_top+1);
  20.     dx_top = unique(dx+1, dx+dx_top+1)-dx-1;
  21.     for (int i = 1; i <= n; i++) {
  22.         seg[i].l = lower_bound(dx+1, dx+dx_top+1, seg[i].l)-dx;
  23.         seg[i].r = lower_bound(dx+1, dx+dx_top+1, seg[i].r)-dx;
  24.     }
  25. }
  27. int max_val[MAXN*4], lc[MAXN*4], rc[MAXN*4], l[MAXN*4], r[MAXN*4], tag[MAXN*4];
  28. int root = 0, top = 0;
  30. inline void pdw(int nd)
  31. {
  32.     max_val[nd] += tag[nd];
  33.     if (lc[nd]) tag[lc[nd]] += tag[nd], tag[rc[nd]] += tag[nd];
  34.     tag[nd] = 0;
  35. }
  37. inline void update(int nd)
  38. { max_val[nd] = max(max_val[lc[nd]], max_val[rc[nd]]); }
  40. void build(int &nd, int opl, int opr)
  41. {
  42.     nd = ++top, l[nd] = opl, r[nd] = opr;
  43.     if (opl < opr)
  44.         build(lc[nd], opl, (opl+opr)/2), build(rc[nd], (opl+opr)/2+1, opr);
  45. }
  47. void modify(int nd, int opl, int opr, int dt)
  48. {
  49.     pdw(nd);
  50.     if (l[nd] == opl && r[nd] == opr) tag[nd] += dt;
  51.     else {
  52.         int mid = (l[nd] + r[nd]) >> 1;
  53.         if (opr <= mid) modify(lc[nd], opl, opr, dt);
  54.         else if (opl > mid) modify(rc[nd], opl, opr, dt);
  55.         else modify(lc[nd], opl, mid, dt), modify(rc[nd], mid+1, opr, dt);
  56.         pdw(lc[nd]), pdw(rc[nd]), update(nd);
  57.     }
  58. }
  60. int query(int nd, int opl, int opr)
  61. {
  62.     pdw(nd);
  63.     if (l[nd] == opl && r[nd] == opr) return max_val[nd];
  64.     else {
  65.         int mid = (l[nd] + r[nd]) >> 1;
  66.         if (opr <= mid) return query(lc[nd], opl, opr);
  67.         else if (opl > mid) return query(rc[nd], opl, opr);
  68.         else return max(query(lc[nd], opl, mid), query(rc[nd], mid+1, opr));
  69.     }
  70. }
  72. inline int read()
  73. {
  74.     int a = 0, c;
  75.     do c = getchar(); while (!isdigit(c));
  76.     while (isdigit(c)) {
  77.         a = a*10+c-'0';
  78.         c = getchar();
  79.     }
  80.     return a;
  81. }
  83. int main()
  84. {
  85.     n = read(), m = read();
  86.     for (int i = 1; i <= n; i++) {
  87.         seg[i].l = read();
  88.         seg[i].r = read();
  89.         seg[i].len = seg[i].r-seg[i].l;
  90.     }
  91.     sort(seg+1, seg+n+1);
  92.     dx_init();
  93.     build(root, 1, dx_top);
  94.     int ans = INT_MAX;
  95.     int l = 1, r = 0;
  96.     while (r < n) {
  97.         while (r < n && query(root, 1, dx_top) < m) 
  98.             ++r, modify(root, seg[r].l, seg[r].r, 1);
  99.         if (query(root, 1, dx_top) >= m)
  100.             ans = min(ans, seg[r].len-seg[l].len);
  101.         while (l <= n && query(root, 1, dx_top) >= m) {
  102.             if (query(root, 1, dx_top) >= m)
  103.                 ans = min(ans, seg[r].len-seg[l].len);
  104.             modify(root, seg[l].l, seg[l].r, -1);
  105.             l++;
  106.         }
  107.         if (query(root, 1, dx_top) >= m)
  108.             ans = min(ans, seg[r].len-seg[l].len);
  109.     }
  110.     if (ans == INT_MAX)
  111.         puts("-1");
  112.     else printf("%d\n", ans);
  113.     return 0;
  114. }

NOI2015 寿司餐厅

每个数大于的质因子最多只有一个，然后把相同的化为一类，大力分类讨论dp即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 505;
  5. int n;
  6. long long P;
  8. int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
  10. long long dp[2][1<<8|1][1<<8|1];
  11. long long p[2][2][1<<8|1][1<<8|1];
  12. vector<int> kind[MAXN];
  14. int main()
  15. {
  16.     scanf("%d%lld", &n, &P);
  17.     for (int i = 2; i <= n; i++) {
  18.         int S = 0, num = i;
  19.         for (int j = 0; j < 8; j++)
  20.             if (num%prime[j] == 0) {
  21.                 S |= 1<<j;
  22.                 while (num%prime[j] == 0) num /= prime[j];
  23.             }
  24.         if (num == 1) kind[n+1].push_back(S);
  25.         else kind[num].push_back(S);
  26.     }
  27.     int now = 0, nxt = 1;
  28.     dp[now][0][0] = 1;
  29.     for (register int i = 0; i <= n; i++) {
  30.         int nw = 0, nx = 1;
  31.         if (kind[i].empty()) continue;
  32.         memcpy(p[0][nw], dp[now], sizeof dp[now]);
  33.         memset(p[0][nx], 0, sizeof p[0][nx]);
  34.         memcpy(p[1][nw], dp[now], sizeof dp[now]);
  35.         memset(p[1][nx], 0, sizeof p[1][nx]);
  36.         for (register vector<int>::iterator l = kind[i].begin(); l != kind[i].end(); ++l) {
  37.             //cerr << i << " " << *l << endl;
  38.                 for (register int j = 0; j < 1<<8; j++)
  39.                 for (register int k = 0; k < 1<<8; k++) {
  40.                     (p[0][nx][j][k] += p[0][nw][j][k]) %= P;
  41.                     (p[1][nx][j][k] += p[1][nw][j][k]) %= P;
  42.                         (p[0][nx][j|(*l)][k] += p[0][nw][j][k]) %= P;
  43.                     (p[1][nx][j][k|(*l)] += p[1][nw][j][k]) %= P;
  44.                 }
  45.             memset(p[0][nw], 0, sizeof p[0][nw]);
  46.             memset(p[1][nw], 0, sizeof p[1][nw]);
  47.             swap(nw, nx);
  48.         }
  49.         for (register int j = 0; j < 1<<8; j++)
  50.             for (register int k = 0; k < 1<<8; k++)
  51.                 dp[now][j][k] = (p[0][nw][j][k]+p[1][nw][j][k]-dp[now][j][k])%P;
  52.     }
  53.     for (register int i = 1; i <= kind[n+1].size(); i++) {
  54.         int S = kind[n+1][i-1];
  55.         for (register int j = 0; j < 1<<8; j++)
  56.             for (register int k = 0; k < 1<<8; k++) {
  57.                 long long val = dp[now][j][k];
  58.                 (dp[nxt][j][k] += val) %= P;
  59.                     (dp[nxt][j][k|S] += val) %= P;
  60.                     (dp[nxt][j|S][k] += val) %= P;
  61.             }
  62.         memset(dp[now], 0, sizeof dp[now]);
  63.         swap(now, nxt);
  64.     }
  65.     long long ans = 0;
  66.     for (register int j = 0; j < 1<<8; j++) {
  67.         for (register int k = 0; k < 1<<8; k++) {
  68.             if ((j&k) == 0)
  69.                 (ans += dp[now][j][k]) %= P;
  70.             //cerr << dp[now][j][k] << " ";
  71.         }
  72.         //cerr << endl;
  73.     }
  74.     printf("%lld\n", (ans+P)%P);
  75.     return 0;
  76. }

「NOI2015」荷马史诗

真...哈夫曼编码裸题

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100050;
  6. long long w[MAXN];
  7. int n, k;
  8. long long tot_len = 0;
  10. struct pt {
  11.     long long val;
  12.     int lev;
  13.     friend bool operator < (const pt &a, const pt &b)
  14.     { return a.val == b.val ? a.lev > b.lev : a.val > b.val; }
  15. };
  17. priority_queue<pt> heap; 
  19. int main()
  20. {
  21.     scanf("%d%d", &n, &k);
  22.     for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
  23.     while ((n-1)%(k-1) != 0) w[++n] = 0;
  24.     for (int i = 1; i <= n; i++) heap.push((pt){w[i], 0});
  25.     while (heap.size() > 1) {
  26.         long long val = 0;
  27.         int lev = 0;
  28.         for (int i = 1; i <= k; i++) {
  29.             pt a = heap.top(); heap.pop();
  30.             val += a.val, lev = max(lev, a.lev);
  31.         }
  32.         tot_len += val;
  33.         heap.push((pt){val, lev+1});
  34.     }
  35.     cout << tot_len << endl << heap.top().lev << endl;
  36.     return 0;
  37. }

4545: DQS的trie

LCT维护广义后缀自动机Right集合大小.......................
太TM难写了啊...
「不过貌似用splay维护dfs序要好写一点...什么时候尝试一个」

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  5. struct  link_cut_trees {
  6.     int chl[MAXN][2], fa[MAXN], rev[MAXN];
  7.     int tag[MAXN], dat[MAXN];
  8.     int stk[MAXN], top;
  10.     bool is_rt(int x)
  11.     { return chl[fa[x]][0] != x && chl[fa[x]][1] != x;}
  13.     inline void pdw(int nd)
  14.     {
  15.         if (chl[nd][0]) tag[chl[nd][0]] += tag[nd], rev[chl[nd][0]] ^= rev[nd];
  16.         if (chl[nd][1]) tag[chl[nd][1]] += tag[nd], rev[chl[nd][1]] ^= rev[nd];
  17.         if (rev[nd]) swap(chl[nd][0], chl[nd][1]);
  18.         dat[nd] += tag[nd];
  19.         rev[nd] = 0, tag[nd] = 0;
  20.     }
  22.     void zig(int nd)
  23.     {
  24.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  25.         int son = chl[nd][tp^1];
  26.         if (son) fa[son] = p; if (!is_rt(p)) chl[g][tg] = nd;
  27.         fa[nd] = g, fa[p] = nd, chl[nd][tp^1] = p, chl[p][tp] = son;
  28.     }
  30.     void splay(int nd)
  31.     {
  32.         stk[top = 1] = nd;
  33.             for (int i = nd; !is_rt(i); i = fa[i]) stk[++top] = fa[i];
  34.         while (top) pdw(stk[top--]);
  35.         while (!is_rt(nd)) {
  36.             int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  37.             if (is_rt(p)) { zig(nd); break; }
  38.             if (tp == tg) zig(p), zig(nd);
  39.             else zig(nd), zig(nd);
  40.         }
  41.     }
  43.     void access(int x)
  44.     {
  45.         for (int y = 0; x; x = fa[y = x])
  46.             splay(x), chl[x][1] = y;
  47.     }
  49.     void make_rt(int x)
  50.     { access(x), splay(x), rev[x] ^= 1; }
  52.     void link(int x, int y) // x --> y
  53.     {
  54.         fa[x] = y, access(y), splay(y), tag[y] += dat[x];
  55.     }
  57.     void cut(int x)
  58.     {
  59.         access(x), splay(x), tag[chl[x][0]] -= dat[x];
  60.         fa[chl[x][0]] = 0, chl[x][0] = 0;
  61.     }
  63.     int get_dat(int x)
  64.     {
  65.         access(x), splay(x);
  66.         return dat[x];
  67.     }
  68. } ;
  70. struct SAM {
  71.     int chl[MAXN][3], fa[MAXN], maxl[MAXN], top, root;
  72.     link_cut_trees LCT;
  73.     long long ans;
  75.     SAM()
  76.     { top = root = 1, ans = 0; }
  78.     int push(int nd, int x)
  79.     {
  80.         int p = nd, np = ++top; LCT.dat[np] = 1, maxl[np] = maxl[p]+1;
  81.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  82.         if (!p) fa[np] = root, ans += maxl[np]-maxl[fa[np]], LCT.link(np, root);
  83.         else {
  84.             int q = chl[p][x];
  85.             if (maxl[q] == maxl[p]+1) fa[np] = q, ans += maxl[np]-maxl[fa[np]], LCT.link(np, q);
  86.             else {
  87.                 int nq = ++top; maxl[nq] = maxl[p]+1;
  88.                 memcpy(chl[nq], chl[q], sizeof chl[q]);
  89.                 fa[nq] = fa[q], LCT.link(nq, fa[nq]);
  90.                 ans += maxl[nq]-maxl[fa[nq]];
  91.                 ans -= maxl[q]-maxl[fa[q]];
  92.                 fa[q] = fa[np] = nq;
  93.                 ans += maxl[q]-maxl[fa[q]], ans += maxl[np]-maxl[fa[np]];
  94.                 LCT.cut(q), LCT.cut(np), LCT.link(np, nq), LCT.link(q, nq);
  95.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  96.             }
  97.         }
  98.         return np;
  99.     }
  101.     int get_pt(int nd, const char *str)
  102.     {
  103.         if (*str == '\0') return nd;
  104.         if (!chl[nd][*str-'a']) return -1;
  105.         return get_pt(chl[nd][*str-'a'], str+1);
  106.     }
  108.     inline long long diff_substring()
  109.     { return ans; }
  111.     inline int match_times(const char *str)
  112.     {
  113.         int nd = get_pt(root, str);
  114.         if (nd == -1) return 0;
  115.         return LCT.get_dat(nd);
  116.     }
  117. };
  119. struct trie {
  120.     struct node {
  121.         int to, next;
  122.         char dis;
  123.     } edge[MAXN*2];
  124.     int head[MAXN], top;
  125.     inline void push(int i, int j, char c)
  126.     { edge[++top] = (node){j, head[i], c}, head[i] = top; }
  128.     int stat[MAXN], vis[MAXN];
  129.     int root;
  130.     SAM autometa;
  131.     queue<int> que;
  133.     trie()
  134.     { root = 1, stat[root] = 1, top = 0; }
  136.         void dfs(int x)
  137.     {
  138.         vis[x] = 1;
  139.         for (int i = head[x]; i; i = edge[i].next) {
  140.             int to = edge[i].to, c = edge[i].dis-'a';
  141.             if (vis[to]) continue;
  142.             stat[to] = autometa.push(stat[x], c);
  143.                 dfs(to);
  144.         }
  145.     }
  147.     inline int match_times(const char *str)
  148.     { return autometa.match_times(str); }
  150.     inline long long diff_substring()
  151.     { return autometa.diff_substring(); }
  152. } T;
  154. int n, m;
  155. int id;
  157. char str[MAXN];
  159. int main()
  160. {
  161.     scanf("%d%d", &id, &n);
  162.     for (int i = 1; i < n; i++) {
  163.         int u, v; char c;
  164.         scanf("%d%d %c\n", &u, &v, &c);
  165.         T.push(u, v, c), T.push(v, u, c);
  166.     }
  167.     T.dfs(1);
  168.     scanf("%d", &m);
  169.     for (int i = 1; i <= m; i++) {
  170.         int opt, r, t;
  171.         scanf("%d", &opt);
  172.         if (opt == 1) {
  173.             printf("%lld\n", T.diff_substring());
  174.         } else if (opt == 2) {
  175.             scanf("%d%d", &r, &t), t--;
  176.             while (t--) {
  177.                 int u, v;
  178.                 char c;
  179.                 scanf("%d%d %c\n", &u, &v, &c);
  180.                 T.push(u, v, c), T.push(v, u, c);
  181.             }
  182.             T.dfs(r);
  183.         } else if (opt == 3) {
  184.             scanf("%s", str);
  185.             printf("%d\n", T.match_times(str));
  186.         } else throw;
  187.     }
  188.     return 0;
  189. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注