CQBZ Round 13

· · 个人记录

贪心题好好贪，别一来就做成了博弈论

回退背包现推没搞出来，无语

F题建立辅助树的思想需要学习

A

由于 w_i>\sum_{j=1}^{i-1}w_j，可以得到每一种方案都可以用一个二进制数表示选择与否。

那么选出第 k 大的方案就把 k 所对二进制位的 w 加起来即可。

注意这里我们是从第 0 小开始，而答案是从第 1 小开始，所以 k 要先减去1.

B

简单的递归问题。

首先预处理出 f_i,g_i 分别表示 i 级汉堡的层数和肉饼数，可以得到 f_i=2f_{i-1}+3,g_i=2g_{i-1}+1。

设计函数 solve(n,x) 表示要吃掉 n 级汉堡的前 x 层。

分类讨论：

  1. x\ge f_n$，答案显然为 $g_n
  2. f_{n-1}+1\ge x$，答案为 $solve(n-1,x-1)
  3. 否则将其分为两部分，solve(n-1,x-1)+solve(n-1,x-f_{n-1}-2)+1

C

简单的贪心问题，但我做成了博弈论还倒推挂了。

首先我们将林老师的字符串自小到大排序，把电脑的字符串自大到小排序，他们显然为了各自的目的会依次放入排序后的 1,2\dots \frac{n}{2} 号元素。

我们考虑每一轮，设进行到第 i 轮，林老师手上要填 x，电脑手上要填 y，则有：

  1. > - $x\le y$，此时显然林老师会把当前能填的第一个位置填掉 > - $x>y$，此时在电脑没填的所有字符都比 $x$ 要小，则林老师显然会将自己的字符填在可填的最后一个位置，以达成目的（有点像智猪博弈？）

D

简单的退背包问题。

首先注意到，一个数 a_i 不能删，当且仅当至少存在一个牌组 (不含 i) 和 x 满足 x<k,a_i+x\ge k。

这个判断可以使用背包。注意 O(nk) 可过。

那么问题化为如何在 O(nk) 的时间内处理出缺少某个牌 a_i 所能频出的解的集合。

简单的01背包问题，我们将其转化为求解方案数，然后先跑出所有牌都可以取的情况。然后对于每个牌退背包判断即可。

考场上忘了退包板子

#include<iostream>
#include<cstdio>
using namespace std;
#define N 1050500
#define int long long 
int f[N],a[N];
const int p=998244353;
signed main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0]=1;int ans=n;
    for(int i=1;i<=n;i++){
        int w=a[i];
        for(int i=k;i>=w;i--)f[i]+=f[i-w],f[i]%=p;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>k){
            --ans;continue;
        }
        int w=a[i];
        for(int i=w;i<=k;i++)f[i]-=f[i-w],f[i]%=p;
        for(int i=k-1;i>=k-w;--i)if(f[i]!=0){
            --ans;break;
        }
        for(int i=k;i>=w;i--)f[i]+=f[i-w],f[i]%=p;
    }
    cout<<ans<<"\n";
}

E

高斯消元板题，毫无思维难度。。

F

首先可以猜出贪心策略。先去离根节点最近的一个传送门，然后不断选择最近的传送门进行更新(这里把已经开了的传送门当作一个节点看)。

这个贪心策略的证明是简单的。

可以这样想，我们就是要确定一个更新的顺序，使得代价最小。

那么我们将 k 个传送门两两连边建立完全图，所求即为其中一颗最小的生成树再加上根节点到该生成树中的点的距离的最小值。为什么呢？一颗生成树可以衍生出很多更新顺序，只需要按着这个生成树，随意指定一颗根，进行深度优先搜索即可。（搜索的过程也即扩展顺序）。

这个做法是 O(k^2\log_n) 的，因为最短路。考虑优化。

让我们想想，在完全图的最小生成树中，必然是有许多边可以忽略的。如何判断呢？

这就是本题最关键的地方了：

建立虚图，建立规则为：

设 c_u 是距离节点 u 最近的传送门的编号，设 dis_u 为对应的距离，则对于原图中边 (u,v)，若 c_u\neq c_v，建立边 (c_u,c_v,dis_u+dis_v)。

对于 c 的处理，可以跑一边多源最短路。

证明？个人感觉这个结论拿出来很流畅，但是想不到。我还是太弱了。

感性理解：如果不是这样，那么就等价于在原图上跑了环亦或者更长的路，将这条长路拆掉，必然更优。