2022牛客多校补题3

2022牛客多校3补题

A

给出两棵编号 $1-n$ 的树A和B，A和B树上每个节点均有一个权值，给出 $k$ 个关键点

的编号 $x_1…x_n$ ，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树A上

LCA的权值大于树B上LCA的权值

观察和不断模拟可以发现一系列的点的LCA可以通过前缀LCA实现。

故预处理出关键点序列的在树A B上的前缀LCA和后缀LCA，枚举去掉的关键节点并使用前后缀LCA算出剩余节点的LCA比较权值即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
template <class T> void Min(T &a, const T b) { if (a > b) a = b; }
template <class T> void Max(T &a, const T b) { if (a < b) a = b; }
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

struct Tree {
    std::vector<int> sz, top, dep, parent, in;
    int cur;
    std::vector<std::vector<int>> e;
    Tree(int n) : sz(n), top(n), dep(n), parent(n, -1), e(n), in(n), cur(0) {}
    void addEdge(int u, int v) {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    void init() {
        dfsSz(0);
        dfsHLD(0);
    }
    void dfsSz(int u) {
        if (parent[u] != -1)
            e[u].erase(std::find(e[u].begin(), e[u].end(), parent[u]));
        sz[u] = 1;
        for (int &v : e[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfsSz(v);
            sz[u] += sz[v];
            if (sz[v] > sz[e[u][0]])
                std::swap(v, e[u][0]);
        }
    }
    void dfsHLD(int u) {
        in[u] = cur++;
        for (int v : e[u]) {
            if (v == e[u][0]) {
                top[v] = top[u];
            } else {
                top[v] = v;
            }
            dfsHLD(v);
        }
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        if (dep[u] < dep[v]) {
            return u;
        } else {
            return v;
        }
    }
};
void solve()
{
	int n, k;
	cin >> n >> k;
	vi x(k);
	for(int i = 0; i < k; i++)
	{
		cin >> x[i];
		x[i]--;
	}

	Tree A(n), B(n);
	vi a(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 1; i < n; i++)
	{
		int p;
		cin >> p;
		p--;
		A.addEdge(i, p);
	}
	vi b(n);
	for(int i = 0; i < n; i++)
		cin >> b[i];
	for(int i = 1; i < n; i++)
	{
		int p;
		cin >> p;
		p--;
		B.addEdge(i, p);
	}
	A.init();
	B.init();

	vi prea(k), sufa(k), preb(k), sufb(k);
	for(int i = 0; i < k; i++)
	{
		if(i == 0)
			prea[i] = preb[i] = x[i];
		else
		{
			prea[i] = A.lca(prea[i - 1], x[i]);
			preb[i] = B.lca(preb[i - 1], x[i]);
		}
	}
	for(int i = k - 1; i >= 0; i--)
	{
		if(i == k - 1)
			sufa[i] = sufb[i] = x[i];
		else
		{
			sufa[i] = A.lca(sufa[i + 1], x[i]);
			sufb[i] = B.lca(sufb[i + 1], x[i]);
		}
	}
	int ans = 0;
	for(int i = 0; i < k; i++)
	{
		if(i == 0)
		{
			if(a[sufa[i + 1]] > b[sufb[i + 1]])
				ans++;
		}
		else if(i == k - 1)
		{
			if(a[prea[i - 1]] > b[preb[i -  1]])
				ans++;
		}
		else
		{
			int va = A.lca(prea[i - 1], sufa[i + 1]);
			int vb = B.lca(preb[i - 1], sufb[i + 1]);
			if(a[va] > b[vb])
				ans++;
		}
	}
	cout << ans << "\n";

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

C

题意： 给定n个字符串，求一个将他们拼接起来的方案，使得结果的字典序最小。

对$n$个字符串排序， $a$ 在 $b$ 前面的条件是 $a + b < b + a$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5, mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    vector<string> s(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> s[i];
    sort(s.begin() + 1, s.end(), [](string a, string b){
        return a + b < b + a;
    });
    for(int i = 1; i <= n; i++)
        cout << s[i];
    cout << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    // cin >> t;
    t = 1;
    while(t--)
        solve();
    return 0;
}

F

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

缀都连通

考虑一条链，那么两端的顶点是满足情况的，如果是其他的两个点那么不满足情况。

考虑一个环，发现环中的任意两个点都满足情况。

考虑一个图，图中可能存在环。

那么对所有的点双缩点之后，必须是一条链，如果不是一条链就不能满足。首先通过tarjan求出割点以及点双。

如果图本身就不连通（即有多个连通块），不满足。

如果点双等于1，即是一个环，满足。

接下来是对于一般的连通图，我们对于边界处的点双进行赋值，第一个边界处点双非割点全部赋为1，第二个边界处点双中非割点全部赋为2，那么询问时，如果两个点的值加和是3，即可以满足要求。

主要是如何判断是否是处于边界的点双，边界处的点双，那么此点双中的割点所在点双只有2个，不能有多个，如果有多个，必然不是在边界（因为存在一个割点至少则会存在两个点双）。

代码中为什么没有 $d = 2$

因为存在以下情况：

上图是满足情况的，中间的点双连通分量的 $d = 2$ ，但是边界1和6点都已经确定了，可以通过边界确定是否满足情况。

上图是不满足情况的，中间的点双中 $d = 2$，但是边界也可以确定，同样可以通过边界来判断是否满足情况。

那么其他情况也是如此，都是可以通过边界点双连通分量来判断， $d = 2$ 因为牵扯到有满足情况和不满足情况的，暂不考虑（但是他们可以通过边界点双来判断）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
template <class T> void Min(T &a, const T b) { if (a > b) a = b; }
template <class T> void Max(T &a, const T b) { if (a < b) a = b; }
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

// sum[i] 是点i所在点双连通分量的个数
// ans[i] 是点i所在第几个边界的点双连通分量中
int low[N], dfn[N], stk[N], top, ts, dcc_cnt, root = 1, sum[N], ans[N];
vector<int> dcc[N], e[N];
bool cut[N];
void tarjan(int u)
{
	dfn[u] = low[u] = ++ts;
	stk[++top] = u;

	int flag = 0;
	for(auto v : e[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(dfn[u] <= low[v])
			{
				flag++;
				dcc_cnt++;
				if(u != root || flag > 1) cut[u] = 1;
				int x;
				do
				{
					x = stk[top--];
					sum[x]++;
					dcc[dcc_cnt].push_back(x);
				}while(x != v);
				dcc[dcc_cnt].push_back(u);
				sum[u]++;
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}
void solve()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	tarjan(1);

	bool is = 1;
	for(int i = 1; i <= n && is; i++)
		if(!dfn[i])
			is = 0;

	if(is && dcc_cnt != 1)
	{
		int id = 0;
		for(int i = 1; i <= dcc_cnt; i++)
		{
			int d = 0; 
			for(auto x : dcc[i])
				if(cut[x]) d += sum[x] - 1;

			if(d > 2) is = 0; // 
			else if(d == 1) // 端点处的点双
			{
				id++; // 端点处点双个数加1
				for(auto x : dcc[i])
					if(!cut[x])
						ans[x] = id; // 此点双中非割点赋值
			}
		}
	}

	int q;
	cin >> q;
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		if(!is) cout << "NO\n";
		else if(dcc_cnt == 1) cout << "YES\n";
		else
		{
			if(ans[x] + ans[y] == 3) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

H

给出长度为 $n$ 的小写字符串A和 $k$ 个长度为 $m$ 的小写字符串 $B_1…B_k$ ，B的每个位置拥有统一的权值 $v_1…v_m$ ，对于每个 $B_i$ 求最大和区间满足该区间构成的字符串是A的子串（空区间合法）。

可以将问题进行转化，相当于对 $B_i$ 的每个位置求出它作为结束位置在 A 中的最长子串长度，然后在该区间求最大子段和，所有位置的最大值即为答案。

对于每个位置的最长子串，可以对 A 建后缀自动机，然后 $B_i$ 从左往右在A的后缀自动机上转移，如果当前节点无法转移则跳至父亲节点（表示去掉一个前缀字符再次进行匹配），最后无法转移则长度为 0 ，转移成功则为转移前节点的最大长度加一。

最大子段和可以通过前缀和与ST表求，B中满足是A的子串的区间为 $[l, r]$ 时， 则最大子段和可以通过 $s[r] - min(s[j]), l \leq j \lt r$ 不断进行更新。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
template <class T> void Min(T &a, const T b) { if (a > b) a = b; }
template <class T> void Max(T &a, const T b) { if (a < b) a = b; }
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

struct SuffixAutomaton {
    static constexpr int ALPHABET_SIZE = 26, N = 1e5;
    struct Node {
        int len;
        int link;
        int next[ALPHABET_SIZE];
        Node() : len(0), link(0), next{} {}
    } t[2 * N];
    int cntNodes;
    SuffixAutomaton() {
        cntNodes = 1;
        std::fill(t[0].next, t[0].next + ALPHABET_SIZE, 1);
        t[0].len = -1;
    }
    void init(string s) {
        int p = 1;
        for(auto x : s)
            p = extend(p, x - 'a');        
    }
    int extend(int p, int c) {
        if (t[p].next[c]) {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1)
                return q;
            int r = ++cntNodes;
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            std::copy(t[q].next, t[q].next + ALPHABET_SIZE, t[r].next);
            t[q].link = r;
            while (t[p].next[c] == q) {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = ++cntNodes;
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c]) {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        return cur;
    }
}sam;

ll f[N][30], a[N];
int lg[N];
void init(int n)
{
    lg[0] = -1;
    for(int i = 1; i <= n; i++)
    {
        lg[i] = lg[i - 1] + (i & (i - 1) ? 0 : 1);
        f[i][0] = a[i];
    }
    for(int j = 1; j <= lg[n]; j++)
        for(int i = 0; i + (1 << j) - 1 <= n; i++)
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
ll query(int l, int r)
{
    int k = lg[r - l + 1];
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    
    string s;
    cin >> s;
    sam.init(s);

    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    init(m);

    while(k--)
    {
        ll ans = 0;
        string t;
        cin >> t;
        t = " " + t;
        int p = 1, l = 0;
        for(int i = 1; i <= m; i++)
        {
            int c = t[i] - 'a';
            while(p && !sam.t[p].next[c])
                p = sam.t[p].link, l = sam.t[p].len;
            if(p)
            {
                p = sam.t[p].next[c], l++;
                Max(ans, a[i] - query(i - l, i - 1));
            }
            else p = 1, l = 0;
        }
        cout << ans << "\n";
    }

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

J

给定一个城市有若干十字路口，右转不需要等红灯，直行、左转和掉头都需要，求起

点到终点最少等几次红灯

把每条路看做点，十字路口处连边，形成一个边权为0/1的有向图。

可以使用dijkstra求最短路。

同时也可以用01BFS解决，此时使用deque维护队列，边权为0时入队头，边权为1时入队尾。

无论一个路口四个方向怎么给，因为都是按照逆时针方向给出的，所以所有路的相对关系都可以得到，每走到一个路口，都会知道当前路口的四个方向的情况。

$dis[i][j]$ 代表从起点的路到达终点路的最小等待数，因为点数过多，将第二维压缩，压缩成四个方向，即到达（ $i$，$i$ 路口的第 $j$ 个方向指向的路口）这条路上。

队列中存的是路的起始和结束位置，以及到达该路上的最小等待红灯数。

对于01BFS的理解，我们首先扩展的是距离等于0的位置（这样肯定是最优的，没有距离嘛），所以就是先走当前的最短路，然后再扩展有距离的路，也是一层一层的扩展。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
template <class T> void Min(T &a, const T b) { if (a > b) a = b; }
template <class T> void Max(T &a, const T b) { if (a < b) a = b; }
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int N = 5e5 + 5, M = N;
const int mod = 1e9 + 7;
const ld eps = 1e-8;

int dis[N][4], to[N][4];

void solve()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 4; j++)
			cin >> to[i][j];

	int sx, sy, fx, fy;
	cin >> sx >> sy >> fx >> fy;

	memset(dis, 0x3f, sizeof dis);

	deque<array<int, 3>> dq;
	dq.push_front({sx, sy, 0});
	while(!dq.empty())
	{
		auto t = dq.front();
		dq.pop_front();

		int x = t[0], y = t[1], w = t[2];

		if(!y) continue;
		int id = -1;
		for(int i = 0; i < 4; i++)
		{
			if(to[x][i] == y)
				id = i;
		}
		if(dis[x][id] > w)
			dis[x][id] = w;
		else continue;

		for(int i = 0; i < 4; i++)
			if(to[y][i] == x)
				id = (i + 1) % 4;

		for(int i = 0; i < 4; i++)
		{
			if(i == id)
				dq.push_front({y, to[y][i], w});
			else dq.push_back({y, to[y][i], w + 1});
		}
	}

	int id = -1;
	for(int i = 0; i < 4; i++)
		if(to[fx][i] == fy)
			id = i;
	if(dis[fx][id] == 0x3f3f3f3f) cout << "-1\n";
	else cout << dis[fx][id] << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}