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
    //部分反例和手玩过程
    
    • 0
      @ 2026-10-13 15:07:49

      模拟赛的时候被这个题硬控了我不信我做不出A。

      思路

      只有三种元素。J 只能作为开头,0 只能作为中间。难点在于 I,既可以开头也可以结尾。而且并没有朴素的方式可以判定一个 I 作为哪个更优。(这里本人对能想到的判定方式都轻松构造反例,按下不表)。

      这提醒我们对 I 可能有两种处理方式:反悔/dp。

      dp 是不行的,因为一个 I 同时可能对前后的 O 造成影响,会出现后效性问题。(可能有强大的方法可以实现,但是我太蒻了)。

      所以考虑反悔:我们从左往右处理。设 xx 表示当前出现的开头数量,xoxo 表示出现的两个前缀字符的数量。

      • 当读入 J 时,只能作为开头,令 x=x+1x=x+1。
      • 当读入 O 时,只能作为中间,如果 x≠0x\ne 0 令 xo=xo+1,x=x−1xo=xo+1,x=x-1。

      这样对于前两个字符的处理是合理的,但是留下来一个伏笔:没人要的 O 是否还有作用。

      对于读入 I 进行反悔贪心:

      • 如果 xo≠0xo\ne 0 :先钦定它作为结尾。
      • 否则考虑是否能替换前面的作为结尾的 I。
      • 若不能替换,令它作为开头使 x=x+1x=x+1

      这么说可能不清楚,下面解释一下,有一个显然的性质:任何一个 I 可以替换一个它前面出现的作为结尾的 I。而这样的替换在当前状态下不会使答案变劣(符合反悔逻辑)。同时解放了一个相对靠前的 I 可以令其变为开头结合更早出现的 O。(这句话可以结合第一个小样例理解)。

      也就是说上面的第二条成立的条件是当前最早出现的作为结尾的 I 后面有一个未被使用的 O。 这个容易使用队列维护。

      代码

      #include<iostream>
      #include<queue> 
      #define int long long
      using namespace std;
      string s;int n,ans,x,xo;
      queue<int> q, qi;
      signed main(){
      	cin >> n >> s;s=" "+s;
      	for(int i=1;i<=n;i++){
      		if(s[i]=='N') x++;
      		else if(s[i]=='O'){
      			if(x){
      				x--,xo++;
      			}else q.push(i);
      		}else{
      			if(xo){
      				qi.push(i);xo--,ans++;
      			}else{
      				if(qi.empty()) x++;
      				else{
      					while(!q.empty()&&!qi.empty()&&qi.front()>q.front()) q.pop(); 
      					if(!q.empty()&&!qi.empty()&&qi.front()<q.front()){
      						q.pop();qi.pop();
      						xo++;qi.push(i);
      					}else{
      						x++;//不得已作开头 
      					}
      				}
      			}
      		}
      	}cout << ans << '\n';
      	return 0;
      } 
      
      
      • 1

      信息

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