傳送門
文章目錄
題意：
給你一個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。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=2010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-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(n
==1) return;for(int i
=1;i
<n
;i
++)if(!y
[i
]){swap(y
[i
],y
[n
]);ans
[++tot
]={2,i
,n
};for(int j
=1;j
<=n
;j
++) swap(a
[j
][i
],a
[j
][n
]);break;}for(int i
=1;i
<n
;i
++)if(x
[i
]){swap(x
[i
],x
[n
]);ans
[++tot
]={1,i
,n
};for(int j
=1;j
<=n
;j
++) swap(a
[i
][j
],a
[n
][j
]),y
[j
]-=a
[n
][j
];break;}dfs(n
-1);}int main()
{
scanf("%d",&n
);for(int i
=1;i
<=n
-1;i
++){int aa
,b
; scanf("%d%d",&aa
,&b
);x
[aa
]++; y
[b
]++;a
[aa
][b
]=1;}dfs(n
);cout
<<tot
<<endl
;for(int i
=1;i
<=tot
;i
++) printf("%d %d %d\n",ans
[i
].op
,ans
[i
].a
,ans
[i
].b
);return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #163 (Div. 2) C. Below the Diagonal 分治的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
