C~F Java题解，代码已去除冗余~~~
首先翻转的区间如果在同一行，上下的大小关系不变，因此是平衡的；而如果相差行数不小于2，大小关系必然破坏，是不平衡的；如果翻转区间在相邻两行，为了使得大小关系不被破坏，只需要上下两行的区间在行内位次上互不重叠即可，时间复杂度TlogC，其中C==1e9
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--){
long n=sc.nextInt(),l[]=find(sc.nextLong()),r[]=find(sc.nextLong());
System.out.println(l[0]==r[0]||r[0]-l[0]==1&&l[1]>r[1]?"Yes":"No");
}
}
static long[] find(long p){
long l=1,r=(int)1e9;
while(l<r){
long mid=(l+r)>>1;
if(mid*(mid+1)/2>=p){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(l*(l+1)/2>=p){
r=l;
}
break;
}
}
return new long[]{r,p-r*(r-1)/2};
}
}
贪心地填充每一行，在填充的时候，尽量填充比依靠自己的两个上一行麻将都不轻的重量，选择这样的最轻的那个来填充，直到无法再次填充，时间复杂度O(Tnlogn)
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=1;
Queue<Integer> q[]=new Queue[n];
for(int j=0;j<n;j++){
q[j]=new PriorityQueue<>();
for(int k=0;k<n;k++){
q[j].add(sc.nextInt());
}
}
List<Integer> list=new ArrayList<>();
list.add(q[0].poll());
for(int j=1;j<n;j++){
List<Integer> cur=new ArrayList<>();
while(!q[j].isEmpty()&&q[j].peek()<list.get(0)){
q[j].poll();
}
if(q[j].isEmpty()){
break;
}
cur.add(q[j].poll());
boolean ok=true;
for(int k=1;k<j;k++){
int max=Math.max(list.get(k),list.get(k-1));
while(!q[j].isEmpty()&&q[j].peek()<max){
q[j].poll();
}
if(q[j].isEmpty()){
ok=false;
break;
}
cur.add(q[j].poll());
}
if(ok){
while(!q[j].isEmpty()&&q[j].peek()<list.get(j-1)){
q[j].poll();
}
if(q[j].isEmpty()){
break;
}
cur.add(q[j].poll());
}
else{
break;
}
list=cur;
ans++;
}
System.out.println(ans);
}
}
}
首先需要判断最基本的形态么也就是最少需要的麻将重量之和，也就是第一行1个，第二行2个，直到第n行个，如果k小于这个总和，那么无解；此时需要若干次将某些底层行全部加1，这个问题是一个完全背包问题，时间复杂度O(nk)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt();
if(n*(n+1)*(n*2+1)/6>k){
System.out.println(-1);
}
else{
k-=n*(n+1)*(n*2+1)/6;
int last[][]=new int[k+5][];
boolean has[]=new boolean[k+5];
has[0]=true;
for(int i=n;i!=0;i--){
int s=(n+i)*(n-i+1)/2;
for(int j=s;j<=k;j++){
if(!has[j]&&has[j-s]){
has[j]=true;
last[j]=new int[]{j-s,i};
}
}
}
if(!has[k]){
System.out.println(-1);
}
else{
int ans[]=new int[n+5];
for(int i=k;i!=0;i=last[i][0]){
ans[last[i][1]]++;
}
for(int i=1;i<=n;i++){
System.out.print(i+(ans[i]+=ans[i-1])+" ");
}
}
}
}
}
将n行的麻将序列化为n个数组，那么每次推到麻将，按照行来进行合并内部区间，其构成的单独影响就是消去一个以其为底边的直角三角形，那么对于更靠下的边的影响，可以分解为两层之间的影响，再把三角形上部的影响转存到第一层的位置，时间复杂度O(能过)
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--){
sc.next();
TreeMap<Long,List<long[]>> map=new TreeMap<>();
map.put(0L,new ArrayList<>());
for(int j=sc.nextInt();j!=0;j--){
long a[]=find(sc.nextLong());
map.putIfAbsent(a[0],new ArrayList<>());
map.get(a[0]).add(new long[]{a[1],a[1]});
}
long ans=0;
for(Long j=map.lastKey();j>0;j=map.lowerKey(j)){
Long next=map.lowerKey(j);
List<long[]> list1=merge(map.get(j)),list2=map.get(next);
for(long a[]:list1){
if(a[1]-a[0]+1<=j-next){
ans+=(a[1]-a[0]+1)*(a[1]-a[0]+2)/2;
}
else{
ans+=((a[1]-a[0]+1)*(a[1]-a[0]+2)-(a[1]-a[0]+1-(j-next))*(a[1]-a[0]+2-(j-next)))/2;
list2.add(new long[]{a[0],a[1]-(j-next)});
}
}
}
System.out.println(ans);
}
}
static List<long[]> merge(List<long[]> list){
List<long[]> ans=new ArrayList<>();
Collections.sort(list,(a,b)->Long.compare(a[0],b[0]));
ans.add(list.get(0));
for(int i=1;i<list.size();i++){
long a[]=list.get(i);
if(a[0]>ans.get(ans.size()-1)[1]+1){
ans.add(a);
}
else{
ans.get(ans.size()-1)[1]=Math.max(ans.get(ans.size()-1)[1],a[1]);
}
}
return ans;
}
static long[] find(long p){
long l=1,r=(int)1e9;
while(l<r){
long mid=(l+r)>>1;
if(mid*(mid+1)/2>=p){
r=mid;
}
else{
l=mid+1;
}
if(l==r-1){
if(l*(l+1)/2>=p){
r=l;
}
break;
}
}
return new long[]{r,p-r*(r-1)/2};
}
}
京公网安备 11010502036488号