P6316 [COCI2006-2007#3] TROJKE 题解

Soul_direction · 2023-08-12 10:32:05 · 题解

Link

听说博客食用更佳呦

题目概要：

有一个 n \times n 的方格，每个格子都有一个大写字母或为空，方格中不会出现重复字母。求方格上一条线穿过 3 个字母的线，有几条。

主要思路：

首先可以看到，这道题数据范围很小，3 \le n \le 100，所以构思暴力算法，时间复杂度为 O((n^2)^3)，即 O(n^6)，n 最大为 100，最大运算量达到了 1*10^{12}，老师说过，1*10^{8} 是极限，显然，暴力无法通过此题。

再次观察，你会发现，题目保证不会重复字母，也就是说，我们可以枚举字母，时间复杂度也是常数级别，根本不会超时。

代码提要：

核心代码推导：

那如何判断三点一线呢？祭出我们的斜度公式：

但是斜率有可能是无穷大，也就是垂直于横轴，所以我们利用比的性质，得到了以下公式：

也就是这样：

这样判断函数就落成了：

bool cmp(direction a,direction b){
    return a.x<b.x;
}
bool QAQ(int i,int j,int k){
    x[1].x=a[i].x;x[1].y=a[i].y;
    x[2].x=a[j].x;x[2].y=a[j].y;
    x[3].x=a[k].x;x[3].y=a[k].y;
    sort(x+1,x+3+1,cmp);
    return (x[2].x-x[1].x)*(x[3].y-x[2].y)==(x[3].x-x[2].x)*(x[2].y-x[1].y);
}

核心代码注解：

请注意，这里的枚举并不那保证 x 的升序排列，所以用到了 sort 进行排序。

AC code：

#include <iostream>
#include <algorithm>
#include <string>
#define maxn 110
#define inf 2147483647
using namespace std;
struct direction{//定义一个坐标系结构图
    int x,y;
}a[27],x[4];
inline int read(){//快读
    int x=0,f; char ch=0;
    while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void print(int x){//快写
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
bool cmp(direction a,direction b){
    return a.x<b.x;
}
bool QAQ(int i,int j,int k){//核心判断函数（不要在意这个函数名）
    x[1].x=a[i].x;x[1].y=a[i].y;
    x[2].x=a[j].x;x[2].y=a[j].y;
    x[3].x=a[k].x;x[3].y=a[k].y;
    sort(x+1,x+3+1,cmp);
    return (x[2].x-x[1].x)*(x[3].y-x[2].y)==(x[3].x-x[2].x)*(x[2].y-x[1].y);
}
int main(){
    int n,ans=0;
    char ch;
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>ch;
            if(ch!='.'){
                a[ch-'@']={i,j};//'@'的ascll码是64，所有字母的ascll减去'@'就刚好等于1~26
            }
        }
    }
    for(int i=1;i<=26;i++){
        if(!a[i].x)continue;
        for(int j=i+1;j<=26;j++){//切记j=i+1，负责会多次对一个点枚举，导致错误
            if(!a[j].x)continue;
            for(int k=j+1;k<=26;k++){
                if(a[k].x&&QAQ(i,j,k))ans++;
            }
        }
    }
    write(ans);
    return 0;//完结撒花~
}