题解：P14745 [ICPC 2021 Seoul R] Trio

· · 题解

题意清晰，不再累述。

分析

乍一看，好像无从下手，我们先打个暴力。

具体怎么做呢？我们可以先预处理，将每个数的千、百、十、个位数字提取出来，存储为数组，方便后续访问。再三重循环，枚举每一种的可能，依次判断是否可以组成三元组。

code:

#include<bits/stdc++.h>
using namespace std;
int n,v[2009][5],ans;
bool check1(int a,int b,int c,int i){//判断第 i 位
    int x=v[a][i],y=v[b][i],z=v[c][i];
    if(x==y&&y==z)return 1;
    else if(x!=y&&x!=z&&z!=y)return 1;
    return 0;
}
bool check(int a,int b,int c){
    for(int i=0;i<=4;i++){//逐位判断
        if(!check1(a,b,c,i))return 0;
    }return 1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v[i][0]=x%10;
        v[i][1]=x/10%10;
        v[i][2]=x/100%10;
        v[i][3]=x/1000;
        //提取每一位的数
    }for(int i=1;i<n-1;i++){//枚举
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<=n;k++){
                if(check(i,j,k)){
                    ans++;
                }
            }
        }
    }cout<<ans;
    return 0;
}

勉强卡过前十二个测试点。

再优，，我们的输入输出似乎浪费了很多时间，而且调用函数也浪费了点时间，将输入输出改成快读快写，将判断函数拉出来。

code:

#include<bits/stdc++.h>
using namespace std;
int n,v[2009][5],ans;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }return x*f;
}inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)print(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        v[i][0]=x%10;
        v[i][1]=x/10%10;
        v[i][2]=x/100%10;
        v[i][3]=x/1000;
    }for(int i=1;i<n-1;i++){
        int i0=v[i][0],i1=v[i][1],i2=v[i][2],i3=v[i][3];
        for(int j=i+1;j<n;j++){
            int j0=v[j][0],j1=v[j][1],j2=v[j][2],j3=v[j][3];
            for(int k=j+1;k<=n;k++){
                int k0=v[k][0],k1=v[k][1],k2=v[k][2],k3=v[k][3];
                bool f0=(i0==j0&&j0==k0)||(i0!=j0&&i0!=k0&&j0!=k0),f1=(i1==j1&&j1==k1)||(i1!=j1&&i1!=k1&&j1!=k1),f2=(i2==j2&&j2==k2)||(i2!=j2&&i2!=k2&&j2!=k2),f3=(i3==j3&&j3==k3)||(i3!=j3&&i3!=k3&&j3!=k3);
                if(f1&&f2&&f3&&f0)ans++;
            }
        }
    }print(ans);
    return 0;
}

勉强卡过前十五个测试点。

好像没法再优化了？我伤心的打起来正解。

我们可以先看看数据大小，1 \le n \le 2000，我们便可以大胆的猜测，这道题要用 O(n^2) 的做法通过。

我们可以先枚举确定前两个数，再用前两个数查找满足条件的第三个数，具体怎么查找呢？我们一位一位的，若前两个数的第 k 位相同，那么查找与之相同数位的相同数有几个相加即可。若前两个数的第 k 位不同，就用所有情况减去两数该位数字的情况。

这时有同学可能就会问：那查找情况的时候不是也要用 O(n) 的复杂度？那怎么变成 O(n^2) 的时间？其实我们可以在输入的时候提前预处理查找的个数，这样就可以将 O(n) 转化为 O(1) 的复杂度。从而将整体的 O(n^3) 的复杂度优化到 O(n^2)。

ACcode:

#include<bits/stdc++.h>
using namespace std;
int n,v[2009][5],t[19][19][19][19],ans,f[9];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }return x*f;
}inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)print(x/10);
    putchar(x%10+'0');
}inline int find(int i,int x[],int y[],int z[]){//查找第三个数的情况
    int num=0;
    if(i==4)num+=t[z[0]][z[1]][z[2]][z[3]];//递归出口
    else if(x[i]==y[i])z[i]=x[i],num+=find(i+1,x,y,z);//相同的情况
    else{//反之，不同的情况
        z[i]=0,num+=find(i+1,x,y,z);
        z[i]=x[i],num-=find(i+1,x,y,z);
        z[i]=y[i],num-=find(i+1,x,y,z);
    }return num; 
} 
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        v[i][0]=x%10;
        v[i][1]=x/10%10;
        v[i][2]=x/100%10;
        v[i][3]=x/1000;
        //提取位数
        for(int j0=0;j0<2;j0++){//预处理，每位有相同和不同两种，共十六种。
            for(int j1=0;j1<2;j1++){
                for(int j2=0;j2<2;j2++){
                    for(int j3=0;j3<2;j3++){
                        t[j0*v[i][0]][j1*v[i][1]][j2*v[i][2]][j3*v[i][3]]++;
                    }
                }
            }
        }
    }for(int i=1;i<=n;i++){//枚举前两个数
        for(int j=i+1;j<=n;j++){
            ans+=find(0,v[i],v[j],f);//查找第三个数
        }
    }print(ans/3);//由于答案有重复，去重。
    return 0;
}