AGC016
2022/4/28 23:12:46
本文主要是介绍AGC016,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
D XOR Replace
设 \(a_{n+1}\) 为异或和,则操作等价于 swap 一个数和末尾。
将置换拆成循环,对于一个大小非 \(1\) 的循环需要 \(size+1\) 次操作,所以 \(n\) 减去大小为 \(1\) 的循环个数加上大小不为 \(1\) 的循环个数。
E Poor Turkeys
设 \([f_{i,j}=1]\) 表示想让 \(i\) 活着,则在后面某个时刻需要 \(j\) 挡刀。(换句话说就是 \(j\) 不能在之前时刻被吃掉)
考虑倒着递推,如果有一个时刻吃掉的两只鸡都要用来挡刀,那 \(i\) 就死定了;否则把没有用来挡刀的那只鸡状态改为需要挡刀。初始状态就是 \(f_{i,i}=1\)
然后最后两只鸡能共存的条件就是:这两只鸡能活下来,而且拿来挡刀的鸡的集合没有交集。
F Games on DAG
设 \(x_i\) 表示 \(i\) 的 \(SG\) 函数,对于所有 \(x_i=v\) 的 \(i\),他们内部之间不能有连边,且对于所有 \(k<v\) 都要存在一个 \(x_j=k\) 使得 \(i\) 连向 \(k\),对于连向其他点的边可以随意连。
直接做不是很好做,考虑选出所有 \(x_i=0\) 的 \(i\),其他的点必须至少连向一个点,然后这些点连出去的边可以随便连。
连完这些点以后,可以把这些点删掉,然后所有 \(SG\) 函数减一,就可以递归了。
这篇关于AGC016的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验