【APIO2021】雨林跳跃

  • 考虑每个点它能到达的点的集合,可以发现是个 \(V\) 字形的图案,因为每个点第一步只有 \(2\) 种选择。

    然后暴力就是用单调栈求出每个点的两条出边后 \(bfs\) 一遍即可。

  • \(C...D\) 段最高的高度为 \(mx\),若 \(B...C-1\) 有比它高的则无解。

  • \(A...B\) 中只有后缀 \(max < mx\) 的范围可能有解,设为 \(A‘...B\)

    考虑 \(A‘...B\) 中最高的为 \(x\)\(x\) 左边的一定比它劣,而右边的向右第一步能走到的范围必定也在 \(x\) 的范围之内,不会更优。

  • 于是转化为单点到区间的最短路径。

  • \(x\)\(k\) 步到达的最左与最右为 \(l,r\),若 \(r < C\) 则答案一定比 \(k\) 大。

    而这个可以通过倍增求出 \(k\) 使得 \(x\)\(k + 1\) 步便会超过或到达 \(C\)

    • \(h_l < h_r\),则答案为 \(k + 1\),直接从 \(r\) 向右走一步即可。
    • 否则
      • \(l\) 向右一步到达的点在区间内部,则答案为 \(k + 1\)
      • 否则 \(r\) 只能一直向右走,可以单方向倍增求出答案。
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;

typedef pair <int, int> pii;

const int N = 6e5 + 10;

int n, h[N], l[N][20], r[N][20], f[N][20], top, s[N], b[N];

pii g[N][20];

pii qmax_(int l, int r) {
	int k = b[r - l + 1];
	return max(g[l][k], g[r - (1<<k) + 1][k]);
}

void init(int N, vector <int> H) {
	n = N, b[0] = -1;
	
	for (int i = 1; i <= n; i++)	
		h[i] = H[i - 1], g[i][0] = pii(h[i], i), b[i] = b[i>>1] + 1;
		
	for (int k = 1; k <= b[n]; k++)
		for (int i = 1; i + (1<<k) - 1 <= n; i++)
			g[i][k] = max(g[i][k - 1], g[i + (1<<k - 1)][k - 1]);
		
	for (int i = 1; i <= n; i++) {
		while (top && h[s[top]] < h[i])
			top--;
		
		l[i][0] = top ? s[top] : i;
		s[++top] = i;
	}
	
	top = 0;
	
	for (int i = n; i; i--) {
		while (top && h[s[top]] < h[i])
			top--;
		
		f[i][0] = r[i][0] = top ? s[top] : i;
		s[++top] = i;
	}
	
	for (int k = 1; k <= b[n]; k++)
		for (int i = 1; i <= n; i++) {
			l[i][k] = min(l[l[i][k - 1]][k - 1], l[r[i][k - 1]][k - 1]);
			r[i][k] = max(r[l[i][k - 1]][k - 1], r[r[i][k - 1]][k - 1]);
			f[i][k] = f[f[i][k - 1]][k - 1];
		}
}

int minimum_jumps(int A, int B, int C, int D) {
	A++, B++, C++, D++;
	
	int mx = qmax_(C, D).first, L = A, R = B + 1;
	
//	cout<<mx<<‘ ‘<<qmax_(B, C - 1).first<<‘\n‘;
	
	if (qmax_(B, C - 1).first > mx)
		return -1;
		
	while (L < R) {
		int mid = (L + R)>>1;
		
		if (qmax_(mid, R).first > mx)
			L = mid + 1;
		else	
			R = mid;
	}
	
	int x = qmax_(L, B).second, ans = 0, y = x;
	
	for (int k = b[n]; k >= 0; k--)
		if (max(r[x][k], r[y][k]) < C) {
			ans += 1<<k;
			int p = min(l[x][k], l[y][k]), q = max(r[x][k], r[y][k]);
			x = p, y = q;
		}
	
	if (h[y] > h[x]) 
		return ans + 1;
	
	if (f[x][0] >= C && f[x][0] <= D)
		return ans + 1;
	
	for (int k = b[n]; k >= 0; k--)
		if (f[y][k] < C)
			y = f[y][k], ans += 1<<k;
	
	return ans + 1;
}

【APIO2021】雨林跳跃

上一篇:win10系统 更新后与VMware Workstation 与 Device/Credential Guard 不兼容问题


下一篇:Sql Server助手类