[题解]JOI 2020 Final 题解

• 省选临近却无比颓废，逼自己去做 JOI

A

题意

• 给定一个长度为 (N+1) 的数组 (A) 和一个长度为 (N) 的数组 (B)

• 对于每个 (1le ile N+1)，求出：对每个 (1le jle N) 求出一个 (k_j)，满足 (k) 数组包含 (1) 到 (N+1) 中除 (i) 外的所有数，最小化 (max_{i=1}^Nmax(A_{k_i}-B_i,0))

• (1le Nle 2 imes10^5)，(1le A_i,B_ile10^9)

Solution

• 可以发现 (a<b,c<d) 时 (b-c>a-c) 且 (b-c>b-d)，故 (a) 配 (c)，(b) 配 (d) 比 (a) 配 (d)，(b) 配 (c) 优

• 故把两个数组排序，预处理出排序以后两个数组长度为 (i) 的前缀匹配的 (max(a-b))，后缀同理，即可求出答案

• (O(Nlog N))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}

typedef long long ll;

const int N = 2e5 + 5;

int n, b[N];
ll pre[N], suf[N], ans[N];

struct elem
{
	int x, id;
} a[N];

inline bool comp(elem a, elem b)
{
	return a.x < b.x;
}

int main()
{
	read(n);
	for (int i = 1; i <= n + 1; i++) read(a[i].x), a[i].id = i;
	std::sort(a + 1, a + n + 2, comp);
	for (int i = 1; i <= n; i++) read(b[i]);
	std::sort(b + 1, b + n + 1);
	for (int i = 1; i <= n + 1; i++) pre[i] = Max(pre[i - 1], 1ll * a[i].x - b[i]);
	for (int i = n + 1; i >= 1; i--) suf[i] = Max(suf[i + 1], 1ll * a[i].x - b[i - 1]);
	for (int i = 1; i <= n + 1; i++) ans[a[i].id] = Max(pre[i - 1], suf[i + 1]);
	for (int i = 1; i <= n + 1; i++) printf("%lld ", ans[i]);
	return puts(""), 0;
}

B

题意

• 有一个只包含 J、O、I 的长度为 (N) 的字符串

• 每次可以删掉一个字符，但如果删掉的字符不在串首或串尾，则要花费 (1) 的代价

• 求把原串变成 JJ... JOO...OII... I（三种字母均有 (K) 个）的最小代价，或者判断无解

• (3le Nle2 imes10^5)，(1le Klefrac N3)

Solution

• 易得选出一个最短的子串包含 JJ... JOO... OII... I 为子序列，这个子串长度减去 (3K) 即为答案

• 于是我们只需求出对于每个 (i)，以 (i) 开头的后缀中该子序列最后一个字符所在的下标

• 预处理 (i) 之后字符 J、O、I 分别第 (K) 次出现的位置即可

• (O(N))

Code

#include <bits/stdc++.h>

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

const int N = 2e5 + 5, INF = 0x3f3f3f3f;

int n, k, nxt[N][3], top[3], stk[3][N], ans = INF;
char s[N];

int main()
{
	std::cin >> n >> k;
	scanf("%s", s + 1);
	for (int i = n; i >= 1; i--)
	{
		int c = s[i] == 'I' ? 2 : (s[i] == 'O' ? 1 : 0);
		stk[c][++top[c]] = i;
		for (int c = 0; c < 3; c++)
			if (top[c] >= k) nxt[i][c] = stk[c][top[c] - k + 1] + 1;
	}
	for (int i = 1; i <= n; i++)
	{
		int lst = nxt[nxt[nxt[i][0]][1]][2];
		if (lst) ans = Min(ans, lst - i - k * 3);
	}
	return std::cout << (ans == INF ? -1 : ans) << std::endl, 0;
}

C

题意

• 有一个长为 (L) 的环，环上有 (N) 个点，第 (i) 个位置为 (X_i)，两两不同且不为原点

• 如果一个点在时刻 (T_i) 之前经过则会得到 (1) 的收益

• 一开始在原点，每次可以花费 (1) 的时间向某个方向走 (1) 个长度单位

• 求最大收益

• (1le Nle 200)，(1le L,T_ile10^9)，(1le X_i<L)，(X) 按严格递增序给出

Solution

• 显然每次走到的点一定是一段前缀并上一段后缀

