非传统题瞎做

老年退役人了

非传统题瞎做

因为已经是退役人了，但还是割舍不掉这玩意，就随便瞎写点东西吧。

[LOJ#2489]. 「2018 集训队互测 Day 4」小修和小栋猜♂数字

非常傻逼的题目，我真是服了，就他妈。

不告诉你要能做出来几个数字，然后用几次操作，我真是日了狗。

吐了，这什么东西。

我发现最大值最小值肯定搞不出来，次大值和次小值虽然知道但是不清楚是哪个位置，剩下的位置随便搞一搞，所以吧，答案大概是可以确定 \(n-4\) 个位置。

我们考虑暴力做 \(4\) 次询问首先搞出来前四个位置的那两个位置较大，那两个位置较小啥的。

然后考虑加入一个位置，令现在的 较大值集合为 \(s_{max}[0,1]\)，而较小值集合为 \(s_{min}[0,1]\) （均为位置），然后较大值为 \(v_2\)，较小值为 \(v_1\)

那么加入一个位置 \(i\)，考虑

ask(i,s_{min}[0],s_{max}[0])

，然后就有，答案为 \(V\)

• \(v_1<V<V_2\) 那么 \(a_{pos}=V\)
• \(v_1=V\) 那么 \(a_{s_{min}[0]}=v_1\)，并将 \(s_{min}[0] = i\)，且次小值更新为

  ask(i,s_min[1],s_max[0])

• \(v_2=V\) 那么 \(a_{s_{max}[0]}=v_2\), 并将 \(s_{max}[0] = i\)，且次大值更新为

  ask(i,s_max[1],s_min[0])

• \(V<v_1\) 那么 \(a_{s_{min}[1]}=v_1\), 并将 \(s_{min}[1] = i\)，且次小值更新为 \(V\)
• \(V>v_2\) 那么 \(a_{s_{max}[1]}=v_2\), 并将 \(s_{max}[1] = i\)，且次大值更新为 \(V\)

#include "guess.h"
void guess(int n) {
	if (n < 5) {
		return;
	}
	int x[5], q10, q20, q11, q21, v2, v1, s1, s3, s2;
	x[1] = ask(2, 3, 4);
	x[2] = ask(1, 3, 4);
	x[3] = ask(1, 2, 4);
	x[4] = ask(1, 2, 3);
	for (int i = 2; i <= 4; ++i) {
		if (x[i] == x[1]) {
			s1 = i;
		}
		else {
			s2 = i;
		}
	}
	for (int i = 2; i <= 4; ++i) {
		if (i != s1 && i != s2) {
			s3 = i;
		}
	}
	if (x[1] < x[s2]) {
		q20 = 1;
		q21 = s1;
		q10 = s2;
		q11 = s3;
		v2 = x[s2];
		v1 = x[1];
	}
	else {
		q10 = 1;
		q11 = s1;
		q20 = s2;
		q21 = s3;
		v2 = x[1];
		v1 = x[s2];
	}
	for (int i = 5; i <= n; ++i) {
		int V = ask(q10, q20, i);
		if (v1 < V && V < v2) {
			answer(i, V);
		}
		else if (V == v1) {
			answer(q10, v1);
			v1 = ask(q11, q10 = i, q20);
		}
		else if (V == v2) {
			answer(q20, v2);
			v2 = ask(q21, q20 = i, q10);
		}
		else if (V < v1) {
			answer(q11, v1);
			q11 = i;
			v1 = V;
		}
		else {
			answer(q21, v2);
			q21 = i;
			v2 = V;
		}
	}
}