C~F Java题解，代码已去除冗余~~~
特判一下s最后一个字符如果不是1，那么无解，因为数列本身一定是个排列；；否则每次遇到字符1，就把这个字符到上一个字符1中间的数字倒置，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String s=sc.next();
if(s.charAt(n-1)=='0'){
System.out.println(-1);
}
else{
List<Integer> ans=new ArrayList<>();
for(int i=1,last=0;i<=n;i++){
if(s.charAt(i-1)=='1'){
ans.add(i);
for(int j=last+1;j<i;j++){
ans.add(j);
}
last=i;
}
}
for(int a:ans){
System.out.print(a+" ");
}
}
}
}
利用前缀和分别计算字符0和字符1的个数，以及排列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();
long k=sc.nextLong(),pre[][]=new long[n+1][3];
String s=sc.next();
for(int i=1;i<=n;i++){
pre[i]=pre[i-1].clone();
pre[i][s.charAt(i-1)-'0']++;
if(s.charAt(i-1)=='1'){
pre[i][2]+=pre[i-1][0];
}
}
for(int i=0,j=0;i<n;i++){
while(j<=n&&find(i,j,pre)<k){
j++;
}
if(j<=n&&find(i,j,pre)==k){
System.out.println(i+1+" "+j);
return;
}
}
System.out.println("-1");
}
static long find(int l,int r,long pre[][]){
return pre[r][2]-pre[l][2]-pre[l][0]*(pre[r][1]-pre[l][1]);
}
}
构造的出的二分图中，两个集合中的点的度数和一定相同，那么可以利用01判断总度数一半的分割是否可以做到，并记录转移路线，最后配对儿输出，时间复杂度O(dn^2)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),d[]=new int[n+5],sum=0;
for(int i=1;i<=n;i++){
d[i]=sc.nextInt();
sum+=d[i];
}
if(sum%2==1){
System.out.println("-1");
}
else{
boolean has[]=new boolean[sum+1];
has[0]=true;
int last[]=new int[sum+1];
for(int i=1;i<=n;i++){
for(int j=sum;j>=d[i];j--){
if(!has[j]&&has[j-d[i]]){
last[j]=i;
has[j]=true;
}
}
}
if(!has[sum/2]){
System.out.println("-1");
}
else{
boolean chosen[]=new boolean[n+5];
for(int i=sum/2;i!=0;i-=d[last[i]]){
chosen[last[i]]=true;
}
System.out.println(sum/2);
for(int i=1,j=1;i<=n;i++){
if(chosen[i]){
while(true){
while(chosen[j]){
j++;
}
if(d[j]>=d[i]){
d[j]-=d[i];
for(int p=0;p<d[i];p++){
System.out.println(i+" "+j);
}
break;
}
else{
for(int p=0;p<d[j];p++){
System.out.println(i+" "+j);
}
d[i]-=d[j];
j++;
}
}
}
}
}
}
}
}
首先需要按照区间大小排序，并构造好最短区间的排列方式；；从第二个区间开始，需要枚举左边新区间的0的个数，以及在此情况下的新增01排列的范围，再讲左右新区间的内的数字以先1后0的方式排好（这样对应的是最少新增），再按照配比个数的方式分别重排逐步完成新增的01数，时间复杂度O(n+m)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),ans[]=new int[n];
long arr[][]=new long[m][];
for(int i=0;i<m;i++){
arr[i]=new long[]{sc.nextInt()-1,sc.nextInt()-1,sc.nextInt(),sc.nextInt(),sc.nextLong()};
}
Arrays.sort(arr,(a,b)->Long.compare(a[1]-a[0],b[1]-b[0]));
for(int i=m-1;i>0;i--){
for(int j=2;j<5;j++){
arr[i][j]-=arr[i-1][j];
}
}
if(!generate1(arr[0],ans)){
System.out.println("-1");
}
else{
int preL=(int)arr[0][0],preR=(int)arr[0][1],preX=(int)arr[0][2],preY=(int)arr[0][3];
for(int i=1;i<m;i++){
if(!generate2(arr[i],ans,preX,preY,preL,preR)){
System.out.println("-1");
return;
}
preL=(int)arr[i][0];
preR=(int)arr[i][1];
preX+=(int)arr[i][2];
preY+=(int)arr[i][3];
}
for(int a:ans){
System.out.print(a);
}
}
}
static boolean generate2(long arr[],int ans[],int preX,int preY,int preL,int preR){
int l=(int)arr[0],x=(int)arr[2],y=(int)arr[3];
long k=arr[4];
for(int i=0;i<=x&&i<=preL-l;i++){
int xl=i,yl=preL-l-i,xr=x-xl,yr=y-yl;
if(yl<=y&&k>=(long)xl*(preY+yr)+(long)yr*preX&&k<=(long)xl*(y+preY)+(long)yr*(preX+xr)){
k-=(long)xl*(preY+yr)+(long)yr*preX;
for(int j=l;j<l+yl;j++){
ans[j]=1;
}
for(int j=l+yl-1;k!=0&&j>=l;j--){
if(k>=xl){
ans[j]=0;
ans[j+xl]=1;
k-=xl;
}
else{
ans[j]=0;
ans[j+(int)k]=1;
k=0;
}
}
for(int j=preR+1;j<=preR+yr;j++){
ans[j]=1;
}
for(int j=preR+yr;k!=0;j--){
if(k>=xr){
ans[j]=0;
ans[j+xr]=1;
k-=xr;
}
else{
ans[j]=0;
ans[j+(int)k]=1;
k=0;
}
}
return true;
}
}
return false;
}
static boolean generate1(long arr[],int ans[]){
int l=(int)arr[0],x=(int)arr[2],y=(int)arr[3];
long k=arr[4];
if(k>(long)x*y){
return false;
}
for(int i=0;i<y;i++){
ans[l+i]=1;
}
for(int i=l+y-1;i>=l&&k!=0;i--){
if(k>=x){
ans[i]=0;
ans[i+x]=1;
k-=x;
}
else{
ans[i]=0;
ans[i+(int)k]=1;
break;
}
}
return true;
}
}
京公网安备 11010502036488号