• DP：(f_{l,r,i}) 和 (g_{l,r,i}) 分别表示走到了 ([1,l]cup[r,n])，获得 (i) 收益需要的最少时间，(f) 表示最后停在 (l)，(g) 表示最后停在 (r)

• 转移即枚举下一次到达 (l+1) 还是 (r-1)，具体方程略

• (O(N^3))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline void GMin(T &a, const T &b) {if (b < a) a = b;}

template <class T>
inline void GMax(T &a, const T &b) {if (b > a) a = b;}

const int N = 205, INF = 0x3f3f3f3f;

int n, L, X[N], T[N], f[N][N][N], g[N][N][N], ans;

int main()
{
	read(n); read(L); X[n + 1] = L;
	for (int i = 1; i <= n; i++) read(X[i]);
	for (int i = 1; i <= n; i++) read(T[i]);
	memset(f, INF, sizeof(f)); memset(g, INF, sizeof(g));
	f[0][n + 1][0] = 0; g[0][n + 1][0] = 0;
	for (int l = 0; l <= n; l++)
		for (int r = n + 1; r > l + 1; r--)
			for (int i = 0; i <= l + n - r + 1; i++)
			{
				int tf = f[l][r][i] + X[l + 1] - X[l],
					tg = g[l][r][i] + X[r] - X[r - 1],
					wf = g[l][r][i] + L - X[r] + X[l + 1],
					wg = f[l][r][i] + L - X[r - 1] + X[l];
				GMin(f[l + 1][r][i + (tf <= T[l + 1])], tf);
				GMin(g[l][r - 1][i + (tg <= T[r - 1])], tg);
				GMin(f[l + 1][r][i + (wf <= T[l + 1])], wf);
				GMin(g[l][r - 1][i + (wg <= T[r - 1])], wg);
			}
	for (int l = 0; l <= n; l++)
		for (int r = n + 1; r > l; r--)
			for (int i = 0; i <= l + n - r + 1; i++)
			{
				if (l >= 1 && f[l][r][i] <= T[l]) GMax(ans, i);
				if (r <= n && g[l][r][i] <= T[r]) GMax(ans, i);
			}
	return std::cout << ans << std::endl, 0;
}

D

题意

• 给定一个 (N) 点 (M) 边的有向图，每条边有长度 (C) 和翻转代价 (D)，求翻转最多一条边之后，(1) 到 (N) 的最短路加上 (N) 到 (1) 的最短路的最小值

• (2le Nle 200)，(1le Mle 5 imes10^4)，(0le Cle10^6)，(0le Dle 10^9)，可能存在重边

Solution

• 考虑翻转 (<u,v>) 之后 (1) 到 (N) 最短路的可能情况：

• （1）(1) 先到 (v)（不能经过 (u)），然后走 (<v,u>)，最后 (u) 到 (N)（不能经过 (v)）

• （2）(1) 到 (u)，然后通过该边的一条重边到达 (v)，最后 (v) 到 (N)

• （3）(1) 到 (N)，不经过点 (u)

• （4）(1) 到 (N)，不经过点 (v)

• （5）(1) 到 (N)，(v) 在 (u) 前，也就是说先 (1) 到 (u)，再 (u) 到 (N)（不能经过 (v)）

• （6）(1) 到 (N)，(u) 和 (v) 之间隔了至少一个点，也就是枚举 (x)，先 (1) 到 (x)（不经过 (v)），再 (x) 到 (N)（不经过 (u)）

• (N) 到 (1) 同理

• 于是只需对于任意 (u) 预处理不经过点 (u) 的单源最短路，(N) 次 Dijkstra 即可，注意可以使用不加优先队列的 (O(N^2+M)) 暴力 Dijkstra

• (O(N^3+NM))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

const int N = 205, M = 5e4 + 5, INF = 0x3f3f3f3f;

int n, m, d[M], ans, d1[N][N], d2[N][N], d3[N][N], d4[N][N], alt[M], lf[M], rf[M];
bool vis[N];
std::vector<int> eg[N][N];

struct graph
{
	int ecnt, nxt[M], adj[N], st[M], go[M], val[M];

	void add_edge(int u, int v, int w)
	{
		nxt[++ecnt] = adj[u]; adj[u] = ecnt; st[ecnt] = u; go[ecnt] = v; val[ecnt] = w;
	}
	
