贪心（不同情况下有不同策略）题单报告

书接上回。

感觉这个标题起得云里雾里的颇有上次讲的“反悔自动机”的奇妙风范，坏了会回旋镖插我自己身上了（

感觉这样的贪心很厉害。什么叫不同情况下有不同策略呢？就是说你要分讨，分讨的每一种情况我们都要保证这是当前的最优解。这听起来是不是还是很扯，其实这是为了方便我自己看的，所以我瞎扯瞎扯问题不大(/ω＼)

这个就当是我自己瞎扯的吧(/ω＼)

P2587

田忌赛马，典题。

无论这道题多么经典和简单，如果完全没有接触，我们很难找到解法。所以让我们来发散的思考思考

我们战术分析一下老祖宗流传给我们的田忌赛马策略，假设 A 代表田忌，B 代表齐王

A 0.5 1.5 2.5
B 1 2 3

如果硬碰硬，那么田忌永远打不赢，所以田忌换了一个策略，用 0.5 兑 3，然后用 1.5，2.5 分别赢了 1 和 2。

这告诉我们可以这样来操作，除了一味地要赢以外，还可以用最小的去兑对方最大的。

这样的操作让我们得到一些东西

1. 这道题是贪心没跑了。
2. 我们可以先排个序。
3. 我们有这样的贪心策略

• 要赢最多场次。
• 在当前赢了最多场次的前提下，我们要尽量用最小的代价赢。用上面的例子来说，很显然用 2.5 赢对方的 1 实在是太浪费了。

我们可以维护 \(min1, max1\) 代表当前田忌的最小值最大值的下标（是下标），\(min2, max2\) 代表齐王的最小值最大值下标。

很显然，我们会选择用最小对最小（最大对最大也可以）

如果用最小对最小，那么会有三种情况

1. \(a(min1) > b(min2)\) 要赢就赢，这时候肯定是最小的代价来赢的。
2. \(a(min1) < b(min2)\) 这个时候 \(min1\) 肯定谁都打不过，那么我们怎么办？我们直接让它兑 \(b(max2)\) 吗？不，万一 \(a(max1) > a(max2)\) 呢？能直接赢下一场胜利岂不更好？
   但这也启发我们，来比较 max
   • \(a(max1) > b(max2)\)，那么就赢了它。
   • \(a(max1) < b(max2)\) 那么此时没有选择应为 \(min1\) 谁也打不过，所以我们就用它兑掉 \(max2\)。
   • \(a(max1) = b(max2)\) 这是一个值得玩味的情况，它看上去就没那么显然了。比如说田忌的最小兑齐王的最小，然后我用最大的和齐王的打平？但是这肯定不如我用最小兑最大来的优。还是那个道理，\(min1\) 谁也打不过，所以兑最大比兑最小来的划算，而且此时 \(b(max2)\) 就会更新成 \(b(max2')\) 并且 \(b(max2') \le b(max2)\)。\(max1\) 可能能赢也可能打平，反正不会输，最坏情况下是 \(-1\)，但是更好一点的情况是 \(0\)。所以我们选择兑一局
3. \(a(min1) = b(min2)\)，打平。学习上面的思路，我们比较 max
   • \(a(max1) > b(max2)\)，赢了它。
   • \(a(max1) < b(max2)\)，\(min1\) 谁也打不过。是平局一下还是兑 \(b(max2)\) 呢？
     平局的话，那么 max1 要输，所以是价值是 \(-1\)。
     兑的话，\(min1\) 要输一局，然后 \(max1\) 肯定会赢或平（起码不会输），最坏的话价值是 \(-1\)，最好的话输一局赢一局就刚好是 \(0\) 了，就更优了。
     所以我选择兑一局。
   • \(a(max1) = b(max2)\) 全平。和上面一样，考虑平局一下和兑一下。
     平局的话，那么就价值是 \(0\)。
     兑一下的话，\(min1\) 可能输也可能平，\(max1\) 可能赢也可能平，最坏的话价值是 \(0\)。
     值得一提的是这种情况最好价值也是 \(0\)。因为如果 \(min1\) 平 \(max2\) 说明 \(a\) 和 \(b\) 里面所有元素都相等。这个时候 \(max1\) 是平的，所以最好价值还是 \(0\)。
     其实这两种情况等价，不过为了方便我们还是可以选择兑一局（因为兑一局的情况更多一些）

这是代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
void init() {
	int n; cin >> n;
	for(int p = 1; p <= n; p++)
		cin >> a[p];
	for(int p = 1; p <= n; p++)
		cin >> b[p];
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	int min1 = 1, min2 = 1, max1 = n, max2 = n, cnt = 0;

	for(int p = 1; p <= n; p++) {
		if(a[min1] > b[min2]) min1++, min2++, cnt += 2;
		else if(a[min1] == b[min2]) {
			if(a[max1] > b[max2]) max1--, max2--, cnt += 2;
			else if(a[max1] < b[max2]) min1++, max2--;
			else {//a[max1] == b[max2]
				if(a[min1] == b[max2]) cnt++;
				min1++, max2--;
			}
		}
		else min1++, max2--;
	}
	cout << cnt << ' ';

	min1 = 1, min2 = 1, max1 = max2 = n, cnt = 0;
	for(int p = 1; p <= n; p++) swap(a[p], b[p]);

	for(int p = 1; p <= n; p++) {
		if(a[min1] > b[min2]) min1++, min2++, cnt += 2;
		else if(a[min1] == b[min2]) {
			if(a[max1] > b[max2]) max1--, max2--, cnt += 2;
			else if(a[max1] < b[max2]) min1++, max2--;
			else {//a[max1] == b[max2]
				if(a[min1] == b[max2]) cnt++;
				min1++, max2--;
			}
		}
		else min1++, max2--;
	}
	cout << 2 * n - cnt << endl;
}
int main() {

    // freopen("read.in", "r", stdin);
    // freopen("write.out", "w", stdout);
	init();
}

