题解:AT_s8pc_4_a Atcoder Handles

Lybei

2024-11-15 22:04:19

Solution

这不是傻鸟都会做吗。

题目大意:给定 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?? ,将全部填上 asakaaT 比较即可得知 S_i 能否排在 T 前;将全部填上 zszkzzT 比较即可得知 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);