Educational Codeforces Round 53 (Rated for Div. 2)

比赛链接

Educational Codeforces Round 53 (Rated for Div. 2)

A. Diverse Substring

题面

给定一个字符串$S$S，求出一个子串满足子串中出现的所有字母出现次数不超过这个子串长度的一半(下取整)，如果不存在输出NO。

解法

• 显然，只要不是所有字符都相同，那么这个串一定存在这样的子串。我们只要找到一个长度为2且两个字符不相同的子串就可以了。
• 时间复杂度：$O(n)$O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
int main() {
	int l; cin >> l;
	string st; cin >> st;
	for (int i = 0; i < l - 1; i++)
		if (st[i] != st[i + 1]) return cout << "YES\n" << st[i] << st[i + 1] << "\n", 0;
	cout << "NO\n";
	return 0;
}

B. Vasya and Books

题面

给定一个入栈序列，然后每一次按照顺序询问从栈顶取出$x$x时至少要往栈中放入多少个数。保证询问合法。

解法

• 因为保证询问合法且按照顺序，那么我们直接按照题意模拟即可
• 时间复杂度：$O(n)$O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
int a[200010], used[200010];
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1, l = 0; i <= n; i++) {
		int x, s = 0; read(x);
		while (l < n && a[l] != x && !used[x]) l++, s++, used[a[l]] = 1;
		cout << s << ' ';
	}
	cout << "\n";
	return 0;
}

C. Vasya and Robot

题面

给定一个长度为$n$n的操作序列，可以上下左右移动。可以修改一些操作，修改的代价为修改的最大位置-最小位置+1。问从$(0,0)$(0,0)走到一个定点$(x,y)$(x,y)的最小代价，如果无解输出$-1$−1。
$n≤2×10^5$n≤2×105

解法

• 可以先将无解的情况去除：1.$(0,0)$(0,0)到$(x,y)$(x,y)的曼哈顿距离和$n$n奇偶不同 2.$n$n小于$(0,0)$(0,0)到$(x,y)$(x,y)的曼哈顿距离。然后判断答案是否可以为0。
• 那么现在就一定需要修改。可以发现，这个答案其实是满足单调性的，所以我们可以考虑二分答案，假设为$mid$mid。那么问题就转化成如何检查答案合法性。
• 考虑枚举左端点$l$l，那么可以进行修改的区间就变成$[l,l+mid-1]$[l,l+mid−1]，我们可以计算出除去这个区间其他操作带来的影响，然后判断一下当前坐标到$(x,y)$(x,y)的曼哈顿距离是否不超过$mid$mid即可。
• 时间复杂度：$O(n\log n)$O(nlogn)。

代码

#include <bits/stdc++.h>
#define N 200010
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
int n, sx, sy; char st[N]; map <char, char> rev;
void Move(char c, int &x, int &y) {
	if (c == 'U') y++; if (c == 'D') y--;
	if (c == 'L') x--; if (c == 'R') x++;
}
bool check(int mid) {
	int ax = 0, ay = 0, bx = 0, by = 0;
	for (int i = mid + 1; i <= n; i++) Move(st[i], bx, by);
	for (int i = 1; i <= n - mid + 1; i++) {
		int x = ax + bx, y = ay + by;
		if (abs(sx - x) + abs(sy - y) <= mid) return true;
		Move(st[i], ax, ay), Move(rev[st[i + mid]], bx, by);
	}
	return false;
}
int main() {
	cin >> n >> st + 1 >> sx >> sy;
	if (abs(sx) + abs(sy) > n || (abs(sx) + abs(sy)) % 2 != n % 2) return cout << "-1\n", 0;
	int x = 0, y = 0;
	for (int i = 1; i <= n; i++) Move(st[i], x, y);
	if (x == sx && y == sy) return cout << "0\n", 0;
	rev['U'] = 'D', rev['D'] = 'U', rev['L'] = 'R', rev['R'] = 'L';
	int l = 1, r = n, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
			else l = mid + 1;
	}
	cout << ans << "\n";
	return 0;
}

D. Berland Fair

题面

有一个长度为$n$n的环，每一个点上有一个权值$a[i]$a[i]。你一开始有一个权值$T$T，从1号点出发，沿着环进行如下操作：如果当前的$T$T不小于$a[i]$a[i]，那么$T-a[i],ans+1$T−a[i],ans+1，否则$T$T不变。问最后的$ans$ans。
$n≤2×10^5,T≤10^{18}$n≤2×105,T≤1018

