智能网站搭建,凡科商城怎么收费,为什么不自己做购物网站,怎么做阿里巴巴官网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个n∗nn*nn∗n的矩阵#xff0c;给你n−1n-1n−1个位置#xff0c;这些位置为111#xff0c;其他位置为000#xff0c;操作定义为交换两行或者交换两列#xff0c;让你通过不超过1e51e51e5次操作…传送门
文章目录题意思路题意
给你一个n∗nn*nn∗n的矩阵给你n−1n-1n−1个位置这些位置为111其他位置为000操作定义为交换两行或者交换两列让你通过不超过1e51e51e5次操作将所有为111的位置的都换到主对角线的下面。
思路
题目中说n−1n-1n−1个111的位置那么必定有一列全为000那么我们通过一次操作将这一列换到第nnn列之后在找任意一个有111的一行换到第nnn行让后递归处理(n−1)∗(n−1)(n-1)*(n-1)(n−1)∗(n−1)规模的矩阵即可。 操作次数为2∗n2*n2∗n。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N2010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int x[N],y[N],tot;
int a[N][N];
struct Node
{int op,a,b;
}ans[N*N];void dfs(int n)
{if(n1) return;for(int i1;in;i)if(!y[i]){swap(y[i],y[n]);ans[tot]{2,i,n};for(int j1;jn;j) swap(a[j][i],a[j][n]);break;}for(int i1;in;i)if(x[i]){swap(x[i],x[n]);ans[tot]{1,i,n};for(int j1;jn;j) swap(a[i][j],a[n][j]),y[j]-a[n][j];break;}dfs(n-1);}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in-1;i){int aa,b; scanf(%d%d,aa,b);x[aa]; y[b];a[aa][b]1;}dfs(n);couttotendl;for(int i1;itot;i) printf(%d %d %d\n,ans[i].op,ans[i].a,ans[i].b);return 0;
}
/**/
