前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CF536D Tavas in Kansas

CF536D Tavas in Kansas

作者头像
yzxoi
发布2022-09-19 14:16:55
5910
发布2022-09-19 14:16:55
举报
文章被收录于专栏:OI

CF536D Tavas in Kansas

题目链接:CF536D

  • 给定一张 n 个点 m 条边的可能有自环和重边的无向连通图,每条边都有一个非负边权。
  • 小 X 和小 Y 在这张图上玩一个游戏,在游戏中,第 i 个城市有一个权值 p_i
  • 一开始,小 X 在城市 s 中,小 Y 在城市 t 中,两人各有一个得分,初始为 0,小 X 为先手,然后轮流进行操作。
  • 当轮到某一个人时,他必须选择一个非负整数 x,以选定所有与他所在的城市的最短距离不超过 x 的还未被选定过的城市,他的得分将会加上这些城市的权值。
  • 另外,每个人每次必须能够至少选定一个城市。
  • 当没有人可以选择时,游戏结束,得分高者获胜。
  • 现在请你计算出,在两人都使用最佳策略的情况下,谁会获胜(或者判断为平局)。
  • n \le 2 \times 10^3m \le 10^5p_i \le 10^9

Tutorial

首先从 s,t 分别跑一次最短路,容易发现答案仅与其相对大小有关,因此先离散化。

容易将其抽象成一个表格,其中第 i 号点位于 (d_{s,i},d_{t,i}),权值为 p_i,两人分别从 上/左 取若干 行/列。

注意到 n\leq 2\times 10^3,考虑 dp,设 f_{k,i,j} 表示在各自最优策略下当前小 X/小 Y 先手,剩余的点为 (i,j) 及其右下角范围,小 X 的权值与小 Y 的权值的差。

发现其实没必要枚举每个人取到哪一行/列进行转移,只需要一行行一列列转移时注意是否要交给对方即可。

\begin{align}&f_{0,i,j}\leftarrow \max { f_{0,i+1,j} , f_{1,i+1,j}}+S(i,j,i,c_1) \quad [\exists p\in [i,j,i,c_1]]\\&f_{1,i,j}\leftarrow \min { f_{0,i,j+1} , f_{1,i,j+1}}-S_{i,j,c_0,j} \quad[\exists p\in [i,j,c_0,j]]\end{align}

Solution

代码语言:javascript
复制
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e3+10,M=1e5+10;
int n,m,s[2],a[N],vis[N],fir[N],nxt[M<<1],son[M<<1],w[M<<1],tot,cnt,c[2],sz[N][N];
LL sum[N][N],b[N],dp[2][N][N],F[2][N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
queue<int> q;
I void Spfa(){
    RI u,i,j;for(memset(vis,0,sizeof(vis)),memset(F,63,sizeof(F)),j=0;j<2;j++){
        W(!q.empty()) q.pop();F[j][s[j]]=0,q.push(s[j]);W(!q.empty())
        for(vis[u=q.front()]=0,q.pop(),i=fir[u];i;i=nxt[i]) F[j][to]>F[j][u]+w[i]&&(F[j][to]=F[j][u]+w[i],!vis[to]&&(q.push(to),vis[to]=1));
    }
}
I int Sz(CI i1,CI j1,CI i2,CI j2){return sz[i2][j2]-sz[i1-1][j2]-sz[i2][j1-1]+sz[i1-1][j1-1];}
I LL Sum(CI i1,CI j1,CI i2,CI j2){return sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1];}
int main(){
    RI i,j,k,x,y,z;for(read(n,m,s[0],s[1]),i=1;i<=n;i++) read(a[i]);
    for(i=1;i<=m;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);
    for(Spfa(),k=0;k<2;k++){
        for(cnt=0,i=1;i<=n;i++) b[++cnt]=F[k][i];
        for(sort(b+1,b+cnt+1),c[k]=cnt=unique(b+1,b+cnt+1)-b-1,i=1;i<=n;i++) F[k][i]=lower_bound(b+1,b+cnt+1,F[k][i])-b;
    }
    for(i=1;i<=n;i++) sum[F[0][i]][F[1][i]]+=a[i],sz[F[0][i]][F[1][i]]++;
    for(i=1;i<=c[0];i++) for(j=1;j<=c[1];j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1],sz[i][j]+=sz[i-1][j]+sz[i][j-1]-sz[i-1][j-1];
    for(i=c[0];i;i--) for(j=c[1];j;j--){
        if(Sz(i,j,i,c[1])) dp[0][i][j]=max(dp[0][i+1][j],dp[1][i+1][j])+Sum(i,j,i,c[1]);
        else dp[0][i][j]=dp[0][i+1][j];
        if(Sz(i,j,c[0],j)) dp[1][i][j]=min(dp[0][i][j+1],dp[1][i][j+1])-Sum(i,j,c[0],j);
        else dp[1][i][j]=dp[1][i][j+1];
    }
    return puts(dp[0][1][1]>0?"Break a heart":dp[0][1][1]<0?"Cry":"Flowers"),0;
}
本文参与?腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-06-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客?前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体同步曝光计划? ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • CF536D Tavas in Kansas
    • Tutorial
      • Solution
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
      http://www.vxiaotou.com