D.Chocolate
博弈题
题意
有一块大小为n*m的巧克力,起始坐标为(1,1)
每次操作可以选择一个坐标(a,b),并吃掉(1,1):(a,b)中的所有巧克力
每次操作必须吃掉至少一块巧克力,吃掉最后一块巧克力的玩家输
解题思路
1*1:显然先行必输
其他:对于总数m*n。若总数为奇数,则先行开局吃偶数个,若总数为偶数,则先行开局吃奇数个。
然后剩余个数变为奇数个,后续每一步,先行者都保证吃完后剩余奇数个巧克力且行数/列数多于1,或1*1(可以证明在任何状态下,一定有一种这样的操作)。
先行必胜
参考程序
1 2 3 4 5 6 7 8
| int solve() { ll n,m; cin >> n >> m; if(n==1&&m==1) cout << "Walk Alone" << endl; else cout << "Kelin" << endl; return 0; }
|
H.Matches
二分、包络
题意
给定两个长度为 $n$ 的序列 $a,b$ ,定义他们之间的距离为对应元素差的绝对值之和,即:
可以对其中一个序列交换两个数,问至多操作一次后的最小距离。
解题思路
绝对值的本质就是数轴上区间的大小,把每一对元素看作一个区间,就能将问题转化。
对于某一个区间, $a_i,b_i$ 决定它自身的正反序
对于某两个区间:
覆盖区域有 相交、包络、不交 三种相对关系
正反序有 正序、反序 两种相对关系
组合之下便有6种相对关系
针对两个区间的相对关系的转换,展开以下分类讨论
1.正序相交 $\rightleftarrows$ 正序包络
2.正序不交 $\rightleftarrows$ 反序包络
3.反序不交 $\rightleftarrows$ 反序相交
可以看到绝对值减小的情况只有两种:
1.反序相交 $\Rightarrow$ 反序不交
2.反序包络 $\Rightarrow$ 正序不交
它们对距离的减少量都是重叠区间大小的两倍
综上所述,只需要找出反序相交和反序包络的情况中,重叠区间最大的情况,即可得到答案。
对于输入数据,可以先按照 $a_i,b_i$ 的相对大小,将正序区间和反序区间分别存入两个容器,记为 $S,T$ ,并算出初始值 $sum$
对 $S$ 进行预处理,按照区间起点排序,去除被正序包络的区间(不难证明,被正序包络的区间对答案的贡献一定不大于正序包络它的区间)
对于 $T$ 中的每个区间,二分查找 $S$ 中与它有交集的区间,求出重叠区间大小的最大值 $dif$
最终答案为 $sum-2\times dif$
参考程序
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
| int solve() { ll n,sum=0,dif=0; cin >> n; vector<pll> v(n); FORLL(i,0,n-1) cin >> v[i].first; FORLL(i,0,n-1) cin >> v[i].second; vector<pll> S,T; vector<ll> Sx,Sy,len; for(auto [a,b]:v) { sum+=abs(a-b);
if(a<b) S.emplace_back(a,b); if(a>b) T.emplace_back(b,a); }
SORT(S); ll r=-INF; for(auto p:S) { if(p.second<=r) continue; r=p.second; Sx.emplace_back(p.first); Sy.emplace_back(p.second); len.emplace_back(p.second-p.first); }
auto finddif=[&](ll x,ll y){ ll m=Sx.size(),re=0; ll l=upper_bound(ALL(Sx),x)-Sx.begin(); ll r=lower_bound(ALL(Sy),y)-Sy.begin(); if(l>0) re=max(re,min(Sy[l-1],y)-x); if(r<m) re=max(re,y-max(Sx[r],x)); if(r>l) re=max(re,*max_element(len.begin()+l,len.begin()+r)); return re; };
for(auto [x,y]:T) dif=max(dif,finddif(x,y)); cout << sum-dif*2 << endl; return 0; }
|
J.Roulette
数学题
题意
初始有 $n$ 元钱,目标为赢得 $m$ 元钱(即共 $n+m$ 元钱)
每次投注 $x$ 元,有50%的概率输掉,50%的概率赢得 $2x$ 元
第一局投注 $1$ 元,接下来的每局按下述策略投注:
如果某局剩下的钱不足以按上述策略投注,则失败退场
问达成目标的概率有多大
解题思路
投注采用的是倍投法,考虑每一轮投注为:输若干局直到赢一局
- 第一局就赢了,则获得 $1$ 元
- 第 $n$ 局赢了,则获得 $2^{n-1} - (2^{n-2}+2^{n-3}+\cdots+2+1)=1$ 元
综上,每一轮赢取的钱数固定为 $1$ 元
根据题意,直到输到无法投注才失败,则对于每轮投注
- 失败的概率为: $\dfrac{1}{2^a}$
- 成功的概率为: $1-\dfrac{1}{2^a}$
其中 $a$ 是这轮投注的局数
那么对于整个投注过程,成功的概率为:$\prod\limits_{i=n}^{n+m-1} (1-\dfrac{1}{2^{a_i}})$
考虑本金与可以进行的投注轮数的关系,进行第a轮至少需要的本金为:
$1+2+\cdots+2^{a-1}=2^a-1$
以此为边界对集合 ${n,n+1,\cdots,m+n-1}$ 做划分(划分内投注轮数相同,成功率相同),分别计算每个划分的成功率,再相乘得到结果
时间复杂度
划分数 $\log n$,快速幂等操作 $\log n$,总复杂度 $O(\log^2n)$
参考程序
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
| const int MOD=998244353; #define Get_Mod(x) ((x)%MOD) ll QuickPow(ll x,ll y){ ll ans=1; while(y){ if(y&1) ans=Get_Mod(x*ans); x=Get_Mod(x*x); y>>=1; } return ans; } ll Get_Inv(ll a){ return QuickPow(a,MOD-2); } int solve() { ll n,m; cin >> n >> m; ll a,b,c; ll base=0,t=(n+1)>>1; while(t){ base++; t>>=1; } ll l=n,r=pow(2,base+1)-2; ll re=1; if(m+n<=r) { a=QuickPow(2,base); b=Get_Mod(Get_Mod(a+MOD-1)*Get_Inv(a)); c=QuickPow(b,m); re=Get_Mod(re*c); base++; } else{ while(r<=m+n-1) { a=QuickPow(2,base); b=Get_Mod(Get_Mod(a+MOD-1)*Get_Inv(a)); c=QuickPow(b,r-l+1); re=Get_Mod(re*c);
base++; l=pow(2,base)-1; r=pow(2,base+1)-2; } if(l<m+n) { a=QuickPow(2,base); b=Get_Mod(Get_Mod(a+MOD-1)*Get_Inv(a)); c=QuickPow(b,m+n-l); re=Get_Mod(re*c); } } cout << re << endl; return 0; }
|
K.Subdivision
图论-BFS最短路
题意
给定一个无权无向图 $G=(V,E),|V|=n,|E|=m$
每次操作可以选定一条边,在其中插入一个点使其分裂成两条边
问操作任意次数后,与点 $v_1$ 距离不大于 $k$ 的点至多有多少个
解题思路
对于无向图 $G$ ,以点 $v_1$ 为根,用BFS确定最短路,刻画BFS树
可以很容易得到以下结论:
1.不在BFS树上的边可以无限分裂,对BFS树上点的距离无影响
2.分裂操作对答案有贡献的情况是:这条边至少有一个端点的距离 $dist_i$ 小于 $k$ 。从端点的角度,分裂这条边的最大贡献是 $k-dist_i$
那么可以对BFS树上的点进行分类讨论:
1.在图上具有除父节点外的其他邻节点:分裂以它为端点的树边,或导致其它邻节点到根的距离增大,对答案有损失。故只允许它在非树上的有效边上分裂
2.在图上没有除父节点外的其他邻节点:允许其在回溯的树边上分裂,对答案没有损失,只有贡献
我赛时写的程序和标程其实差不多,只是后面想歪了写了个图存储BFS树然后卡死在那了//
所以本篇参考程序后半部分照抄借鉴了标程,并加入了对BFS的优化:
由于距离 $dist_i$ 大于 $k$ 的点 $v_i$ 上一定没有对答案有贡献的边(这是最短路的特性决定的,不难证明),BFS只需搜索完 $dist_i$ 小于等于 $k$ 的点并加入BFS树即可,在 $k<<n$ 的情况下可以大幅减少BFS时间
参考程序
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
| int solve() { ll n,m,k; cin >> n >> m >> k; vector<vector<ll>> G(n+1); ll u,v; pll tpll; vector<ll>::iterator it; FORLL(i,1,m) { cin >> u >> v; G[u].emplace_back(v); G[v].emplace_back(u); } queue<ll> q; vector<ll> dist(n+1,-1); vector<ll> pre(n+1,0); vector<ll> leaf(n + 1,0); q.push(1);dist[1]=0; while(!q.empty()&&dist[q.front()]<k) { u=q.front(); q.pop(); for (auto v: G[u]){ if (dist[v]!=-1) continue; q.push(v); dist[v]=dist[u]+1; pre[v]=u; leaf[u]=1; } }
ll re=1; FORLL(i,2,n){ if(dist[i]==-1||dist[i]>k) continue; ll cnt=0; for(auto p:G[i]){ if(p==pre[i]||i==pre[p]) continue; ++cnt; } if (!leaf[i]) cnt = max(cnt, 1ll); re+=(k-dist[i])*cnt+1; }
cout << re << endl; return 0; }
|