前言
心态不好, 多想想
那我是不是要去学后缀数组?
好的跑去学了一下()
思路
首先考虑 \(\textrm{sa, height}\) 数组的约束
在此之前先给出一些定义
- \(\textrm{sa}\) 数组存储排名为 \(i\) 的后缀在原序列上的位置
- \(\textrm{rank}\) 数组存储原序列上的位置对应的排名
- \(\textrm{height}\) 数组存储相邻排名的后缀的最大公共前缀
考虑其约束
-
\(\forall i \in (1, n], S[\textrm{sa}_i] \geq S[\textrm{sa}_{i - 1}]\)
这是显然的, 否则不可能满足排名, 更一般的
\(\displaystyle rank_{\textrm{sa}_{i-1}+1}>rank_{\textrm{sa}_i+1} \textrm{ s.t. } S[\textrm{sa}_i] > S[\textrm{sa}_{i - 1}] \) -
\(\forall i \in (1, n], j \in [0, \textrm{height}_i), S[\textrm{sa}_i + j] = S[\textrm{sa}_{i - 1} + j]\)
也不难理解
进一步的, 还约束了
\(\displaystyle i + \textrm{height}_i \leq n \textrm{ s.t. } S[\textrm{sa}_i + \textrm{height}_i] > S[\textrm{sa}_{i - 1} + \textrm{height}_i] \)
好约束全了, 就是说我也是可能想得到
差分约束做法 (\(\rm{fake}\))
思路
看到这一车不等式考虑差分约束
搞得具体一点
首先对于这个约束
\(\forall i \in (1, n], S[\textrm{sa}_i] \geq S[\textrm{sa}_{i - 1}]\)
更一般的
\(\displaystyle rank_{\textrm{sa}_{i-1}+1}>rank_{\textrm{sa}_i+1} \textrm{ s.t. } S[\textrm{sa}_i] > S[\textrm{sa}_{i - 1}] \)
发现可以转化成两种情况
\(S[\textrm{sa}_i] \geq S[\textrm{sa}_{i - 1}] + 0\)
\(S[\textrm{sa}_i] \geq S[\textrm{sa}_{i - 1}] + 1\)
究其原因是 \(S\) 必须是整数, 不然找一个 \(\rm{ASCLL}\) 为 \(16.75\) 的东西给我
其次对于这个约束
\(\forall i \in (1, n], j \in [0, \textrm{height}_i), S[\textrm{sa}_i + j] = S[\textrm{sa}_{i - 1} + j]\)
进一步的
\(\displaystyle i + \textrm{height}_i \leq n \textrm{ s.t. } S[\textrm{sa}_i + \textrm{height}_i] > S[\textrm{sa}_{i - 1} + \textrm{height}_i] \)
类似上面转化成
\(S[\textrm{sa}_i + j] \geq S[\textrm{sa}_{i - 1} + j] + 0\)
\(S[\textrm{sa}_i + j] + 0 \leq S[\textrm{sa}_{i - 1} + j]\)
\(S[\textrm{sa}_i + \textrm{height}_i] \geq S[\textrm{sa}_{i - 1} + \textrm{height}_i] + 1\)
具体为什么要搞成最长路的形式, 在这里进行一次证明
我们想令 \(dis_n \geq dis_1 + L\) , 只有最长路才满足这个柿子, 相当于求出了 \(dis_n\) 的最小值
你发现最长路可能出现正权边, 需要使用 \(\rm{spfa}\)
注意全局加一个 \(S[0] + 1 \leq S[i], i \in [1, n]\)
实现
#include <bits/stdc++.h>
const int MAXN = 5206; //41
int n;
int sa[MAXN], rk[MAXN], height[MAXN]; // 后缀数组常用数组
class graph
{
private:
public:
struct node { int from, to, w, next; };
node edge[MAXN * MAXN]; int cnt = 0, head[MAXN];
/*初始化*/ void head_init() { for (int i = 0; i <= n; i++) head[i] = -1; }
/*加边*/ void addedge(int u, int v, int w) { edge[++cnt].to = v; edge[cnt].from = u, edge[cnt].w = w, edge[cnt].next = head[u]; head[u] = cnt; }
} gra;
/*建图*/
void mkgra() {
gra.head_init();
/*第一类约束*/ for (int i = 2; i <= n; i++) (rk[sa[i - 1] + 1] > rk[sa[i] + 1]) ? gra.addedge(sa[i - 1], sa[i], 1) : gra.addedge(sa[i - 1], sa[i], 0);
/*第二类约束*/
for (int i = 2; i <= n; i++) {
if (!(~height[i])) continue;
for (int j = 0; j < height[i]; j++) gra.addedge(sa[i] + j, sa[i - 1] + j, 0), gra.addedge(sa[i - 1] + j, sa[i] + j, 0);
if (i + height[i] <= n) gra.addedge(sa[i - 1] + height[i], sa[i] + height[i], 1);
}
/*超级原神*/ for (int i = 1; i <= n; i++) gra.addedge(0, i, 1);
}
int dis[MAXN]; bool inq[MAXN]; std::queue<int> q;
/*差分约束*/
void spfa(int st) {
memset(inq, false, sizeof inq); memset(dis, 128, sizeof dis);
dis[st] = 0; q.push(st); inq[st] = true;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int e = gra.head[u]; ~e; e = gra.edge[e].next) {
int v = gra.edge[e].to, w = gra.edge[e].w;
if (dis[v] < dis[u] + w) {
dis[v] = dis[u] + w;
if (!inq[v]) { inq[v] = true; q.push(v); }
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &sa[i]), rk[sa[i]] = i;
for (int i = 2; i <= n; i++) scanf("%d", &height[i]);
mkgra();
spfa(0);
for (int i = 1; i <= n; i++) std::cout << char(dis[i] + 'a' - 1);
return 0;
}
更巧妙的做法
思路
你发现跑差分约束还是太神经了
事实上建出来的图中, \(=0\) 的边连接的两点合并到一起, 剩下的就是个拓扑排序
进一步发现 \(\textrm{sa}\) 一定是一种拓扑排序, 按照其处理即可
\(=0\) 的合并考虑使用并查集
具体一点
首先对于这个约束
\(\forall i \in (1, n], S[\textrm{sa}_i] \geq S[\textrm{sa}_{i - 1}]\)
更一般的
\(\displaystyle rank_{\textrm{sa}_{i-1}+1}>rank_{\textrm{sa}_i+1} \textrm{ s.t. } S[\textrm{sa}_i] > S[\textrm{sa}_{i - 1}] \)
考虑记录所有 \(<\) 的连边, 如果是 \(\leq\) 的连边, 直接在最后计算答案的时候, 把 \(ans_{\textrm{sa}_i}\) 先赋值成 \(S[\textrm{sa}_{i - 1}]\) 即可, 正确性在于 \(\textrm{sa}\) 顺序一定是一个拓扑序
其次对于这个约束
\(\forall i \in (1, n], j \in [0, \textrm{height}_i), S[\textrm{sa}_i + j] = S[\textrm{sa}_{i - 1} + j]\)
也不难理解
进一步的, 还约束了
\(\displaystyle i + \textrm{height}_i \leq n \textrm{ s.t. } S[\textrm{sa}_i + \textrm{height}_i] > S[\textrm{sa}_{i - 1} + \textrm{height}_i] \)
我们考虑把所有 \(=\) 缩成一个点, 然后 \(<\) 正常连边
注意一点是先处理缩点再加边
总的来说, 我们先合并, 再建边, 最后处理答案的时候带上 \(\leq\) 的约束
实现
这个思路不难实现, 直接给出 \(\rm{std}\)
#include <bits/stdc++.h>
#define fo(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
const int maxn = 5005;
int n;
int SA[maxn], Rank[maxn], height[maxn];
int eql[maxn];
vector<int> larger[maxn];
int geteql(int x) { return eql[x] == x ? x : eql[x] = geteql(eql[x]); }
int T;
char ans[maxn];
int main()
{
scanf("%d", &n);
fo(i, 1, n) scanf("%d", &SA[i]), Rank[SA[i]] = i;
fo(i, 2, n) scanf("%d", &height[i]);
Rank[0] = Rank[n + 1] = 0;
fo(i, 1, n) eql[i] = i;
fo(i, 2, n)
if (height[i] > -1)
{
int x = SA[i - 1], y = SA[i];
fo(j, 1, height[i]) eql[geteql(x + j - 1)] = geteql(y + j - 1);
}
fo(i, 1, n) geteql(i);
fo(i, 2, n)
{
int x = SA[i - 1], y = SA[i];
if (~height[i]) {
if (x + height[i] <= n)
larger[eql[y + height[i]]].push_back(eql[x + height[i]]);
}
x = SA[i - 1] + 1, y = SA[i] + 1;
if (Rank[x] > Rank[y])
larger[eql[SA[i]]].push_back(eql[SA[i - 1]]);
}
ans[eql[SA[1]]] = 'a';
fo(i, 2, n)
{
ans[eql[SA[i]]] = ans[eql[SA[i - 1]]]; // 处理 <=
for (int x : larger[eql[SA[i]]]) // 处理 <
if (ans[eql[x]] + 1 > ans[eql[SA[i]]])
ans[eql[SA[i]]] = ans[eql[x]] + 1;
}
fo(i, 1, n) putchar(ans[geteql(i)]);
puts("");
}
看似没改实则改了一堆, 更符合我的理解
总结
约束限制类问题, 考虑具体表示约束
一个误区是递归表示约束, 事实上字典序只需要一个位置更大即可, 不能递归约束
差分约束不够优秀时, 考虑转化成拓扑排序一类问题
注意常见的缩点思想
标签：Everybody,Somebody,Lost,int,height,textrm,eql,sa,SA From： https://www.cnblogs.com/YzaCsp/p/18679866傳自我的手機:
我們的思想確有問題, 求真的同學們不要用 \(\rm{spfa}\) , 會影響你的數學思維, 三年一篇四大都沒有