IOI2018 Combo

题意

有一个长度为$n$的字符串S,你需要调用交互函数去猜出它是什么

交互函数int press(string p)输出一个字符串,返回p的一个子串和S的前缀最长公共长度

要注意,S,p都只能由4个字母(abxy)构成,而且S的首字母只会出现一次.

$n \leq 2000$,调用次数$\leq n+2$,$|p|$不超过4n

题解

直接暴力枚举4个字母,调用4n次,得分5分

发现只需要枚举三个(剩下一个就知道了),得分5分.

发现S的首字母只会出现一次.后面只需要枚举2次.得分30分.

性质还没有用上.如果是子串的话有点不好解决因为会多算很多不必要的东西.

想一想首字母的用法.

它可以作为一个”分割字母”,隔开多个串,那么多个串之间无关,而且因为是首字母,那么实际上问的东西就是”分割字母”+询问串得到的这样仅仅一个东西.

考虑怎么判断每一位是什么.相当于一个3选2的过程.但是只有一次机会.

如果A是”分割字母”,要求第二个位置,可以这样

AB|AXA|AXB|AXY

用A把串分成四个部分,如果第二位是B,那么函数会返回2,如果是X则是3,是Y就是1.

这样就可以在一次调用就判断下一个字母什么了.

倒数第二次长度是$4n-1$的,满足条件,而对于最后一位不能这样算,就会多一次.

总次数是$3+(n-2)+2=n+3$,就可以得97分了.

想了好久就是没想出来这一下怎么卡.结果第二天语文课上面突然就想出来了….

要第一次询问输出两种,然后再折半,log(4)是2….两次就好了,发现自己很制杖.

然后就应该能愉快地AC签到题了….

总结

因为没数据评测的缘故,代码目前还没写,不过这样的题应该只需要思路,代码难度很低.

在$ViXbob$神仙的步步指导下想出来的.(%%%),感觉没什么毛病.

作为IOI的签到题,它出的很妙,还是简单写下博客纪念一下…..

如果官方不发数据会考虑出一个数据放OJ上去,但是感觉写grader还要写一个SAM,就很毒瘤,过几天再说把.

Leave a Reply

Your email address will not be published. Required fields are marked *