Prime Deletion（Problem - A - Codeforces）
题目大意：给定一串由1-9组成的字串，每个数出现且只出现一次，要求不改变相对顺序，从中删除一些字符，使得留下的数是一个质数。留下的数最少为2位。
思路：这题很简单，它说最少留两位，那么我们就留两位，那就是输出以不同数开头的两位质数即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s;
cin>>s;
if(s[0]=='1') printf("13
");
else if(s[0]=='2') printf("23
");
else if(s[0]=='3') printf("37
");
else if(s[0]=='4') printf("41
");
else if(s[0]=='5') printf("53
");
else if(s[0]=='6') printf("61
");
else if(s[0]=='7') printf("71
");
else if(s[0]=='8') printf("89
");
else printf("97
");
}
}
Two Binary Strings（Problem - B - Codeforces）
题目大意：我们给定两个01串，要求每次选定一个01串的一个区间[l,r]，要求s[l]=s[r]，然后我们将l<i<r的位置全部改成s[l],问最终能否使两个字串相等。
两个字串满足3个要求：
长度相等，
以0开头以1结尾，
长度小于等于5000。
思路：我们可以发现用来修改的，不仅s[l]=s[r]，它们俩同时还要与另一个字串中的对应位置相等，不然修改是没有意义的。然后就是修改策略问题，一个策略就是我们尽可能地多改一些，全部统一最好。这里有个很关键的条件，以0开头以1结尾，最开始就因为没注意这个条件，试了很多有问题的方法。那么我们就这个条件来看，只要字串中有0相等的位置，都可以跟开头一块儿作为一个区间，只要有相等的1的位置，都可以和结尾作为一个区间。我本来想的是按照最优策略改最长的区间，如果左右两个区间不相交，那么就看中间没被修改的部分，如果左右相交，就分别看两种情况下没被修改的部分是否有不相等的位置，但是这种思路不太好，
1
00001 101000100 1001
00010 101000010 0111这个样例就不合适(我把找的位置切开了)
我们根据这个来看，可以左边区间稍短一点右边区间稍长一点，然后两者中间的全部相等，这样就能实现，所以，我们分别记录两者的另一端点可能出现的位置，然后暴力组合，找出合法组合，如果没有那么就判否即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s1,s2;
cin>>s1>>s2;
int l=s1.size()-1;
vector<int>v1,v0;
for(int i=l;i>=0;i--)
{
if(s1[i]==s2[i]&&s1[i]=='0')
{
v0.push_back(i);
}
}
for(int i=0;i<=l;i++)
{
if(s1[i]==s2[i]&&s1[i]=='1')
{
v1.push_back(i);
}
}
int flag=1;
for(int i=0;i<v0.size();i++)
{
for(int j=0;j<v1.size();j++)
{
int l=v0[i],r=v1[j];
if(l>r) continue;
flag=1;
for(int k=l;k<=r;k++)
{
if(s1[k]!=s2[k])
{
flag=0;
break;
}
}
if(flag) break;
}
if(flag) break;
}
if(flag) printf("YES
");
else printf("NO
");
}
}
Queries for the Array（Problem - C - Codeforces）
题目大意：现有一个空数组和一串操作字符，同时定义数组长度小于2或者数组中相邻元素满足ai<=aj时，将数组视为有序，操作字串中一共有四种操作：
'+':向数组末尾添加一个字符
'-'：弹出末尾字符
‘0’查询到数组为非有序状态
‘1’查询到数组为有序状态
问这串字符串能否正确执行。
思路：显然'+'和'-'都可以正确操作，关键就在于查询结果是否是我们想要的。因为在查询之前，我们添加数可能有很多种情况，所以我们把它视为自由状态，数组一旦有序，那么有序部分就始终有序除非全部弹出，那么我们就可以用一个变量来表示它至少到第几位还是有序的，在查询单减状态时，如果它最少的有序位数等于数组长度或者当前数组长度小于2，那么肯定需要判否。如果查询数组无序而且没有判否说明可以无序，为了满足无序状态同时尽快还原成单增状态，我们只将不等关系放在最后一个字符处。那么就用一个变量来记录这个位置，如果它被弹出就将这个变量置0，在查询有序的时候，如果这个被标记位置小于数组长度，那么就说明前面有一处无序，显然整个数组都应为无序，判否。
所以实际上就是，用最小有序的位数与总位数的关系来判断是否无序，用上一次标记的无序的为位来判断数组是否有序。因为正着判不好判，那么我们直接反过来判断。另外在判断之前数组就是无序数组，只有开始判断了，数组才有性质，而且这个性质是与我们的查询挂钩的，而且为了最优策略，我们实际上的落脚点在最后一个元素。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s;
cin>>s;
int z=0,y=0,f=0;
int flag=1;
for(int i=0;i<s.size();i++)
{
if(s[i]=='+') z++;
else if(s[i]=='-')
{
if(y==z) y=z-1;
if(f==z) f=0;
z--;
}
else if(s[i]=='1')
{
if(f)
{
flag=0;
break;
}
y=z;
}
else if(s[i]=='0')
{
if(z==y||z<2)
{
flag=0;
break;
}
if(!f) f=z;
}
}
if(flag) printf("YES
");
else printf("NO
");
}
}
Sorting By Multiplication（Problem - D - Codeforces）
题目大意：现有一个数组，我们可以对数组进行操作：每次选定一段区间，将区间内的数全部乘上同一个整数(可正可负)，问最少操作几次可以得到一个单增的序列。
思路：我们很容易得到的一个性质是两个数同时乘一个正数不会改变相对大小，同时乘一个负数相对大小变化一下，但是乘一个负数是有代价的，整个区间内的数全部变小(原数组都是正数)，所以这个操作不能再中间位置执行，否则就会得不偿失。很明显是在前缀中执行，所以我最开始想的是统计前缀中连续的需要被修改的有多少个数，然后再加上后面要修改的，因为后面要修改的显然只能一位一位改，但注意到，我们可以在前面凑出单减，那么就是前缀凑单减的操作次数+后缀改成单增的操作次数+1的最小值即为所求。所以最关键的点在于想到前缀的单减可以凑出来。（增变减乘负数即可）
#include<bits/stdc++.h>
using namespace std;
int l[200010],r[200010],a[200010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(l,0,sizeof l);
memset(r,0,sizeof r);
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1]) l[i]=l[i-1]+1;
else l[i]=l[i-1];
}
for(int i=n-1;i>=1;i--)
{
if(a[i]>=a[i+1]) r[i]=r[i+1]+1;
else r[i]=r[i+1];
}
int ans=1e9;
ans=min(ans,r[1]);
for(int i=2;i<=n;i++)
{
//当前元素在l中作为前缀或在r中作为后缀，只能用一次
//统计前缀的时候，l[i]判断了当前位置的值需不需要改变
//统计后缀的时候，r[i]也考虑了当前位置的元素需不需要改变
ans = min(ans,l[i]+r[i+1]+1);
ans=min(ans,l[i-1]+r[i]+1);
}
cout<<ans<<endl;
}
}
ps:这道题实际和（活动 - AcWing）有点像，都是从前后缀合成的角度来考虑，本题的后缀好说，最关键就是想到前缀是可以拼凑的。这个题其实已经简化了，因为样例中把乘-1的情况给出来了，不然难点就是前缀乘-1了。