解法

• 假设从$1$1号点出发回到$1$1号点为一次更新，那么显然相同的更新情况一定是一段连续的区间组成的。
• 那么我们就可以暴力做这个过程。每一次从$1$1到$n$n计算会选择哪些点以及$T$T的情况，然后可以$O(1)$O(1)计算不断这样做直到不能做为止的时候$T$T的大小和$ans$ans的情况。然后重复上述过程即可。
• 可以发现，因为有取模操作，所以最坏情况下$T$T每一次缩小一半。
• 时间复杂度：$O(n\log T)$O(nlogT)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
ll a[200010];
int main() {
	int n; ll T, ans = 0; read(n), read(T);
    for (int i = 1; i <= n; i++) read(a[i]);
    while (true) {
        ll sum = 0, cnt = 0;
        for (int i = 1; i <= n; i++) 
			if (T >= a[i]) T -= a[i], cnt++, sum += a[i];
        if (sum > 0) cnt *= (T / sum) + 1, T %= sum, ans += cnt;
        	else break;
    }
    cout << ans << "\n";
	return 0;
}

E. Segment Sum

题面

给定三个数$l,r,k$l,r,k，问区间$[l,r]$[l,r]中有所有出现不超过$k$k种数字的数的和。
$l,r≤10^{18}$l,r≤1018

解法

• 显然可以数位dp
• 设$f[i][j][0/1][0/1]$f[i][j][0/1][0/1]表示当前做到数的第$i$i位，选择数字的集合为$j$j，是否有前导零和前$i$i位是否完全和原数相同的答案。这里的答案返回的是一个pair，记录的是满足这些条件额数的个数和对这些数的和。
• 转移比较简单，假设当前枚举到的位置填$x$x，有$s$s个数满足要求，那么这一位为$x$x对答案的贡献就可以表示成$10^{i-1}sx$10i−1sx。
• 时间复杂度：$O(2^{10}×18×10×4)$O(210×18×10×4)。

代码

#include <bits/stdc++.h>
#define Mod 998244353
#define ll long long
#define N 110
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
pair <int, int> f[N][1 << 11][2][2]; int a[N], pw[N]; ll l, r, K;
pair <int, int> dp(int pos, int s, bool lim, bool l, int tot) {
	if (tot > K) return make_pair(0, 0);
	if (pos == -1) return make_pair(!l, 0);
	if (f[pos][s][lim][l].first != -1) return f[pos][s][lim][l];
	int x = (lim) ? a[pos] : 9, s1 = 0, s2 = 0;
	for (int i = 0; i <= x; i++)
		if (!l) {
			pair <int, int> t = dp(pos - 1, s | (1 << i), lim && i == a[pos], l, tot + ((s & (1 << i)) == 0));
			int tx = t.first, ty = t.second;
			s1 = (s1 + tx) % Mod, s2 = (s2 + 1ll * i * pw[pos] % Mod * tx % Mod) % Mod, s2 = (s2 + ty) % Mod;
		} else
			if (i == 0) {
				pair <int, int> t = dp(pos - 1, s, lim && i == a[pos], true, tot);
				int tx = t.first, ty = t.second;
				s1 = (s1 + tx) % Mod, s2 = (s2 + ty) % Mod;
			} else {
				pair <int, int> t = dp(pos - 1, s | (1 << i), lim && i == a[pos], false, tot + 1);
				int tx = t.first, ty = t.second;
				s1 = (s1 + tx) % Mod, s2 = (s2 + 1ll * i * pw[pos] % Mod * tx % Mod) % Mod, s2 = (s2 + ty) % Mod;
			}
	if (!lim && !l) f[pos][s][lim][l] = make_pair(s1, s2);
	return make_pair(s1, s2);
}
int solve(ll n) {
	int len = -1; ll x = n;
	while (x) a[++len] = x % 10, x /= 10;
	memset(f, -1, sizeof(f));
	pair <int, int> tmp = dp(len, 0, 1, 1, 0);
	return tmp.second;
}
int main() {
	read(l), read(r), read(K); pw[0] = 1;
	for (int i = 1; i <= 20; i++) pw[i] = 10ll * pw[i - 1] % Mod;
	cout << (solve(r) - solve(l - 1) + Mod) % Mod << "\n";
	return 0;
}

F. Choosing Two Paths

题面

