1 条题解
-
0
下面我们说“奇偶”指 ‘l’ 前元素数量的奇偶(所以偶删yq,奇删l)、“爆”指删 ‘l'、1组指单独一个“ylq"
我们发现不断重复——删光偶的,再把第一个爆掉是不优的(70pts
如:
ylq ylq ylq ylq yyylqqq我们显然发现,因为1组不管怎么削都只能削一次,所以贪心的尽量让1组的爆掉是好的
那我们按过程模拟,显然会超时的(因为有很多1组的我们要留着爆掉
我们需要以O(n)为基础的解法
考虑刚才说的贪心,不管是否真的必须爆掉,把1组的爆掉一定不劣,所以枚举一遍并记录前面能爆掉的最大数量就好了
Code:
#include<bits/stdc++.h> #define F first #define S second #define mkp make_pair using namespace std; string s;int n; int get(int i){ int ct=0; for(int j=1;0<i-j&&i+j<=n;j++){ if(s[i-j]=='y'&&s[i+j]=='q') ct++; else break; } return ct; } int main() { freopen("sakuzyo.in","r",stdin); freopen("sakuzyo.out","w",stdout); cin>>s;n=s.size();s=' '+s+' '; queue<pair<bool,int> > q; for(int i=1;i<=n;i++){ if(s[i]=='l'&&s[i-1]=='y'&&s[i+1]=='q') q.push(mkp((i-1)&1,get(i))); } int ans=0,ct=0; while(!q.empty()){ pair<bool,int> i=q.front();q.pop(); if(!i.S) continue; if(i.S==1){ if(i.F||ct) ct++;ans++; } else{ if(!i.F) ans++,i.S--; ans+=min(i.S-1,ct)+1;ct++; } } cout<<ans; return 0; }
信息
- ID
- 963
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 62
- 已通过
- 3
- 上传者