• 欢迎光临~

# CF1033E 做题体验

### 题目链接

``````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);
ma[chose] = ret; return ret;
}
``````

• 我们把 (B) 按照大小平均分成两个集合 (B_1)(B_2)
• 分别查询 (check(B_1,A))(check(B_2,A)) ，如果一个为真则取为真的，否则任意取一个。
• 不难发现，最后集合 (B) 只会剩下一个节点，那个节点就是 (p) 。复杂度 (O(log n))

``````#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 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);
}

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);
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]);
for (int t : rt) now.emplace_back(t);
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]);
now.emplace_back(p);
if (edge1 < edge2) return true;
return false;
}

inline void DFS(int, int);
inline int LCA(int, int);

signed main(void) {
if (n == 1) {
printf("Y 1 n1");
return 0;
}
now.emplace_back(1);
rt = now;
for (int edgenum = 1, rootteam; edgenum < n; edgenum++) {
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;
// 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]);
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 (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) {
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) {