[弱省胡策] (sf OVOO)
题目描述
(sf Oxide) 有一棵 (n) 个点的树，每条边有一个权值。
定义一个连通块为一个点集与使这些点连通的所有边（这些点必须连通），定义一个连通块的权值为这个连通块的边权和（如果一个连通块只包含一个点那么它的权值为 (0)）。
(sf Oxide) 希望你求出包含 (1) 号点的所有连通块中权值第 (k) 小的连通块的权值。如果不存在则输出满足条件最大连通块的权值。
(n,kle 10^5)。
解法
考虑从 (1) 号点开始扩展，那么有两种方法：在边集覆盖的点中选权值最小的边扩展；去掉边集中一条边，从剩余边集覆盖的点中选权值最小的边扩展。
具体实现用可持久化左偏树维护。左偏树维护可选边集，根就是当前被选的边。每次去掉根节点维护的边，合并左右儿子以实现操作二。去掉根节点后，扩展根节点维护的边的终点 (v) 所连的最小权值边，然后将 (v) 所连的边加入可选边集，实现操作一。
至于为什么只扩展 (v) 所连的最小权值边，是因为对于未加入边集的可选边，连加入可选边都无法保证，加入可选边和可选边的可选边这种操作肯定是不优的；对于已经被去掉的根节点，它的可选边也已经加入集合。
由于合并时不能将被合并两点信息破坏，所以需要可持久化。时间复杂度 (mathcal O(nlog (nlog n)+kcdot (log k+log (nlog n))))。算得很粗糙…
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <queue>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,k,d[maxn*45],w[maxn*45];
int ls[maxn*45],rs[maxn*45];
int rt[maxn],idx,to[maxn*45];
struct node {
int u; ll w;
node() {}
node(int U,ll W):u(U),w(W) {}
bool operator < (const node &t) const {
return w>t.w;
}
};
priority_queue <node> q;
int NewNode(int v,int W) {
w[++idx]=W,to[idx]=v;
return idx;
}
void Give(int o,int x) {
ls[o]=ls[x],rs[o]=rs[x];
w[o]=w[x],to[o]=to[x];
d[o]=d[x];
}
int merge(int x,int y) {
if(!x or !y)
return x|y;
int o=++idx;
if(w[x]>w[y]) swap(x,y);
Give(o,x);
rs[o]=merge(rs[o],y);
if(d[rs[o]]>d[ls[o]])
swap(ls[o],rs[o]);
d[o]=d[rs[o]]+1;
return o;
}
int main() {
n=read(9),k=read(9)-1;
for(int i=2;i<=n;++i) {
int fa=read(9),w=read(9);
rt[fa]=merge(rt[fa],NewNode(i,w));
}
node t=node(0,0);
q.push(node(rt[1],w[rt[1]]));
while(k--) {
if(q.empty()) break;
t=q.top(); q.pop();
int nxt=merge(ls[t.u],rs[t.u]);
if(nxt)
q.push(node(nxt,t.w+w[nxt]-w[t.u]));
nxt=merge(nxt,rt[to[t.u]]);
if(nxt)
q.push(node(nxt,t.w+w[nxt]));
}
print(t.w,'
');
return 0;
}
( ext{[BZOJ 4212] })神牛的养成计划
解法
首先，对于每个 ( m dna) 序列哈希一下前缀与后缀，然后对于每个询问，(mathcal O(n)) 地枚举即可。
考虑更优的解法。( m trie) 树可以快速求出包含某前缀的字符串个数，但是询问相当于要求同时具有两个前缀。可以先将 ( m dna) 序列按字典序排序正向插入 ( m trie) 树，得到包含某前缀的序列下标区间，然后按排序倒序插入 ( m trie) 树（可持久化），最后查询前缀对应下标区间内，有多少个 ( m dna) 序列的后缀为给定后缀即可。时间复杂度是 (mathcal O(2cdot 10^6cdot 32))。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-');
write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair <int,int> type;
const int maxn=2e6+2;
int n,idx,u_idx,t[2][maxn][26];
short siz[maxn],mx[maxn],mn[maxn];
int rt[2001],ans;
string s[2001];
void ins(int &o,int pre,int id) {
int p; p=o=++u_idx;
int len=s[id].length();
for(int i=len-1;i>=0;--i) {
int d=s[id][i]-'a';
for(int k=0;k<26;++k)
t[1][p][k]=t[1][pre][k];
t[1][p][d]=++u_idx;
p=t[1][p][d],pre=t[1][pre][d];
siz[p]=siz[pre]+1;
}
}
void ins(short id) {
int p=0,len=s[id].length();
for(int i=0;i<len;++i) {
int d=s[id][i]-'a';
if(!t[0][p][d])
t[0][p][d]=++idx,
mn[idx]=3000;
p=t[0][p][d];
mx[p]=max(mx[p],id);
mn[p]=min(mn[p],id);
}
}
type ask() {
int len=s[0].length(),p=0;
for(int i=0;i<len;++i) {
int d=s[0][i]-'a';
if(!t[0][p][d])
return make_pair(0,0);
p=t[0][p][d];
}
return make_pair(mn[p],mx[p]);
}
int ask(int l,int r) {
int len=s[0].length(),ret=0;
for(int i=len-1;i>=0;--i) {
int d=s[0][i]-'a';
ret=siz[t[1][r][d]]-siz[t[1][l][d]];
if(!ret)
return 0;
r=t[1][r][d],l=t[1][l][d];
}
return ret;
}
void Decode() {
cin>>s[0];
int len=s[0].length();
for(int i=0;i<len;++i)
s[0][i]=(s[0][i]-'a'+ans)%26+'a';
}
int main() {
n=read(9);
for(int i=1;i<=n;++i)
cin>>s[i];
sort(s+1,s+n+1);
for(int i=1;i<=n;++i)
ins(i);
for(int i=1;i<=n;++i)
ins(rt[i],rt[i-1],i);
type ran;
for(int m=read(9);m;--m) {
Decode();
ran=ask();
Decode();
if(ran.first==0) {
puts("0");
continue;
}
print(ans=ask(rt[ran.first-1],rt[ran.second]),'
');
}
return 0;
}