CF97C Winning Strategy

倍增floyd 负环 分数规划

---

今天心情不大好,因为各种原因今天爆0...QAQ
首要原因就是这道杠了两个多小时的T1.
最开始没有给样例解释,手玩了好久的样例发现怎么也凑不出,后来才知道是无穷的,凑得出才怪了.其实给了样例解释之后就暗示这题可以二分逼近答案.
此题有三种方法:

倍增floyd

看到题这个算法就在脑子中间闪过,然而,,,仅仅是闪过而已.
先处理出转移矩阵,$mat[c][i][j]$表示走$2^c$步,剩余i个1滴血随从转移到j个1滴血的随从的最小值.
但如果你每次只砍一排,然后接着再换一批新的再砍一排,以此无限地砍下去,那么状态是无限的.是无限的吗?
考虑缩减状态数.显然当我们的人数在2n以内,都是必须要保留的.超过2n我们可以先砍掉.由于是无穷,所以我们的1滴血的人数可以是负数,因为可以忽略前面几项,前面几次操作可以都是增加1滴血的人数的.
于是直接倍增就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 205
#define ll long long
using namespace std;
int n,cur,pre,m,cnt;
double inf,p[maxn],ans,tim;
struct matrix
{
    double a[maxn][maxn];
    void init(){memset(a,0xc2,sizeof(a));}
    double* operator [] (int x){return a[x];}
    matrix operator * (matrix x)
        {
            matrix y;y.init();
            for(int i=1;i<=m;i++)
                for(int j=1;j<=m;j++)
                    for(int k=1;k<=m;k++)
                        if(a[i][k]!=inf&&x[k][j]!=inf)
                            y[i][j]=max(y[i][j],a[i][k]+x[k][j]);
            return y;
        }
}mat[35],f;
int main()
{
    //freopen("blasphemy.in","r",stdin);
    //freopen("blasphemy.out","w",stdout);
    cin>>n;m=n<<1;
    for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=0;i<=30;i++)mat[i].init();f.init();
    inf=f[0][0];f[0][0]=0;
    for(int i=0;i<=m;i++)//转移矩阵
        for(int j=0;j<=n;j++)
        {
            int k=i+n-j-j;
            if(i-j>=0&&k>=0&&k<=m)mat[0][i][k]=max(mat[0][i][k],p[j]);
        }
    cnt=1;pre=1;
    for(int c=1;cnt<=30;c<<=1,cnt++)
    {
        for(int i=0;i<=m;i++)
            if(f[cur][i]!=inf)
            {
                for(int j=0;j<=m;j++)
                    if(mat[cnt-1][i][j]!=inf)
                        f[pre][j]=max(f[pre][j],f[cur][i]+mat[cnt-1][i][j]);
                f[cur][i]=inf;
            }
        tim+=c;mat[cnt]=mat[cnt-1]*mat[cnt-1];swap(cur,pre);
        for(int i=0;i<=m;i++)ans=max(ans,f[cur][i]/tim);
    }
    printf("%.10lf\n",ans);
    return 0;
}

分数规划

最后我们是要得到最大的ans使得下面的式子恒成立,ans越小越有可能合法.

$$ans<=\frac{a_0p_0+a_1p_1+a_2p_2+...}{a_0+a_1+a_2+...}\\ a_0(ans-p_0)+a_1(ans-p_1)+...<=0$$
像上面处理转移矩阵一样建图,二分ans,跑出负环说明合法(因为可以在负环上面无限绕),check更大的ans

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 305
#define maxm 500005
#define ll long long
using namespace std;
int n,vis[maxn],o[maxn],cn[maxn],nxt[maxm],head[maxn];
int to[maxm],cnt,m;
double p[maxn],mid,w[maxm],dis[maxn];
const double eps=1e-10;
queue<int> q;
void add(int u,int v,double ww)
{
    nxt[++cnt]=head[u];head[u]=cnt;
    to[cnt]=v;w[cnt]=ww;
}
bool spfa(int s)
{
    dis[s]=0;while(!q.empty())q.pop();
    q.push(s);vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();++cn[u];
        vis[u]=1;o[u]=0;if(cn[u]==m)return 1;
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+w[i]+mid)
            {
                dis[v]=dis[u]+w[i]+mid;
                if(!o[v])q.push(v),o[v]=1;
            }
        }
    }
    return 0;
}
bool check()
{
    memset(o,0,sizeof(o));
    memset(vis,0,sizeof(vis));
    memset(cn,0,sizeof(cn));
    for(int i=0;i<=m;i++)dis[i]=1e15;
    for(int i=0;i<=m;i++)
        if(!vis[i])if(spfa(i))return 1;
    return 0;
}
int main()
{
    //freopen("blasphemy.in","r",stdin);
    //freopen("blasphemy.out","w",stdout);
    cin>>n;m=n*2;
    for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=0;i<=m;i++)
        for(int j=0;j<=n;j++)
        {
            int k=i+n-j-j;
            if(k>0&&k<=m)add(i,k,-p[j]);
        }
    double l=0,r=1;
    while(r-l>eps)
    {
        mid=(l+r)*0.5;
        if(check())l=mid;
        else r=mid;
    }
    printf("%.10lf\n",l);
    return 0;
}

结论

每一种p对应一种修改:$p_i$表示增加了场上$n-2i$个1血人数,于是我们要是他们一直循环下去得到一个最优解,其实就是求,每个背包有个重量$n-2i$,价值$p_i$,要求重量和为0.
这个结论其实考场上也yy了,只是觉得肯定是错的于是去想怎么合并多个符号相同的价值.其实完全是不要考虑的,因为一定是一个正数和一个负数是最优的,(不知道证明,感性理解).于是我们只要枚举一个正的,一个负的,直接算他们的$(w[i]p[j]+w[j]p[i])/(w[i]+w[j])$的最大值就可以了.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 205
#define ll long long
using namespace std;
int n;
double c[maxn],p[maxn],ans;
int main()
{
    //freopen("blasphemy.in","r",stdin);
    //freopen("blasphemy.out","w",stdout);
    cin>>n;
    for(int i=0;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=0;i<=n;i++)c[i]=fabs(n-2*i);
    for(int i=0;i<=(n-1)/2;i++)
        for(int j=(n-1)/2+1;j<=n;j++)
            ans=max(ans,(c[j]*p[i]+c[i]*p[j])/(c[j]+c[i]));
    printf("%.12lf",ans);
    return 0;
}