9.12 T2 技能大赛

Vision271 · 2022-09-13 09:27:41 · 个人记录

题意

• 有 n 名选手和 m 个项目。每个项目恰有 2 名选手擅长。

• 每名选手的出场费为 a_i，定义选手集合 U 的代价为 \prod\limits_{i\in U}a_i。

• 定义合法集合为每个项目都至少有一位集合内选手擅长的集合。求所有合法集合的代价和。

数据范围

解析

0.题意转化

• 注意到没有给 m 的范围。嗯？

• 仔细想一下发现本质不同的项目数很少，至多只有 n^2 种。

• 还是很不可做，虽然数据范围明示折半，但是不知道从何做起。

• 建图！把选手视为点，项目视为边，于是我们得到一个一般图，问题就转化为这个一般图的所有点覆盖的代价和。

1.折半设计

• 显然不可能对着项目折，找死呢。

• 对选手进行折半搜索，如果我们整一个 dp_{sta}=state，其中 sta 为选手选取情况，state 为项目覆盖情况，则暴力预处理的复杂度为 O(2^\frac{n}{2}\times \frac{n}{2}^2)，纸面 8\times 10^7，考虑到毕竟要做很多遍，用 bitset 的位运算在大数据下有不小的帮助（事实上，这里就是瓶颈）。

• 怎么合并？如果暴力合并的话显然和没折半一样。

• 很容易联想到遗失的答案。不妨取 state 的补集 comstate，然后做 FMT 求超集和，复杂度为...

• 扯！这复杂度直奔 2^{n^2}，根本没救。

• 还是回到选手。如果问题转化为对选手求超集和，那么问题就简单多了，暴力 FMT O(2^\frac{n}{2}\times \frac{n}{2}) 就好，显然还没有预处理大。

• 不妨将折半的前一半选手称为“左部”，后一半选手称为“右部”。此时如果有一条仅在右部内的边，我怎么知道我的补集需要那条边的哪个端点还是都要？

• 哈哈哈哈哈哈哈（孔明.舌战群儒）。毋需如此！

• 只有处理完毕自己那半部内部边的 sta 才是有意义的。我需要的补集，主要是受跨部边的影响。从而没问题了。

• 后面就是码力时间。示范代码如下：

const int maxn=37,maxm=1297;
int n,m;
int zuo,you; 

ll cost[maxn];

int req[maxn];//对应点，如果在左边没有选，在右边必须选谁。这是个 state。

bitset<maxm> has;//判重边 
bitset<maxm> zuoreq,youreq;//所需的 
bitset<maxm> ava[maxn];//能覆盖的 

il void init(){
    n=rd(),m=rd(),mod=rd();

    For(i,0,n-1) cost[i]=rd();

    zuo=n>>1,you=n-zuo;
    //0~zuo-1 | zuo~n-1 (-zuo/+zuo ahead)
    //          0~you-1
    ri int u,v,hs;
    For(i,1,m){
        u=rd()-1,v=rd()-1;
        if(u>v) swap(u,v);
        hs=u*36+v;
        if(has[hs]) --i,--m;
        else{
            has[hs]=1;
            if(u<zuo && v<zuo) zuoreq[i]=1;
            else if(u>=zuo && v>=zuo) youreq[i]=1;
            else req[u]|=(1<<(v-zuo));//肯定是 u 在左，v 在右
            ava[u][i]=ava[v][i]=1;
        }
    }
    return;
}

il int lowbit(int x){return x&(-x);}

const int maxsta=1<<18;
int zuofull;
bitset<maxm> avazuo[maxsta];
ll costzuo[maxsta];
bitset<maxsta> viszuo;

il void dfszuo(int sta){
    if(!sta) return;
    ri int low=lowbit(sta),lg=log2(low),to=sta^low;
    if(!viszuo[to]) viszuo[to]=1,dfszuo(to);
    avazuo[sta]=avazuo[to]|ava[lg];
    costzuo[sta]=costzuo[to]*cost[lg]%mod;
    return;
}

