2 条题解

  • 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;
    } 
    
    

    信息

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