2023牛客暑期多校訓練營9-J Puzzle: Star Battle

https://ac.nowcoder.com/acm/contest/57363/J

題意

解題思路

出題人都說是詐騙題（，可以發現滿足每行每列恰好有$n$個星星只有兩種方案，分別是：


判斷這兩種情況是否滿足區域要求即可。

代碼

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2000;
int a[N][N],n,c[N],d[N];
vector<pair<int,int>>v[2];
int main(){cin>>n;for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++){v[0].pb({2*i-(j<=n),2*j-(i>n)});v[1].pb({2*i-(j>n),2*j-(i<=n)});}for(int i=1;i<=4*n;i++)for(int j=1;j<=4*n;j++)cin>>a[i][j];for(auto x:v[0]){c[a[x.first][x.second]]++;}for(auto x:v[1]){d[a[x.first][x.second]]++;}int f=0;for(int i=1;i<=4*n;i++){if(c[i]!=n){f=1;break;}}if(!f){puts("Yes");for(auto x:v[0]){cout<<x.first<<' '<<x.second<<'\n';}return 0;}for(int i=1;i<=4*n;i++){if(d[i]!=n){f=0;break;}}if(f){puts("Yes");for(auto x:v[1]){cout<<x.first<<' '<<x.second<<'\n';}}else puts("No");
}