[ICPC2019 WF]Circular DNA

题目链接：https://codeforces.com/gym/102511/problem/D

题目描述

你在一个研究 DNA 的生物信息科研小组实习。一串 DNA 上有很多不同种类的基因，被称作不同的基因类。一个基因类的基因又被一个特殊的核苷酸序列所标记，称为基因标记。一个基因类 有两种标记，起始标记 和结尾标记 。干完一些脏活之后（培养细菌，抽取细胞，蛋白质工程等），你的科研团队成功将一段 DNA 转化成一个序列的形式，该序列只由基因标记组成。

你的科研团队提出了一个有趣的假说，认为基因的表达取决于基因类上形成的某种恰当的结构。一个基因类 被认为是结构恰当的，就是说将序列中所有的 和 取出按序列中的顺序构成子序列，这个序列需是结构恰当的：

s_ie_i 是结构恰当的。

s_iNe_i当 N 是结构恰当的时，该序列是结构恰当的。

AB 当A,B 均是结构恰当的时，该序列是结构恰当的。

麻烦的是，你所研究的这种 DNA 是环状的，你需要将其从某一个位置切开后才是一个 DNA 序列，显然有的基因类是否恰当取决于你在什么位置切开它。你要解决的问题就是选择一个位置使得最大化切开后恰当的基因类数。记你切的是 p 标记之前的键，那么在有多个 p 满足条件时，你需要给出最小的 p。

Solution

WF居然还有水题。。

考虑维护 q[i],p[i] ：对于编号 i 来说，有 q[i] 个 e_i 空余，有 p[i] 个 s_i 空余。

然后扫描一遍，模拟成环，每次将当前序列的最前端的 s_i 或 e_i 移动至末尾端 ，然后继续维护。

首先，如果编号 i 能构成结构恰当，num(e_i)=num(s_i)

如果将一个 s_i 从头移到尾，会多出一个 e_i 空余 和 s_i 空余 （形如 …e_i…..s_i）

如果将一个 e_i 从头移至尾，会减少一个 e_i 空余 和 s_i 空余 （形如 …s_i…..e_i）

#include<bits/stdc++.h>
const int N = 1e6 + 10 ;
int n,a[N<<1],a_1=1,a_2,p[N],q[N];
char b[N<<1];
std::set<int> s;
void init(){
    scanf("%d\n",&n);
    for(int i=1;i<n;++i)
        scanf("%c%d ",&b[i],&a[i]);
    scanf("%c%d",&b[n],&a[n]);
}
void solve(){

    int ans=0,max=0,pos=0;

    for(int i=1;i<=n;++i){
        s.insert(a[i]);
        if(b[i]=='s') q[a[i]]++;          //( 
        else{
            if(q[a[i]]) q[a[i]]--;
            else p[a[i]]++;            //      )
        }
    }

    for(auto d:s) if(!q[d]&&!p[d]) ans++;

    max=ans,pos=1;

    for(int i=1;i<=n;++i){
        int x = a[i];
        if(b[i]=='s'){
            if(!q[x]&&!p[x]) ans--;
            q[x]++;
            p[x]++;
            if(!q[x]&&!p[x]) ans++;
        }
        else{
            if(!q[x]&&!p[x]) ans--;
            q[x]--;
            p[x]--;
            if(!q[x]&&!p[x]) ans++;
        }
        if(ans>max){
            max=ans;
            pos=i+1;
        }
    }
    printf("%d %d\n",pos,max);
}
int main(){
    init();
    solve();
    return 0;
}