CF1861(div2)题解

CF1861

A. Prime Deletion

题意：
一串9个数字，1-9只出现一次，删除若干个字符，使数字为质数
思路：
1在3前输出13，3在1前输出31

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		string s;
		cin >> s;
		if(s.find("1") < s.find("3"))
			cout << 13;
		else
			cout << 31;
		cout << endl;
	}
}

B. Two Binary Strings

题意：
一串01串，第一个必定为0，最后一个必定为1，可进行如下操作
取下标 $i,j(a_i=a_j)$，将下标为 $i+1\to j-1$ 的数变为 $a_i$
思路：
01串中有连续的01，即 $a_i=0,a_{i+1}=1$

void solve(){
	string a,b;
	cin>>a>>b;
	bool g=0;
	for(int i=0;i<a.size()-1;i++){
		if(a[i]==b[i]&&a[i+1]==b[i+1]&&a[i]=='0'&&a[i+1]=='1')g=1;
	}
	cout<<(g?"YES\n":"NO\n");
}

C. Queries for the Array

题意：
给定一个初始为空的数组，一串字符串表示操作
‘+’表示从数组后添加一个数字
‘-‘表示从数组后删除一个数字
‘1’表示检查该数组，为单调递增（长度小于2也为单调增）
‘0’表示检查该数组，为单调递减
问字符串是否合法？
思路： 用set维护出现0时数组最末端的位置，表示该位置使数组不为单调增 用一个变量维护出现1时，固定的单调增长度，长度随每次数组长度减少而更新

void solve(){
	string s;
	cin>>s;	
	int a=0,b=0,cnt=0;
	set<int> S;
	for(int i=0;i<s.size();i++){
		if(s[i]=='+'){
			cnt++;
		}
		else if(s[i]=='-'){
			S.erase(cnt);
			cnt--;
			a=min(cnt,a);
		}
		if(s[i]=='0'){
			if(S.empty()){
				if(cnt<=max(a,1)){
					cout<<"NO\n";
					return;
				}
				else S.insert(cnt);
			}
		}
		else if(s[i]=='1'){
			if(S.size()){
				cout<<"NO\n";
				return;
			}
			a=max(a,cnt);
		}
	}
	cout<<"YES\n";
}

D. Sorting By Multiplication

题意：
给定长度为n的数组，可以进行如下操作：
选择区间 $[l,r]$ 乘上x(任意数)
最小操作数使数列单调递增
思路：
对于连续单调递减的一部分，乘上负数会单调递增
用 $pre_i$ 表示前i(包括i)个数有多少个连续单调递减的部分
用 $suf_i$ 表示后i(包括i)个数有多少个连续单调递增的部分
i从 $1\to n-1,ans=max(ans,pre_i+suf_{i+1}-1)$ ,有一个部分可以不变所以减1
i=n时单独考虑，此时 $suf_{i+1}=0$ ,只考虑pre，即全部部分变为负数，不能减1，更新 $ans=max(ans,pre_n)$

void solve(){
    int n;
    cin>>n;
    vector<ll> a(n+1),pre(n+2),suf(n+2); 
    for(int i=1;i<=n;i++)cin>>a[i];
    pre[1]=1,suf[n]=1;
    for(int i=2;i<=n;i++){
        pre[i]=pre[i-1];
        if(a[i]>=a[i-1])pre[i]++;
    }
    for(int i=n-1;i>=1;i--){
        suf[i]=suf[i+1];
        if(a[i]>=a[i+1])suf[i]++;
    }
    ll ans=INF;
    for(int i=0;i<n;i++){
        ll tmp=pre[i]+suf[i+1]-1;
        ans=min(ans,tmp);
    }
    ans=min(ans,pre[n]);
    cout<<ans<<"\n";
}