ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF1290B Irreducible Anagrams 题解

posted on 2021-01-29 11:38:06 | under 题解 |

我真的只是开个VP啊,然后就遇到了这个B,想了一个小时也没想出来......有被毒瘤到/kk

我们考虑对于一个串$s$,求出它的每个前缀每个字符的出现次数,我们把这个每个字符的出现次数搞成一个数组,这个数组可以看作表示了26维空间中的一个点。

考虑每个前缀的这个点,应该是上一个前缀的点在某一维度上$+1$得到的。所以如果设$s$中各个字符出现次数分别为$a,b,c,...$,那么把每个前缀的点描出来,每个点向上一个前缀的点连线,应该可以构成从$(0,0,0,...)$到$(a,b,c,...)$的一条路径,其中每一步都是向某个正方向走了$1$单位距离。

所以我们的问题变成了,找一条从$(0,0,0,...)$到$(a,b,c,...)$的路径,满足每一步都是向某个正方向走$1$单位距离,并且它和这个串描述的路径不在这两个端点之外的地方相交。

为什么这样做呢?考虑交点的意义,如果两个串描述的路径有一个交点,我们可以以交点作为第一段的结尾,把这两个串分成两段,前一段根据定义是anagram,后一段显然也是anagram,这就说明你找的串是个reducible anagram;同时容易证明一对reducible anagram的分段处也一定是路径的交点。所以找irreducible anagram,等价于找没有交点的路径。

然后我们考虑,如果是在三维或者更高维空间中,绕路应该是很容易并且极可能可行的一件事——因为你在每个切片上都有两个自由度,不可能被逼得无路可走。所以我们可以大胆猜测,当这个空间有至少三个自由度,也就是$a,b,c,...$中至少三个不为$0$时,肯定存在方案。证明的话,可以去看其它题解的构造。

但是在二维空间中,这件事不一定能办。观察样例我们发现,如果开头结尾不同,那我们交换开头结尾,就得到了一个irreducible anagram。那么如果开头结尾相同呢?我们假设开头结尾都是字符a,另一种字符是b。考虑$s$的路径是在这个平面上走了这么一条路 : $(0,0)\rightarrow (1,0)\rightsquigarrow (a-1,b)\rightarrow (a,b)$,然后如果你要构造的话,肯定是走$(0,0)\rightarrow (0,1)\rightsquigarrow (a,b-1)\rightarrow (a,b)$(不然开头结尾就相交了)。然后你发现这两条路径是从不同方向跨过对角线$(0,0)\rightarrow (a,b)$的,那么它们不可能不相交,所以有两种字符并且开头结尾相同时是无解的。

在一维空间中,也就是只有一种字符的情况下,直接特判掉即可。

使用前缀和,复杂度$O((n+m)\Sigma)$。

#include<stdio.h>
#include<string.h>

int n,m;
char s[200002];
int pre[200002][26];

int main()
{
    scanf("%s%d",s+1,&m);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<26;j++)
            pre[i][j]+=pre[i-1][j];
        pre[i][s[i]-'a']++;
    }
    for(int i=1,l,r,cnt;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        cnt=0;
        for(int j=0;j<26;j++)
            if(pre[r][j]-pre[l-1][j]) cnt++;
        printf(cnt>=3||(cnt==1&&l==r)||(cnt==2&&s[l]!=s[r])?"YES\n":"NO\n");
    }
    return 0;
}