LOJ3274

Solution

考虑先把所有大小为22的集合的答案问出来,不难发现答案只可能是1122

我们称答案为11的点对(x,y)(x, y)为一条边,那么每个点的度数只可能是1133

只有与它同色或喜欢/被喜欢的点才会答案为11。若喜欢/被喜欢的点重合,那就只有一条边

若一个点度数为11,则可以直接得到同色的点

若一个点度数为33,设它为xx,三条边分别为(x,y1),(x,y2),(x,y3)(x, y_1), (x, y_2), (x, y_3)。只需询问{x,y1,y2},{x,y1,y3},{x,y2,y3}\{x, y_1, y_2\}, \{x, y_1, y_3\}, \{x, y_2, y_3\}这三个集合,得到答案为11的那个集合所缺的点即为和xx同色的点

这样就得到了询问O(n2)O(n^2)的做法了


考虑优化前半部分的复杂度

不难发现这些边连成的图是二分图,设当前要处理ii点与1i11 \sim i - 1点之间的连边,考虑将1i11 \sim i - 1这些点分成两个独立集,满足集合内部没有边(可以暴力染色处理)

我们可以根据独立集的性质来判断是否有边: 一个集合SS是独立集当且仅当Query(S)=SQuery(S) = |S|。也就是说,点ii和一个独立集SS有边当且仅当Query({S,i})S+1Query(\{S, i\}) \ne |S| + 1

于是可以通过二分来逐条找边了

复杂度O(nlogn)O(n \log n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include "chameleon.h"
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc lf/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1000;

int N, P[MAXN + 5];
int A[MAXN + 5][MAXN + 5];
int stk[MAXN + 5][5];
vector <int> G[MAXN + 5];

int col[MAXN + 5];
vector <int> node[2];

inline void dfs (int x, int c)
{
col[x] = c;
node[c].pb (x);
for (int y : G[x]) if (col[y] == -1) dfs (y, !c);
}

inline void calc (vector <int> vec, int x)
{
while (1)
{
vec.pb (x);
if (Query (vec) == vec.size()) return ;
vec.pop_back();

int l = 0, r = vec.size() - 1, goal = -1;
while (l <= r)
{
int mid = (l + r) >> 1;

static vector <int> tmp; tmp.clear();
for (int i = l; i <= mid; ++i) tmp.pb (vec[i]);
tmp.pb (x);

if (Query (tmp) != tmp.size()) goal = mid, r = mid - 1;
else l = mid + 1;
}
if (goal == -1) return ;

int y = vec[goal];

stk[x][++stk[x][0]] = y, stk[y][++stk[y][0]] = x;
G[x].pb (y), G[y].pb (x);

vec.erase (vec.begin() + goal);
}
}

inline void get_edges (int x)
{
node[0].clear(), node[1].clear();
memset (col, -1, sizeof col);

for (int i = 1; i < x; ++i) if (col[i] == -1) dfs (i, 0);

calc (node[0], x);
calc (node[1], x);
}

void Solve (int n)
{
N = n * 2;

for (int i = 1; i <= N; ++i) stk[i][++stk[i][0]] = i;

for (int i = 1; i <= N; ++i) get_edges (i);

for (int i = 1; i <= N; ++i)
{
int p;
if (stk[i][0] == 2) p = stk[i][2];
else
{
for (int j = 2; j <= 4; ++j)
{
vector <int> vec; vec.clear();
for (int k = 1; k <= 4; ++k) if (j != k) vec.pb (stk[i][k]);
if (Query (vec) == 1)
{
p = stk[i][j];
break;
}
}
}

P[i] = p;
}

static int vis[MAXN + 5];

for (int i = 1; i <= N; ++i)
{
if (stk[i][0] == 2)
{
if (!vis[i] && !vis[P[i]]) Answer (i, P[i]), vis[i] = vis[P[i]] = 1;
}
else
{
for (int j = 2; j <= 4; ++j)
{
int x = stk[i][j];
if (P[x] == i || P[i] == x) continue;
if (!vis[i] && !vis[x]) Answer (i, x), vis[i] = vis[x] = 1;
}
}
}
}