P10996 【MX-J3-T3】Tuple

jjy2023 · 2024-08-25 20:00:13 · 题解

P10996 【MX-J3-T3】Tuple

比赛时只想出 68 分算法，~挠破头想了一个小时，卡常也没卡过去~，赛后看官方题解竟如此清爽，当场给我整麻了。

68 分做法：

用一个 set 加上 tuple 来存储三元组，再枚举第四个数。时间复杂度为 O(nm\log m)。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
set<tuple<int,int,int>> s;
set<pair<int,int>> s1,s2,s3;//我也不知道这一段什么意思，但加上速度会变快
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;++i)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        s.insert(make_tuple(x,y,z));
        s1.insert({x,y});
        s2.insert({x,z});
        s3.insert({y,z});
    }
    for(const auto&i:s)
        for(register int j=4;j<=n;++j)
        {
            int x=get<0>(i),y=get<1>(i),z=get<2>(i);
            if(s.count({x,y,j})&&s.count({x,z,j})&&s.count({y,z,j})) ans++;
        }
    printf("%d",ans);
    return 0;
}

100 分算法：

先枚举第一个数 a，用一个二维数组 f 来维护 (a,b,c) 是否存在。再枚举 (b,c,d)，若 f_{b,c},f_{b,d},f_{c,d} 都存在，那么 (a,b,c,d) 也存在。时间复杂度为 O(nm)。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,m,b[50005],c[50005],d[50005],ans=0;
bool f[2005][2005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i],&c[i],&d[i]);
    for(int a=1;a<=n;a++)
    {
        for(int i=1;i<=m;i++)
            if(b[i]==a) f[c[i]][d[i]]=1;
        for(int i=1;i<=m;i++)
            if(f[b[i]][c[i]]==1&&f[c[i]][d[i]]==1&&f[b[i]][d[i]]==1) ans++;
        for(int i=1;i<=m;i++)
            if(b[i]==a) f[c[i]][d[i]]=0;
    }
    cout<<ans;
    return 0;
}