洛谷P1219、P1784、P11229三题的题解

因为八个皇后位置之间相互制约，所以肯定得记录每个皇后的位置。
我们可以枚举每一个格子的位置，再看它的列、对角线是否与其他皇后相等。（dfs传进的参数为行号，不会相重）

#include<bits/stdc++.h>usingnamespacestd;intn,a[15],cnt;boolc[15],d1[30],d2[30];boolcheck(intr,inti){return!c[i]&&!d1[r-i+n]&&!d2[r+i];}voiddfs(intr){if(r==n){cnt++;if(cnt<=3){for(inti=0;i<n;i++){cout<<a[i]+1<<" ";}cout<<endl;}return;}for(inti=0;i<n;i++){if(check(r,i)){//放a[r]=i;c[i]=d1[r-i+n]=d2[r+i]=true;dfs(r+1);//回溯a[r]=0;c[i]=d1[r-i+n]=d2[r+i]=false;}}}intmain(){cin>>n;dfs(0);cout<<cnt;return0;}

此题和上一题解法类似，但是做标记的方式需改变。
规则：每一行、每一列数字不能重复。但是这样下去范围依然比较大，怎么办呢？
我们知道，一个九宫格可以分成九个“三宫格”，而这个“三宫格”里面的数字是不能重复的，所以就诞生了一个数组box,对于第i行j列的数字有box[i/3][j/3][a[i][j]]为1。

using namespace std; int a[9][9]; bool row[9][10],col[9][10],box[3][3][10]; vector<pair<int,int>> b; bool check(int r,int c,int i) { return !row[r][i]&&!col[c][i]&&!box[r/3][c/3][i]; } void dfs(int idx) { if(idx==(int)b.size()) { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { cout<<a[i][j]<<" "; } cout<<endl; } exit(0); } int r=b[idx].first; int c=b[idx].second; for(int i=1;i<=9;i++) { if(check(r,c,i)) { a[r][c]=i; row[r][i]=col[c][i]=box[r/3][c/3][i]=true; dfs(idx+1); row[r][i]=col[c][i]=box[r/3][c/3][i]=false; } } } int main() { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { cin>>a[i][j]; if(a[i][j]!=0) { row[i][a[i][j]]=true; col[j][a[i][j]]=true; box[i/3][j/3][a[i][j]]=true; } else b.push_back({i,j}); } } dfs(0); return 0; }

首先我看见这题的第一想法是尽量的多去拼8，因为它需要的木棍数最多，直接7个if判断余数，最后输出一/两个数字加一堆8。
但是这不是最优解，细心推导我们还会发现如果退回去一个或两个8能创造更小的数（自己尝试时试3个就行了，越往后其他数字拼起的位数越多）。

接着照着这张图写一堆if就行了。

#include<bits/stdc++.h>usingnamespacestd;intt;intmain(){cin>>t;while(t--){intn;cin>>n;if(n%7==0){for(inti=1;i<=n/7;i++)cout<<8;cout<<endl;}elseif(n%7==1){if(n==1){cout<<-1<<endl;continue;}cout<<10;for(inti=1;i<=n/7-1;i++)cout<<8;cout<<endl;}elseif(n%7==2){cout<<1;for(inti=1;i<=n/7;i++)cout<<8;cout<<endl;}elseif(n%7==3){if(n==3){cout<<7<<endl;continue;}intx=n/7;if(x==1)cout<<22<<endl;else{x-=2;cout<<200;for(inti=1;i<=x;i++)cout<<8;cout<<endl;}}elseif(n%7==4){if(n==4){cout<<4<<endl;continue;}cout<<20;for(inti=1;i<n/7;i++)cout<<8;cout<<endl;}elseif(n%7==5){cout<<2;for(inti=1;i<=n/7;i++)cout<<8;cout<<endl;}elseif(n%7==6){cout<<6;if(n==6){cout<<endl;continue;}for(inti=1;i<=n/7;i++)cout<<8;cout<<endl;}}return0;}