考虑一个对子对 \(A,B\) 的贡献,如果 \(x_1\le y_1,x_2\le y_2\) 的一对点会贡献 \(0,0\) 或 \(+1,+1\),\(x_1<x_2,y_1>y_2\) 会贡献 \(0,+1\) 或 \(+1,0\)。
设第一种对子最多 \(sum1\) 个,第二种最多 \(sum2\) 个。那么对 \(A+B\) 的奇偶性有限制。如果奇偶性满足,可以解除 \(+1,+1\) 的对子数和 \(+1,0\) 的对子数,这两个数如果在分别在 \([0,sum1],[0,sum2]\) 中就是能构造的(根据打表结果也是如此)。
已经会判 yes/no。考虑强行归纳构造。
从 \(1\sim n^2\) 一个一个塞数进去,枚举填哪个位置,填进去以后一些位置的大小关系会确定。假设此时第一种第二种对子未确定的还有 \(t1,t2\) 个,已经确定是 +1,+1 与 +1,0 的对子是 \(x1,x2\) 个,那判断 \(A\in [x1,x1+t1],B\in [x2,x2+t2]\),盲猜如果都满足就可以进入下一轮填数,写一下会发现挺对的。
但复杂度是 \(O(n^4)\) 的,考虑如何用 \(n^4\) 过掉 300!!!
要尽量降低 check 的次数,中间尝试过好几种乱搞方法,比如xjb排序什么的,下面只说一下比较有用的办法。
发现能卡掉各种乱搞的数据答案很有特性承认面向数据,很多 \(i,i+1\) 在位置上相邻,于是先枚举上一次填的位置周围的 8 个位置 check,如果都不行再 check \(n^2\) 个位置。
这样在出题人的数据里最多 check 只有 \(n^3\) 级别次的样子,加个树状数组就跑到了 500+ms。
官方题解写的是:把点按照 \((x,y),(y,x)\) 以及其反序排成4个序列,只需要 check 4 个点,也不知道正确性是为何。
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll unsigned int
using namespace std;
inline ll read()
{
char c=getchar();ll x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n;
ll sum1,sum2,xx,yy,x,y;
int a[305][305],s[305][305],len;
int tr[305][305];
void Add(int x,int y){
For(i,x,n)for(int j=y;j<=n;j+=j&-j)tr[i][j]++;
}
int Q(int x,int y){
int s=0;
for(;y;y^=y&-y)s+=tr[x][y];
return s;
}
int sum(int xl,int xr,int yl,int yr){
if(xl>xr||yl>yr)return 0;
return Q(xr,yr)-Q(xl-1,yr)-Q(xr,yl-1)+Q(xl-1,yl-1);
}
bool chk(int i,int j,int k){
ll d1=i*j-1-Q(i,j);
ll nx=x-d1;
ll ns1=sum1-((n-i+1)*(n-j+1)-1-sum(i,n,j,n))-d1;
if(nx<0||nx>ns1)return 0;
ll d2=(i-1)*(n-j)-sum(1,i-1,j+1,n);
ll ns2=sum2-((n-i)*(j-1)-(sum(i+1,n,1,j-1)))-d2;
ll ny=y-d2;
if(ny>=0&&ny<=ns2){
sum1=ns1,sum2=ns2,x=nx,y=ny;
a[i][j]=k;
Add(i,j);
return 1;
}
return 0;
}
bool vis[90005];
int Cnt,lstx=1,lsty=1;
int fa[90005];
int gf(int x){
while(x^fa[x])x=fa[x]=fa[fa[x]];
return x;
}
int id[305][305],cntfail;
void putin(int k){
int X=lstx,Y=lsty;
For(ii,X-1,X+1)
For(jj,Y-1,Y+1){
int i=(ii<=0?ii+n:ii); if(i>n)i-=n;
int j=(jj<=0?jj+n:jj); if(j>n)j-=n;
if(i>=1&&j>=1&&i<=n&&j<=n&& !a[i][j] && chk(i,j,k)){
lstx=i,lsty=j;
return;
}
}
++cntfail;
For(i,1,n)
For(j,1,n)
if(!a[i][j] && chk(i,j,k)){
lstx=i,lsty=j;
return;
}
assert(0);
}
signed main()
{
// freopen("my.out","w",stdout);
n=read(),x=read(),y=read();
For(i,1,n)
For(j,1,n){
sum1+=i*j-1;
sum2+=(i-1)*(j-1);
}
if((x+y+sum2)%2)puts("No"),exit(0);
xx=(x+y-sum2)/2;
yy=(x-y+sum2)/2;
// xx=0,yy=sum2;
if(xx<0||yy<0||xx>sum1||yy>sum2)puts("No"),exit(0);
puts("Yes");
// cout<<"X,Y "<<xx<<" "<<yy<<' '<<sum1<<" "<<sum2<<"\n";
x=xx,y=yy;
For(k,1,n*n)putin(k);
// cout<<"cnt: "<<cntfail; exit(0);
For(i,1,n)For(j,1,n)cout<<a[i][j]<<" \n"[j==n];
return 0;
}
标签:check,int,gym,102586,305,sum2,inversions,对子,ll
From: https://www.cnblogs.com/Rainbowsjy/p/16739755.html