这不是傻鸟都会做吗。
题目大意:给定 N 个人的名字 S_1,S_2,...,S_N ,保证均由小写字母构成,其中一些字母未知而被问号代替。现在有一个人名为小写字母字符串 T ,求将 T 插入 S 中后按照字典序排序, T 所有可能的不同排名。
对于已知的字符串 S_i ,它没有任何可变的余地,一定在 T 的前面或后面中的一种,例如 tourist
一定在 zhoukangyang
前面。
对于含有问号的字符串,同样可能固定地大于或小于 T 。如 t??r??t
一定在 taa
后面,因为无论 ?
取什么值都不可能使 t??r??t
的前三位 t??
的字典序小于 taa
,而 t??r??t
长度更大,字典序一定更靠后。
而若 S_i 能形成的字典序最小的值( S_i 为定字符串则这个值为 S_i )与 T 相同或小于 T ,则代表我们有办法把 S_i 排在 T 前面。反之亦然。
例如对于 S_i= t??
,T= taa
,把 S_i 设为 taa
即可将 S_i 排在 T 前,设为 tot
即可排在 T 后。
因此对于 S_i= s?k??
,将全部填上 a
的 sakaa
与 T 比较即可得知 S_i 能否排在 T 前;将全部填上 z
的 szkzz
与 T 比较即可得知 S_i 能否排在 T 后。
我们可以依此得出只能排在 T 前面的 S_i 数量 l ,只能排在 T 后面的 S_i 数量 r ,那么 T 与这 l+r 个串的相对位置已经确定,其它字符串可能排在 T 前面或后面,我们不关心。
共有 N+1 个串(含 T ),其中 l 个必须排在 T 前, r 个必须排在 T 后。
比较字典序直接使用小于号即可。战国时代的ATcoder繁文缛节,输出时最后一个数不能带空格且必须换行。
```cpp
//I love Poncirus forever
for(int i=1;i<=n;i++)
{
string s1=s[i],s2=s[i];//s1为s_i的最小值,s2为最大值
int len=s[i].size();
for(int j=0;j<len;j++) if(s1[j]=='?') s1[j]='a';
for(int j=0;j<len;j++) if(s2[j]=='?') s2[j]='z';
int ilove=(s1<=t),poncirus=(t<=s2);
if(ilove&&!poncirus) l++;
if(!ilove&&poncirus) r++;
}
for(int i=l+1;i<=n-r;i++) cout<<i<<' ';
cout<<n-r+1<<'\n';
return (0.0);