首页 > 其他分享 >gym 102586 G. matrix inversions

gym 102586 G. matrix inversions

时间:2022-09-28 22:25:42浏览次数:35  
标签:check int gym 102586 305 sum2 inversions 对子 ll

考虑一个对子对 \(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

相关文章

  • gym.ActionWrapper使用时的注意点——step函数可以覆盖observation函数
    本文说的这个gym.ActionWrapper继承类的问题和gym.ObservationWrapper继承类的问题性质是一样的,具体看:gym.ObservationWrapper使用时的注意点——reset和step函数可以覆盖......
  • gym.ObservationWrapper使用时的注意点——reset和step函数可以覆盖observation函数
    记录一个刚学习到的gym使用的点,就是gym.ObservationWrapper使用时的注意点——reset和step函数可以覆盖observation函数。  给出代码:importgymclassWrapper(gy......
  • 【NEERC2011】【GYM100085F】Flights 题解
    【NEERC2011】【GYM100085F】Flights题意给定\(n\)个抛物线,保证开口向下且与\(x\)轴的两个交点都在\(x\)轴正半轴或原点。\(m\)次询问,每次询问给定四个数\(L,R,......
  • Gym103855 M(切比雪夫距离)
    M.ShortQuestion  题意:求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\min\left(\left|p_i-p_j\right|,\left|q_i-q_j\right|\right)\)的值  首先带上......
  • gym.error.NameNotFound: Environment PongNoFrameskip doesn't exist.
    解决办法经过多处搜索找到的解决办法!主要参考的是参考链接2。出现这种错误的主要原因是安装的gym不够全。我一开始下载gym库的时候输入的是pipinstallgym后来才知......
  • GYM100851 F - Froggy Ford(最短路铜牌题)
    题意:​ 现在有一条河,河中有n个石头,你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头,请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头......
  • 222怎么写一个自己的gym环境
    首先我按照遗传算法纯python写好了强化学习算法只要把这个移植到gym框架就好  主要看了这两个网址https://blog.csdn.net/weixin_44597347/article/details/12430......
  • gym-101667K Untangling Chain
    UntanglingChain构造显然对于一条线段来说,走到头只有左右两边可以选择,换句话说,第一次是横着走,第二次是竖着走,因此可以构造一个走法,让他每次都突破自身走过路径的四个边(......
  • H - Mr. Panda and Birthday Song Gym - 101775H
    题意:给你一个长度不大于1e6的字符串,由'a'-'z'或‘?’组成,且‘?’可转化为任意小写字母。和两个数x,y。现在有两个条件:字符串中存在任意一个长度为x的子串均为元音,或存在......
  • gym-101667E How Many to Be Happy
    HowManytoBeHappy?最小割因为是最小生成树,因此可以考虑对于一条边来说,他的左右两端的点视为处于两个不同的集合,然后只通过该边进行连接,这样最小生成树就必然会利用这......