1 条题解

  • 0
    @ 2026-11-5 10:57:35

    下面我们说“奇偶”指 ‘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;
    }
    

    [2026济南登峰营] D1 P2 削除射线(sakuzyo) - 文件读写

    信息

    ID
    963
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    62
    已通过
    3
    上传者