Educational Codeforces Round 130 (Div. 2)
CONTEST传送门
战况
Standing
Rating
补题
D - Guess The String
题目大意
这是一道交互题，首先输入一个整数，表示一个字符串的长度(1<=n<=1000)。我们需要通过询问推这个字符串并最终输出，询问包括两种
第一种询问不能超过26次，第二种询问不能超过6000次。
当时的思路
先用一个整数表示一个位置的字符，相同的整数表示同一个字符。
遍历字符串，对于每一个位置 i，从当前位置 i 往前遍历 j ，每找到一个此次遍历未见过的字符，便询问 ? 2 i j ，找到那个第一个等于 区间已知字符的不同的数量+1 的位置，那个位置之前遍历的那个位置的字符便对应于位置 i 的字符。
最后再询问每一个整数对应的字符。
错因
第二种询问的询问次数过多。
改进
因为是26个字母，注意到 $\log_2(26)=4.7\leq 5$ ,于是我们便可以使用二分进行查询，即可通过。
代码
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
| #include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const int MAXX=1005;
const double eps=0.0000001;
struct CC{
char ans;
int num;
}a[MAXX];
int n,num_cnt,last[MAXX],s[MAXX];
char getans[MAXX];
inline void solve_it(){
scanf("%d",&n);
a[1].num=num_cnt=1;
last[1]=1;
for(int i=2;i<=n;++i){
int l=1,r=num_cnt+1,mid,in;
for(int j=1;j<=num_cnt;++j)
s[j]=last[j];
sort(s+1,s+num_cnt+1);
while(l<r){
mid=(l+r)/2;
printf("? 2 %d %d\n",s[mid],i);
fflush(stdout);
scanf("%d",&in);
if(in==num_cnt-mid+1)
l=mid+1;
else
r=mid;
}
if(l==1){
a[i].num=++num_cnt;
last[num_cnt]=i;
}
else{
int flag=s[l-1];
for(int j=1;j<=num_cnt;++j)
if(last[j]==flag){
a[i].num=j;
last[j]=i;
break;
}
}
}
for(int i=1;i<=n;++i){
if(!getans[a[i].num]){
printf("? 1 %d\n",i);
fflush(stdout);
char in;
cin>>in;
getans[a[i].num]=in;
}
a[i].ans=getans[a[i].num];
}
printf("! ");
for(int i=1;i<=n;++i)
printf("%c",a[i].ans);
printf("\n");
fflush(stdout);
}
signed main(){
solve_it();
return 0;
}
|
总结
当时脑子里也出现过使用二分的想法，但是由于二分写的太少，非常不熟练，短时间内无法写出来，于是便放弃了二分的想法。
还是得多练二分。
