2 条题解

  • 4
    @ 2026-10-13 14:33:09

    SOLUTION

    这貌似是贪心 round ,看起来这个题像是贪心了,于是先想贪心。

    首先发现 NOI,IOI 都以 O 作为中心,直觉上认为要枚举 O,判断他的两边的情况。

    11

    能不能从前往后枚举 O,假设前面的 O 已经处理完了,所以我们从前面随便选一个没用过的 I 或 N 当开头。

    对于后面的,由于选太往前的 I 会导致后面没有 I 当开头,于是直接选最后面没用过的 I。

    这个算法显然是假的,因为他过不了样例 1,具体原因是后面的 O 后面没有 I 用了。

    22

    既然后面的 O 要有 I,那能不能提前给他留出一个 I 不用呢?

    具体地,从后往前枚举,遇到 I 就入队列,遇到 O 就弹出队头,与之配对。

    之后从前往后枚举,用一个数组标记是否用过这个位置,在枚举时统计能当前面 I 或 N 的个数。

    遇到 O 时,看他是否已经被配对且前面还有空闲的 I 或 N,都满足则 ans++。

    这个算法可以通过全部小样例和大样例,感觉应该对了吧。

    33

    其实并非,感觉上有反例,我写了一个对拍,拍了 <1s< 1s 就挂了。

    观察一组简单的数据:IOOIOII。

    显然答案应该为 22,但上述算法给出 11。

    简单分析可以发现,在枚举到 i=2i=2 的 O 时,算法错误地把他和 i=1,4i=1,4 的 I 配了对,导致没法继续组成答案。

    而且,i=3,6i=3,6,i=5,7i=5,7 这两个配对完全没有用上。

    这时有一个简单的补救方法:加一步反悔,把用不上的配对中的 I 给上一个用,把靠前的 I 变成空闲的。显然空闲的 I 越靠前就越优,这样改不会更劣。

    也就是枚举到成功配对的 O 的时候,如果前面没有可以用的空闲的 I 或 N,就要做这个反悔。

    这样总该对了吧?

    44

    其实还没对,我继续跑对拍,发现在大约第 20002000 组出锅了。

    发现 33 中所述并不完备,对于同一个 O,如果有多个已经计入答案可以反悔的,理应对最前面的一个反悔。

    于是我们做一些改进,用队列存储所有已经计入答案的 NOI,IOI 中靠后的 I,每次反悔时取出队头,再把新的 I 扔进队尾,显然队列内元素有序。

    最后发现对拍跑不出错来了,直接提交,喜提 100100 pts。

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    string s;
    int usd[1001000];
    int q[1001000],fr=1,tl=0;
    int mtc[1001000];//match
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n>>s;
        s=' '+s;
        for(int i=n;i>=1;i--){
            if(s[i]=='O'){
                if(fr<=tl) mtc[i]=q[fr++];
            }
            if(s[i]=='I') q[++tl]=i;
        }
        fr=1,tl=0;
        int ans=0,si=0;//si表示空闲的 I or N
        for(int i=1;i<=n;i++){
            if(s[i]=='O'){
                if(mtc[i]&&si) usd[mtc[i]]=1,si--,ans++,q[++tl]=mtc[i];
                else if(mtc[i]&&!si&&ans){
                    int lst=q[fr++];
                    if(lst<i) si++;
                    usd[mtc[i]]=1,usd[lst]=0;
                    q[++tl]=mtc[i];
                }
            }
            else if(!usd[i]) si++;
        }
        cout<<ans<<'\n';
        return 0;
    }
    // NO NO ONOO I NN I III
    //  I O O O I ONNIOIOINI
    // *****O*IOIONI
    // NOI O NO I NO O OIIII
    // INOOIOONNINIOII
    //部分反例和手玩过程
    

    信息

    ID
    900
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    51
    已通过
    10
    上传者