CF97C Winning Strategy

标签：check   一个   amp   分数   忽略   mem   struct   floyd   bool   

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

倍增floyd

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

#include
#include
#include
#include
#include
#include
#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>n;m=n=0&&k>=0&&k

分数规划

最后我们是要得到最大的ans使得下面的式子恒成立,ans越小越有可能合法.
\[ans
像上面处理转移矩阵一样建图,二分ans,跑出负环说明合法(因为可以在负环上面无限绕),check更大的ans

#include
#include
#include
#include
#include
#include
#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 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>n;m=n*2;
    for(int i=0;i0&&keps)
    {
        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
#include
#include
#include
#include
#include
#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

CF97C Winning Strategy

标签：check   一个   amp   分数   忽略   mem   struct   floyd   bool   

原文地址：https://www.cnblogs.com/terribleterrible/p/9827558.html