本文主要是介绍2024年广东省大学生程序设计竞赛暨广东省邀请赛-个人线上赛 D. 马（构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
题目详情 - 马 - HydroOJ
中国象棋规则，n*m的地图放k个马，使得任意两个马互相不能攻击
思路来源
乱搞ac
题解
三个三角形数之和一定能表示所有数（打表发现的）
输出一个矩形抠掉三个等腰直角三角形即可
原题的spj好像有点问题，自己搬了一下造了个交洛谷过了
代码
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e3+10,M=3e6+10;
int t,n,m,k,z[N];
array<int,3>now[M];
bool vis[M],swp;
vector<P>ans;
void init(){rep(i,0,1000)z[i]=i*(i+1)/2;rep(i,0,1000){rep(j,0,i){now[z[i]+z[j]]={i,j,0};vis[z[i]+z[j]]=1;}}rep(i,1,1000000){if(!vis[i]){for(int j=0;;j++){int v=z[j];if(i>=v && vis[i-v]){now[i]={now[i-v][0],now[i-v][1],j};break;}}}}
}
void check(){vector<vector<bool>>got(n+1,vector<bool>(m+1,0));for(auto &x:ans){got[x.fi][x.se]=true;}static int dx[]={1,1,-1,-1,2,2,-2,-2};static int dy[]={2,-2,2,-2,1,-1,1,-1};int cnt=0;for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(!got[i][j]) continue;cnt++;for(int d=0;d<8;d++) {int x=i+dx[d],y=j+dy[d];if(x<1||x>n||y<1||y>m||!got[x][y]) continue;int nx=i+dx[d]/2,ny=j+dy[d]/2;if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&got[nx][ny]) continue;if(got[x][y])assert(false);}}}if(cnt!=k)assert(false);
}
void out(){puts("YES");assert(SZ(ans)==k);check();for(auto &x:ans){if(swp)swap(x.fi,x.se);}sort(ans.begin(),ans.end());for(auto &x:ans){printf("%d %d\n",x.fi,x.se);}ans.clear();swp=0;
}
bool sol(){if(n>m)swap(n,m),swp=1;if(n<=2){rep(j,1,m){rep(i,1,n){if(SZ(ans)<k)ans.pb(P(i,j));else return 1;}}return 1;}rep(x,1,n){rep(y,x,m){int del=x*y-k;if(del<0)continue;int x1=now[del][0],x2=now[del][1],x3=now[del][2];assert(x1*(x1+1)/2 + x2*(x2+1)/2 + x3*(x3+1)/2 == del);if(x1<=x && x2<=x-(x==y) && x3<=min(y-x1,x-x2)){rep(i,1,x){rep(j,1,y){if(i+j<=1+x1)continue;if(i+j>=x+y-x2+1)continue;if(j-i>=y-x3)continue;ans.pb(P(i,j));}}return 1;}}}assert(false);return 0;
}
int main(){init();sci(t);while(t--){sci(n),sci(m),sci(k);sol();out();}return 0;
}这篇关于2024年广东省大学生程序设计竞赛暨广东省邀请赛-个人线上赛 D. 马（构造）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
