2 条题解
-
0
模拟赛的时候被这个题硬控了
我不信我做不出A。思路
只有三种元素。
J只能作为开头,0只能作为中间。难点在于I,既可以开头也可以结尾。而且并没有朴素的方式可以判定一个I作为哪个更优。(这里本人对能想到的判定方式都轻松构造反例,按下不表)。这提醒我们对
I可能有两种处理方式:反悔/dp。dp是不行的,因为一个I同时可能对前后的O造成影响,会出现后效性问题。(可能有强大的方法可以实现,但是我太蒻了)。所以考虑反悔:我们从左往右处理。设 表示当前出现的开头数量, 表示出现的两个前缀字符的数量。
- 当读入
J时,只能作为开头,令 。 - 当读入
O时,只能作为中间,如果 令 。
这样对于前两个字符的处理是合理的,但是留下来一个伏笔:没人要的
O是否还有作用。对于读入
I进行反悔贪心:- 如果 :先钦定它作为结尾。
- 否则考虑是否能替换前面的作为结尾的
I。 - 若不能替换,令它作为开头使
这么说可能不清楚,下面解释一下,有一个显然的性质:任何一个
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
- 上传者