A. Prime Deletion

题意：给定一个0-9的排列，要求一个长度>=2的子序列，使得该子序列是质数
做法：考虑31或者13即可。不过当时没有立刻想到，感觉1000以内的质数必有答案，打了暴力。用时就多了点。

Code

#include<bits/stdc++.h>
using namespace std;
int pri[1005],pos[11],cnt;
void solve(){
	string s;
	cin>>s;
	int len=s.length();
	memset(pos,0,sizeof pos);
	for(int i=0;i<len;i++){
		int x=s[i]-'0';
		pos[x]=i;
	}
	for(int i=1;i<=cnt;i++){
		int l=0,x=pri[i];
		if(x<=10) continue;
		int num[11];
		while(x){
			l++;
			num[l]=x%10;
			x/=10;
		}
		reverse(num+1,num+1+l);
		int ok=1;
		for(int i=2;i<=l;i++){
			if(pos[num[i]]>pos[num[i-1]]) continue;
			ok=0;
		}
		if(ok){
			cout<<pri[i]<<endl;
			return;
		}
	}
}
void init(){
	for(int i=2;i<1000;i++){
		int flag=1;
		for(int j=2;j<i;j++)
			if(i%j==0) flag=0;
		if(flag==1){
			cnt++;
			pri[cnt]=i;
		}
	}
}
int main(){
//	freopen("lys.in","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

B.Two Binary Strings

题意：给定01串，第一位必然是0，最后一位是1，可以做的操作是每次把两个字符相同(就是都1或者都是0)之间的所有字符都变成一样，问能否使ab串相等
做法：有一个观察：所有可以变成相同的串最后必然会变成00001111串的形式，所以考虑能否变成这样。符合情况当且仅当存在i，使得a[i]=b[i]='1',a[i-1]=b[i-1]='0'

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],l[maxn],r[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],l[i]=r[i]=0;
	
	l[0]=l[n+1]=r[0]=r[n+1]=0;
	for(int i=2;i<=n;i++){
		l[i]=l[i-1]+(a[i]>=a[i-1]);
	}
	
	for(int i=n-1;i>=1;i--){
		r[i]=r[i+1]+(a[i]>=a[i+1]);
	}
	
	int ans=n+1;
	for(int i=1;i<=n;i++){
		ans=min(ans,l[i]+1+r[i+1]);
	}
	ans=min(ans,l[n]+1);
	ans=min(ans,r[1]);
	cout<<ans<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

C.Queries for the Array

题意：给定一个固定的操作序列，+表示在数列末尾加一个任意值，-表示删去当前末尾的数，1表示当前的序列是有序的，0表示无须，问是否可能。
做法：最开始的想法是维护一个最近的有序长度，然后详细讨论从状态1变成状态0，从状态0变成状态1可不可行等等，但是想法有些难落地。从维护有序长度出发，考虑干脆维护一个区间好了，那最终思路就出来了。具体的细节看代码

Code

#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s;
	cin>>s;
	int len=s.length();
	int arr_l=0,l=0,r=0;
	for(int i=0;i<len;i++){
		if(s[i]=='+'){
			if(r==arr_l) r++;
			arr_l++;
		    if(!l) l++;
		}
		else if(s[i]=='-'){
			if(arr_l==r){
				r--;
			}
			if(arr_l==l){
				l--;
			}
			arr_l--;
		}
		else if(s[i]=='1'){
			if(arr_l!=r&&arr_l!=1){
			//	cout<<i<<" "<<l<<" "<<r<<" "<<arr_l<<endl;
				cout<<"NO"<<endl;
				return;
			}
			l=r;
		}
		else if(s[i]=='0'){
			if(l>=arr_l) {
			//	cout<<i<<" "<<l<<" "<<r<<" "<<arr_l<<endl;
				cout<<"NO"<<endl;
				return;
			}
			r=min(r,arr_l-1);
			l=min(l,r);
		}
	}
	cout<<"YES"<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

D.Sorting By Multiplication

题意：每次可以选择一个区间对区间内每一个数乘上一个整数（可以为负），要求使得数组最后变成严格递增的最少次数
做法：首先考虑如果只用正数去乘的话就很显然。再考虑乘以一个负数。
这里有几个观察：
- 1 是负数段一定是连续的，设想如果不连续，中间有一截正数，那最后还是要把中间的正数变成负数，或者把负数再变回去（显然这没有意义），基于这种思想我们就可以把负数段合并了。
- 2 负数段一定是在前面的部分，也就是说，它是一个前缀。如果不是前缀的话，前面肯定有正数，那么同理，要么把正数变成负数，要么再把负数段变成正数(你干啥子咧)。
- 3 所以最终的思路是枚举分段点，计算前面的一段变成严格递减的代价，后面一段，然后前后合并，记得+1（把递减的前缀乘以一个负数）

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],l[maxn],r[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],l[i]=r[i]=0;
	
	l[0]=l[n+1]=r[0]=r[n+1]=0;
	for(int i=2;i<=n;i++){
		l[i]=l[i-1]+(a[i]>=a[i-1]);
	}
	
	for(int i=n-1;i>=1;i--){
		r[i]=r[i+1]+(a[i]>=a[i+1]);
	}
	
	int ans=n+1;
	for(int i=1;i<=n;i++){
		ans=min(ans,l[i]+1+r[i+1]);
	}
	ans=min(ans,l[n]+1);
	ans=min(ans,r[1]);
	cout<<ans<<endl;
}
int main(){
	//freopen("lys.in","r",stdin);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}