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

港控/mmm° 2023-06-01 14:59 5阅读 0赞

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

## 题目描述 ##

[传送门][Link 1]

## 思路 ##

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

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

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

对于第一个子问题，比较简单，预处理一下拥有哪几种矿石时的总价值。然后对整个图用\\(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; }

转载于:https://www.cnblogs.com/Heinz/p/11443279.html

[Link 1]: https://nanti.jisuanke.com/t/37268