解析

本題的關鍵是暴力與構造結合的思想
本題一排排往上填的想法不難得出，但是在列數較小的時候就會GG
所以考慮在n>=5，m<5時，交換n，m，顯然問題還是等價的
如果nm均小于5，就直接暴力dfs解決
在最后的邊界需要打億個小表
還有一個特殊情況需要特判
3100豈是浪得虛名

代碼

#include<bits/stdc++.h> using namespace std; const int N=2e5+100; const int mod=1e9+7; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,k; vector<int>s[N]; int a[16][16],flag; void dfs(int x,int y){if(y>m){dfs(x+1,1);return;}if(x>n){int num(0);for(int i=1;i<n;i++){for(int j=1;j<m;j++){int cnt=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];if(cnt==3) num++;if(cnt==4) num+=4;}}if(num==k){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) putchar(a[i][j]||(k==0&&i==1&&j==1)?'*':'.');putchar('\n');}flag=1;}return;}a[x][y]=0;dfs(x,y+1);if(flag) return;a[x][y]=1;dfs(x,y+1);a[x][y]=0; } void bf(){dfs(1,1);if(!flag) printf("-1\n");putchar('\n');return; } void work1(){int x=m-5;//printf("k=%d\n",k);if(m==5){if(k==0){flag=1;return;}if(k==1){s[n][1]=1;flag=1;return;}if(k==2){s[n][1]=s[n][5]=1;flag=1;return;}if(k==3){s[n][1]=s[n][3]=1;flag=1;return;}if(k==4){s[n][2]=s[n][4]=1;flag=1;return;}if(k==5){s[n][1]=s[n][2]=1;flag=1;return;}if(k==6){s[n][1]=s[n][2]=s[n][5]=1;flag=1;return;}if(k==7){s[n][1]=s[n][2]=s[n][4]=1;flag=1;return;}if(k==8){flag=0;return;}if(k==9){s[n][1]=s[n][2]=s[n][3]=1;flag=1;return;}if(k==10){s[n][1]=s[n][2]=s[n][4]=s[n][5]=1;flag=1;return;}if(k==11){flag=0;return;}if(k==12){flag=0;return;}if(k==13){s[n][1]=s[n][2]=s[n][3]=s[n][4]=1;flag=1;return;}if(k==14){flag=0;return;}if(k==15){flag=0;return;}if(k==16){s[n][1]=s[n][3]=s[n][4]=s[n][5]=s[n][2]=1;flag=1;return;}flag=0;return;}else{if(k==0){flag=1;return;}if(k==1){s[n][m]=1;flag=1;return;}if(k==2){s[n][x+2]=1;flag=1;return;}if(k==3){s[n][x+2]=s[n][m]=1;flag=1;return;}if(k==4){s[n][x+2]=s[n][x+4]=1;flag=1;return;}if(k==5){s[n][x+1]=s[n][m]=1;flag=1;return;}if(k==6){s[n][x+1]=s[n][x+4]=1;flag=1;return;}if(k==7){s[n][x+2]=s[n][x+4]=s[n][x+5]=1;flag=1;return;}if(k==8){s[n][x+1]=s[n][x+2]=1;flag=1;return;}if(k==9){s[n][x+1]=s[n][x+2]=s[n][m]=1;flag=1;return;}if(k==10){s[n][x+1]=s[n][x+2]=s[n][x+4]=1;flag=1;return;}if(k==11){flag=0;return;}if(k==12){s[n][x+1]=s[n][x+2]=s[n][x+3]=1;flag=1;return;}if(k==13){s[n][x+1]=s[n][x+2]=s[n][x+4]=s[n][x+5]=1;flag=1;return;}if(k==14){flag=0;return;}if(k==15){flag=0;return;}if(k==16){s[n][x+1]=s[n][x+2]=s[n][x+3]=s[n][x+4]=1;flag=1;return;}if(k==19){s[n][x+1]=s[n][x+2]=s[n][x+3]=s[n][x+4]=s[n][x+5]=1;flag=1;return;}flag=0;return;} } void work2(int x,int y){flag=1;if(k==0) return;y--;//printf("k=%d\n",k);if(k==1){if(y<=m-2) s[x][m]=1;else s[x+1][1]=1;return;}if(k==2){if(y<=m-3) s[x][m-1]=1;else s[x+1][2]=1;return;}if(k==3){if(y<=m-4){s[x][y+2]=1;s[x][m]=1;}else if(y>=m-1){s[x+1][1]=s[x+1][3]=1;}else if(y<=1){s[x][3]=s[x][m]=1;}else if(y==m-2){s[x+1][2]=1;s[x][m]=1;}else{s[x+1][1]=1;s[x][m-1]=1;}return;} } int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifint T=read();int tim(0),f(0);while(T--){flag=0;n=read();m=read();k=read();++tim;//if(tim==1) f=n==12&&m==12&&k==400;//assert(n<5&&m<5);//++tim;//if(oo==100&&tim>=60) //if(f&&tim>=46) printf("%d %d %d\n",n,m,k);//if(f) continue;//if(oo==100) continue;if(n<5&&m<5){bf();continue;}bool jd(0);if(n>m) swap(n,m),jd=1;if(n==3&&k==8*(m-1)-8){if(!jd){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) putchar(j==m?'.':'*');putchar('\n');}}else{for(int j=1;j<=m;j++){for(int i=1;i<=n;i++) putchar(j==1?'.':'*');putchar('\n');}}putchar('\n');continue;}for(int i=1;i<=n;i++){s[i].clear();s[i].shrink_to_fit();s[i].resize(m+10);for(int j=1;j<=m;j++) s[i][j]=i==1;}for(int i=2;i<=n;i++){int o=0;for(int j=1;j<=m;j++){//printf("(%d %d) k=%d\n",i,j,k);if(i==n&&m-j+1<=5){o=1;work1();break;}if(k<4){o=1;work2(i,j);break;}s[i][j]=1;if(j==1) k-=1;else if(j==m) k-=3;else k-=4;}if(o) break;}if(!flag){printf("-1\n");putchar('\n');continue;}if(!jd){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) putchar(s[i][j]?'*':'.');putchar('\n');}}else{for(int j=1;j<=m;j++){for(int i=1;i<=n;i++) putchar(s[i][j]?'*':'.');putchar('\n');}}putchar('\n');}return 0; } /* */

總結

以上是生活随笔為你收集整理的CF720C Homework（构造）（暴力）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。