本题为交互题
有一个长度为n的字符串，你每次询问给定一对(l,r)，然后交互库会乱序给出区间[l,r]内所有子串的乱序。你最多可以询问3次，并且需要保证所有询问给出的串个数之和不能超过⌈0.777(n+1)2⌉
你需要根据交互库给出的信息还原出原字符串
n≤100
Link
CF1287E
Solution
因为乱序，所以先把所有得到的字符串，在读进来的时候直接sort一下
先考虑一种比较暴力确定所有位置的方法:
先询问(1,n)，然后询问(1,n−1)，把第一次询问得到的字符串可重集去掉第二次询问得到的字符串可重集，那么剩下的一定就是原串的每一个后缀。根据这些后缀即可还原原串。但此时询问复杂度是O(n2)的
对于正解做法，首先考虑对于给定串长的前一半执行上面的算法，得到这个字符串的前一半。再询问一次整个串，并统计出cnti,x表示所有长度为i的串中x字符出现的次数。
不难发现当i>⌊2n⌋时，cnti,x−cnti+1,x表示的就是[n−i+1,i]中x字符出现的次数。
从小到大依次考虑i∈[2n+1,n]，那么此时[1,i−1]中每一个位置的字符都已经确定了，所以就可以很轻松地确定位置i是什么字符了
总询问复杂度：O(2×2(2n)2+2n2)=O(43n)
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
154
155
156
157
158
| #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 y1 Y1
#define y2 Y2
#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/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}
const int MAXN = 100;
int N, M;
inline void Query (int l, int r) { cout << "? " << l << ' ' << r << endl; cout.flush(); }
map <string, int> Map;
string S, T;
vector <string> vec;
inline int cmp (string a, string b) { return a.size() < b.size(); }
inline void solve_pre ()
{
Query (1, M - 1);
for (int t = 1; t <= M * (M - 1) >> 1; ++t)
{
cin >> T;
sort (T.begin(), T.end());
++Map[T];
}
Query (1, M);
for (int t = 1; t <= M * (M + 1) >> 1; ++t)
{
cin >> T;
sort (T.begin(), T.end());
if (Map[T]) --Map[T];
else vec.pb (T);
}
sort (vec.begin(), vec.end(), cmp);
static string suf;
for (int i = 0; i < vec.size(); ++i)
{
if (!i) suf.pb (vec[0][0]);
else
{
static int bkt[30];
for (int j = 0; j < vec[i].size(); ++j) ++bkt[vec[i][j] - 'a'];
for (int j = 0; j < vec[i - 1].size(); ++j) --bkt[vec[i - 1][j] - 'a'];
for (int j = 0; j < 26; ++j) if (bkt[j])
{
bkt[j] = 0;
suf.pb ('a' + j);
break;
}
}
}
reverse (suf.begin(), suf.end());
S.pb ('0'); S += suf;
}
int cnt[MAXN + 5][MAXN + 5];
inline void solve_suf ()
{
Query (1, N);
for (int i = 1; i <= N * (N + 1) >> 1; ++i)
{
cin >> T;
for (int j = 0; j < T.size(); ++j) ++cnt[T.size()][T[j] - 'a'];
}
for (int i = M + 1; i <= N; ++i)
{
for (int j = N - i + 1; j < i; ++j) --cnt[i][S[j] - 'a'];
for (int j = 0; j < 26; ++j) if (cnt[i][j] - cnt[i + 1][j])
{
S.pb ('a' + j);
break;
}
}
}
inline void Solve ()
{
if (N == 1)
{
Query (1, 1);
cin >> T;
cout << "! " << T << endl;
return ;
}
solve_pre ();
solve_suf ();
cout << "! ";
for (int i = 1; i <= N; ++i) printf("%c", S[i]);
fflush (stdout);
}
inline void Input ()
{
N = read<int>(), M = max (2, N >> 1);
}
int main ()
{
#ifdef hk_cnyali
freopen("E.in", "r", stdin);
freopen("E.out", "w", stdout);
#endif
Input ();
Solve ();
return 0;
}
|