gpt4 book ai didi

洛谷P10693

转载 作者:撒哈拉 更新时间:2024-07-22 12:59:36 57 4
gpt4 key购买 nike

洛谷P10693 好奇怪的题目编号 。

思路提取

input 11 2 13 4 5 3 7 9 9 11 11 12 output 9 。

以人造数据为例。 首先我们让\(i\)\(\to\)\(a_i\)连边,整个分三种情况(对应图中三部分).

  • 第一部分:\(i\)坐到了\(a_i\)(\(a_i\)\(\le\)\(n\))这个位置,那么\(a_i\)就没有地方坐了,他只能坐到他心仪的位置,也就是\(a_{a_i}\)(\(a_{a_i}\)\(\le\)\(n\)),以此类推,如果最后一个人\(k\)心仪的位置是\(i\),也就是\(a_k=i,\)也就是他坐回了\(i\)这个位置,也就是他又连向了\(i\),也就是形成了一个环,那么环上的所有人都可以做到心仪的位置上去,且最终把环上所有人原来的位置(即庆典设计师设计的位置)都占满了,不会影响到环外的人,所有环都是如此,环的大小均可加入答案中.

  • 第二部分:注意到第一部分有两个细节\(a_i\)\(\le\)\(n\)和\(a_{a_i}\)\(\le\)\(n\),那么如果大于了呢?那就连不下去了,就会出现链的情况,链中的所有人也都可以坐到心仪的位置,链的长度也都可加入.

  • 第三部分:前两部分其实都有一个潜在的前提,就是所有人心仪的位置都不重复,那如果重复了呢?就会变成第三部分。第三部分就注定有人坐不到心仪的位置,那么要取最大的,我们可以发现第二部分其实是第三部分的特殊情况.

最后此篇关于洛谷P10693的文章就讲到这里了,如果你想了解更多关于洛谷P10693的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

57 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com