“蔚来杯“2022牛客暑期多校训练营3 ACFHJ

A.Ancestor LCA+暴力查询

题目分析

给出两棵编号$1-n$的树$A,B$，$A,B$树上每个节点均有一个权值，给出$k$个关键点的编号$x_1\dots x_n$，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树$A$上$LCA$的权值大于树$B$上$LCA$的权值。

处理出所有关键节点的前缀$LCA$和后缀$LCA$，然后枚举所有的关键节点求$LCA$后$Check$计数即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 862118861;

int a[N], b[N], key[N];
vector<int> g1[N], g2[N];

struct LCA{
    
    struct edge{
     int to, len, next; } E[N];
    int cnt, last[N], fa[N], top[N], deep[N], siz[N], son[N], val[N];
    void addedge(int a, int b, int len = 0){
    
        E[++cnt] = (edge){
    b, len, last[a]}, last[a] = cnt;
    }
    void dfs1(int x){
    
        deep[x] = deep[fa[x]] + 1;
        siz[x] = 1;
        for (int i = last[x]; i; i = E[i].next){
    
            int to = E[i].to;
            if (fa[x] != to && !fa[to]){
    
                val[to] = E[i].len;
                fa[to] = x;
                dfs1(to);
                siz[x] += siz[to];
                if (siz[son[x]] < siz[to]) son[x] = to;
            }
        }
    }
    void dfs2(int x){
    
        if (x == son[fa[x]]) top[x] = top[fa[x]];
        else top[x] = x;
        for (int i = last[x]; i; i = E[i].next)
            if (fa[E[i].to] == x && fa[E[i].to] != E[i].to) dfs2(E[i].to);
    }
    void init(int root) {
     dfs1(root), dfs2(root); }
    int query(int x, int y){
    
        for (; top[x] != top[y]; deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]);
        return deep[x] < deep[y] ? x : y;
    }
}ta, tb;

int pa[N], pb[N], sa[N], sb[N];

inline void solve(){
    
    int n = 0, k = 0; cin >> n >> k;
    for(int i = 1; i <= k; i++) cin >> key[i];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++){
    
        int fa; cin >> fa;
        ta.addedge(fa, i), ta.addedge(i, fa);
    }
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 2; i <= n; i++){
    
        int fa; cin >> fa;
        tb.addedge(fa, i), tb.addedge(i, fa);
    }
    ta.init(1), tb.init(1);
    pa[1] = pb[1] = key[1], sa[k] = sb[k] = key[k];
    for(int i = 2; i <= k; i++) 
        pa[i] = ta.query(pa[i - 1], key[i]), pb[i] = tb.query(pb[i - 1], key[i]);
    for(int i = k - 1; i >= 1; i--)
        sa[i] = ta.query(sa[i + 1], key[i]), sb[i] = tb.query(sb[i + 1], key[i]);
    int ans = 0;
    for(int i = 1; i <= k; i++){
    
        int qa = 0, qb = 0;
        if(i == 1){
    
            qa = sa[i + 1], qb = sb[i + 1];
        } else if(i == k){
    
            qa = pa[i - 1], qb = pb[i - 1];
        } else {
    
            qa = ta.query(pa[i - 1], sa[i + 1]);
            qb = tb.query(pb[i - 1], sb[i + 1]);
        }
        if(a[qa] > b[qb]) ans++;
    }
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

C.Concatenation 签到？

题目分析

排序规则$A+B<B+A$，排序后直接输出即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10, MOD = 1e9 + 7;

string s[N];

inline void solve(){
    
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++){
    
        cin >> s[i];
    }
    string ans;
    sort(s + 1, s + 1 + n, [](string &a, string &b){
     return (a + b) < (b + a); });
    for(int i = 1; i <= n; i++) cout << s[i];
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

F.Fief 点双连通分量

题目分析

给定一个无向图，每次询问两点x, y，求是否存在一个n的排列，使得第一个元素为x，最后一个元素为y，且排列的任意一个前缀、任意一个后缀都连通。

对于询问$x,y$，当且仅当添加一条边$(x,y)$以后图是点双联通的，才为$Yes$。

队友$gkjj$写的，后面再补，贴个代码

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long
#define ll long long
#define pb push_back
using namespace std;
const string yes="YES\n",no="NO\n";
const int mod = 1000000007,N = 400005,inf=1e18;
const ull base=13331;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    
    for(;y;y>>=1,(x*=x)%=mo) if(y&1)(res*=x)%=mo;
    return res;
}
const int M=1000050;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;

int n,m,fkcnt,q;
int head[N];
struct node {
    
    int to,nxt;
}e[M];
int idx=0;
void add_edge(int u,int v){
    
    e[idx].to=v;
    e[idx].nxt=head[u];
    head[u]=idx++;
}

