2017省选集训测试赛（二十五）Problem B recollection
2024-08-31 06:03:34
@(XSY)[后缀数组, 启发式合并, ST表]
Description
Solution
后缀数组 + 启发式合并 + Sparse Table.
这是第一次写树上后缀数组.
对以每个点为根的子树统计答案, 用一个set来维护子树下每个点节点在的排名, 启发式合并一颗子树的信息和当前节点的信息.
一些边界情况需要注意.
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
const int N = 1 << 18, MOD = 998244353, K = 47;
int n;
inline int modPower(int a, int x)
{
int res = 1;
for(; x; a = (long long)a * a % MOD, x >>= 1)
if(x & 1)
res = (long long)res * a % MOD;
return res;
}
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1;
char c;
while(! isdigit(c = getchar()))
if(c == '-')
sgn *= -1;
while(isdigit(c))
a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
struct trieTree
{
int pw[18], hd[N], tp, ltr[N], hsh[N][18];
inline void initialize()
{
memset(hd, -1, sizeof(hd));
tp = 0;
ltr[1] = 0;
for(int i = 0; i < 18; ++ i)
pw[i] = modPower(K, 1 << i);
memset(hsh, 0, sizeof(hsh));
}
struct edge
{
int v, nxt;
}edg[N];
inline void addEdge(int u, int v, int c)
{
edg[tp].v = v, edg[tp].nxt = hd[u];
hd[u] = tp ++;
ltr[v] = c;
}
int dep[N], anc[N][18];
void DFS(int u, int pre)
{
anc[u][0] = pre, hsh[u][0] = ltr[u];
for(int i = 1; i < 18; ++ i)
anc[u][i] = anc[anc[u][i - 1]][i - 1], hsh[u][i] = (hsh[anc[u][i - 1]][i - 1] + (long long)hsh[u][i - 1] * pw[i - 1] % MOD) % MOD;
for(int i = hd[u]; ~ i; i = edg[i].nxt)
dep[edg[i].v] = dep[u] + 1, DFS(edg[i].v, u);
}
int sa[N], rk[N], ht[N];
inline int getLCP(int u, int v)
{
int res = 0;
for(int i = 18 - 1; ~ i; -- i)
if(hsh[u][i] == hsh[v][i])
u = anc[u][i], v = anc[v][i], res += 1 << i;
return res;
}
inline void getSuffixArray()
{
dep[1] = 0;
DFS(1, 1);
static int sum[N];
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++ i)
++ sum[ltr[i]];
for(int i = 1; i < N; ++ i)
sum[i] += sum[i - 1];
for(int i = 1; i <= n; ++ i)
sa[-- sum[ltr[i]]] = i;
int p = 0;
rk[sa[0]] = p;
for(int i = 1; i < n; ++ i)
rk[sa[i]] = ltr[sa[i]] == ltr[sa[i - 1]] ? p : ++ p;
int lim = p + 1;
for(int len = 0; lim < n; ++ len)
{
static std::vector<int> suc[N];
for(int i = 1; i <= n; ++ i)
suc[i].clear();
for(int i = 0; i < n; ++ i)
if(dep[sa[i]] >= 1 << len)
suc[anc[sa[i]][len]].push_back(sa[i]);
static int tmpSa[N];
int p = 0;
for(int i = 0; i < n; ++ i)
if(dep[sa[i]] < 1 << len)
tmpSa[p ++] = sa[i];
for(int i = 0; i < n; ++ i)
for(std::vector<int>::iterator itr = suc[sa[i]].begin(); itr != suc[sa[i]].end(); ++ itr)
tmpSa[p ++] = *itr;
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++ i)
++ sum[rk[i]];
for(int i = 1; i < N; ++ i)
sum[i] += sum[i - 1];
for(int i = n - 1; ~ i; -- i)
sa[-- sum[rk[tmpSa[i]]]] = tmpSa[i];
static int tmpRk[N];
memcpy(tmpRk, rk, sizeof(rk));
rk[sa[0]] = p = 0;
for(int i = 1; i < n; ++ i)
{
if(tmpRk[sa[i]] != tmpRk[sa[i - 1]] || tmpRk[anc[sa[i]][len]] != tmpRk[anc[sa[i - 1]][len]])
++ p;
rk[sa[i]] = p;
}
lim = p + 1;
}
ht[0] = 0;
for(int i = 1; i <= n; ++ i)
if(rk[i])
ht[rk[i]] = getLCP(i, sa[rk[i] - 1]);
}
int ST[N << 1][18];
inline void getSparseTable()
{
memset(ST, 127, sizeof(ST));
for(int i = 0; i < n; ++ i)
ST[i][0] = ht[i];
for(int i = 1; i < 18; ++ i)
for(int j = 0; j < n; ++ j)
ST[j][i] = std::min(ST[j][i - 1], ST[j + (1 << i - 1)][i - 1]);
}
inline int getMin(int L, int R)
{
int tmp = log2(R - L + 1);
return std::min(ST[L][tmp], ST[R - (1 << tmp) + 1][tmp]);
}
std::set<int> st[N];
inline std::set<int>::iterator getLast(std::set<int>::iterator p)
{
return -- p;
}
inline std::set<int>::iterator getNext(std::set<int>::iterator p)
{
return ++ p;
}
int DFS1(int u)
{
st[u].insert(rk[u]);
int res = 0;
for(int i = hd[u]; ~ i; i = edg[i].nxt)
{
int v = edg[i].v;
res = std::max(res, DFS1(v));
if(st[u].size() < st[v].size())
std::swap(st[u], st[v]);
for(std::set<int>::iterator itr = st[v].begin(); itr != st[v].end(); ++ itr)
{
st[u].insert(*itr);
std::set<int>::iterator p = st[u].find(*itr);
if(p != st[u].begin())
res = std::max(res, getMin(*getLast(p) + 1, *p) + dep[u]);
if(getNext(p) != st[u].end())
res = std::max(res, getMin(*p + 1, *getNext(p)) + dep[u]);
}
}
return res;
}
inline int getAns()
{
for(int i = 1; i <= n; ++ i)
st[i].clear();
return DFS1(1);
}
}org;
int main()
{
#ifndef ONLINE_JUDGE
freopen("recollection.in", "r", stdin);
freopen("recollection.out", "w", stdout);
#endif
using namespace Zeonfai;
n = getInt();
org.initialize();
for(int i = 2; i <= n; ++ i)
{
int pre = getInt(), c = getInt();
org.addEdge(pre, i, c + 1);
}
org.getSuffixArray();
org.getSparseTable();
printf("%d", org.getAns());
}
2017.8.10 第二次写这一道题
#include <cstdio>
#include <cctype>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1;
char c;
while(! isdigit(c = getchar())) if (c == '-') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
const int N = (int)2e5, LOG = 18, K = 47, MOD = (int)1e9 + 7;
int n, ans = 0;
int pw[LOG];
inline int power(int a, int x)
{
int res = 1;
for(; x; a = (long long)a * a % MOD, x >>= 1) if(x & 1) res = (long long)res * a % MOD;
return res;
}
inline std::set<int>::iterator getPrevious(std::set<int>::iterator p)
{
return -- p;
}
inline std::set<int>::iterator getNext(std::set<int>::iterator p)
{
return ++ p;
}
struct trieTree
{
struct node
{
std::vector<node*> suc, pst[LOG];
node *anc[LOG];
int c, dep, rk, _rk;
int hsh[LOG];
inline node()
{
suc.clear();
for(int i = 0; i < LOG; ++ i) pst[i].clear();
}
}nd[N + 1];
inline void addEdge(int u, int v, int c)
{
nd[v].c = c; nd[u].suc.push_back(nd + v);
}
void DFS(node *u, node *pre)
{
u->dep = pre == NULL ? 0 : pre->dep + 1;
u->anc[0] = pre;
if(u->anc[0] != NULL) u->anc[0]->pst[0].push_back(u);
u->hsh[0] = u->c;
for(int i = 1; i < LOG; ++ i) if(u->anc[i - 1] != NULL)
{
u->anc[i] = u->anc[i - 1]->anc[i - 1];
if(u->anc[i] != NULL) u->anc[i]->pst[i].push_back(u), u->hsh[i] = (u->hsh[i - 1] + (long long)u->anc[i - 1]->hsh[i - 1] * pw[i - 1] % MOD) % MOD;
}
for(auto v : u->suc) DFS(v, u);
}
node *SA[N];
inline void sort()
{
static int sum[N];
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++ i) ++ sum[nd[i].c];
for(int i = 1; i <= 301; ++ i) sum[i] += sum[i - 1];
for(int i = 1; i <= n; ++ i)
SA[-- sum[nd[i].c]] = nd + i;
int p = 0;
SA[0]->rk = p;
for(int i = 1; i < n; ++ i) SA[i]->rk = SA[i]->c == SA[i - 1]->c ? p : ++ p;
int cnt = p + 1;
for(int i = 0; cnt < n; ++ i)
{
p = 0;
static node *tmpSA[N];
for(int j = 1; j <= n; ++ j) if(nd[j].dep < 1 << i) tmpSA[p ++] = nd + j;
for(int j = 0; j < n; ++ j) for(auto u : SA[j]->pst[i]) tmpSA[p ++] = u;
memset(sum, 0, sizeof(sum));
for(int j = 1; j <= n; ++ j) ++ sum[nd[j].rk];
for(int j = 1; j < cnt; ++ j) sum[j] += sum[j - 1];
for(int j = n - 1; ~ j; -- j) SA[-- sum[tmpSA[j]->rk]] = tmpSA[j];
for(int j = 1; j <= n; ++ j) nd[j]._rk = nd[j].rk;
p = 0;
SA[0]->rk = p;
for(int j = 1; j < n; ++ j)
{
if(SA[j]->_rk != SA[j - 1]->_rk || SA[j - 1]->dep < 1 << i || SA[j - 1]->anc[i]->_rk != SA[j]->anc[i]->_rk) ++ p;
SA[j]->rk = p;
}
cnt = p + 1;
}
}
inline int getLCP(node *u, node *v)
{
int res = 0;
for(int i = LOG - 1; ~ i; -- i) if(u->dep >= 1 << i && v->dep >= 1 << i && u->hsh[i] == v->hsh[i])
res += 1 << i, u = u->anc[i], v =v->anc[i];
return res;
}
inline void merge(int dep, std::set<int> &a, std::set<int> &b)
{
if(a.size() < b.size()) std::swap(a, b);
for(std::set<int>::iterator p = b.begin(); p != b.end(); ++ p)
{
a.insert(*p);
std::set<int>::iterator tmp = a.find(*p);
if(tmp != a.begin()) ans = std::max(ans, dep + getLCP(SA[*getPrevious(tmp)], SA[*p]));
if(getNext(tmp) != a.end()) ans = std::max(ans, dep + getLCP(SA[*getNext(tmp)], SA[*p]));
}
b.clear();
}
std::set<int> getAnswer(node *u)
{
std::set<int> st; st.clear(); st.insert(u->rk);
for(auto v : u->suc)
{
std::set<int> tmp = getAnswer(v);
merge(u->dep, tmp, st);
}
return st;
}
}T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("recollection.in", "r", stdin);
freopen("recollection.out", "w", stdout);
#endif
using namespace Zeonfai;
for(int i = 0; i < LOG; ++ i) pw[i] = power(K, 1 << i);
n = getInt();
for(int i = 2; i <= n; ++ i)
{
int pre = getInt(), c = getInt() + 1;
T.addEdge(pre, i, c);
}
T.DFS(T.nd + 1, NULL);
T.sort();
T.getAnswer(T.nd + 1);
printf("%d\n", ans);
}
最新文章
- c#连接关闭了，事务并没有关闭
- Linux Shell 文本处理工具集锦 zz
- 简易的IOS位置定位服务
- Pyqt 中__init__(self,parent==None) parent理解
- Memcache学习php完整一例
- [转] VB之Val()函数的使用
- 魔改——MFC SDI程序 转换为 MDI程序
- Android SingleTask与SingleInstance的区别
- PS太大GIMP可用
- 检测 HTML5\CSS3\JAVASCRIPT 在浏览器的适应情况
- Android HelloChart Demo
- awk 命令详解
- workbench的schema讲解一：(维度dimension设置的基本内容)
- 在学习JavaScript中用到的示例
- mysql5.7 版本中 timestamp 不能为零日期 以及sql_mode合理设置
- Python IO内核交互了解
- 使用google guava做内存缓存
- [VBS]检测计算机各硬件信息
- Linux CentOS 6.5 下 vsftpd ftp服务器搭建
- SpringBoot中使用纯scala进行开发 配置教程 非常简单的案例