首先看一波题，考场瞬间自信，大概是用了二十分钟写了一个O(n^3)的暴力，然后没有写force对拍，然后就挂了
挂的原因具体就是我在调试的时候删了一行核心代码，然后还没与发现，然后还过了样例
思路大体上来讲就是暴力，但是担心40^4被卡，所以简单的优化了一下，我们先用n^2的时间跑一遍
对于每一个空地 ，我们先把它改为‘w’，然后判断途中是否有增加的五子
然后就是一个小的优化，对于每一次改变，我们不用全都搜一遍，因为一共只有八个方向，所以只用最多跑40个，现在的时间复杂度是o(n^2*320)，看起来是可以过了
然而还可以更优，对于每一个五子，我们只需要判断原来是否有超过五个，所以最多只用跑五个
然后我们就惊奇的发现时间复杂度降为了o(n^3);（5*8=40=n）
具体而言就是记录每个方向白子的个数，最后判断。
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n; struct node{ int y,x; }ans[100006]; bool cmp(const node a,const node b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int total=0; char map[46][46]; bool check(int i,int j){ map[i][j]='w'; int l=-1,r=-1,u=-1,d=-1,lu=-1,ld=-1,ru=-1,rd=-1,x=i,y=j,cnt=0; while(y<n&&map[x][y]=='w'&&r<=5) y++,r++; x=i,y=j; while(y>=0&&map[x][y]=='w'&&l<=5) y--,l++; x=i,y=j; while(x>=0&&map[x][y]=='w'&&u<=5) x--,u++; x=i,y=j; while(x<n&&map[x][y]=='w'&&d<=5) x++,d++; x=i,y=j; while(x>=0&&y>=0&&map[x][y]=='w'&&lu<=5) x--,y--,lu++; x=i,y=j; while(x<n&&y>=0&&map[x][y]=='w'&&ld<=5) x++,y--,ld++; x=i,y=j; while(x>=0&&y<n&&map[x][y]=='w'&&ru<=5) x--,y++,ru++; x=i,y=j; while(x<n&&y<n&&map[x][y]=='w'&&rd<=5) x++,y++,rd++; if(l==5&&r==5) cnt--; else if(l+r<=8&&l+r>=4) if(l!=5&&r!=5) cnt++; if(u==5&&d==5) cnt--; else if(u+d<=8&&u+d>=4) if(u!=5&&d!=5) cnt++; if(lu==5&&rd==5) cnt--; else if(lu+rd<=8&&lu+rd>=4) if(lu!=5&&rd!=5) cnt++; if(ld==5&&ru==5) cnt--; else if(ld+ru<=8&&ld+ru>=4) if(ld!=5&&ru!=5) cnt++; map[i][j]='*'; if(cnt>=1) return true; return false; } int main(){ //freopen("wuzi.in","r",stdin); //freopen("wuzi.out","w",stdout); n=rd(); for(int i=0;i<n;i++) scanf("%s",map[i]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(map[i][j]=='*') if(check(i,j)) ans[++total].y=j,ans[total].x=i; sort(ans+1,ans+total+1,cmp); for(int i=1;i<=total;i++) printf("%d %d ",ans[i].y,ans[i].x); return 0; }
当然，这道题还有一个o(n^2)的方法，我考场也想出来了，但是懒得写了（感谢他的题面）
给大家推荐一个大牛的博客：https://www.cnblogs.com/jason2003/p/9742264.html