非傳統題瞎做

老年退役人了

非傳統題瞎做

因為已經是退役人了，但還是割舍不掉這玩意，就随便瞎寫點東西吧。

[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;
		}
	}
}