C~G Java题解，代码已去除冗余~~~~
最终的字符串只有两种，而且只要从左到右一次判断当前的字符是否合法，之后再进行修改即可保证每个位置最多修改一次且不影响后边的前边的字符，时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int n=sc.nextInt(),ans=(int)1e9;
String s=sc.next();
for(int j=0;j<2;j++){
char c[]=s.toCharArray();
int count=0;
for(int k=n-1,p=j;k>0;k--,p^=1){
if(c[k]-'0'!=p){
c[k]=(char)(p+'0');
c[k-1]=(char)(((c[k-1]-'0')^1)+'0');
count++;
}
}
ans=Math.min(ans,n>1&&c[0]==c[1]?(int)1e9:count);
}
System.out.println(ans<1e9?ans:-1);
}
}
}
所得字符串必定是“1010”结构或者“0101”结构，直接构造两次前缀和后缀的最小修改即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),ans=(int)1e9,pre[][]=new int[n+1][2];
String s=sc.next();
for(int i=1;i<=n;i++){
pre[i]=pre[i-1].clone();
pre[i][s.charAt(i-1)-'0']++;
}
for(int a[]:new int[][]{{1,0,1,0},{0,1,0,1}}){
int left[]=new int[n+1];
left[2]=pre[1][a[0]]+pre[2][a[1]]-pre[1][a[1]];
for(int i=3;i<=n;i++){
left[i]=Math.min(left[i-1],pre[i-1][a[0]])+pre[i][a[1]]-pre[i-1][a[1]];
}
for(int i=n-1,min=pre[n][a[3]]-pre[n-1][a[3]]+pre[n-1][a[2]]-pre[n-2][a[2]];i>=3;min=Math.min(min,pre[n][a[3]]-pre[i-1][a[3]])+pre[i-1][a[2]]-pre[i-2][a[2]],i--){
ans=Math.min(ans,min+left[i-1]);
}
}
System.out.println(ans);
}
}
对于能够分割的完整“1”段来说，每一段可以由单个字符0来分隔，而长度为len的01段，其造成的贡献为len*(len-1)/2，因此这个题可以借助背包来预处理得到[1,2e5]范围内的需要的最短字符串总长度，之后直接输出，时间复杂度(C^1.5+T),C==2e5
import java.util.*;
public class Main{
static int pre[]=new int[200005];
static{
Arrays.fill(pre,(int)1e9);
pre[0]=0;
for(int i=1;i<=2e5;i++){
for(int j=1;j*(j-1)/2<=i;j++){
pre[i]=Math.min(pre[i],pre[i-j*(j-1)/2]+j);
}
}
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
System.out.println(pre[sc.nextInt()]-1);
}
}
}
上道题中在预处理的时候，需要记载一下更新的来源（也就是最后一段01段的长度），时间复杂度O((C^1.5+Tsqrt(k)),C==2e5)
import java.util.*;
public class Main{
static int pre[]=new int[200005],last[]=new int[200005];
static{
Arrays.fill(pre,(int)1e9);
pre[0]=0;
for(int i=1;i<=2e5;i++){
for(int j=1;j*(j-1)/2<=i;j++){
if(pre[i]>pre[i-j*(j-1)/2]+j){
pre[i]=pre[i-j*(j-1)/2]+j;
last[i]=j;
}
}
}
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i!=0;i--){
int k=sc.nextInt();
StringBuilder ans=new StringBuilder();
for(;k!=0;k-=last[k]*(last[k]-1)/2){
ans.append("0");
for(int j=last[k]-1;j!=0;j--){
ans.append("1");
}
}
System.out.println(ans.substring(1));
}
}
}
直接生成一个随机映射替换[1,2e5]内的数字，再构造1、2、3次方的前缀和高强度验证（具体看代码），时间复杂度O(C+n+q),C==2e5
import java.util.*;
import java.io.*;
public class Main{
static long rand[]=new long[200005],pre[][]=new long[200005][4];
static{
for(int i=1;i<=200000;i++){
rand[i]=(long)(Math.random()*1e9);
for(long j=1,k=rand[i];j<=3;j++,k*=rand[i]){
pre[i][(int)j]=pre[i-1][(int)j]+k;
}
}
}
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st=new StringTokenizer(bf.readLine());
int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken());
long hash[][]=new long[n+1][4];
st=new StringTokenizer(bf.readLine());
for(int i=1;i<=n;i++){
int a=Integer.parseInt(st.nextToken());
for(long j=1,k=rand[a];j<=3;j++,k*=rand[a]){
hash[i][(int)j]=hash[i-1][(int)j]+k;
}
}
for(;q>0;q--){
st=new StringTokenizer(bf.readLine());
int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken());
boolean ans=(r-l)%2==1;
for(int j=1;j<=3;j++){
ans&=hash[r][j]-hash[l-1][j]==pre[(r-l)/2+1][j]*2;
}
bw.write(ans?"Yes\n":"No\n");
}
bw.flush();
}
}
另有莫队解法，待续。。。。。
京公网安备 11010502036488号