Atcoder-AGC033C

这篇具有很好参考价值的文章主要介绍了Atcoder-AGC033C。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

看到这道题,是个博弈论,没见过树上的,于是想到在数列里的博弈论,又联想到树的特殊形式————链。

于是我们来讨论一下链的情况(对于没有硬币的点,我们就视为它被删掉了):

Atcoder-AGC033C
讨论链的情况

发现若是选择两端的点,顶点数会减一;若是选择中间的点,顶点数会减二。

现在我们站在链的角度来思考在树上选择的情况,一颗树可以看成一条链且在某些顶点上有分支的图。我们再来以这种方式来选点找找规律,发现树上的点删着删着最后总会变成一条链,且这条链是最长链的子链,于是我们把看这棵树的形式转换为其最长链(直径)且在某些顶点上有分支的图:

Atcoder-AGC033C
例子

通过手玩这个例子后发现,我们若是选最长链两端的点,最长链顶点数会减一;若是选择非最长链两端的点,最长链顶点数会减二,其余的分支会因为持续的选点而被删完。

所以发现,在树上的问题被我们转化成了在链上的问题,妙哉!

讨论完了删点的变化情况,我们再来讨论一下必胜条件:若最长链上有 \(i-1\)\(i-2\) 个点时均必胜,则最长链上有 \(i\) 个点时必败,否则必胜,特殊的,若最长链上有 \(1\) 个点时必胜,有 \(2\) 个点时必败。
打表发现用树的最长链上点的个数 \(\mod 3\) ,若等于 2 后手胜,否则先手胜。

Code:文章来源地址https://www.toymoban.com/news/detail-480039.html

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2e5 + 5;

int n, x, y, fir, sec;
int la[N], en[N << 1], ne[N << 1], idx;

void add(int x, int y) {
	en[ ++ idx] = y; 
	ne[idx] = la[x];
	la[x] = idx;
}

void dfs(int u, int f, int step) {
	for (int i = la[u]; i; i = ne[i]) {
		int v = en[i];
		if(v == f) continue;
		if(fir < step) fir = step, sec = v; dfs(v, u, step + 1);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i < n; ++ i ) cin >> x >> y, add(x, y), add(y, x);
	dfs(1, 0, 1); dfs(sec, 0, 1); 
	if((fir + 1) % 3 == 2) cout << "Second";
	else cout << "First";
	return 0;
}

到了这里,关于Atcoder-AGC033C的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【学习笔记】[AGC021F] Trinity

    第一步有点难😅 考虑加入每一列,发现我们只关心当前还未确定的行的数目 设 d p i , j dp_{i,j} d p i , j ​ 表示有 i i i 列,其中 j j j 行未确定的方案数。钦定每一列至少有一个黑色格子。 d p i , j = j ( j + 1 ) 2 d p i − 1 , j + ∑ k ≥ 1 ∑ k ≤ l ≤ j ( j − l + 1 ) ( l k ) d p i − 1 , j

    2024年02月12日
    浏览(75)
  • AGC004B Colorful Slimes

    题目链接:Colorful Slimes 思路:挺神奇的$dp$ 一个比较显然的结论:最小值的方案中第$2$种操作最多用$n-1$次 证明大概就是一个数用$n-1$次一定会变成另一个数 下面说说$dp$的思路: $dp[i][j]$表示能用最多$j$次第$2$种操作能变成$a_i$的最小值 假设$a_k$所有可以用最多$j$次第$2$种操作

    2024年02月08日
    浏览(31)
  • [AGC001E] BBQ Hard题解

    [AGC001E] BBQ Hard 计算: [sum_{i=1}^{n}sum_{j=i+1}^nbinom{a_i+b_i+a_j+b_j}{a_i+a_j}] 其中 (n leq 2 times 10^5) , (a_i,b_i leq 2000) 以 (a_i) 代 (a_i+b_i) 则等价于求 [sum_{i=1}^{n}sum_{j=i+1}^nbinom{a_i+a_j}{b_i+b_j}] 考虑使得式子变得更加对称,我们可以不限制 (i,j) 的相对大小,之后减去 (i=j) 的

    2024年02月04日
    浏览(31)
  • [AGC055A] ABC Identity 题解

    给定长度为 (3n (1 le n le 2e5)) 的序列,其中字母 A,B,C 各有 (n) 个。 一个合法序列 (T) 满足以下条件: 其长度为 (3k (1 le k le n)) 。 (T_1 = T_2 = ... = T_k) (T_{k + 1} = T_{k + 2} = ... = T_{2k}) (T_{2k + 1} = T_{2k + 2} = ... = T_{3k}) (T_1, T_{k + 1}, T_{2k + 1}) 互不相同。 求一个把这个序列分

    2024年02月08日
    浏览(49)
  • [AGC055B] ABC Supremacy 题解

    给定两个长度为  (n)  的字符串  (a) , (b) 。 你可以进行若干次以下操作: 若  (a)  中的一个 子串 为  ABC , BCA  或  CAB ,那么可以将这个子串替换为  ABC , BCA  或  CAB 。 求能否将  (a)  变成  (b) ,输出  YES  或  NO 。 不难发现,我们可以根据一些变换将 A

    2024年02月08日
    浏览(37)
  • 鸿蒙原生应用/元服务实战-AGC团队账户

    多人及内外结合去开发运营鸿蒙原生应用元服务时,需要用到团队账户,AGC提供了强大的团队角色与权限分工能力。 团队帐号是开发者联盟为实名开发者提供的多个成员帐号登录与权限管理服务。当前团队帐号支持成员参与应用市场(付费推广、应用内付费除外)开发、运营

    2024年01月20日
    浏览(40)
  • openssl3.2/test/certs - 033 - time stamping certificates

    openssl3.2 - 官方demo学习 - test - certs /*! file my_openssl_linux_log_doc_033.txt note openssl3.2/test/certs - 033 - time stamping certificates 带时间戳的证书 自己调用openssl时, 如果也要动态参数文件(不落地), 也可以参照.sh的用法, 自己建立多个参数输入的管道, 拼好配置文件内容, 再将管道名称传给

    2024年01月25日
    浏览(43)
  • 【AGC】集成APMS SDK后台无数据问题

    【 问题描述 】 开发者按照文档集成了APMS SDK,但是在AGC后台没有数据,需要帮忙定位。 【 问题分析 】 后台没有性能数据的原因有很多,要从端侧和与云侧进行定位分析。 1.     首先需要查看端侧的调试日志,调试日志可以直观的看到性能信息的收集与上报动作。 打开

    2024年02月10日
    浏览(36)
  • AD936x_增益控制AGC详解

    所有AGC模式都可用于TDD和FDD场景。AD936x具有手动增益控制选项,允许基带处理器控制接收机的增益。 上图为AD936x接收信号路径示意图,每个接收机都有自己的增益表,将增益控制字映射到每个可变增益块。无论使用AGC还是手动增益控制,指针都会在表中上下移动,从而改变一

    2024年02月03日
    浏览(36)
  • 【学习笔记】[AGC063E] Child to Parent

    提供一个多项式做法。 分别设 f u , i , g u , i f_{u,i},g_{u,i} f u , i ​ , g u , i ​ 表示以 u u u 为根时, a u = i a_u=i a u ​ = i 和 a u ≥ i a_uge i a u ​ ≥ i 的方案数,合并子树 v v v 时,转移如下: f u , i = ∑ f u , i − k r × g v . k f_{u,i}=sum f_{u,i-kr}times g_{v.k} f u , i ​ = ∑ f u , i − k

    2024年01月20日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包