锐客网

  1. 首页 > it技术 > >

[USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解

优雅的暴力。
设三个点为 \((i,j,k)\)，则有 \(6\) 个未知数即 \(x_i,x_j,x_k,y_i,y_j,y_k\)。又因为有 \(2\) 条关于这 \(6\) 个未知数的方程 \(ij=jk,ij=ik\)，所以一定能通过枚举其中的 \(4\) 个量来求解，时间复杂度 \(O(n^4)\)。
而这个 \(O(n^4)\) 的暴力是肉眼可见的跑不满（
考虑先枚举点 \(i\)，则有以下四种情况：
[USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解
文章图片

解得 \(x=a,y=a-b\)。
其中，\(a,x>0,0\le b,y \le a\)。
[USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解
文章图片

解得 \(x=a,y=a-b\)。
其中，其中，\(a,x>0,0\le b,y\le a,\color{red}b\not= 0\)。
[USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解
文章图片

解得 \(x=2b-a,y=b-a\)。
其中，\(0\le a [USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解
文章图片

解得 \(x=2b-a,y=b-a\)。
其中，\(0\le a 注意，有些同时存在于两种情况的状态， 需要通过标红的判断去除。
然后就能敲出以下代码：

#include using namespace std; const int maxn=310; inline int read(){ int x=0; char c=getchar(); for(; (c^'.')&&(c^'*'); c=getchar()); return c=='*'; } bool c[maxn][maxn]; int n,ans; int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) c[i][j]=read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){ if(!c[i][j]) continue; for(int a=0; a<=n; a++){ for(int b=0; b<=a; b++){ if(a&&i+a<=n&&j+a<=n&&i-a+b>0&&j+a+b<=n) ans+=(c[i+a][j+a]&c[i-a+b][j+a+b]); if(a&&b&&i-a>0&&j+a<=n&&i+a-b<=n&&j+a+b<=n) ans+=(c[i-a][j+a]&c[i+a-b][j+a+b]); } for(int b=a+1; b<=n; b++){ if(i-b-b+a>0&&j+a<=n&&i-b+a>0&&j+a+b<=n) ans+=(c[i-b-b+a][j+a]&c[i-b+a][j+a+b]); if(a&&i+b+b-a<=n&&j+a<=n&&i+b-a<=n&&j+a+b<=n) ans+=(c[i+b+b-a][j+a]&c[i+b-a][j+a+b]); } } } printf("%d\n",ans); return 0; }

【[USACO20FEB]Equilateral|[USACO20FEB]Equilateral Triangles P 题解】然后你会获得 \(51pt\) 的高分。
容易发现，代码中搜索到了许多冗余的状态，考虑将判断放到循环之外：
#include using namespace std; const int maxn=310; inline int read(){ int x=0; char c=getchar(); for(; (c^'.')&&(c^'*'); c=getchar()); return c=='*'; } bool c[maxn][maxn]; int n,ans; int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) c[i][j]=read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){ if(!c[i][j]) continue; for(int a=0; a<=n; a++){ if(a&&i+a<=n&&j+a<=n) for(int b=max(a-i+1,0); b<=a&&j+a+b<=n; b++) ans+=(c[i+a][j+a]&c[i-a+b][j+a+b]); if(a&&i-a>0&&j+a<=n) for(int b=max(i+a-n,1); b<=a&&b<=n-j-a; b++) ans+=(c[i-a][j+a]&c[i+a-b][j+a+b]); if(j+a<=n) for(int b=a+1; j+a+b<=n&&b+b

然后就过了。
祝AC。

    推荐阅读


    上一篇：初识——HTTP3

    下一篇：JVM垃圾回收阅读笔记