题解 P7113 【排水系统】

· · 题解

这可能是我写的最后一篇题解了……T2看错题，用了 2h 获得了 0pts 的高分。

考场思路：

拓扑序板题？？？

再套个分数运算模板？

好像 ll 会炸，那就用 long double。

于是 30min 写完去看后面的题了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fs
{
    unsigned int cnt2,cnt3,cnt5;
    long double fz;
    fs operator +(const fs x)
    {
        fs tmp=(fs){max(cnt2,x.cnt2),max(cnt3,x.cnt3),max(cnt5,x.cnt5),0};
        long double tmp1=fz*pow(2,tmp.cnt2-cnt2)*pow(3,tmp.cnt3-cnt3)*pow(5,tmp.cnt5-cnt5);
        long double tmp2=x.fz*pow(2,tmp.cnt2-x.cnt2)*pow(3,tmp.cnt3-x.cnt3)*pow(5,tmp.cnt5-x.cnt5);
        tmp1+=tmp2;
        while(round(tmp1/2)*2==tmp1&&tmp.cnt2>0)--tmp.cnt2,tmp1/=2;
        while(round(tmp1/3)*3==tmp1&&tmp.cnt3>0)--tmp.cnt3,tmp1/=3;
        while(round(tmp1/5)*5==tmp1&&tmp.cnt5>0)--tmp.cnt5,tmp1/=5;
        tmp.fz=tmp1;
        return tmp;
    }
}ans[100001];
int n,m,d[100001],a[100001][11],in[100001],vis[100001];
void dfs(int i)
{
    vis[i]=1;
    if(--in[i]<=0)
    {
        if(d[i])
        {
            fs tmp=ans[i];
            if(d[i]==2)tmp.cnt2+=1;
            if(d[i]==3)tmp.cnt3+=1;
            if(d[i]==4)tmp.cnt2+=2;
            if(d[i]==5)tmp.cnt5+=1;
            for(int j=1;j<=d[i];j++)ans[a[i][j]]=ans[a[i][j]]+tmp,dfs(a[i][j]);
        }
    }
}
signed main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        for(int j=1;j<=d[i];j++)scanf("%d",&a[i][j]),++in[a[i][j]];
    }
    for(int i=1;i<=m;i++)ans[i].fz=1;
    for(int i=1;i<=n;i++)if(in[i]==0&&vis[i]==0)dfs(i);
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            printf("%.0Lf %.0Lf\n",ans[i].fz,((long double)pow(2,ans[i].cnt2))*pow(3,ans[i].cnt3)*pow(5,ans[i].cnt5));
        }
    }
    return 0;
}

赛后发现能卡掉，但是除了自己造的 hack 数据就没有别人卡掉（各种民间数据都是 100，官方数据也是 100）。

这种写法基于浮点数的特性，long double 实际上会保存二进制最高 64 位和指数，这也就意味着 2 的幂次是不会对精度产生影响的，而答案的分母的最大值是 60^{11}，实际上有效的部分是15^{11}，这个数显然没有超过 64 位，于是分母是可以准确输出的，分子如果没有爆 ll 就也是能准确输出的，只要出题人没想到这种方法，就不会去卡。

再贡献两个 hack 数据（仅提供输入数据）。

爆搜复杂度是指数级的，本来只能拿 30 分但是数据太水居然放过了，只要让每个点的出边都是 5 条就可以轻松卡掉，hack数据。

又到了亲手卡掉自己的代码的时候，long double 的 hack 数据只需要让分子的有效数位超过 64 就可以了，hack数据。