	void dij(int S, int X, int *dis)
	{
		for (int i = 1; i <= n; i++) dis[i] = INF;
		memset(vis, 0, sizeof(vis));
		if (S != X) dis[S] = 0;
		while (1)
		{
			int mn = INF, u = 0;
			for (int v = 1; v <= n; v++)
				if (v != X && !vis[v] && dis[v] < mn) mn = dis[v], u = v;
			if (!u) return; vis[u] = 1;
			for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
				if (v != X) dis[v] = Min(dis[v], dis[u] + val[e]);
		}
	}
} G1, G2;

int main()
{
	int x, y, z;
	read(n); read(m);
	for (int i = 1; i <= m; i++)
		read(x), read(y), read(z), read(d[i]), G1.add_edge(x, y, z),
			G2.add_edge(y, x, z), eg[x][y].push_back(i);
	for (int i = 0; i <= n; i++) G1.dij(1, i, d1[i]), G1.dij(n, i, d2[i]),
		G2.dij(1, i, d3[i]), G2.dij(n, i, d4[i]);
	ans = d1[0][n] + d2[0][1];
	for (int u = 1; u <= n; u++)
		for (int v = 1; v <= n; v++)
		{
			int len = eg[u][v].size();
			lf[0] = rf[len + 1] = INF;
			for (int i = 1; i <= len; i++)
				lf[i] = Min(lf[i - 1], G1.val[eg[u][v][i - 1]]);
			for (int i = len; i >= 1; i--)
				rf[i] = Min(rf[i + 1], G1.val[eg[u][v][i - 1]]);
			for (int i = 1; i <= len; i++) alt[eg[u][v][i - 1]] =
				Min(lf[i - 1], rf[i + 1]);
		}
	for (int e = 1; e <= m; e++)
	{
		int u = G1.st[e], v = G1.go[e], dis1 = Min(INF, d1[u][v] + d4[v][u] + G1.val[e]),
			dis2 = Min(INF, d2[u][v] + d3[v][u] + G1.val[e]);
		if (alt[e] < INF) dis1 = Min(dis1, d1[0][u] + d4[0][v] + alt[e]),
			dis2 = Min(dis2, d2[0][u] + d3[0][v] + alt[e]);
		dis1 = Min(dis1, Min(d1[u][n], d1[v][n]));
		dis2 = Min(dis2, Min(d2[u][1], d2[v][1]));
		dis1 = Min(dis1, d1[0][u] + d4[v][u]);
		dis2 = Min(dis2, d2[0][u] + d3[v][u]);
		for (int x = 1; x <= n; x++) if (x != u && x != v)
			dis1 = Min(dis1, d1[v][x] + d4[u][x]),
			dis2 = Min(dis2, d2[v][x] + d3[u][x]);
		if (dis1 < INF && dis2 < INF) ans = Min(ans, dis1 + dis2 + d[e]);
	}
	return std::cout << (ans < INF ? ans : -1) << std::endl, 0;
}

E

题意

• 一个 (N) 个数的序列 (S)，(Q) 组询问

• 每次询问给出 (T,L,R)，回答对于所有 (Lle ile R)，(S) 的区间 ([max(1,i-T),i]) 最大值之和

• (1le N,Qle2 imes10^5)，(1le Sle10^9)

Solution

• 为了方便讨论，下面 (T) 加上一，即表示以 (i) 为结尾的长度为 (K) 的区间

• 先预处理 (pre_i) 表示 (i) 左边第一个严格大于 (a_i) 的数所在下标（没有则为 (-infty)）（由于左端点是 (max(1,i-T+1))，故不存在时不能为 (0)）

• (suf_i) 表示 (i) 右边第一个不小于 (a_i) 的数所在下标（没有则为 (N+1)）（注意一个是严格大于一个是不小于，为避免重复）

• 考虑固定一个 (T) 时，(S_k) 成为以 (i) 为结尾的区间最大值的条件：

• [iin[k+max(0,T-k+pre_k),min(suf_k-1,k+T-1)] ]

• 设这个区间为 ([l_k,r_k])，考虑这两个端点随 (T) 递增时的变化：(r) 先递增 (1)，然后维持不变，(l) 先维持不变，然后递增 (1)

• 回到询问，我们要求的是：

• [sum_{i=L}^Rsum_k[l_kle ile r_k]S_k ]

• 考虑容斥，用 (ile r) 减去 (i<l)，下面只考虑 (r)

• 如果在当前的 (T) 下 (r_k) 维持不变，则可以用线段树，区间 ([le r_k]) 加一，询问区间 ([L,R]) 和

