首页 > 其他分享 >P9170 填数游戏 贺题记录

P9170 填数游戏 贺题记录

时间:2023-07-02 15:26:05浏览次数:48  
标签:cnt Task P9170 贡献 填数 贺题 显然 考虑 Bob

感觉进行对于此类困难问题对于我是很有 educational 的意义的。

这个题考虑贺 ZCPB 伟大的 SD 队长的方法。

妈的,考场上写了 B 先 A 后的弱智做法。

Pre - Task

很自然的,考场上我也会的先想到 \(T_{i, 0} \to T_{i, 1}\), 这样有解得方案显然是树或者基环树的若干森林拼起来。

然后我们可以考虑 \(S_i \to S_i \cap T_i\),因为 Alice 显然不会选没啥用的。

A - Task

显然要么是 -1 要么是 0。

怎么判 -1?就是 \(|V| < |E|\)。

B - Task

考虑将环上的边定向。

考虑 \(|S_i| = 0\) 这个显然是没有贡献的。

考虑 \(|S_i| = 1\) 记 \(cnt_1\) 为顺时针的贡献, \(cnt_2\) 为逆时针的贡献。

考虑 \(|S_i| = 2\),那么这样 Alice 怎么样都可以产生贡献,那么就是 \(cnt_0\) 的贡献。

那么就是考虑将 \(cnt_0\) 分配给 \(cnt_1\) 和 \(cnt_2\) 后让其最小值最大。

\(cnt_1 + cnt_0 < cnt_2\) 的此类情况显然选择前者更优, Bob 会这样填。

否则,那么我们只能平均地填。

\[\lfloor \frac{cnt_0 + cnt_1 + cnt_2}{2}\rfloor \]

这样才是对 Bob 的最优情况。

  • 基环树

考虑延伸 B-Task 的做法。

树边显然只能选非环点,因为环上的点是已经被选中了的,直接考虑 \(S_i\) 即可。

C - Task

考虑将答案以权值的形式挂在每个点上。

首先树的话 Bob 必须要舍弃掉一个点,然后以该点为根,其它点都会放到父边上。

此时的 \(|S_i| \leq 1\),也就意味着要么该边不会产生贡献,要么只会对单个方向产生贡献。

我们会选择一个根,然后考虑贡献,这个时候是经典结论。

子树内 \(+1\) 以及子树外 \(+1\) 这样显然是取决于对于 \(u\) 的一个选择,这个差分即可。

显然的当 \(u = s_e\) 时,子树外的根迫使他走父边,所以要 +1,那另一种情况同理。

最后我们选择权值最大的作为答案就行了。注意是 A 先 B 后。

D - Task

继续考虑答案以权值的形式挂在每个点上。

这时候有 \(|S_i| = 2\) 的情况,可以对任意方向贡献权值。

考虑这时候先定向了一部分边。那么换了根即 \(u \to v\) 显然是取反了一条边的贡献。

那么我们考虑人类智慧,我们显然要取反若干条边,那么直接弄出树的直径,以中点为根,也就是说直径上的每条边它的贡献都会给两个端点之一,显然 Bob 选择二者中较大的更优,所以答案的下界是, \(\lceil \frac{len}{2}\rceil\)。

这个可以考虑画画。

考虑拼起来 C 和 D 两个 task。

把 \(|S_i| = 2\) 的边弄成 1,把其他的弄成 0,然后再加上 \(w_u\),这样就跑一个最后求出该树的带权直径大小除以二上取整的结果就是答案。

Conclusion

搬运题解都好难啊。然后拼起来 ABCD 就是对的。

题外话 : 2023.4.24 恭喜 Cust10 以 3.84KB 优异长度通过此题。

标签:cnt,Task,P9170,贡献,填数,贺题,显然,考虑,Bob
From: https://www.cnblogs.com/Custlo/p/17520813.html

相关文章

  • loj3959. 「联合省选 2023」填数游戏
    有意思的题,做这题的时候也发现了不少有趣的东西虽然不会做。考场上没有看出来建图。事实上本题复杂的性质基本决定它需要一步图论转化,而互不相同也是一个经典限制。可以得到如下建图转化:对于集合\(T_i\)的两个数,在它们之间建立无向边,用定向表示选择,则我们需要给边定向使得每个......
  • 【NOIP2015】【Luogu2615】神奇的幻方(模拟填数)
    problem给一定n*n的矩阵,要求填上1~n*n的数,使之每行、列、对角线的和都相等。n为奇数时,按如下步骤构建:1.若(K−1)在第一行但不在最后一列,则将K填在最后一行,(K−1)所在列的右......
  • 蛇形填数
    蛇形填数题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。如下图所示,小明用从1开始的正整数“蛇形”填充无限大的矩阵。126715.......
  • 【题解】[FJOI2017]矩阵填数
    题目分析:最大值为\(v\)的限制显然可以转化为\(\lev\)的方案数减去\(\lev-1\)的方案数。因为这里有很多个这种限制所以直接容斥就好了,具体来说就是枚举哪些条件取......
  • 蛇形填数——蓝桥杯(简单)
    题目描述如下图所示,小明用从 11 开始的正整数“蛇形”填充无限大的矩阵。  容易看出矩阵第二行第二列中的数是 55。请你计算矩阵中第 2020 行第 2020 列的数......
  • 蛇形填数(矩阵)
    蛇形填数      在nxn方针里填入1,2,...,nxn,要求填成蛇形。例如:n=4时方阵为:10111219  161328  151437    6  54上面的方阵中,多余的空格只......
  • NYOJ 33 蛇形填数——————思维
    蛇形填数时间限制:3000ms|内存限制:65535KB难度:3描述在nn方陈里填入1,2,…,nn,要求填成蛇形。例如n=4时方陈为:10111219161328151437654输入直接输入方陈......