当前位置: 首页 > news >正文

CF2155 Codeforces Round 1056 (Div. 2) 游记(VP)

省流

连蒙带猜拼尽全力 \(4t\),表现分 \(2000\)

10.16

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

翘课了,结果刚开始 \(vp\) 就被发微信找过来,再也不敢翘这种点名的课了。下午带着电脑去补题。

赛时

A 题按题意模拟,省略。
B 题给了一个 \(2 \leq n \leq 100\) 的矩阵,要求往矩阵中填上下左右,人到这个格子就会按照矩阵中的方向走,要求构造一种恰好有 \(k\) 个格子可以走出矩阵的。发现如果用两个箭头互相对着就走不出去,于是把两个互相对着的箭头放在左上角,然后挨个遍历把剩下不能出去的点都指向左上角就行。那么只有当 \(n * n - k\) 恰好为 \(1\) 时无解,以及 \(k = n\) 时就不放一开始的两个箭头。\(13min\) 通过。
C 题给了一排人,每个人只能让左侧的别人或右侧的别人看到,这个人永远能看到自己。给出每个人能看到几个人,问有多少种可能,对一个诡异的数取模。一开始看到题想着应该是 \(dp\),然后考虑转移。发现对于每两个人只有四种情况,然后状态就记录当前最后一个人是左侧人还是右侧人,然后根据情况转移。此时发现情况数其实不会增加,所以答案只有 \(0\)\(1\)\(2\)。然后发现不过样例,因为两个人的差虽然满足,但最后整体的总数可能不满足,但是转移中间记录总数又有点麻烦。考虑答案数量,所以只有第一个人是左人还是右人两种可能,然后按照差值把整个序列存下来,最后再验证一下总数就行了。因为中间差不可能的情况没有提前退出挂了一发,\(38min\) 一发罚时通过。
D 题是交互题,给了 \(n\) 个电池,每次可以选两节电池,如果两节电池都有电就算成功。其中有未知的 \(a\) 个有电的电池,总测试次数不能超过 \(\frac{n^2}{a}\) 次。因为这个东西永远只能两个两个试,所以猜测肯定又是和概率随机这种东西相关。然后想到一个测试过的电池有电的概率就会比别的电池低,于是大胆猜测用两个当前测试次数最少且之前没一起测过的电池就行。用 \(set\) 很容易实现,一发通过于 \(53min\)
E 题是给了一个 \(n * m\) 的矩阵,矩阵中有 \(k\) 个点,每个点可以先往左走一列,然后往上下左这三个方向随便走,不能重复,在走过的地方都留下一个新点。两个人轮流走点,问谁最后动不了另一个人赢。一开始先想广泛的,只有一列肯定后手赢,有两列则看第二列的奇偶性。然后想到第三列的数可以任意变化第二列的奇偶性,于是最后一个走最后一列的必胜,也就是只看最后一列的奇偶性。然后特判一下行数为 \(1\) 的,就是每一列往前走的所有列的贡献之和加 \(1\) 就是这一列的贡献之和,然后就可以计算总行动次数,根据奇偶性就可以得到结果了。交上去挂了几发,因为我对前面的想法怎么都找不出问题,所以把精力花在看实现上,找出了几个行数为 \(1\) 时的错误,但也没有通过第二个测试点,比赛就结束了。

赛后

看了 E 的题解,发现题解中说只要有一列是奇数就先手胜,非常懊恼。因为先手并不一定要第一步取最高位,而是可以取最高奇数位并把所有位都变为偶数个,然后后手全偶数就必败了。
看了 D 的正解,是利用鸽巢原理,遍历一段中至少出现一个好电池,再每个遍历所有电池,就可以 \(n * \frac{n}{a}\) 次必定得到了。

2025年10月16日

http://www.hskmm.com/?act=detail&tid=32298

相关文章:

  • 【隐语SecretFlow社区】万字长文解读构建可信数据空间相关标准
  • Android四大组件之Servers、BroadcastReceiver、ContentProvider(内容提供者)
  • 2025年智能装备与机器人国际学术会议(IER 2025)
  • 编程计算定投黄金的收益率
  • 客户管理软件是什么?深度解析及标杆产品推荐
  • openresty开发lua-resty-openssl之rsa公钥加密私钥解密 - liuxm
  • 2025年6款主流CRM系统详解
  • 动手动脑及实验性问题总结
  • 华为云rds pg 11升级17
  • 盘点2025破碎仪厂家/提供研磨处理方案的厂家
  • 全球顶尖的医疗器械CRM软件(深度对比)
  • uni-app x开发商城系统,tabBar
  • Delphi TscGPPageControl动态创建新页面与加载Frame框架
  • 静态方法访问类的实例成员
  • 2025年冷冻研磨仪厂家,研磨仪厂家排行,知名品牌介绍
  • 组织研磨仪厂家品牌推荐/知名品牌,组织研磨仪哪家好?
  • The World of Torrents (How it Works?)
  • 进口微量粘度计代理商推荐,优质供应商分享
  • 10月16日
  • 进口高温高压粘度计优质供应商,粘度计代理商推荐
  • Apache Doris 内部数据裁剪与过滤机制的完成原理
  • 2025 年循环烘箱厂家推荐榜:热风循环烘箱厂家聚焦节能智能,这家企业成多行业优选
  • 10.16
  • 2598. 执行操作后的最大 MEX——模运算
  • 2025通风天窗厂家推荐正鑫,专业定制工业厂房通风排烟系统
  • 阿里面试:Redis挂了怎么办?集群 节点挂,怎么 恢复数据? 多长时间 的数据 可能 丢失?
  • Ubuntu 上安装 PHP 环境
  • 2025年工业陶瓷厂家 TOP 企业品牌推荐排行榜,工业陶瓷,氧化铝陶瓷推荐这十家公司!
  • 2025年石墨干燥机厂家推荐榜:真空干燥机/振动流化床干燥机/闪蒸干燥机高效环保成主流,这家企业凭实力登顶
  • 2025年空调系统/锅炉房运维服务厂家最新权威推荐榜:专业托管运维与设备维修外包服务深度解析