"Wei Lai Cup" 2022 Niuke summer multi school training camp 3 acfhj

A.Ancestor LCA+ Violent inquiry

Topic analysis

Give two numbers $1-n$ The tree of $A,B$,$A,B$ Each node in the tree has a weight , give $k$ Number of key points $x_1\dots x_n$, Ask how many ways to remove exactly one key point so that the remaining key points are in the tree $A$ On $LCA$ The weight of is greater than that of the tree $B$ On $LCA$ A weight .

Process the prefixes of all key nodes $LCA$ And suffixes $LCA$, Then enumerate all the key nodes to find $LCA$ after $Check$ Count .

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 Sign in ？

Topic analysis

Sort rule $A+B<B+A$, Output directly after sorting .

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 Point biconnected component

Topic analysis

Given an undirected graph , Ask two points each time x, y, Ask whether there is one n Permutation , Make the first element x, The last element is y, And any prefix of the arrangement 、 Any suffix is connected .

For enquiries $x,y$, If and only if you add an edge $(x,y)$ The following figure is a double connection , Only then $Yes$.

Teammate $gkjj$ Written , I'll make up later , Post a code

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];// Which points are there in the double connected component of each point 
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

Topic analysis

Given the parent string and several substrings , The length of substring is fixed , Each position has a weight , It is required to find a continuous interval in the common substring of the substring and the parent string , Make the sum of weights of continuous intervals maximum , Find the maximum weight sum .

First, set up the parent string SAM, Then use the segment tree to maintain the maximum value of the static interval sum , Then each time the inserted string ：

We set two variables $v,l$, Indicates the current state and matching length respectively , In limine $v=t_0$ And $l=0$, That is, the match is an empty string .

Now let's describe how to add a character $T_i$ And recalculate the answer ：

• If there is one from $v$ To character $T_i$ The transfer of , We just need to move and let $l$ Self increase one .
• If there is no such transfer , We need to shorten the current matching part , This means that we need to transfer according to the suffix link ：

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

meanwhile , Need to shorten the current length . Obviously, we need to $l$ The assignment is $\mathrm{len}(v)$.

Every time you find a legal range , Query directly on the line segment tree and update the answer .

The data is very watery , You can live without shrinking , Here is a group of special examples made by friends ：

Input ：

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

Output ：

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 shortest path

Topic analysis

There are several intersections in a given city , You need to wait for the red light to turn right , Go straight 、 Both left turns and U-turns are required , Please wait for the red light at least several times from the beginning to the end .

You can think of each path as a point , The situation of intersection disposal is even , Edge right assignment $0,1$, Turn into $0-1$ Shortest path problem , And then run straight $dijkstra$ that will do .

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;
}