2022牛客多校3补题

2022牛客多校3补题

更好观感

A

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

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

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

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

C

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

H

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

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

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

J

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

点到终点最少等几次红灯

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

可以使用dijkstra求最短路。

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

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

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

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

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84