矿石采集（计蒜客信息学3月提高组模拟赛）

题目描述

传送门

思路

这题首先，题意要看懂。。。。

可以将问题分为几个子问题

• 所有询问从起点到终点能获得的最大矿物价值。
• 选取若干个时间区间不相交的询问，使得按题意要求算到的期望值最大。

对于第一个子问题，比较简单，预处理一下拥有哪几种矿石时的总价值。然后对整个图用\(tarjan\)强连通缩点。单个点的矿石状态为包含的点的或和。然后以每个点为起点跑一边\(bfs\)或\(dfs\)即可,最终求出每个询问的最优价值\(v_i\)。

对于第二个子问题，对于时间区间不相交处理较简单，很套路，排序一维，数据结构(树状数组etc)维护另一维。

然后就是难点，算期望。经过一系列的推导可以得到如下结论：

\(f[i]\)表示以\(i\)为执行任务的起点，能得到的最大起点，有：

\[f[j]=(1-p_j)*f[i]+(1-p_j)*v_j-c_j\]

有了这个，我们就可以按每个任务起点时间从大到小进行转移了。最终复杂度\(O(n^{2..3}+nlog_n)\)

code

#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l),i##R=(r);i<=i##R;i++)
#define DOR(i,r,l) for(int i=(r),i##L=(l);i>=i##L;i--)
#define loop(i,n) for(int i=0,i##R=(n);i<i##R;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef double db;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int N=1e5+5,M=220,inf=1e9;
int n,m,K,q; 
int mi[M],w[M];
char s[15];
struct Graph{
    int tot,to[M],nxt[M],head[M];
    void add(int x,int y){tot++;to[tot]=y;nxt[tot]=head[x];head[x]=tot;}
    void clear(){mms(head,-1);tot=0;}
    #define EOR(G,i,x) for(int i=G.head[x];i!=-1;i=G.nxt[i])
}G,T;
struct Query{
    int s,t,c,l,r;
    db p;
    int val;
    bool operator<(const Query &A)const{
        return l>A.l;
    }
}Q[N];
int b[N<<1],h;
int rev[1050];
int dfn[M],low[M],bel[M],cnt,tot;
int stk[M],tp,stat[M];
void tarjan(int x){
    low[x]=dfn[x]=++tot;
    stk[++tp]=x;
    EOR(G,i,x){
        int v=G.to[i];
        if(!dfn[v]){
            tarjan(v);
            chkmin(low[x],low[v]);
        }else if(!bel[v])chkmin(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]){
        int t;cnt++;
        do {
            bel[t=stk[tp--]]=cnt;
            stat[cnt]|=mi[t];
        }while(t!=x);
    }
}
bool link[M][M];
void construct(){
    FOR(x,1,n)EOR(G,i,x){
        int v=G.to[i];
        link[bel[x]][bel[v]]=1;
    }
}
int vis[M][1050],ti;
int mxv[M];
int dis[M][M];
void dfs(int x,int S){
    if(vis[x][S]==ti)return;
    vis[x][S]=ti;
    chkmax(mxv[x],rev[S]);
    FOR(v,1,cnt)if(link[x][v])
        dfs(v,S|stat[v]);
}
void init_val(){
    loop(i,1<<K)loop(j,K)if(i>>j&1)rev[i]+=w[j];
    FOR(i,1,n)if(!dfn[i])tarjan(i);
    construct();
    FOR(i,1,cnt){
        FOR(j,1,cnt)mxv[j]=-inf;
        ti=i,dfs(i,stat[i]);
        FOR(j,1,cnt)dis[i][j]=mxv[j];
    }
    loop(i,q)Q[i].val=dis[bel[Q[i].s]][bel[Q[i].t]];
}
void init_Interval(){
    h=0;
    loop(i,q)b[++h]=Q[i].l,b[++h]=Q[i].r;
    sort(b+1,b+h+1);
    h=unique(b+1,b+h+1)-b-1;
    loop(i,q){
        Q[i].l=lower_bound(b+1,b+h+1,Q[i].l)-b;
        Q[i].r=lower_bound(b+1,b+h+1,Q[i].r)-b;
    }
}
struct Binary_Indexed_Tree{
    #define lowbit(x) (x&(-x))
    db c[N<<1];
    void update(int x,db val){while(x)chkmax(c[x],val),x-=lowbit(x);}
    db query(int x){db ret=0;while(x<(N<<1))chkmax(ret,c[x]),x+=lowbit(x);return ret;}
}BIT;
int main(){
    scanf("%d%d%d%d",&n,&m,&K,&q);
    FOR(i,1,n){
        scanf("%s",s);
        loop(j,strlen(s))mi[i]|=((s[j]-'0')<<j);
    }
    G.clear();
    FOR(i,1,m){
        int x,y;scanf("%d%d",&x,&y);
        G.add(x,y);
    }
    loop(i,K)scanf("%d",&w[i]);
    loop(i,q){
        scanf("%d%d%d%lf%d%d",&Q[i].l,&Q[i].s,&Q[i].t,&Q[i].p,&Q[i].c,&Q[i].r);
        Q[i].r+=Q[i].l;
    }
    init_val();
    init_Interval();
    sort(Q,Q+q);
    db ans=0;
    loop(i,q){
        db Val=BIT.query(Q[i].r);
        Val=(Val+Q[i].val)*(1.0-Q[i].p)-1.0*Q[i].c;
        chkmax(ans,Val);
        BIT.update(Q[i].l,Val);
    }
    printf("%.6lf\n",ans);
    return 0;
}

矿石采集（计蒜客信息学3月提高组模拟赛）

原文：https://www.cnblogs.com/Heinz/p/11443279.html