2 条题解
-
4
SOLUTION
这貌似是贪心 round ,看起来这个题像是贪心了,于是先想贪心。
首先发现
NOI,IOI都以O作为中心,直觉上认为要枚举O,判断他的两边的情况。能不能从前往后枚举
O,假设前面的O已经处理完了,所以我们从前面随便选一个没用过的I或N当开头。对于后面的,由于选太往前的
I会导致后面没有I当开头,于是直接选最后面没用过的I。这个算法显然是假的,因为他过不了样例 1,具体原因是后面的
O后面没有I用了。既然后面的
O要有I,那能不能提前给他留出一个I不用呢?具体地,从后往前枚举,遇到
I就入队列,遇到O就弹出队头,与之配对。之后从前往后枚举,用一个数组标记是否用过这个位置,在枚举时统计能当前面
I或N的个数。遇到
O时,看他是否已经被配对且前面还有空闲的I或N,都满足则ans++。这个算法可以通过全部小样例和大样例,感觉应该对了吧。
其实并非,感觉上有反例,我写了一个对拍,拍了 就挂了。
观察一组简单的数据:
IOOIOII。显然答案应该为 ,但上述算法给出 。
简单分析可以发现,在枚举到 的
O时,算法错误地把他和 的I配了对,导致没法继续组成答案。而且,, 这两个配对完全没有用上。
这时有一个简单的补救方法:加一步反悔,把用不上的配对中的
I给上一个用,把靠前的I变成空闲的。显然空闲的I越靠前就越优,这样改不会更劣。也就是枚举到成功配对的
O的时候,如果前面没有可以用的空闲的I或N,就要做这个反悔。这样总该对了吧?
其实还没对,我继续跑对拍,发现在大约第 组出锅了。
发现 中所述并不完备,对于同一个
O,如果有多个已经计入答案可以反悔的,理应对最前面的一个反悔。于是我们做一些改进,用队列存储所有已经计入答案的
NOI,IOI中靠后的I,每次反悔时取出队头,再把新的I扔进队尾,显然队列内元素有序。最后发现对拍跑不出错来了,直接提交,喜提 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
模拟赛的时候被这个题硬控了
我不信我做不出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; } - 当读入
- 1
信息
- ID
- 900
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 51
- 已通过
- 10
- 上传者