题目大意
题目名称：E2. Interactive Graph (Hard Version)（交互式图困难版）
题目描述
这是一个交互题。
后台有一个包含 n 个顶点和 m 条边的有向无环图（DAG），图中没有自环和重边。
你的任务是在最多进行 n+m 次询问的情况下，确定图中所有的边。
你可以进行如下格式的询问：
? k
系统会返回该图中按字典序排列的所有路径列表中的第 k 条路径。
-
路径定义：一个顶点序列 u1,u2,…,ul，满足图中存在边 (ui,ui+1)。
-
字典序定义：序列 a 小于序列 b 当且仅当 a 是 b 的真前缀，或者在两者第一个不同的位置上，a 的元素小于 b 的元素。
-
返回格式：系统首先返回路径长度 q。如果 q=0，表示不存在第 k 条路径；否则，随后返回 q 个整数表示该路径的顶点序列。
-
数据范围：1≤n≤30，1≤k≤230。
输出格式
当你确定了所有边后，输出 ! m，随后输出 m 行，每行两个整数 u,v，代表存在一条从 u 到 v 的有向边。
样例
Input
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
| 3
5
1 1
2 1 2
3 1 2 4
3 1 2 5
2 1 3
3 1 3 4
3 1 3 5
1 2
1 3
1 4
1 5
1
0
2
1 1
1 2
2 2 1
|
Output
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
|
? 1
? 2
? 3
? 4
? 5
? 6
? 7
? 8
? 11
? 14
? 15
! 6
1 3
1 2
2 4
3 4
2 5
3 5
? 2
! 0
? 1
? 2
? 3
! 1
2 1
|
样例解释
以第一个测试用例为例：
-
n=5。
-
程序依次询问了第 1, 2, …, 15 条路径。
-
例如，? 3 返回了 3 1 2 4，表示字典序第 3 小的路径是 1→2→4。
-
通过这些路径信息，程序最终判断出图中有 6 条边，并输出了它们（如 1→3, 1→2 等）。
思路讲解
那么我们把我们可以记忆化的东西已经全部在图上标出来了。我们为什么要记忆化呢？其实我们的目标就在于，我们每次询问啊，我们都尽量想比较好的去找到它的出边，是吧？
如果有大量的这个路径，它实际上是没有什么信息的增量的。它大量的这个路径啊，就是它没有什么信息的增量。
比如说我们来看12这个路径，它就告诉了我们从12有一条出边。然后我们现在想要看1还有哪些出边，那么这个时候124、125实际上没有给我们带来信息的增量，但是13啊又给我们带来了信息的增量，但是134，135。但实际上又没有了信息的增量。所以我们就要想办法去跳过没有信息增量的东西。比如说12，它没有信息的增量。就是1~2以后，然后我们查找到 cnt 2实际上有3个，然后我们直接便利到12的时候，我们就直接跳到13，是不是就会好很多？
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
| auto solve=[&](auto && self,ll u,ll cur_k) -> void {
if (cnt_ls[u]) {
return;
}
vis[u]=1;
cnt_ls[u]=1;
while (true) {
vector<ll> res=query(cur_k+cnt_ls[u]);
auto it=find(all(res),u);
if (it==res.end() || it==prev(res.end())) {
return;
}
ll to=*next(it);
self(self,to,cur_k+cnt_ls[u]);
edges.push_back({u,to});
cnt_ls[u]+=cnt_ls[to];
}
};
ll cur_k=0;
for (ll u=1;u<=N;++u){
if (!vis[u]) {
solve(solve,u,cur_k+1);
}
cur_k+=cnt_ls[u];
}
|
AC代码
AC
https://codeforces.com/contest/2197/submission/362863587
源代码
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
struct Edge {
ll u,v;
bool operator<(const Edge &o )const {
if (u!=o.u) return u<o.u;
return v<o.v;
}
bool operator==(const Edge & o) const {
return u==o.u && v==o.v;
}
};
void out_ans(const vector<Edge> &vec) {
cout<<"! "<<SZ(vec)<<endl;
for (auto &[u,v]:vec) {
cout<<u<<" "<<v<<endl;
}
}
void Solve() {
ll N;
cin >> N;
vector<ll> cnt_ls(N+2);
vector<char> vis(N+2);
vector<Edge> edges;
map<ll,vector<ll>> memo;
auto query=[&](ll k) -> vector<ll> {
auto it=memo.find(k);
if (it!=memo.end()) {
return it->second;
}
cout<<"? "<<k<<endl;
ll n;
cin>>n;
if (n==-1) {
exit(0);
}
vector<ll> res(n);
for (auto &v:res) {
cin>>v;
}
memo[k]=res;
return res;
};
auto solve=[&](auto && self,ll u,ll cur_k) -> void {
if (cnt_ls[u]) {
return;
}
vis[u]=1;
cnt_ls[u]=1;
while (true) {
vector<ll> res=query(cur_k+cnt_ls[u]);
auto it=find(all(res),u);
if (it==res.end() || it==prev(res.end())) {
return;
}
ll to=*next(it);
self(self,to,cur_k+cnt_ls[u]);
edges.push_back({u,to});
cnt_ls[u]+=cnt_ls[to];
}
};
ll cur_k=0;
for (ll u=1;u<=N;++u){
if (!vis[u]) {
solve(solve,u,cur_k+1);
}
cur_k+=cnt_ls[u];
}
sort(all(edges));
edges.resize(unique(all(edges))-edges.begin());
out_ans(edges);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）
错误的采用了比较复杂的编程方法。
采用了比较复杂的递归式的 sub 函数，这其实是会出问题的。就是我们以后写这个 solve 递归式 solve 函数，就是就是去找这个 q 点的这个逻辑，不应该放在子数当中，不应该放在子程序当中。那你应该你自己去找这个东西。
说白了就是寻找停止点的逻辑不应该放在你的子函数当中。
书写相关递归函数时，也可以尽量不要使用较为复杂的返回类型。可以直接就是将返回值存在一数组之中，我们整体的这个返回类型就是 void 就可以了。
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
| auto solve=[&](auto && self,ll u,ll cur_k) -> pair<ll,ll> {
vis.erase(u);
vector<ll> res=query(cur_k+1);
mx_cur_k=max(mx_cur_k,cur_k+1);
auto it=find(all(res),u);
if (it==res.end() || it==prev(res.end())) {
if (res.empty()) {
return {0,0};
}else {
return {0,res.back()};
}
}
ll to=*next(it);
cnt_ls[u]=1;
edges.push_back({u,to});
while (true) {
ll cnt_to;
tie(cnt_to,to)=self(self,to,cur_k+cnt_ls[u]);
if (cnt_to==0) {
return {cnt_ls[u],to};
}
cnt_ls[u]+=cnt_to;
edges.push_back({u,to});
}
};
|
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
struct Edge {
ll u,v;
bool operator<(const Edge &o )const {
if (u!=o.u) return u<o.u;
return v<o.v;
}
bool operator==(const Edge & o) const {
return u==o.u && v==o.v;
}
};
void out_ans(const vector<Edge> &vec) {
cout<<"! "<<SZ(vec)<<endl;
for (auto &[u,v]:vec) {
cout<<u<<" "<<v<<endl;
}
}
void Solve() {
ll N;
cin >> N;
vector<ll> cnt_ls(N+2);
set<ll> vis;
for (int i=1;i<=N;++i) {
vis.insert(i);
}
vector<Edge> edges;
map<ll,vector<ll>> memo;
auto query=[&](ll k) -> vector<ll> {
auto it=memo.find(k);
if (it!=memo.end()) {
return it->second;
}
cout<<"? "<<k<<endl;
ll n;
cin>>n;
if (n==-1) {
exit(0);
}
vector<ll> res(n);
for (auto &v:res) {
cin>>v;
}
memo[k]=res;
return res;
};
ll mx_cur_k=1;
auto solve=[&](auto && self,ll u,ll cur_k) -> pair<ll,ll> {
vis.erase(u);
vector<ll> res=query(cur_k+1);
mx_cur_k=max(mx_cur_k,cur_k+1);
auto it=find(all(res),u);
if (it==res.end() || it==prev(res.end())) {
if (res.empty()) {
return {0,0};
}else {
return {0,res.back()};
}
}
ll to=*next(it);
cnt_ls[u]=1;
edges.push_back({u,to});
while (true) {
ll cnt_to;
tie(cnt_to,to)=self(self,to,cur_k+cnt_ls[u]);
if (cnt_to==0) {
return {cnt_ls[u],to};
}
cnt_ls[u]+=cnt_to;
edges.push_back({u,to});
}
};
while (!vis.empty()) {
solve(solve,*vis.begin(),mx_cur_k);
}
sort(all(edges));
edges.resize(unique(all(edges))-edges.begin());
out_ans(edges);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
|