美团笔试

1.模拟题，分别对RBG每个位置往左往右找即可。

2.凑颜色，直接二分答案，因为是无环转换，因此可以直接从a转换到b，再从b转换到c。

using ll = long long;
void solve() {
	int a, b, c;
	int x, y;
	cin >> a >> b >> c;
	cin >> x >> y;

	auto check = [&](int k) {
		ll reta = a, retb = b, retc = c;
		ll resa = max(0ll, reta - k);
		retb += resa / x;
		ll resb = max(0ll, retb - k);
		retc += resb / y;
		return min({reta, retb, retc}) >= k;
	};

	int l = 0, r = (int)1e9;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (check(m)) {
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	cout << l - 1 << '\n';
}

3.

题目描述：

输入n q x y（定义权值数组为a），表示有n个点，q个询问，如果a[nxt[i]] > a[i]，则+x, 否则+y， x和y可能是负数，

第二行输入nxt数组，表示i->nxt[i]有一条边

然后第三行输入权值数组a

接下来又q（1e5）个询问，每个询问给出ui和ki表示从ui起始最多跳ki步能取得的最大和是多少？

1<=ui<=n 1<=ki<=1e9

解题思路：考虑k太大不可能直接去模拟每一步，因此我们只需要考虑贡献的计算。

考虑把k按2进制拆分，这样去算贡献，然后合并，那么这个问题就变成了从每个点开始走(2^j)-1步能取得的最大和是多少？

这个我们考虑st表构建的过程，比较类似，也是贡献合并，因此我们的状态就设计出来了。

定义

f[i][j]：i这个点跳2^j - 1步到哪？

g[i][j]: i这个点跳2^j-1步最大贡献是多少？

比较显然的是f[i][j]的转移

f[i][j] = f[f[i][j - 1][j - 1]

接下来是考虑维护g[i][j]，考虑合并两个节点时，最大贡献有什么情况呢？

1.可能原本就是左节点的答案

2.可能是原本左节点的和+右节点的靠左端的最大值和

那么我们把g[i][j]的最大值维护就想明白了。

我们需要同时维护左端最大和，该节点的总和，该节点的答案。

代码实现：

using ll = long long;
const int N = 2e5 + 5;
const int B = 31;

int f[N][B];
struct Node {
	ll lmx, tmx;
	ll s;
}g[N][B];

void solve() {
	int n, q;
	int x, y;
	cin >> n >> q;
	cin >> x >> y;

	vector<int> nxt(n + 1), a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> nxt[i];
	}

	auto merge = [&](Node &lhs, Node &rhs) {
		Node t;
		t.tmx = lhs.tmx;
		t.lmx = max(lhs.lmx, lhs.s + rhs.lmx);
		t.tmx = max(t.tmx, t.lmx);
		t.s = lhs.s + rhs.s;
		return t;
	};
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		f[i][0] = nxt[i];
		if (a[nxt[i]] > a[i]) {
			Node gt;
			gt.lmx = x;
			gt.tmx = x;
			gt.s = x;
			g[i][0] = gt;
		} else {
			Node gt;
			gt.lmx = y;
			gt.tmx = y;
			gt.s = y;
			g[i][0] = gt;
		}
	}
	for (int i = 1; i <= 30; i++) {
		for (int j = 1; j <= n; j++) {
			g[j][i] = merge(g[j][i - 1], g[f[j][i - 1]][i - 1]);
			f[j][i] = f[f[j][i - 1]][i - 1];
		}
	}

	auto query = [&](int u, int k) {
		Node t = {0, 0, 0};
		ll ret = 0;

		for (int i = 30; i >= 0; i--) {
			if (k >> i & 1) {
				t = merge(t, g[u][i]);
				u = f[u][i];
			}
			ret = max(ret, t.tmx);
		}
		return ret;
	};
	while (q--) {
		int u, k;
		cin >> u >> k;
		cout << query(u, k) << '\n';
	}
}