int youfull;
bitset<maxm> avayou[maxsta];
ll costyou[maxsta];
bitset<maxsta> visyou;

il void dfsyou(int sta){
    if(!sta) return;
    ri int low=lowbit(sta),lg=log2(low),to=sta^low;
    if(!visyou[to]) visyou[to]=1,dfsyou(to);
    avayou[sta]=avayou[to]|ava[lg+zuo];
    costyou[sta]=costyou[to]*cost[lg+zuo]%mod;
    return;
}

int reqsta[maxsta];
bitset<maxm> forcheck;

bitset<maxsta> filped;

ll sum[maxsta];
ll ans;
il void work(){
    zuofull=(1<<zuo)-1,costzuo[0]=1;
    For(i,0,zuofull) if(!viszuo[i]) viszuo[i]=1,dfszuo(i);

    youfull=(1<<you)-1,costyou[0]=1;
    For(i,0,youfull) if(!visyou[i]) visyou[i]=1,dfsyou(i);

    //下面先对左边每个 sta 求一下它需求的补集。
    ri int forfind,low;
    For(i,0,zuofull){
        forcheck=zuoreq&avazuo[i];
        if(forcheck!=zuoreq) reqsta[i]=-1;
        else{
            forfind=zuofull^i;//这些是没选的。
            while(forfind){
                low=lowbit(forfind);
                reqsta[i]|=req[(int)log2(low)];
                forfind^=low;
            }
        }
    }

    //然后吗，我们知道超集和求不了，所以转换一下：把这些补集反转，问题就变成了求这些反集的子集和
    For(i,0,zuofull)
        if(~reqsta[i])
            reqsta[i]=youfull^reqsta[i];

    //接下来我们得相应地把和 you 有关的东西全部反转过来...顺便把子集和初始化一下。
    For(i,0,youfull){
        forcheck=youreq&avayou[i];
        if(forcheck!=youreq) continue;//你没用。
        //你肯定有用；那么我们现在把你反转扔进 sum。
        sum[i^youfull]=costyou[i];
    }

    //处理子集和 
    For(i,0,you-1)
        For(sta,0,youfull)
            if(sta&(1<<i))
                add(sum[sta],sum[sta^(1<<i)]);

    For(i,0,zuofull)
        if(~reqsta[i])
            add(ans,costzuo[i]*sum[reqsta[i]]%mod);

    wt(ans);
    return;
}

2.暴搜

• 没想到吧，暴搜也能过！

• 我们将所有边都规定成 i\to j(i>j) 的单向边，然后按编号从小到大搜。

• 到 i 时，如果 i 的各个边有一条还没有被满足（即 j 没有选），则必须选 i。

• 凭感觉知道这个剪枝很强，但是不够。这样只有 90 pts。

• 发现边越稀疏状态数越多。那...？

• 把孤立点拿出来不参与搜索，最后乘上系数！左边的每一个方案都要乘上右边的子集和，那说白了就是 \times(x_1+1)\times (x_2+1)\times \dots\times (x_k+1)。展开的效果就是每个选或不选（参考约数和函数）。

• 过了（这个的代码就不粘了）。

总结与反思

1.知识点

• 折半的本质就是减小数据范围以便于暴力。折半的瓶颈就在于合并不能退化成纯暴力。

• 百般武艺，此乃暴搜！搜索博大精深，最难的反而是只有状态设计和剪枝的朴素搜索，尽管复杂度无法刻画，它却可能发挥出超乎想象的力量。

2.解题中的失误

• 我觉得时间安排不太好。应该设法搞出时间写个暴力的（当时想麻烦了，想的暴力是折半+暴力合并。那还不如直接写暴力好写）。

• upd：补题居然一遍过了。

3.其他

• 题意转化。题意转化。题意转化。