我是靠谱客的博主 诚心背包,这篇文章主要介绍Atcoder 3671 ABS 博弈,结论 && Atcoder 3672 MUL 最大权闭合子图,最小割,现在分享给大家,希望可以做个参考。

    • 两题题意
    • 题解

两题题意

https://arc085.contest.atcoder.jp/
略.

题解

复制代码
1
2
3
4
5
6
D: 结论:先手只有两种选择:取剩下最后一张,或者取完. 由于题解的证明不是非常高妙,接下来我们来严谨地证明先手所得不可能更优. 首先我们发现最后一张牌必定是给两人中的一人的,那么两人的最优决策都是使得自己手上最后这张牌与a[n]差的绝对值最大或者最小,而且都会尽量将决策权掌握在自己手中,也就是会把第n张牌让给对方. 如果先手选择的牌编号小于n-1,后手不管如何都可以使先手选择的牌无效(只要后手不直接选第n张). 这样后手可以将选择权掌握在自己手中并将a[n]让与先手,这样显然不能使先手的决策更优. 证毕.

代码如下.

复制代码
1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h> //Ithea Myse Valgulious /*省略*/ using namespace std; const int aoi=2018; int a[aoi]; int main(){ int n=read(),i,z=read(),w=read(); for (i=1;i<=n;++i) a[i]=read(); write(n==1?abs(a[n]-w):max(abs(a[n]-w),abs(a[n-1]-a[n]))); }
复制代码
1
2
3
4
5
6
7
8
E: 吐槽:我本来以为ARC的题都非常清真,用的都是提高组算法,结果它反手给我一网络流! 基本只要把这题转化为最大权闭合子图并跑一个网络流,你就能够A掉了. 首先我们思考最优的情况就是把负数全部爆破,只留下正数. 这样求出一个sum. 如果不行,我们考虑建n+2个点,除源汇外还有n个,编号为1-n. 然后我们把编号为i的点和它所有倍数连inf边,正数和汇点连,负数和源点连,并跑出最小割(最大流). 此题便解决了.
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h> //Ithea Myse Valgulious namespace chtholly{ typedef long long ll; #define re0 register int #define rec register char #define rel register ll #define gc getchar #define pc putchar #define p32 pc(' ') #define pl puts("") /*By Citrus*/ inline int read(){ int x=0,f=1;char c=gc(); for (;!isdigit(c);c=gc()) f^=c=='-'; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return f?x:-x; } template <typename mitsuha> inline bool read(mitsuha &x){ x=0;int f=1;char c=gc(); for (;!isdigit(c)&&~c;c=gc()) f^=c=='-'; if (!~c) return 0; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return x=f?x:-x,1; } template <typename mitsuha> inline int write(mitsuha x){ if (!x) return 0&pc(48); if (x<0) x=-x,pc('-'); int bit[20],i,p=0; for (;x;x/=10) bit[++p]=x%10; for (i=p;i;--i) pc(bit[i]+48); return 0; } inline char fuhao(){ char c=gc(); for (;isspace(c);c=gc()); return c; } }using namespace chtholly; using namespace std; const int yuzu=1e5,inf=0x3f3f3f3f; typedef int fuko[yuzu]; int n,m,cnt,s,t; namespace maxflow{ fuko dep,head,cur; struct edge{int to,next,f;}e[yuzu]; void add(int u,int v,int f){ e[cnt]=edge{v,head[u],f},head[u]=cnt++; e[cnt]=edge{u,head[v],0},head[v]=cnt++; } int bfs(){ queue<int> q; memset(dep,-1,sizeof dep); dep[s]=0,q.push(s); for (;!q.empty();){ int i,u=q.front();q.pop(); for (i=head[u];~i;i=e[i].next){ int v=e[i].to; if (!~dep[v]&&e[i].f){ dep[v]=dep[u]+1; q.push(v); } } }return ~dep[t]; } ll dfs(int u,int flow,ll tflow=0){ if (u==t||!flow) return flow; for (int &i=cur[u];~i;i=e[i].next){ int v=e[i].to; if (dep[v]==dep[u]+1){ int nf=dfs(v,min(flow,e[i].f)); e[i].f-=nf,e[i^1].f+=nf; tflow+=nf,flow-=nf; if (!flow) break; } }return tflow; } ll dinic(){ ll ans=0; for (;bfs();ans+=dfs(s,inf)) memcpy(cur,head,sizeof cur); return ans; } int main(){ int i,j;ll sum=0; memset(head,-1,sizeof head); n=read(),s=n+1,t=n+2; for (i=1;i<=n;++i){ int a=read(); if (a>0) add(i,t,a),sum+=a; else add(s,i,-a); } for (i=1;i<=n;++i) for (j=i;j<=n;j+=i) add(i,j,inf); write(sum-dinic()); } } int main(){ maxflow::main(); }

谢谢大家.

最后

以上就是诚心背包最近收集整理的关于Atcoder 3671 ABS 博弈,结论 && Atcoder 3672 MUL 最大权闭合子图,最小割的全部内容,更多相关Atcoder内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(102)

评论列表共有 0 条评论

立即
投稿
返回
顶部