CF1292E

link

题意:有一个包含O,H,C的串,你现在只知道长度,每次可以询问一个串t在这个串里的所有出现位置,代价是$\frac{1}{|t|^2}$,你需要用不超过1.4的代价询问出这个串。

这个做法目前是$1.333333$的。

下面用1来代替C,2来代替H,3来代替O。

考虑可以先询问长度为2的串,可以得到每个字符前后可以接哪些字符。

假设我们已经有确定的位置了,可以进行如下操作来找到原串:

对于每个极长(已经确定位置的)串,如果前一个/后一个可以确定,就加上这个字符

如果没有字符能被这样加上,就找到最长的子串,在前面和后面中选出可能情况较少的一边,遍历每个取值,询问直到加上这个取值出现在原串里(最后一个取值不用询问)

那么现在考虑询问长度为2的串来找到确定的位置

考虑询问完一个串之后,除了出现位置其它位置都不是这个子串。

那么考虑先按照11,12,13的顺序询问,如果找到了11或12子串,可以直接暴力搞出原串。否则询问完13之后就没有1开头的串了,也就是除了最后一个位置,其它没确定的位置一定不是1,如果找到了13可以暴力判,次数<= $0.75+\sum_{i=3}^n\frac{1}{i^2}$ 其中某一个串找到了位置,则可以直接暴力判。

如果都没找到可以考虑询问23和32,如果找到了至少一个,那么剩下除了最后一个位置都已经确定了,只用询问一次长度为n

如果全部没找到则串只有可能是22221 33331 22222 33333这四种情况,可以判一次2222再判一次33333解决,代价是$1.25+\frac{1}{(n-1)^2}+\frac{1}{n^2}$,$n=4$时为$1.423611$,$n=5$时为$1.3525$。

考虑优化$n=4$的情况。

考虑询问23之后的局面

如果发现了23可以询问32再判一次是1.3125的

如果没发现则只能333…222..1这种串了

情况大概有这些:

1
2
3
4
5
6
7
8
9
3331
3321
3221
2221
3333
3332
3322
3222
2222

考虑按照长度为3的子串分组:

1
2
3
4
5
6
7
8
9
10
11
12
3331 (333)
3333
3332

2221 (222)
3222
2222

3322
3221 (322)

3321 (3321)

直接按顺序询问不够优秀,因为最后一组个数太多,可以和第二组交换

所以流程就变成了:

1
2
3
询问 333 如果存在就判断3331/3332 (1次3 2次4) 否则
询问 322 如果存在就得到答案 否则
询问 222 如果存在就得到答案 否则答案是3321

于是$n=4$最坏情况变成了1.333,已经足以通过了

考虑优化$n>4$的前面一部分:

注意到最坏情况依然是23和32都没找到的情况,考虑套用类似优化:

1
2
3
4
5
考虑询问23之后的局面

如果发现了23可以询问32再判一次

如果没发现则只能333...222..1这种串了

不过n增加之后不好找规律了,考虑通用操作

(下文无特殊情况均为len=n-1)

1
2
3
4
5
6
先判333...
然后333...2
然后333...22
然后类似的直到发现子串或者322...也没找到
如果发现子串那么一定最多只有最后一个字符不知道,可以是1/2,暴力询问
如果没发现那么222..一定是一个子串,判222..1或222..2。

这一部分最坏变成了1.29

然后我不会优化n=4了

贴个代码

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
int n;
int nx[4][4];
int w[55];
int od[4],id[4];
char s[]={" CHO"};
bool ask(const vector<int>&vt){
cout<<"? ";
for(auto i:vt)cout<
cout<<endl;
int k;
cin>>k;
if(!~k)exit(0);
if(!k)return 0;
int m=vt.size();
for(;k;--k){
int x;
cin>>x;
for(int i=0;i
}
return 1;
}
bool find(){
int s=-1,at=0;
for(int i=1;i<=n;++i)if(w[i]){
if(i>1&&id[w[i]]==1){
for(int j=1;j<=3;++j)if(nx[j][w[i]]){w[i-1]=j;return 1;}
}
int j=i;
while(w[j+1])++j;
if(j1){

for(int k=1;k<=3;++k)if(nx[w[j]][k]){w[j+1]=k;return 1;}
}
if(chkmax(s,j-i))at=i;
i=j;
}
if(s==n-1)return 0;
int wi=at==1?inf:id[w[at]],wo=at+s==n?inf:od[w[at+s]]-(at+s==n-1||od[1]?0:1);
if(wi<=wo){
vector<int> q(s+2);
for(int i=0;i<=s;++i)q[i+1]=w[i+at];
int c=id[w[at]];
for(int i=1;i<=3;++i)if(nx[i][w[at]]){
if(c>1){
q[0]=i;
if(ask(q))return 1;
--c;
}
else {w[at-1]=i;return 1;}
}
}
else{
vector<int> q(s+2);
for(int i=0;i<=s;++i)q[i]=w[i+at];
int c=wo;
for(int i=1;i<=3;++i)if(nx[w[at+s]][i]&&(i!=1||at+s==n-1||od[1])){
if(c>1){
q[s+1]=i;
if(ask(q))return 1;
--c;
}
else {w[at+s+1]=i;return 1;}
}
}
return 0;
}
bool try2(int x,int y){
if(ask({x,y})){nx[x][y]=0;--od[x];--id[y];return 1;}
else {nx[x][y]=0;--od[x];--id[y];return 0;}
}
void answer(){
cout<<"! ";
for(int i=1;i<=n;++i)cout<
cout<<endl;
int k;
cin>>k;
if(!~k)exit(0);
for(int i=1;i<=n;++i)w[i]=0;
}
bool gg(){
if(n==4){
if(ask({3,3,3})){
nx[3][3]=0;
if(!w[4])return ((ask({3,3,3,1}))||(w[4]=2)),0;
return 0;
}
else if(ask({2,2,2})){
nx[2][2]=0;
if(!w[4])w[4]=1;
if(!w[1])w[1]=3;
return 0;
}
else if(ask({3,2,2})){
if(w[1])w[4]=1;
else w[1]=3;
return 0;
}
else return (w[1]=3,w[2]=3,w[3]=2,w[4]=1),0;
}
else{
vector<int> v(n-1,3);
int m=n-1;
while(m&&!ask(v)){v[m-1]=2;--m;}
for(int i=0;i-1;++i)w[i+1]=v[i];

while(find());
return 0;
}
}
bool fnd(){
while(find());
return 1;
}
void query(){
for(int i=1;i<=3;++i)for(int j=1;j<=3;++j)nx[i][j]=1;
for(int i=1;i<=3;++i)od[i]=id[i]=3;
(try2(1,1)||try2(1,2)||try2(1,3)||(try2(3,2)&&(try2(2,3)||1))||gg())&&fnd();
answer();
}
signed main(){
int t;
cin>>t;
for(;t;--t){
cin>>n;
query();
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×