[20190725NOIP模拟测试8]题解

深藏阁楼爱情的钟 2021-10-29 08:50 295阅读 0赞

# [Orz][] #

# T1 #

大水题，考场上看到题目中什么前几位相同末尾加字母莫名慌的一批

后来发现直接无脑哈希就能$O(n)$

KMP同样可切

仔细读题，数组别开小

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #define re register
    using namespace std;
    typedef unsigned long long ull;
    const int N=200005,base=131;
    int T,la,lb;
    ull power[N],ha[N],hb[N];
    char A[N],B[N],ed[3];
    inline void ini()
    {
        for(int i=0;i<=la;i++)
            ha[i]=hb[i]=0;
    }
    inline void work()
    {
        scanf("%d%d",&la,&lb);
        scanf("%s",A+1);
        scanf("%s",ed);
        ini();
        for(re int i=1;i<=lb;i++)
            B[i]=A[i];
        B[++lb]=ed[0];
        for(re int i=1;i<=lb;i++)
            hb[i]=hb[i-1]*base+B[i];
        for(re int i=1;i<=la;i++)
            ha[i]=ha[i-1]*base+A[i];
        //debug();while(1);
        int ans=0;
        for(re int i=1;i<=min(la,lb);i++)
        {
            if(i==1)
            {
                if(A[1]==B[lb])ans=1;
                continue;
            }
            if(ha[i]==hb[lb]-hb[lb-i]*power[i])
                ans=max(ans,i);
            //cout<<geta(1,i)<<' '<<getb(lb-i+1,lb)<<endl;
        }
        printf("%d\n",ans);
    
    }
    int main()
    {
        scanf("%d",&T);
        power[0]=1;
        for(re int i=1;i<=N;i++)
            power[i]=power[i-1]*base;
        while(T--)work();
        return 0;
    }

# T2 #

画画图可以发现，所谓“必经之路”就是删去后使1和n不联通的点

那么这些点一定是原图的割点，同时满足删掉后1和n不再联通

于是大概思路就出来了：跑$Tarjan$，再乱搞满足第二个条件

不难发现，要满足后者，当且仅当n在所求得割点的搜索树子树上

那么这个条件反映到$Tarjan$算法上是什么呢？

即**对于割点x，存在与它相连的点y，满足$dfn\[y\] \\leq dfn\[n\]$**

为什么？

考虑$dfn\[\]$的实际含义：每个点被访问的时间戳，我们可以用它判断点被访问的先后

**如果y与n位于不同子树（不成立情况）:**

先访问n再访问y：显然$dfn\[y\]>dfn\[x\]$，不满足

反之：$dfn\[y\]$已更新而$dfn\[n\]$未更新，也不满足

**如果y与n同树：**

y在n前/y即为n：成立

n在y前（不成立）：显然此时$dfn\[y\]>dfn\[n\]$,不满足

命题得证。

inline void tarjan(int x)
    {
        low[x]=dfn[x]=++ind;
        int flag=0;
        for(int i=head[x];i;i=nxt[i])
        {
            if(!dfn[to[i]])
            {
                tarjan(to[i]);
                low[x]=min(low[x],low[to[i]]);
                if(low[to[i]]>=dfn[x])
                {
                    flag++;
                    if((x!=1||flag>1)&&dfn[to[i]]<=dfn[n])iscut[x]=1;
                }
            }
            else low[x]=min(low[x],dfn[to[i]]);
        }
    }

还有一个问题：如果单想到要让n在割点的子树里，很容易写成dfn\[x\]<dfn\[n\]

然额实际上是不行的，会获得30分的好成绩（雾

为什么呢？

如果n位于由x出发的一条返祖路径上就完蛋了。

可以自己画图玩一下。

# T3 #

玄学题，[点我看大佬题解][Link 1]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const int N=1000005;
    const ll inf=0x7fffffffffff;
    int T;
    char str[N];
    int s[N<<1],cnt[N<<1],len;
    ll val[N<<1];
    void ini()
    {
        for(int i=1;i<=len*2;i++)
            s[i]=cnt[i]=val[i]=0;
    }
    void work()
    {
        ll ans=inf;
        scanf("%s",str+1);
        len=strlen(str+1);
        ini();
        for(int i=1;i<=len;i++)
            s[i]=s[i+len]=(str[i]=='B'?0:1);
        /*for(int i=1;i<=(len<<1);i++)
            cout<<s[i];*/
        for(int i=1;i<=(len<<1);i++)
            cnt[i]=cnt[i-1]+s[i],val[i]=val[i-1]+i*s[i];
        int p=1;
        for(int i=1;i<=len;i++)
        {
            ll res=inf;
            for(int j=p;j<=i+len+1;j++)
            {
                ll lnum=cnt[j-1]-cnt[i-1];
                ll rnum=cnt[i+len-1]-cnt[j-1];
                ll sum=(val[j-1]<<1)-val[i-1]-lnum*i+rnum*1LL*(i+len-1)-val[i+len-1]-(lnum-1)*lnum/2-(rnum-1)*rnum/2;
                if(sum>res)break;
                res=sum,p=j;
                ans=min(ans,res);
            }
        }
        cout<<ans<<endl;
    }
    int main()
    {
        //cout<<0x7fffffffffff<<endl;while(1);
        scanf("%d",&T);
        while(T--)work();
        return 0;
    }

转载于:https://www.cnblogs.com/Rorschach-XR/p/11247992.html

[Orz]: https://www.cnblogs.com/Rorschach-XR/p/11243159.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/fd69ab35c8af408cb97ebac9faad66e4.png
[Link 1]: https://www.cnblogs.com/hzoi-DeepinC/p/11246615.html