int dfn[N],low[N],timestamp=0;
int stk[N],top=0;
int id[N],dcc_cnt;
int from[200005];
vector<int>dcc[N];//每个点双联通分量里面有哪些点
bool cut[N];
int root;
vector<int>p[300005];
void tarjan(int u){
    
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    if(u==root &&head[u]==-1){
    
        dcc_cnt++;
        dcc[dcc_cnt].pb(u);
        return ;
    }
    int cnt=0;
    for(int i=head[u];~i;i=e[i].nxt){
    
        int j=e[i].to;
        if(!dfn[j]){
    
            tarjan(j);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<=low[j]){
    
                cnt++;
                if(u!=root||cnt>1){
    
                    cut[u]=true;
                }
                ++dcc_cnt;
                int y;
                do{
    
                    y=stk[top--];
                    dcc[dcc_cnt].pb(y);
                }while(y!=j);
                dcc[dcc_cnt].pb(u);

                /*p[dcc_cnt].push_back(u); p[u].push_back(dcc_cnt);*/

            }
        }
        else {
    
            low[u]=min(low[u],dfn[j]);
        }
    }
}
void build(){
    
    for(int i=1;i<=dcc_cnt;i++){
    
        for(auto x:dcc[i]){
    
            from[x]=i+n;
        }
    }
    for(int i=1;i<=n;i++){
    
        if(cut[i])from[i]=i;
    }
    for(int u=1;u<=n;u++){
    
        for(int i=head[u];~i;i=e[i].nxt){
    
            int v=e[i].to;
            if(from[u]!=from[v]){
    
                p[from[u]].push_back(from[v]);
            }
        }
    }
    for(int i=1;i<=n+dcc_cnt;i++){
    
        sort(p[i].begin(),p[i].end());
        p[i].erase(unique(p[i].begin(),p[i].end()),p[i].end());
    }

}
void solve(){
    
    cin>>n>>m;
    memset(head,-1,sizeof head);
    for(int i=1;i<=m;i++){
    
        int u,v;cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    for(root=1;root<=n;root++){
    
        if(!dfn[root]){
    
            tarjan(root);
            fkcnt++;
        }
    }
    /*for(int i=1;i<=dcc_cnt;i++){ cout<<i<<":"; for(auto x:dcc[i]){ cout<<x<<" "; } cout<<endl; }*/
    cin>>q;
    if(n==2){
    
        for(int i=1;i<=q;i++){
    
            cout<<yes;
        }
        return;
    }
    if(fkcnt>1){
    
        for(int i=1;i<=q;i++){
    
            cout<<no;
        }
        return;
    }
    int cnt1=0,cnt2=0,cao=0,st=0,ed=0;;
    build();
    for(int i=1;i<=n+dcc_cnt;i++){
    
        if(p[i].size()>2){
    
            cao=1;
            break;
        }
        else if(p[i].size()==1){
    
            if(st)ed=i;
            else st=i;
        }
    }
    if(cao){
    
        for(int i=1;i<=q;i++){
    
            cout<<no;
        }
        return;
    }
    if(!ed){
    
        for(int i=1;i<=q;i++){
    
            cout<<yes;
        }
        return;
    }
    //cout<<st<<" "<<ed<<endl;
    /*for(int i=1;i<=n;i++){ cout<<from[i]<<" \n"[i==n]; }*/
    while(q--){
    
        int u,v;
        cin>>u>>v;
        if(from[u]==st&&from[v]==ed||from[u]==ed&&from[v]==st){
    
            cout<<yes;
        }
        else{
    
            cout<<no;
        }
    }
}

void main_init(){
    }
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cout<<fixed<<setprecision(12);
    int t=1;
	main_init();
    //cin>>t;
    while (t--)
        solve();
    
		
}

H.Hacker SAM

题目分析

给定母串以及若干子串，子串长度固定，每个位置都有一个权值，要求在子串和母串的公共子串中找到一个连续区间，使得连续区间的权值和最大，求最大权值和。

首先对母串建立SAM，然后用线段树维护静态区间和的最大值，然后每次对插入的字符串：

我们设置两个变量$v,l$，分别表示当前状态以及匹配长度，一开始 $v=t_0$ 且 $l=0$，即匹配为空串。

现在我们来描述如何添加一个字符 $T_i$ 并为其重新计算答案：

• 如果存在一个从 $v$ 到字符 $T_i$ 的转移，我们只需要转移并让 $l$ 自增一。
• 如果不存在这样的转移，我们需要缩短当前匹配的部分，这意味着我们需要按照后缀链接进行转移：

$$v=\mathrm{link}(v)$$

与此同时，需要缩短当前长度。显然我们需要将 $l$ 赋值为 $\mathrm{len}(v)$。

每次找到合法区间，直接线段树上查询并更新答案即可。

数据很水，不缩也能过，这里提供一组群友造的特殊样例：

输入：

