题解 Flip Machines

开 unr 打的，一上来就开的 F……

稍微参考了官方题解。

题意

给定 $n$ 张牌，正面的数为 $a_i$，背面的数为 $b_i$。

现在有 $m$ 个机器，参数为 $(x_i,y_i)$，有二分之一的概率翻转第 $x_i$ 牌，剩下的二分之一翻转第 $y_i$ 牌。

求出所有对于选取机器的集合 $S$ 中，使得所有牌正面的数之和的期望值最大。

思路

令最优的机器集合为 $S$。

首先，定义集合 $I={i\mid \exists\ j\in S,x_j=i\lor y_j=i}$。

说人话就是只要牌 $i$ 可能被翻转，它就在 $I$ 里面。

易证如果一张牌可能被翻转，无论多少次，最后的正面的期望一定是 $\frac{a+b}{2}$。

所以令翻转一张牌的变化量 $d_i=a_i-\frac{a_i+b_i}{2}=\frac{a_i-b_i}{2}$。

最后的答案就为 $\sum_{i=1}^n{a_i}+\sum_{i\in I}{d_i}$。

现在问题就变成了求 $\max{\sum_{i\in I}d_i}$。

首先把 $x_i=y_i$ 的机器处理掉，如果 $a_{x_i}<b_{b_i}$，那就直接交换。然后就可以不管这些东西了，再翻只会使期望变小。

先钦定 $P={1\le i\le n\mid d_i<0},Q={1\le i \le n\mid d_i\ge0}$。

现在考虑机器。

对于机器 $i$，有三种可能：

$x_i\in Q\land y_i\in Q$，此时肯定要选；
$x_i\in P \land y_i\in P$，此时肯定不选；
对于剩余情况，钦定 $x_i\in P,y_i\in Q$，否则交换 $x_i,y_i$。此时如果 $x_i\in I\cap P$，这个机器就一定要选。

因为选 $Q$ 集合里面的牌都不劣，所以当 $x_i\in P$ 被选中时，所有的在 $Q$ 中能选的 $y_i$ 都一并要选，于是可以建立一个映射 $ls_i$，代表如果选了 $i\in P$ 有哪些在 $Q$ 中的元素能选。

根据上文，发现只需要依据 $I\cup P$ 即可判断 $S$ 的集合。

所以我们只需要找出最优的 $I\cup P$ 即可。（其实就是在 $P$ 里面选出最优的集合。）

有两种方法：

暴力枚举 $I\cup P$。时间复杂度 $O(2^{\vert P\vert}n+m)$。
使用 DP。令 $f_{i,S}$ 为处理了 $P$ 中前 $i$ 个牌，选择的 $Q$ 的集合为 $S$，$P$ 中选的牌的最大值。如果没选 $i$，就不管；如果选了，加上 $d_i$，$S\gets S \cup ls_i$。最后加上 $S$ 中元素的 $d_i$ 即可。时间复杂度 $O(2^{\vert S\vert}n+m)$。

因为 $\vert Q\vert+\vert P\vert=n$，所以 $\min{\vert Q\vert,\vert P\vert}\le \frac{n}{2}$，所以根据 $P,Q$ 集合大小判断使用哪个即可。

最终时间复杂度 $O(2^{\frac{n}{2}}n+m)$。

code

#include<cstring>
#include<iostream>
#include<vector>
#define int long long
using namespace std;
int a[100005],s[100005],x[100005],y[100005],n,m,ans,id[100005],ls[100005],f[100][1148576];
vector<int>Q,P;
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&s[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        if(x[i]==y[i]&&a[x[i]]<s[x[i]])swap(a[x[i]],s[y[i]]);
    }
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]*2;
        int d=a[i]-s[i];
        if(d>=0)
        {
            id[i]=P.size();
            P.push_back(d);
        }
        else
        {
            id[i]=Q.size();
            Q.push_back(-d);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int hx=(a[x[i]]>=s[x[i]]);
        int hy=(a[y[i]]>=s[y[i]]);
        if(hx==hy)
        {
            if(!hx)
            {
                ans+=Q[id[x[i]]]+Q[id[y[i]]];
                Q[id[x[i]]]=Q[id[y[i]]]=0;
            }
        }
        else
        {
            if(!hx)swap(x[i],y[i]);
            ls[id[x[i]]]|=1ll<<id[y[i]];
        }
    }
    if(P.size()<=Q.size())
    {
        int mx=0;
        for(int bit=0;bit<1ll<<(int)P.size();bit++)
        {
            int an=0,q=0;
            for(int i=0;i<(int)P.size();i++)
            {
                if(bit>>i&1)
                {
                    an-=P[i];
                    q|=ls[i];
                }
            }
            for(int i=0;i<(int)Q.size();i++)if(q>>i&1)an+=Q[i];
            mx=max(mx,an);
        }
        ans+=mx;
    }
    else
    {
        memset(f,0xc0,sizeof(f));
        f[0][0]=0;
        int mx=0;
        for(int i=0;i<(int)P.size();i++)
        {
            for(int j=0;j<1ll<<(int)Q.size();j++)
            {
                f[i+1][j]=max(f[i+1][j],f[i][j]);
                f[i+1][j|ls[i]]=max(f[i][j]-P[i],f[i+1][j|ls[i]]);
            }
        }
        for(int bit=0;bit<1ll<<(int)Q.size();bit++)
        {
            int an=f[(int)P.size()][bit];
            for(int i=0;i<(int)Q.size();i++)if(bit>>i&1)an+=Q[i];
            mx=max(mx,an);
        }
        ans+=mx;
    }
    printf("%lf",ans/2.0);
}