Below the Diagonal CodeForces - 266C
2021/8/27 6:06:09
本文主要是介绍Below the Diagonal CodeForces - 266C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:思维
错误思路:
暴力模拟,但是步骤没有统一的规矩.
思路:
递归思想.因为需要将每个棋子放在主对角线以下.那么首先保证最后一列无\(1\),那么再交换有\(1\)的行和最后一行,这样怎么也不会换到对角线上.然后可以发现最后一行,最后一列可以去掉,再重复上面的步骤
Code
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef pair<int,int> PII; const int N = 1010; int n,row[N],col[N],mp[N][N],cnt; int ans[N*100][3]; void solve(int n) { if(n==1) return; for(int i=1;i<n;i++) if(!col[i]) { //交换列 ans[++cnt][0] = 2; ans[cnt][1] = i; ans[cnt][2] = n; for(int j=1;j<=n;j++) swap(mp[j][i],mp[j][n]); swap(col[i],col[n]); break; } //获取空白列 for(int i=1;i<n;i++) if(row[i]) { //交换i与n行 ans[++cnt][0] = 1; ans[cnt][1] = i,ans[cnt][2] = n; for(int j=1;j<=n;j++) swap(mp[i][j],mp[n][j]) ; swap(row[i],row[n]); break; } for(int i=1;i<=n;i++) if(mp[n][i]) { col[i]--; } solve(n-1); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); row[x]++,col[y]++; mp[x][y]++; } solve(n); printf("%d\n",cnt); for(int i=1;i<=cnt;i++) { for(int j=0;j<3;j++) printf("%d ",ans[i][j]); printf("\n"); } return 0; }
这篇关于Below the Diagonal CodeForces - 266C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26解决google chrome helper 内存占用较高!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb