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

文章目录

• ​​A.[Ancestor] LCA+暴力查询​​

• ​​题目分析​​
• ​​Code​​

• ​​C.[Concatenation] 签到？​​

• ​​题目分析​​
• ​​Code​​

• ​​F.[Fief]点双连通分量​​

• ​​题目分析​​
• ​​Code​​

• ​​H.[Hacker]SAM​​

• ​​题目分析​​

• ​​输入：​​
• ​​输出：​​

• ​​Code​​

• ​​J.[Journey]0-1最短路​​

• ​​题目分析​​
• ​​Code​​

A.Ancestor LCA+暴力查询

题目分析

给出两棵编号的树，树上每个节点均有一个权值，给出个关键点的编号，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树上的权值大于树上的权值。

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

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 签到？

题目分析

排序规则，排序后直接输出即可。

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，且排列的任意一个前缀、任意一个后缀都连通。

对于询问，当且仅当添加一条边以后图是点双联通的，才为。

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

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，然后用线段树维护静态区间和的最大值，然后每次对插入的字符串：

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

现在我们来描述如何添加一个字符

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

与此同时，需要缩短当前长度。显然我们需要将 赋值为 。

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

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

输入：

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,
#define rson rt << 1 | 1, mid + 1,

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最短路

题目分析

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

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

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