C~F Java题解，代码已去除冗余~~~~
生成的字符串要么以0开头，要么以1开头，因此先简单交错排列01得到k个相邻，剩下在01则可以跟在某个01后边，时间复杂度O(Tn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int a=sc.nextInt(),b=sc.nextInt(),k=sc.nextInt();
List<Integer> ans=find(0,new int[]{a,b},k);
if(ans==null){
ans=find(1,new int[]{a,b},k);
}
if(ans==null){
System.out.println("-1");
}
else{
for(int c:ans){
System.out.print(c);
}
System.out.println();
}
}
}
static List<Integer> find(int start,int count[],int k){
List<Integer> ans=new ArrayList<>();
if(count[start]==0){
return null;
}
count[start]--;
ans.add(start);
int idx[]=new int[]{-1,-1};
idx[start]=0;
start^=1;
for(int i=0;i<k;i++,start^=1){
if(count[start]==0){
return null;
}
idx[start]=ans.size();
count[start]--;
ans.add(start);
}
for(int i=0;i<2;i++){
if(idx[i]==-1&&count[i]>0){
return null;
}
}
for(int i=0;i<count[start];i++){
ans.add(idx[start]+1,start);
idx[0]++;
idx[1]++;
}
for(int i=0;i<count[start^1];i++){
ans.add(idx[start^1]+1,start^1);
idx[start^1]++;
}
return ans;
}
}
记录最近的01下标，按照题意模拟即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt(),idx[]=new int[]{n,n};
String s=sc.next();
long ans[]=new long[n+1];
ans[n]=(long)1e18;
idx[s.charAt(n-1)-'0']=n-1;
for(int i=n-2;i>=0;i--){
int a=s.charAt(i)-'0';
ans[i]=Math.min(x+ans[idx[a]],y+ans[idx[a^1]]);
idx[a]=i;
}
System.out.println(ans[0]);
}
}
遍历字符串，求出每个字符为结尾的时候时，可以组成的对13取余数的方案数，最后出输出取余为0的答案，时间复杂度O(13n)
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length(),ans[]=new int[13];
ans[0]=1;
for(int i=0;i<n;i++){
char c=s.charAt(i);
int temp[]=new int[13];
for(int j=0;j<13;j++){
if(c=='0'){
temp[j*10%13]=(temp[j*10%13]+ans[j])%mod;
}
else if(c=='1'){
temp[(j*10+1)%13]=(temp[(j*10+1)%13]+ans[j])%mod;
}
else{
temp[j*10%13]=(temp[j*10%13]+ans[j])%mod;
temp[(j*10+1)%13]=(temp[(j*10+1)%13]+ans[j])%mod;
}
}
ans=temp;
}
System.out.println(ans[0]);
}
}
用延迟标记的线段树，动态开点会卡，指针型线段树也卡，因此需要将请求先离散化得到每个区间为左闭右开的，再用数组模拟树，再节点中需要记录奇偶下标中各自01个数，标记是否翻转，标记是否置位再下放信息时，先更新置位信息，再更新翻转信息，不可以颠倒顺序，时间复杂度(qlog(q))，本题对于Java的时限不合理，要优化数据结构的实现方式，懂原理即可
import java.util.*;
import java.io.*;
public class Main{
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 sto=new StringTokenizer(bf.readLine());
int n=Integer.parseInt(sto.nextToken()),q=Integer.parseInt(sto.nextToken()),query[][]=new int[q][],p=1,map[]=new int[q*2+5];
TreeSet<Integer> set=new TreeSet<>();
set.add(n+1);
for(int i=0;i<q;i++){
sto=new StringTokenizer(bf.readLine());
int op=Integer.parseInt(sto.nextToken()),l=Integer.parseInt(sto.nextToken()),r=Integer.parseInt(sto.nextToken());
set.add(l);
set.add(r+1);
query[i]=new int[]{op,l,r+1};
}
for(int a:set){
map[p++]=a;
}
SegTree st[]=new SegTree[(p<<2)+10];
st[1]=new SegTree(1,p-1);
build(st,1,map);
for(int a[]:query){
int l=get(map,a[1],p-1),r=get(map,a[2],p-1)-1;
if(a[0]==1){
setBit(st,1,l,r,map);
}
else if(a[0]==2){
revBit(st,1,l,r,map);
}
else{
int count[][]=find(st,1,l,r,map);
bw.write(String.valueOf(Math.min(count[0][0]+count[1][1],count[0][1]+count[1][0])));
bw.newLine();
}
}
bw.flush();
}
static int get(int map[],int a,int last){
int l=0,r=last;
while(l<r){
int mid=(l+r)>>1;
if(map[mid]<=a){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(map[r]<=a){
l=r;
}
break;
}
}
return l;
}
static void build(SegTree st[],int id,int map[]){
int l=st[id].l,r=st[id].r;
if(l==r){
coverAll(st[id],0,map);
}
else{
int mid=(l+r)>>1;
st[id<<1]=new SegTree(l,mid);
st[id<<1|1]=new SegTree(mid+1,r);
build(st,id<<1,map);
build(st,id<<1|1,map);
pushup(st,id);
}
}
static int[][] find(SegTree st[],int id,int a,int b,int map[]){
int l=st[id].l,r=st[id].r;
if(l==a&&r==b){
return st[id].count;
}
int mid=(l+r)>>1;
clear(st,id,map);
if(b<=mid){
return find(st,id<<1,a,b,map);
}
if(a>mid){
return find(st,id<<1|1,a,b,map);
}
int arr1[][]=find(st,id<<1,a,mid,map),arr2[][]=find(st,id<<1|1,mid+1,b,map),ans[][]=new int[2][2];
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans[i][j]=arr1[i][j]+arr2[i][j];
}
}
return ans;
}
static void setBit(SegTree st[],int id,int a,int b,int map[]){
int l=st[id].l,r=st[id].r;
if(l==a&&r==b){
st[id].cover=true;
st[id].rev=false;
coverAll(st[id],1,map);
}
else{
int mid=(l+r)>>1;
clear(st,id,map);
if(b<=mid){
setBit(st,id<<1,a,b,map);
}
else if(a>mid){
setBit(st,id<<1|1,a,b,map);
}
else{
setBit(st,id<<1,a,mid,map);
setBit(st,id<<1|1,mid+1,b,map);
}
pushup(st,id);
}
}
static void revBit(SegTree st[],int id,int a,int b,int map[]){
int l=st[id].l,r=st[id].r;
if(l==a&&r==b){
reverse(st[id]);
st[id].rev=!st[id].rev;
}
else{
clear(st,id,map);
int mid=(l+r)>>1;
if(b<=mid){
revBit(st,id<<1,a,b,map);
}
else if(a>mid){
revBit(st,id<<1|1,a,b,map);
}
else{
revBit(st,id<<1,a,mid,map);
revBit(st,id<<1|1,mid+1,b,map);
}
pushup(st,id);
}
}
static void clear(SegTree st[],int id,int map[]){
int l=st[id].l,r=st[id].r;
if(l==r){
return;
}
if(st[id].cover){
coverAll(st[id<<1],1,map);
coverAll(st[id<<1|1],1,map);
st[id<<1].rev=st[id<<1|1].rev=false;
st[id<<1].cover=st[id<<1|1].cover=true;
}
if(st[id].rev){
reverse(st[id<<1]);
reverse(st[id<<1|1]);
st[id<<1].rev=!st[id<<1].rev;
st[id<<1|1].rev=!st[id<<1|1].rev;
}
st[id].cover=st[id].rev=false;
}
static void pushup(SegTree st[],int id){
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
st[id].count[i][j]=st[id<<1].count[i][j]+st[id<<1|1].count[i][j];
}
}
}
static void reverse(SegTree st){
for(int i=0;i<2;i++){
st.count[i]=new int[]{st.count[i][1],st.count[i][0]};
}
}
static void coverAll(SegTree st,int a,int map[]){
//把st全部设为a
int l=map[st.l],r=map[st.r+1];
st.count=new int[2][2];
st.count[0][a]=l>r?0:(r-1)/2-(l-1)/2;
st.count[1][a]=l>r?0:r/2-l/2;
}
}
class SegTree{
int l,r,count[][]=new int[2][2];
boolean cover=false,rev=false;
SegTree(int l,int r){
this.l=l;
this.r=r;
}
}
另有bitset做法：
京公网安备 11010502036488号