【WC2016】论战捆竹竿

已经快三周了啊……终于把坑填了……

首先显然是把除了自身的所有border拿出来，即做 \(\left\{ n - b_1, n - b_2, \dots, n - b_k, n \right\}\) 的完全背包。但是值域很大，所以考虑同余最短路。

首先，由 [国家集训队]墨墨的等式 的经验，显然可以 \(O(n^2)\)，因为最长border可以很小，所以可以卡到满。

然后就要一个性质：一个串的border可以分成 \(O\left( \log n \right)\) 个等差数列。证明咕咕咕。

有了这个，就可以干一些有趣的事：

考虑一个有趣的暴力，每次更新一个首项为 \(x\)，公差为 \(d\) 的等差数列时，可以把点按模 \(d\) 剩余系分类，这样子dp更新的区间是连续的。线段树搞搞，因为没有负权所以可以跑dijkstra，然后同样可以不保存边。最后再像之前那题的经验，每个等差数列分别更新。这样复杂度两个 \(\log\)，空间 \(O\left(n\right)\)。（来自官方题解）

然而这样做复杂度还是太大了。能不能不用线段树啊？

我们要将一个等差数列有效边压到 \(O(n)\)，那么也就剩余系有希望了。

观察到一个等差数列是 \(\left[x, x + d, x + 2d, \dots\right]\)，可以考虑模 \(x\)，然后在模 \(x\) 的剩余系下转移，显然还是构成了一堆环。

先考虑如果是在模 \(x\) 意义下的情况的DP转移，注意到等差数列长度的限制，转移点不能太远，因此考虑单调队列维护（也就是滑动窗口类似的）。

然后考虑如何在模 \(P\) 意义下转换为模 \(Q\)。

如果直接将所有能搞出的方案放进去，发现能表示出来的都是 \(dis_i + k \cdot P\) 类型的，这启发我们先把所有 \(dis_i\) 扔到模 \(Q\) 意义下序列上，然后用 \(P\) 更新同余最短路，这样同样能表示出 \(dis_i + k \cdot P\) 了。

所以找出所有等差数列后，对于每个数列分别先转换模数，再做dp转移。注意这道题卡常数（该优化的都优化上去就好了，比如下标加的时候用取模优化）。

我写挂一堆地方：直接拿border长度上去DP，单调队列少个等号，转换模数时用了 \(i\) 而不是 \(dis_i\) 初始化……

#include <bits/stdc++.h> struct data {int x, d, c;data() { x = d = c = 0; }bool ins(int v) {if (!c) return x = v, d = 0, c = 1, true;if (!d) return d = v - x, c = 2, true;if (x + c * d == v) return ++c, true;return false;} } ; const int MAXN = 500010; typedef long long LL; const LL INF = 0x3f3f3f3f3f3f3f3fLL; typedef std::vector<data> V; struct KMP {int nxt[MAXN];V build(char * buf, int len) {for (int i = 1; i <= len; ++i) {int now = nxt[i - 1];while (now && buf[now + 1] != buf[i]) now = nxt[now];nxt[i] = buf[now + 1] == buf[i] && now + 1 != i ? now + 1 : 0;}V res; data rt; int now = nxt[len];while (now) {if (!rt.ins(now))res.push_back(rt), (rt = data()).ins(now);now = nxt[now];}if (rt.x) res.push_back(rt);for (auto & t : res)t.x = len - t.x, t.d = -t.d;std::reverse(res.begin(), res.end());return res;} } kmp;int n; LL W; LL dis[MAXN]; int mod; void getmax(LL & x, LL y) { x < y ? x = y : 0; } void getmin(LL & x, LL y) { x > y ? x = y : 0; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void trans(int v) {static LL d2[MAXN];memset(d2, 0x3f, v << 3);for (int i = 0; i < mod; ++i) getmin(d2[dis[i] % v], dis[i]);const int G = gcd(v, mod);for (int i = 0; i < G; ++i) {int at = i;int tm = mod % v;for (int j = (i + mod) % v; j != i; j += tm - v, j += j >> 31 & v)if (d2[j] < d2[at]) at = j;LL now = d2[at] + mod;for (int j = (at + mod) % v; j != at; j += tm - v, j += j >> 31 & v)getmin(d2[j], now), now = std::min(now, d2[j]) + mod;}mod = v;memcpy(dis, d2, mod << 3); } struct qnode {LL v; int at;qnode() { v = at = 0; }qnode(LL x, int y) { v = x, at = y; } } Q[MAXN]; void dp(int v, int D, int C) {trans(v);const int G = gcd(v, D);for (int i = 0; i < G; ++i) {int at = i;int tm = D % v;for (int j = (i + D) % v; j != i; j += tm - v, j += j >> 31 & v)if (dis[j] < dis[at]) at = j;int qb = 1, qe = 0;for (int j = at, k = 0; k * G != v; j += tm - v, j += j >> 31 & v, ++k) {while (qb <= qe && Q[qb].at + C <= k) ++qb;if (qb <= qe) {auto x = Q[qb];getmin(dis[j], v + x.v + (k - x.at) * D);}while (qb <= qe && Q[qe].v + (k - Q[qe].at) * D >= dis[j]) --qe;Q[++qe] = (qnode) {dis[j], k};}} }int main() {std::ios_base::sync_with_stdio(false), std::cin.tie(0);int T; std::cin >> T;while (T --> 0) {static char buf[MAXN];std::cin >> n >> W >> buf + 1; W -= n;mod = n; memset(dis, 0x3f, n << 3); *dis = 0;for (auto t : kmp.build(buf, n)) dp(t.x, t.d ? t.d : 1, t.c);LL ans = 0;for (int i = 0; i != mod; ++i)dis[i] <= W ? ans += (W - dis[i]) / mod + 1 : 0;std::cout << ans << std::endl;}return 0; }

转载于:https://www.cnblogs.com/daklqw/p/11606992.html

总结

以上是生活随笔为你收集整理的【WC2016】论战捆竹竿的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。