11 11 1
aaaabbbaaaa
2 3 7 5 10 -2 0 10 2 4 0
aaaaaaaaaaa

输出：

25

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
const int INF = 1e9 + 7;

int ww[N];

#define ls rt << 1
#define rs rt << 1 | 1
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r

struct node{
    
	int w, lw, rw, maxw;
	node(){
    
		w = 0;
		lw = rw = maxw = -INF;
	}
	node operator+ (node b) const{
    
		node c;
		c.w = w + b.w;
		c.lw = max(lw, w + b.lw);
		c.rw = max(b.rw, b.w + rw);
		c.maxw = max(max(maxw, b.maxw), rw + b.lw);
		return c;
	}
}tree[N << 2];

void build(int rt, int l, int r){
    
    if(l == r){
    
        tree[rt].w = tree[rt].lw = tree[rt].rw = tree[rt].maxw = ww[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson), build(rson);
    tree[rt] = tree[ls] + tree[rs];
}

node query(int rt, int l, int r, int L, int R){
    
    if(l >= L && r <= R) return tree[rt];
    int mid = l + r >> 1;
    node b, c;
    if(mid >= L) b = query(lson, L, R);
    if(mid < R) c = query(rson, L, R);
    return b + c;
}

struct state {
    
  int len, link;
  std::map<char, int> next;
};

const int MAXLEN = 100000;
state st[MAXLEN << 1];
int sz, last;

void sam_init() {
    
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}

void sam_extend(char c) {
    
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
    
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
    
        st[cur].link = 0;
    } else {
    
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
    
        st[cur].link = q;
        } else {
    
        int clone = sz++;
        st[clone].len = st[p].len + 1;
        st[clone].next = st[q].next;
        st[clone].link = st[q].link;
        while (p != -1 && st[p].next[c] == q) {
    
            st[p].next[c] = clone;
            p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

int ql, qr;
int n, m, k;

int get(const string &T) {
    
    int v = 0, l = 0, best = 0, bestpos = 0, ans = 0;
    for (int i = 0; i < T.size(); i++) {
    
        while (v && !st[v].next.count(T[i])) {
    
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(T[i])) {
    
            v = st[v].next[T[i]];
            l++;
        }
        int nowl = i - l + 1, nowr = i;
        if(nowl <= nowr){
    
            int res = query(1, 1, m, nowl + 1, nowr + 1).maxw;
            ans = max(ans, res);
        }

    }
    return ans;
}

inline void solve(){
    
    cin >> n >> m >> k;
    string a; cin >> a;
    sam_init();
    for (int i = 0; i < a.size(); i++) sam_extend(a[i]);
    for(int i = 1; i <= m; i++) cin >> ww[i];
    build(1, 1, m);
    while(k--){
    
        string s; cin >> s;
        cout << get(s) << endl;
    }
    
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

J.Journey 0-1最短路

题目分析

给定一个城市有若干十字路口，右转需要等红灯，直行、左转和掉头都需要，求起点到终点最少等几次红灯。

可以将每条路径视为点，十字路口处分情况连边，边权赋为$0,1$，转化为$0-1$最短路问题，然后直接跑$dijkstra$即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e6 + 10;

#define pii pair<int, int>
#define mkp make_pair
#define fir first
#define sec second

int n = 0, cnt = 0;
int s1, s2, t1, t2;
vector<pii> g[N];
int dis[N];

struct node{
    
    int fa, to, res, id;
    const bool operator< (const node &x) const {
     return res > x.res; }
};

priority_queue<node> pq;

void dijkstra(){
    
    for(int i = 0; i < 4; i++){
    
        auto &[v, k] = g[s1][i];
        if(v == s2) pq.emplace(node{
    s1, s2, 0, k});
    }
    while(pq.size()){
    
        auto now = pq.top(); pq.pop();
        if(now.to == 0 || dis[now.id] != -1) continue;
        dis[now.id] = now.res;
        for(int i = 0; i < 4; i++){
    
            auto &[to, k] = g[now.to][i];
            if(to == now.fa) pq.emplace(node{
    now.to, g[now.to][(i + 1) % 4].fir, now.res, g[now.to][(i + 1) % 4].sec});
            else pq.emplace(node{
    now.to, g[now.to][(i + 1) % 4].fir, now.res + 1, g[now.to][(i + 1) % 4].sec});
        }
    }
}

void solve(){
    
    cin >> n;
    memset(dis, -1, sizeof(dis));
    for(int i = 1; i <= n; i++){
    
        for(int j = 0; j < 4; j++){
    
            int v; cin >> v;
            g[i].emplace_back(mkp(v, ++cnt));
        }
    }
    cin >> s1 >> s2 >> t1 >> t2;
    dijkstra();
    for(int i = 0; i < 4; i++){
    
        auto &[to, k] = g[t1][i];
        if(to == t2) cout << dis[k] << endl;
    }
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}