闲话 #14: Iranian Combinatorics Olympiad 2024 Day 1 游记（迫真）

· · 生活·游记

省流：打得稀烂。

在 Codeforces 文章区里面看到了伊朗组合数学竞赛的公告。

比较早看到的，然后忘记了这回事。10.31 想起来，于是去看看比赛是啥时候，哟！就是当日 20:30^{\mathrm{UTC+8}}。于是准备开打。（Day 1 排名靠前的可以晋级 Day 2，虽然晋级了，但是只想打 Day 1，因为 Day 2 晚上有牛客。）

团队名 Totoro，成员只有我一个人。

Day 1 是 15 道算答案题，2 个小时。按照赛时开题顺序来写，标红的是答案。题面。

T1（Passed）

知识点：贪心，三位数的加法

真·签到，答案为 10+20+\cdots+100=\color{Red}{550}。

T2（错题）

似乎是错题。可以参照这里。

T13（Failed）

知识点：构造

签到题，但是大意了。答案为 \color{Red}51，我大意了算成了 50！

T14（Failed）

知识点：构造

也是签到题，还是大意了。答案为 \color{Red}199，我又大意了算成了 198，因为少加了一条边，很生气！

T6（Passed）

知识点：枚举子集

签到题。直接枚举两边选取的脚的集合，然后两边相同的和的方案数相乘之后全部相加即可。答案为 \color{Red}123。

T3（Passed）

知识点：状压 DP

直接把每一行可能的集合压成四进制数（可以使用两个二进制位表示一个四进制数），然后转移中可以暴力 dfs。答案为 \color{Red}165636900。

T5（Failed Passed）

知识点：图论，枚举子集

建图后枚举子集算出来 \color{Red}192，但是不对。Codeforces 上主流的答案也是 192，应该是英文版题目描述有误或者其他什么问题。

Upd：官方出来声明了，确实是他们出错了。我对了。哈哈！

T8（Passed）

知识点：打表

签到题。打个表或者瞪眼发现所有这样的数列逆序对均为 90，于是答案为 90+90=\color{Red}180。

T9（Failed）

知识点：位运算

答案为 \color{Red}1048576。为什么我赛时只考虑到了全 0 的情况啊，可能是题读错了。不管了。

T7（Passed）

知识点：构造

答案为 \color{Red}48，猜结论过的，证明过一段时间后补。

T11（Passed）

知识点：枚举子集，去重

直接枚举答案和路径，判断一个答案是否可行。最后记得对答案进行去重，即仅计算本质不同的圆环，答案为 \color{Red}1。

T10（Passed）

知识点：数学期望

根据期望的线性性，把每一行拆开来算。原题条件等价于该行中只出现了不超过 2 种数，概率 P=\dfrac{2^8}{4^8}=2^{-8}，故期望得分为 8\times 64P=\color{Red}2。

T4（Failed）

知识点：博弈论

不会。答案为 \color{Red}101。

T12（Failed）

知识点：构造，最优化

答案为 \color{Red}6，但是赛时不管怎么跑跑出来的答案都是 1，可能题读错了或者啥的。不管了。

T15（Failed）

知识点：构造

不会。答案为 \color{Red}39。