P4785

超级好的一道题，吹爆！

这个报告希望可以更加详细明确的探讨一下这道题的思维过程，欢迎各位来探讨交流 qwq

首先我们战术观察一下这道题目。Democy 子曰，字典序最小就是贪心，所以我们这道题的大框架就是贪心。我们看到这个交换很有意思，\(a_n\) 和 \(a_{\lfloor\frac{n}{2}\rfloor}\) 换。。如果你二叉树学的很扎实或者做过相似的题目（举个例子这题）那么我们就会想到把它放到一个完全二叉树上去。那么每次交换操作就是交换一个儿子和父亲了。

现在我们已经确定了大框架：在完全二叉树上跑贪心。

然后我们继续深入思考。

这道题让我们字典序最小，其实是什么？是我从上到下从左到右把每个点的值串下来的最小字典序。

每次交换儿子和父亲，而且是从 \(i = 2\sim n\) 这样依次交换，放到完全二叉树上，就是从上到下，从左到右的交换。

拿样例举例子，像这样：

这道题的操作是交换，从上到下从左到右交换自己的父亲，这有什么性质？我们可以把一个点通过它的儿子们不断的交换交换交换到下面去，但是不可能把它通过儿子交换上来，这就颇有几分“不同层之间互不干扰”的意味（当然还是有一定干扰的）。在不同子树之间又是基本上互不影响的，我们可以根据不同的子树划分子问题。这就启发我们每次考虑一个父亲和它的两个儿子，然后递归下去。像这样

由于我们不可能把 A 点换上去，所以一个子树是基本独立的。然后呢？我们肯定会考虑 B，C 怎么换。这一共有四种换发

1. 不换
2. B 换 C 不换
3. B 不换 C 换
4. B，C 都换。

通过手玩不难找到这四种情况对应的序列

1. A-B-C
2. B-A-C
3. C-B-A
4. C-A-B

为了字典序最小，首先根肯定要最小，这很容易理解。也就是说，如果 \(a(A)\) 或 \(a(B)\) 是 \(a(A), a(B), a(C)\) 三者中的最小者，那么我们可以直接确定。但是 \(C\) 呢？A，B 可以在子树中继续交换，这就不简单了。因为我们并不知道 A 和 B 放在哪。我们来幻想一下 A 在左子树 B 在右子树和 A 在右 B 在左的情况。画一下图

我们会发现这样一点，我们只需要知道 A，B 在左右子树中最优能在哪个位置就好了。这个位置是在整个二叉树中的编号。我们肯定希望这里面小的的编号小。不妨设 \(a(A) < a(B)\)。令 \(a(A)\) 在左子树的最优位置是 \(pos1\)，在右边的是 \(pos2\)。如果 \(pos1 < pos2\) 就让 A 去左边，反之去右边。\(a(A) > a(B)\) 同理。

那么我们怎么求这个 \(pos1\) 和 \(pos2\) 呢？这个子问题让我们很想 dp 一下（雾，我们可以定义 \(f(u, val)\) 代表以编号 \(u\) 为根的子树根节点的值变成了 \(val\) 后，\(val\) 所处的最优位置。这个问题可以通过上面的策略解决。这样一个 \(val\) 只可能出现在 \(u\) 的祖先上，所以一共只有 \(O(n\log_2 n)\) 种状态，记忆化一下时间复杂度 \(O(n\log2_n)\)。这样说很笼统，但是重新叙述一遍又太累赘，所以具体看代码吧 awa

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5;
int a[MAXN + 10], n;
unordered_map <int, unordered_map <int, int> > f;
int getpos(int now, int val) {
	if(!a[2 * now]) return now;
	if(!a[2 * now + 1]) {
		if(a[2 * now] < val) return 2 * now;
		else return now;
	}
	if(f[now][val]) return f[now][val];

	int A = val, B = a[2 * now], C = a[2 * now + 1];
	if(A < B && A < C) return f[now][val] = now;
	else if(B < A && B < C) return f[now][val] = getpos(2 * now, val);
	else {
		if(A < B) return f[now][val] = min(getpos(2 * now, val), getpos(2 * now + 1, val));
		else {
			if(getpos(2 * now, B) > getpos(2 * now + 1, B))
				return f[now][val] = getpos(2 * now, val);
			else return f[now][val] = getpos(2 * now + 1, val);
		}
	}
	return f[now][val];
}
void dfs(int now) {
	if(!a[2 * now]) return ;
	if(!a[2 * now + 1]) {
		if(a[now] > a[2 * now]) swap(a[now], a[2 * now]);
		return ;
	}
	int &A = a[now], &B = a[2 * now], &C = a[2 * now + 1];
	if(A < B && A < C) dfs(2 * now), dfs(2 * now + 1);
	else if(B < A && B < C) {
		swap(A, B);
		dfs(2 * now), dfs(2 * now + 1);
	}
	else {
		int aa = A, bb = B, cc = C;
		if(getpos(2 * now, min(A, B)) < getpos(2 * now + 1, min(A, B))) B = min(aa, bb), C = max(aa, bb);
		else B = max(aa, bb), C = min(aa, bb);
		a[now] = cc;
		dfs(2 * now), dfs(2 * now + 1);
	}
	return ;
}
void init() {
    scanf("%d", &n);
	for(int p = 1; p <= n; p++)
		scanf("%d", &a[p]);

	dfs(1);
	for(int p = 1; p <= n; p++)
        printf("%d ", a[p]);
}
int main() {
	init();
}

P6927

明天填坑 awa（）