交互入門題瞎做
luogu P7045 「MCOI-03」金牌
看到題解中介紹了一種用於找出序列中出現次數大於 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 的摩爾投票法。
先來賀一波題解給出摩爾投票法的具體操作：
- 我們首先初始化變數 \(\text{ans=}a_1\) , \(\text{cnt=}1\) 。
- 從此序列的第二個數開始掃描，直到第 \(n\) 個數 \(a_n\) ，我們假設現在掃描到了 \(a_i\) 。
- 如果此時 \(\text{ans=}a_i\) 那麼 \(\text{cnt}\leftarrow \text{cnt}+ 1\) 否則 \(\text{cnt}\leftarrow \text{cnt}- 1\) 。
- 如果此時 \(\text{cnt=}0\) ，那麼我們更新 \(\text{ans=}a_i\) 。
- 當我們全部掃完之後，\(\text{ans}\) 就是出現次數大於 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 的數 。
我們現在著手來考慮這個東西和題目有什麼聯繫。
經過簡單的思考，我們可以發現當存在一個數出現次數大於 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 時，那麼它就是無解的。
這個非常好理解，因為從鴿巢原理可以知道，此時一定會有兩個相同的數它們是相鄰的。
如果我們要求出每兩個獎牌的磁性的關係是不可能的，所以我們可以參照摩爾投票法。
- 我們維護一個隊列 \(\text{que}\) ，滿足：隊列中所有的元素的磁性都是一樣的（對標 \(\text{ans}\)）。
- 同時最開始的時候把 \(0\) 號獎牌放在答案序列（對標初始化）。
- 然後大致的含義和上述相同：相同磁場壓入隊列，不同磁場壓入答案數組。
- 一直這樣模擬最後不難發現會得到一個答案序列和一個隊列 \(\text{que}\) 。
現在就是要解決那些多出來的出現次數最多的獎牌。
一種可以很好的放置多餘的獎牌的方案就是在答案序列中插縫擺放，具體可以看程式碼。
點擊查看程式碼
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('\n')
#define quad putchar(' ')
const int N = 5e5 + 5;
int T, n, q, flag, ans[N], tot;
std::queue <int> que;
inline int ask(int id1, int id2) {
printf("%d %d\n", id1, id2);
fflush(stdout);
int ret = 0; scanf("%d", &ret);
return ret;
}
signed main(void) {
std::cin >> T;
for (int test = 1; test <= T; test ++) {
scanf("%d %d", &n, &q);
flag = -1; tot = 0; ans[++tot] = 0;
while (!que.empty()) que.pop();
for (int i = 1; i < n; i++) {
if (que.empty()) {
int tmp = ask(i, ans[tot]);
if (tmp == 1) ans[++tot] = i;
else que.emplace(i);
} else {
int tmp = ask(i, que.front());
if (tmp == 1) {
ans[++tot] = i, ans[++tot] = que.front();
que.pop();
} else que.emplace(i);
}
}
for (int i = 2 * tot; i >= 1; i -= 2)
ans[i] = ans[i / 2], ans[i - 1] = -1;
if (que.size()) {
bool last = 1;
for (int i = 2; i <= 2 * tot; i += 2) {
int tmp = ask(que.front(), ans[i]);
if (tmp && last) ans[i - 1] = que.front(), que.pop();
if (!que.size()) break;
last = tmp;
}
}
if (!que.empty()) {
printf("-1\n");
fflush(stdout);
} else {
printf("%d\n", n);
for (int i = 1; i <= 2 * tot; i++)
if (ans[i] != -1) printf("%d ", ans[i]);
printf("\n");
fflush(stdout);
}
}
return 0;
}
CF1033E Hidden Bipartite Graph
這題看上去一臉不可做，對，我看什麼題都不可做。。。
然後瞄一眼題解，發現一個小 \(\tt Trick\) ：
判定二分圖可以先拉出一個生成樹，対生成樹進行染色然後看相同顏色內有沒有連邊。
所以現在的第一步是拉出一個生成樹。
首先，我們先把題目中要求的交互函數寫出來，我用一個 \(\tt vector\) 記錄查詢的點集。
同時在我自己測試時發現可能會詢問重複的點集，所以用一個 \(\tt map\) 來記錄已經查過的答案。
inline int ask(std::vector<int> chose) {
if (chose.size() == 1) return 0;
std::sort(chose.begin(), chose.end());
if (ma[chose]) return ma[chose];
printf("? ");
write(chose.size()), Enter;
for (int t : chose) write(t), quad; Enter;
fflush(stdout);
int ret; read(ret);
ma[chose] = ret; return ret;
}
接下來就按照生成樹的角度進行思考。
首先我們需要並查集，這個非常簡單不在累述，然後我們會發現要進行 \(n-1\) 次連邊操作。
對於每個連邊操作，我們都要找到一個和根節點所在集合有邊的點 \(p\) 然後連邊。
那麼怎麼找到這樣的點 \(p\) 呢？這裡有一個顯然的結論：
對於點集 \(A\) 和 \(B\) ，如果 \(A\) 和 \(B\) 中的點有邊相連，那麼滿足 \(ask(A)+ask(B)<ask(A\cup B)\)
運用這個結論，我們就可以找到上文所講的 \(p\) 。
我們令根節點所在的點集為 \(A\) ，其他的點構成的點集為 \(B\) 。
同時我們令上文結論中的查詢方式為 \(check(A,B)\) ，及調用 \(check(A,B)\) 就可以知道是否有邊。
因為詢問次數控制較為嚴格，我們考慮 \(O(n\log n)\) 的較大常數做法。
直接能夠想到的是二分做法：（假設 \(B\) 集合的大小為 \(L\)）
- 我們把 \(B\) 按照大小平均分成兩個集合 \(B_1\) 和 \(B_2\) 。
- 分別查詢 \(check(B_1,A)\) 和 \(check(B_2,A)\) ，如果一個為真則取為真的，否則任意取一個。
- 不難發現，最後集合 \(B\) 只會剩下一個節點，那個節點就是 \(p\) 。複雜度 \(O(\log n)\) 。
找到了 \(p\) ，我們還要知道 \(p\) 和根節點集合中的哪一個點有邊，按照相似的方法即可。
只不過此次查詢的 \(check\) 操作更為簡潔，複雜度還是 \(O(\log n)\) 。
重複 \(n-1\) 次上述的操作，我們就找到了一個生成樹，接下來對樹染色非常簡單。
我們令染為白色和黑色的點集分別為 \(white\) 和 \(black\) ，進行一次 \(check(white,black)\) 即可判斷二分圖。
如果是二分圖，那麼接下來非常簡單，現在來討論非二分圖的情況。
我的做法是隨機化，每一次對集合進行一次 \(\tt random_shuffle\) ，然後取 \(\frac{L}{2}\) 。
進行查詢，如果可以的話讓點集大小直接減半，不知道對不對，反正我過了
所以這樣下來，複雜度約為 \(O(n\log n)\) 帶上 \(3\sim 5\) 倍常數，可以通過。
具體可以看程式碼：
點擊查看程式碼
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define quad putchar(' ')
#define Enter putchar('\n')
using std::abs;
using std::pair;
using std::string;
using std::make_pair;
// #define int long long
template <class T> void read(T &a);
template <class T> void write(T x);
template <class T, class ...rest> void read(T &a, rest &...x);
template <class T, class ...rest> void write(T x, rest ...a);
const int N = 1005;
int n, root_edge, tot, ok[N], edgetot, col[N];
int deep[N], fa[N][15], sta[N], top;
std::vector <int> now, rt, white, black;
std::vector <int> dis[N];
std::map <std::vector<int>, int> ma;
struct Edge {
int x, y;
Edge (int _x = 0, int _y = 0) {x = _x; y = _y;}
} edge[N * N];
namespace UFST {
int fa[N], siz[N];
inline int find(int);
inline void rebuild(int);
inline void merge(int, int);
}
inline int ask(std::vector<int> chose) {
if (chose.size() == 1) return 0;
std::sort(chose.begin(), chose.end());
if (ma[chose]) return ma[chose];
printf("? ");
write(chose.size()), Enter;
for (int t : chose) write(t), quad; Enter;
fflush(stdout);
int ret; read(ret);
ma[chose] = ret; return ret;
}
inline bool check(int l, int r) {
now.clear();
for (int i = l; i <= r; i++) now.emplace_back(ok[i]);
int edge1 = ask(now);
for (int t : rt) now.emplace_back(t);
int edge2 = ask(now);
if (edge1 + root_edge < edge2) return true;
return false;
}
inline bool check2(int l, int r, int p) {
now.clear();
for (int i = l; i <= r; i++) now.emplace_back(ok[i]);
int edge1 = ask(now);
now.emplace_back(p);
int edge2 = ask(now);
if (edge1 < edge2) return true;
return false;
}
inline void DFS(int, int);
inline int LCA(int, int);
signed main(void) {
read(n); UFST::rebuild(n);
if (n == 1) {
printf("Y 1 \n1");
return 0;
}
now.emplace_back(1);
root_edge = ask(now);
rt = now;
for (int edgenum = 1, rootteam; edgenum < n; edgenum++) {
root_edge = ask(rt);
tot = 0, rootteam = UFST::find(1);
for (int i = 1; i <= n; i++)
if (UFST::find(i) != rootteam) ok[++tot] = i;
int left = 1, right = tot, mid;
while (left < right) {
mid = (left + right) / 2;
if (check(left, mid)) right = mid;
else left = mid + 1;
}
int point = ok[left];
tot = 0;
for (int t : rt) ok[++tot] = t;
left = 1; right = tot;
while (left < right) {
mid = (left + right) / 2;
if (check2(left, mid, point)) right = mid;
else left = mid + 1;
}
UFST::merge(ok[left], point);
edge[++edgetot] = Edge(ok[left], point);
rt.emplace_back(point);
}
for (int i = 1; i <= edgetot; i++) {
Edge p = edge[i];
dis[p.x].emplace_back(p.y);
dis[p.y].emplace_back(p.x);
}
DFS(1, 0);
for (int i = 1; i <= n; i++) {
if (col[i] == 0) white.emplace_back(i);
else black.emplace_back(i);
}
// for (int num : white) write(num), quad; Enter;
// for (int num : black) write(num), quad; Enter;
int edge1 = ask(white), edge2 = ask(black);
// printf("!!!");write(white.size(), edge1);
int p1, p2;
if (edge1 == 0 && edge2 == 0) {
printf("Y "); write(white.size()), Enter;
for (int num : white) write(num), quad; Enter;
return 0;
} else if (edge1 != 0) {
tot = 0;
for (int num : white) ok[++tot] = num;
while (1) {
now.clear();
std::random_shuffle(ok + 1, ok + 1 + tot);
for (int i = 1; i * 2 - 1 <= std::max(tot, 3); i++) now.emplace_back(ok[i]);
// for (int t : now) write(t), quad; Enter; write(ask(now)); Enter;
if (ask(now)) {
if (now.size() == 2) {p1 = ok[1]; p2 = ok[2]; break;}
tot = (tot + 1) / 2;
}
}
} else if (edge2 != 0) {
tot = 0;
for (int num : black) ok[++tot] = num;
while (1) {
now.clear();
std::random_shuffle(ok + 1, ok + 1 + tot);
for (int i = 1; i * 2 - 1 <= tot; i++) now.emplace_back(ok[i]);
if (ask(now)) {
if (now.size() == 2) {p1 = ok[1]; p2 = ok[2]; break;}
tot = (tot + 1) / 2;
}
}
}
printf("N ");
int lca = LCA(p1, p2);
write(deep[p1] + deep[p2] - 2 * deep[lca] + 1); Enter;
while (1) {
write(p1), quad;
p1 = fa[p1][0];
if (p1 == lca) break;
}
while (1) {
sta[++top] = p2;
if (p2 == lca) break;
p2 = fa[p2][0];
}
while (top) write(sta[top]), quad, top --; Enter;
return 0;
}
inline void DFS(int now, int father) {
deep[now] = deep[father] + 1;
col[now] = 1 - col[father];
for (int i = 0; i <= 12; i++) fa[now][i + 1] = fa[fa[now][i]][i];
for (int t : dis[now]) {
if (t == father) continue;
fa[t][0] = now;
DFS(t, now);
}
}
inline int LCA(int x, int y) {
if (deep[x] < deep[y]) std::swap(x, y);
for (int i = 13; i >= 0; i--)
if (deep[fa[x][i]] >= deep[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 13; i >= 0; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
namespace UFST {
inline int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
inline void rebuild(int n) {
for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
}
inline void merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) return ;
if (siz[x] > siz[y]) std::swap(x, y);
fa[x] = y; siz[y] += siz[x];
}
}
template <class T> void read(T &a) {
int s = 0, t = 1;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') c = getchar(), t = -1;
while (isdigit(c)) s = s * 10 + c - '0', c = getchar();
a = s * t;
}
template <class T> void write(T x) {
if (x == 0) putchar('0');
if (x < 0) putchar('-'), x = -x;
int top = 0, sta[50] = {0};
while (x) sta[++top] = x % 10, x /= 10;
while (top) putchar(sta[top] + '0'), top --;
return ;
}
template <class T, class ...rest> void read(T &a, rest &...x) {
read(a); read(x...);
}
template <class T, class ...rest> void write(T x, rest ...a) {
write(x); quad; write(a...);
}
CF1129E Legendary Tree
一道自認為很有意思的交互題。
題目給出的詢問方式看上去非常申必，但是我們可以從樹的性質下手進行分析。
我們假定這個樹的根節點是 \(1\) ，那麼很顯然，我們可以進行 \(n-1\) 次詢問。
對於第 \(i\) 次詢問，我們是這樣的：
\]
這個表示從根節點出發，經過 \(i\) 節點最後能到達樹上的幾個節點。
幾乎不用想的，上述詢問直接給出了第 \(i\) 個節點的子樹大小 \(siz\) 。
現在每一個節點的子樹大小都確定了，問題轉化成為對於節點 \(i\) 確定它的父親節點是什麼。
考慮到隨著節點深度的不斷增加，節點的子樹大小一定不斷減小。
所以我們按照 \(siz\) 從小到大排序，這樣的話對於每一個節點 \(i\) ，它的兒子一定是在它的左邊。
現在問題就是在 \(i\) 左邊所有沒有被選擇的節點中高效率地找到 \(i\) 的兒子們。
在這裡，我們可以用二分的方法來解決這個問題：
我們假定現在已經掃到了第 \(i\) 個節點，我們記 \(i\) 左邊沒有被選的節點集合為 \(S\) 。
首先，二分的左邊界 \(L\) 一定是 \(1\) ，有邊界我們定為 \(|S|\) ，及 \(S\) 集合的大小。
我們記此時二分出的值為 \(mid\) ，那麼我們進行如下的詢問：
\]
其中 \(u\) 表示當前掃到的節點的編號。
當我們發現詢問的值大於 \(0\) 時，我們就縮小範圍，否則就增大範圍。
最後我們要找的是滿足上述詢問大於 \(0\) 的最小的 \(pos\) ，\(pos\) 表示排完序後的節點編號。
容易發現，其實最後一個 \(pos\) 位置上的節點一定是 \(u\) 的孩子，\(u\) 的定義如上。
這樣進行不斷的詢問，可以發現詢問次數是 \(O(n^2\log n)\) 級別的，顯然可以通過。
點擊查看程式碼
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
const int N = 505;
int n, root, siz[N], fa[N], st[N], tot;
struct Node {
int id, siz;
Node (int _id = 0, int _siz = 0) {
id = _id; siz = _siz;
}
friend bool operator<(const Node &p, const Node &q) {
return p.siz < q.siz;
}
} node[N];
inline int ask_size(int point) {
printf("1\n1\n");
printf("%d\n", n - 1);
for (int i = 2; i <= n; i++) printf("%d ", i);
printf("\n%d\n", point);
fflush(stdout);
int ret; scanf("%d", &ret);
return ret;
}
inline int ask(int point, int right) {
printf("1\n1\n");
printf("%d\n", right);
for (int i = 1; i <= right; i++) printf("%d ", st[i]);
printf("\n");
printf("%d\n", point);
fflush(stdout);
int ret; scanf("%d", &ret);
return ret;
}
signed main(void) {
scanf("%d", &n);
root = 1; siz[root] = n;
for (int i = 2; i <= n; i++) siz[i] = ask_size(i);
for (int i = 1; i <= n; i++) node[i] = Node(i, siz[i]);
std::sort(node + 1, node + 1 + n);
for (int i = 1; i <= n; i++) {
while (1) {
tot = 0;
for (int j = 1; j < i; j++)
if (fa[node[j].id] == 0) st[++tot] = node[j].id;
int left = 1, right = tot, ans = n + 1;
while (left <= right) {
int mid = (left + right) / 2;
if (ask(node[i].id, mid)) {
right = mid - 1;
ans = std::min(ans, mid);
} else left = mid + 1;
}
if (ans == n + 1) break;
fa[st[ans]] = node[i].id;
}
}
printf("ANSWER\n");
for (int i = 2; i <= n; i++)
printf("%d %d\n", fa[i], i);
return 0;
}
CF1705F Mark and the Online Exam
看上去像是經典交互問題，但是好像不太會……
這道題的一種非常直接的想法也是第一步就是先全部試一下 \(\text{T}\) 然後你就能得到一共有多少個答案為 \(\text{T}\) 。
然後最暴力的方法就是每一次把其中一個選項變成 \(\text{F}\) 然後查詢結果。
正確性是沒得講，但是這樣操作的詢問次數是 \(O(n)\) 的級別，會 \(\text{Wrong Answer on test 9}\) 。
下面是一種看到的非常巧妙的構造詢問的方法：
看到 \(n\) 和詢問次數的數量級關係，容易判斷出詢問的次數要是 \(\frac{n}{3}\) 級別才不會有問題。
我們考慮把這 \(n\) 個選擇題平均地分成三個部分，同時為了方便，我們定義 \(m=\left\lfloor\dfrac{n}{3}\right\rfloor\) 。
令序列 \(S\) 為詢問時我們的答案，\(\text{ret=ask(S)}\) 表示一次詢問操作。
- 最簡單的一步令 \(S=\{T,T,\cdots, T\}\) ，\(\text{num=ask(S)}\) 表示答案中有多少個 \(\text{T}\) 。
- 對於每一個 \(i\ (i\leq m)\) ，我們把 \(i\) 和 \(i+m\) 這兩位變成 \(\text{F}\) 其他的位仍然是 \(\text{T}\) ，進行詢問 \(\text{ret=ask(S)}\) ，然後對 \(\text{ret}\) 進行分討。
- \(ret=num+2\) 說明這兩個猜對了，所以 \(i\) 和 \(i + m\) 這兩位都是 \(\text{F}\) 。
- \(ret=num-2\) 說明兩個都猜錯了，所以 \(i\) 和 \(i + m\) 這兩位都是 \(\text{T}\) 。
- \(ret=num\) 說明一個猜對一個猜錯了，我們先放一邊，不進行考慮。
- 令 \(S’=m\times \text{F} + (n-m)\times \text{T}\) ，進行詢問 \(\text{q3=ask(S’)}\) 。
- 對於每一個 \(i\ (i\leq m \text{且第} \ i\ \text{位還沒有被確定})\)，我們把 \(S’\) 的第 \(i\) 變成 \(\text{T}\)，第 \(i+m\) 和 \(i+2m\) 位變成 \(\text{T}\) ，在對其進行詢問 \(\text{ret=ask(S”)}\)。
- \(ret = q3+3\) 三個都猜對了，答案就是 \(\text{TFF}\) 。
- \(ret = q3-3\) 三個都猜錯了，答案是 \(\text{FTT}\) 。
- \(ret = q3+1\) 對了兩個錯了一個，結合上述的分析以及 情況2 的排查可以得出答案是 \(\text{TFT}\) ，在這裡不再證明。
- \(ret = q3-1\) 對了一個錯了兩個，同理，答案是 \(\text{FTF}\) 。
- 對於所有還沒有確定的，直接按照最暴力的方法去做就可以了。
容易發現詢問次數是 \(O(\left\lfloor\dfrac{n}{3}\right\rfloor)\) 級別的，沒有任何問題。
點擊查看程式碼
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <random>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('\n')
const int N = 1e3 + 5;
int n, ans[N], visit[N], num, out[N], ret, q3;
inline int ask(int *ans) {
for (int i = 1; i <= n; i++) {
if (ans[i] == 1) printf("T");
else printf("F");
} Enter;
fflush(stdout);
int ret; scanf("%d", &ret);
if (ret == n) exit(0);
return ret;
}
signed main(void) {
scanf("%d", &n);
memset(out, -1, sizeof(out));
for (int i = 1; i <= n; i++) ans[i] = 1;
num = ask(ans);
int m = n / 3;
for (int i = 1; i <= m; i++) {
int x = i, y = i + m;
ans[x] = ans[y] = 0;
ret = ask(ans);
if (ret == num + 2) out[x] = out[y] = 0;
else if (ret == num - 2) out[x] = out[y] = 1;
ans[x] = ans[y] = 1;
}
std::fill(ans + 1, ans + 1 + n, 1);
for (int i = 1; i <= m; i++) ans[i] = 0;
q3 = ask(ans);
for (int i = 1; i <= m; i++) {
if (out[i] != -1) continue;
ans[i] = 1, ans[i + m] = 0, ans[i + 2 * m] = 0;
ret = ask(ans);
if (ret == q3 - 3) {
out[i] = 0; out[i + m] = 1, out[i + 2 * m] = 1;
} else if (ret == q3 + 3) {
out[i] = 1; out[i + m] = 0; out[i + 2 * m] = 0;
} else if (ret == q3 + 1) {
out[i] = 1; out[i + m] = 0; out[i + 2 * m] = 1;
} else if (ret == q3 - 1) {
out[i] = 0; out[i + m] = 1; out[i + 2 * m] = 0;
}
ans[i] = 0, ans[i + m] = 1, ans[i + 2 * m] = 1;
}
std::fill(ans + 1, ans + 1 + n, 1);
for (int i = 1; i <= n; i++) {
if (out[i] != -1) continue;
ans[i] = 0;
ret = ask(ans);
if (ret < num) out[i] = 1;
else out[i] = 0;
ans[i] = 1;
}
for (int i = 1; i <= n; i++)
printf(out[i] == 1 ? "T" : "F");
Enter;
return 0;
}
CF1142E Pink Floyd
好申必的題，可能是因為我水平不夠吧……
為了解決這道題，首先我們要解決沒有粉色邊全部是綠色邊的情況。
因為詢問的操作次數上限是 \(2n\) 再加上交互庫有自適應功能，所以找 \(u\) 再驗證顯然是不可能的。
我沒有證明，也就感性理解一下好像沒有什麼大的問題。
然後發現一種神奇的做法：可以逐步去篩選那些可能是 \(u\) 的點，最後剩下的顯然就是答案。
初始化時所有的點都在候選的集合裡面，我們令這個集合為 \(S\) 。
枚舉 \(u,v\in S\) 如果 \(u\rightarrow v\) 我們就把 \(v\) 從 \(S\) 中刪掉，否則把 \(u\) 從 \(S\) 中刪掉。
這個東西是非常顯然的，因為我們假設令 \(P(x)\) 表示 \(x\) 點能到的所有點的集合，這個時候我們可以發現當 \(u\rightarrow v\) 的時候可以直接把 \(v\) 納入到 \(P(u)\) 裡面去，所以在不在 \(S\) 中就不那麼必要了。
容易發現：每一次詢問都會有一個點從 \(S\) 集合中刪去，我們一共進行 \(n-1\) 此操作就可以使集合只剩下一個元素，也就是答案。
現在來考慮完整的題目：由數據的範圍可以看出，只走粉邊到達所有的點是不可能的事情，所以考慮從綠邊下手。
同樣的，我們還是要先確定一個可能的答案集合 \(S\) ，使得 \(S\) 中任意的兩個點沒有粉邊相連，且滿足集合內的點能通過一些構造的手段使得能和非集合中的點連邊。
因為集合中是沒有粉邊的情況的，所以我們又回到了一開始 \(m=0\) 的問題上，可以直接調用構造的方法。
仔細分析上述篩選答案的方法，可以發現 \(S\) 中點的入讀度一定是 \(0\) 所以我們可以維護一個拓撲排序。
每次彈出兩個點，然後然後按照篩選的方法捨棄一個，另一個加入到隊列中，最後剩下的就是 \(u\) 。
講的不太明白，具體可以看一下程式碼。
詢問的複雜度是 \(O(n+m)\) 級別的，沒有壓力。
點擊查看程式碼
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('\n')
#define quad putchar(' ')
const int N = 5e5 + 5;
int n, m, ok[305][305], visit[N], in[N], deg[N];
std::vector <int> dis1[N], dis2[N];
inline int ask(int a, int b) {
printf("? %d %d\n", a, b);
fflush(stdout);
int ret; scanf("%d", &ret);
return ret;
}
inline void DFS(int now) {
visit[now] = in[now] = 1;
for (int t : dis1[now]) {
if (in[t] == 0) {
deg[t] ++;
dis2[now].emplace_back(t);
}
if (visit[t] == 0) DFS(t);
}
in[now] = 0;
}
signed main(void) {
scanf("%d %d", &n, &m);
for (int i = 1, x, y; i <= m; i++) {
scanf("%d %d", &x, &y);
dis1[x].emplace_back(y);
}
for (int i = 1; i <= n; i++) {
if (visit[i]) continue;
DFS(i);
}
std::queue <int> que;
for (int i = 1; i <= n; i++)
if (deg[i] == 0) que.emplace(i);
while (que.size() > 1) {
int u = que.front(); que.pop();
int v = que.front(); que.pop();
if (ask(u, v) == 0) std::swap(u, v);
que.push(u);
for (int t : dis2[v]) {
deg[t] --;
if (deg[t] == 0) que.emplace(t);
}
}
printf("! %d\n", que.front());
return 0;
}
給我點贊瞄，給我點贊謝謝喵。