给定一棵$n$n个点的树，要求找到2条路径$x_1\rightarrow y_1,x_2\rightarrow y_2$x1​→y1​,x2​→y2​满足这两条路径的端点均不在另一条路径上，在满足路径交最大的情况下满足路径长度之和最大，输出方案。
保证存在合法的两条路径且它们有交。
$n≤2×10^5$n≤2×105

解法

• 因为满足至少有交，所以我们可以找到一个度数大于2的点作为根。
• 考虑枚举最后交的$lca$lca，那么我们可以尽量让两个端点在$lca$lca的同一个子树里，然后让这两个点的深度尽量大。
• 那么我们可以记$f[i]$f[i]表示以$i$i为$lca$lca的子树中最优的两条路径，辅助数组$g[i]$g[i]表示以点$i$i为根的子树中如果存在分叉点，最深的分叉点的子树中最深的两个点是什么。$f$f和$g$g可以在$dfs$dfs的过程中处理出来。
• 中间可能需要使用sort，时间复杂度：$O(n)$O(n)~$O(n\log n)$O(nlogn)。

代码

#include <bits/stdc++.h>
#define N 200010
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
bool fl[N]; int n, cnt, d[N], s[N], mxd[N];
struct Edge {int next, num;} e[N * 3];
struct Info {
	int sx, sy, lca;
	bool operator < (const Info &g) const {
		if (d[lca] != d[g.lca]) return d[lca] > d[g.lca];
		return d[sx] + d[sy] > d[g.sx] + d[g.sy];
	}
} g[N];
struct Node {int x1, y1, x2, y2, ans, len;} f[N];
bool cmp(int x, int y) {return d[mxd[x]] > d[mxd[y]];}
void add(int x, int y) {
	e[++cnt] = (Edge) {e[x].next, y};
	e[x].next = cnt;
}
void dfs(int x, int fa) {
	d[x] = d[fa] + 1, mxd[x] = x; int tot = 0;
	for (int p = e[x].next; p; p = e[p].next) {
		int k = e[p].num; if (k == fa) continue;
		tot++, dfs(k, x);
		if (d[mxd[k]] > d[mxd[x]]) mxd[x] = mxd[k];
	}
	if (tot >= 2) fl[x] = true;
	vector <Info> a; vector <int> b;
	for (int p = e[x].next; p; p = e[p].next) {
		int k = e[p].num; if (k == fa) continue;
		if (fl[k]) fl[x] = true, a.push_back(g[k]);
			else b.push_back(k);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), cmp);
	if (a.size() >= 2) {
		Info tx = a[0], ty = a[1]; g[x] = tx;
		int x1 = tx.sx, y1 = tx.sy, x2 = ty.sx, y2 = ty.sy;
		f[x] = (Node) {x1, x2, y1, y2};
		f[x].ans = d[tx.lca] + d[ty.lca] - 2 * d[x];
		f[x].len = d[x1] + d[y1] + d[x2] + d[y2] - 4 * d[x];
		return;
	}
	if (a.size() == 1) {
		Info tx = a[0]; g[x] = tx;
		if (b.size() >= 2) {
			int x1 = tx.sx, y1 = tx.sy, x2 = mxd[b[0]], y2 = mxd[b[1]];
			f[x] = (Node) {x1, x2, y1, y2};
			f[x].ans = d[tx.lca] - d[x];
			f[x].len = d[x1] + d[y1] + d[x2] + d[y2] - 4 * d[x];
		}
		return;
	}
	if (b.size() >= 2) g[x] = (Info) {mxd[b[0]], mxd[b[1]], x};
}
int main() {
	read(n); cnt = n;
	for (int i = 1; i < n; i++) {
		int x, y; read(x), read(y);
		add(x, y), add(y, x); s[x]++, s[y]++;
	}
	int rt;
	for (int i = 1; i <= n; i++) if (s[i] >= 3) rt = i;
	memset(fl, false, sizeof(fl)); dfs(rt, 0);
	int mx1 = -INT_MAX, mx2 = mx1; Node ans;
	for (int i = 1; i <= n; i++)
		if (f[i].ans > mx1) mx1 = f[i].ans, mx2 = f[i].len, ans = f[i];
			else if (f[i].ans == mx1 && f[i].len > mx2) mx2 = f[i].len, ans = f[i];
	cout << ans.x1 << ' ' << ans.y1 << "\n";
	cout << ans.x2 << ' ' << ans.y2 << "\n";
	return 0;
}