• 否则把 (r_k) 表示成 (r'_k+T) 的形式，再开一棵线段树，区间 ([le r'_k]) 加一，询问区间 ([L-T,R-T]) 和

• 而 (T) 是不断变化的，故可以把询问离线按 (T) 排序之后，边询问边按 (T) 从小到大处理 (l) 和 (r) 的变化，注意 (l) 不能大于 (r)，遇到这种情况需要把对应区间删掉

• (O((N+Q)log N))

Code

#include <bits/stdc++.h>
#define p2 p << 1
#define p3 p << 1 | 1

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

typedef long long ll;

const int N = 2e5 + 5, M = N << 3;

int n, q, a[N], top, stk[N], pre[N], suf[N];
ll ans[N];

struct seg
{
	ll sum[M], add[M];
	
	void down(int l, int r, int mid, int p)
	{
		add[p2] += add[p]; add[p3] += add[p];
		sum[p2] += add[p] * (mid - l + 1); sum[p3] += add[p] * (r - mid);
		add[p] = 0;
	}
	
	void change(int l, int r, int s, int e, ll v, int p)
	{
		if (e < l || s > r) return;
		if (s <= l && r <= e) return (void) (add[p] += v, sum[p] += v * (r - l + 1));
		int mid = l + r >> 1; down(l, r, mid, p);
		change(l, mid, s, e, v, p2); change(mid + 1, r, s, e, v, p3);
		sum[p] = sum[p2] + sum[p3];
	}
	
	ll ask(int l, int r, int s, int e, int p)
	{
		if (e < l || s > r) return 0;
		if (s <= l && r <= e) return sum[p];
		int mid = l + r >> 1; down(l, r, mid, p);
		return ask(l, mid, s, e, p2) + ask(mid + 1, r, s, e, p3);
	}
} L1, L2, R1, R2;

struct query
{
	int l, r, id;
};

std::vector<query> que[N];
std::vector<int> t1[N], t2[N], t3[N];

int main()
{
	int t, l, r;
	read(n); read(q);
	for (int i = 1; i <= n; i++) read(a[i]);
	stk[top = 0] = 0;
	for (int i = 1; i <= n; i++)
	{
		while (top && a[stk[top]] <= a[i]) top--;
		pre[i] = stk[top]; stk[++top] = i;
	}
	stk[top = 0] = n + 1;
	for (int i = n; i >= 1; i--)
	{
		while (top && a[stk[top]] < a[i]) top--;
		suf[i] = stk[top]; stk[++top] = i;
	}
	for (int i = 1; i <= q; i++)
	{
		read(t); read(l); read(r); if (t < n) t++;
		que[t].push_back((query) {l, r, i});
	}
	for (int i = 1; i <= n; i++)
		L1.change(-n, n, -n, i, a[i], 1), R2.change(-n, n, -n, i - 1, a[i], 1);
	for (int i = 1; i <= n; i++)
	{
		t1[suf[i] - i].push_back(i);
		if (pre[i]) t2[i - pre[i]].push_back(i), t3[suf[i] - pre[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < t1[i].size(); j++)
			R2.change(-n, n, -n, t1[i][j] - 1, -a[t1[i][j]], 1),
			R1.change(-n, n, -n, suf[t1[i][j]] - 1, a[t1[i][j]], 1);
		for (int j = 0; j < t2[i].size(); j++)
			L1.change(-n, n, -n, t2[i][j], -a[t2[i][j]], 1),
			L2.change(-n, n, -n, t2[i][j] - i, a[t2[i][j]], 1);
		for (int j = 0; j < t3[i].size(); j++)
			R1.change(-n, n, -n, suf[t3[i][j]] - 1, -a[t3[i][j]], 1),
			L2.change(-n, n, -n, suf[t3[i][j]] - i, -a[t3[i][j]], 1);
		for (int j = 0; j < que[i].size(); j++)
		{
			int l = que[i][j].l, r = que[i][j].r;
			ans[que[i][j].id] = R1.ask(-n, n, l, r, 1) + R2.ask(-n, n, l - i, r - i, 1)
				- L1.ask(-n, n, l + 1, r + 1, 1)
					- L2.ask(-n, n, l - i + 1, r - i + 1, 1);
		}
	}
	for (int i = 1; i <= q; i++) printf("%lld
", ans[i]);
	return 0;
}