【XX Open Cup GP of Tokyo G】Matrix Inversion

【XX Open Cup GP of Tokyo G】Matrix Inversion

Description

有一个\(n*n\)的矩阵，矩阵中\(1-n*n\)每个数恰好出现一次

给出其按行顺序排的序列的逆序对数\(X\)，以及按列的\(Y\)

构造出这个矩阵

Input

一行三个数\(n,X,Y\)

Output

有解输出Yes，然后输出构造的矩阵

无解输出No

Sample Input

3 8 13

Sample Output

Yes
1 3 4 
2 7 6 
9 8 5 

Data Constraint

\(1\le n\le 300\)

Solution

考虑按行排时，有两种点对，即左上至右下和右上至坐下

设为\(W,Z\)

那么\(W+Z=X,C-Z+W=Y\)（\(C\)为常数）

于是可以判定是否有解

记\(W\)的最大可能值为\(Wm\)，\(Z\)同理

通过归纳我们可以说明所有\(W\in[0,Wm],Z\in[0,Zm]\)的情况都是有解的

这可以通过一个更强的结论证明：

从小到大填数，对于当前没填数的格子

\((i,j)\)最小/最大，\((j,i)\)最小/最大（即双关键字排序）中

一定有一个可以使原来的条件仍满足并归纳下去（可以反证说明）

于是可以简单数据结构做到\(O(n^2\log^2n)\)

也可以精细实现做到\(O(n^2)\)

Code

#include<bits/stdc++.h>
using namespace std;
#define Fo(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 310

namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T>void read(T&x){
		x=0;char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b;}
	inline void pc(char x){*t++=x;if(t-b==sz)flush();}
	template<class T>void write(T x,char c=' '){
		if(x==0)pc('0');int t=0;
		for(;x;x/=10)p[++t]=x%10+'0';
		for(;t;--t)pc(p[t]);pc(c);
	}
	void write(const char *s){for(;*s;pc(*s++));}
	struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;

LL X,Y,Wm,Zm,W,Z;
int T,n,ans[N][N];
struct node{
	int x,y;
	node(int _x=0,int _y=0){x=_x;y=_y;}
}w1[N*N],w2[N*N];
struct tree{
	int s[N][N];
	int lowbit(int x){return -x&x;}
	void change(int x,int y,int v){
		for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j))s[i][j]+=v;
	}
	int query(int x,int y){
		int res=0;
		for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j))res+=s[i][j];
		return res;
	}
	int qur(int l1,int r1,int l2,int r2){
		return query(l2,r2)-query(l2,r1-1)-query(l1-1,r2)+query(l1-1,r1-1);
	}
}t;
vector<node>d;

bool check(int x,int y){
	LL tWm=Wm,tW=W,tZm=Zm,tZ=Z;
	int A=t.qur(1,1,x,y)-1,B=t.qur(x,y,n,n)-1;
	int C=t.qur(1,y+1,x-1,n),D=t.qur(x+1,1,n,y-1);
	tWm-=A+B;tZm-=C+D;tW-=A;tZ-=C;
	if(tW<0||tZ<0||tW>tWm||tZ>tZm)return 0;
	Wm=tWm;W=tW;Zm=tZm;Z=tZ;
	t.change(x,y,-1);
	return 1;
}

int main(){
	read(n);read(X);read(Y);
	Wm=Zm=0;
	Fo(i,1,n) Fo(j,1,n)Wm+=(n-i+1)*(n-j+1)-1,Zm+=(n-i)*(n-j);
	bool flag=1;
	if(X+Y-Zm&1)flag=0;
	W=(X+Y-Zm)/2;
	Z=X-W;
	if(W<0||Z<0||W>Wm||Z>Zm)flag=0;
	if(!flag){write("No\n");continue;}
	int tot=0;
	Fo(i,1,n) Fo(j,1,n)tot++,w1[tot]=(node){i,j},w2[tot]=(node){i,j};
	int l1=1,r1=n*n,l2=1,r2=n*n;
	memset(ans,0,sizeof(ans));
	memset(t.s,0,sizeof(t.s));
	Fo(i,1,n) Fo(j,1,n)t.change(i,j,1);
	Fo(i,1,n*n){
		while(ans[w1[l1].x][w1[l1].y])l1++;
		while(ans[w1[r1].x][w1[r1].y])r1--;
		while(ans[w2[l2].y][w2[l2].x])l2++;
		while(ans[w2[r2].y][w2[r2].x])r2--;
		if(check(w1[l1].x,w1[l1].y))ans[w1[l1].x][w1[l1].y]=i;
		else if(check(w1[r1].x,w1[r1].y))ans[w1[r1].x][w1[r1].y]=i;
		else if(check(w2[l2].y,w2[l2].x))ans[w2[l2].y][w2[l2].x]=i;
		else if(check(w2[r2].y,w2[r2].x))ans[w2[r2].y][w2[r2].x]=i;
	}
	write("Yes\n"); 
	Fo(i,1,n){
		Fo(j,1,n)write(ans[i][j]);
		write("\n");
	}
	return 0;
}

原文地址：http://www.cnblogs.com/AmanoKumiko/p/16886965.html