Petrozavodsk Winter-2018. ITMO U 1 Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 64/164 | 4 | 7 | 12 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by
题意¶
题解¶
C¶
solved by Snakes & JLK
题意¶
交互题。
交互器有一块 \(1\) 单位巧克力。玩家与交互器轮流依次进行 \(n\) 轮，\(n\) 为奇数，玩家先手。
每轮主动方选取对方某块 \(c\) 单位巧克力，将其分为两块并取走其中一块，且主动方取走 \(c'\) 单位巧克力需满足 \(c'\in\left[{c\over 3},{2c\over 3}\right]\)。
交互器作为主动方时会选择玩家持有的最大的巧克力，并取走其 \(2\over 3\)。
玩家需保证 \(n\) 轮结束后持有巧克力总量不小于 \(0.55\) 单位。
\(1\leq n\leq 30\)。
题解¶
若交互器在最后一轮持有一块不小于 \(2\over 3\) 的巧克力，且玩家持有巧克力总量不小于约 \(0.11\)，即可在最后一轮选取交互器最大巧克力的 \(2\over 3\) 确保玩家持有总量不小于 \(0.55\)。
为了使玩家前 \(n-1\) 轮结束后持有巧克力总量最大，需要使各块巧克力大小尽可能平均，防止被偷家。
因此玩家策略是第一轮选取交互器唯一一块巧克力的 \(1\over 3\)，接下来每轮选择除 \(2\over 3\) 外最大一块巧克力的 \(2\over 3\)，在最后一回合选择 \(2\over 3\) 的 \(2\over 3\) 偷家。
不难发现依次经过交互器与玩家两轮后最坏情况玩家最大的一块巧克力 \(a\) 变成了 \(a \over 3\) 与 \(4a\over 9\)，模拟 \(14\) 回合即 \(28\) 轮可以发现玩家持有巧克力总量满足要求。
D¶
solved by JLK
题意¶
有\(2^n\)个人比赛，每个人有一个互不相同的rating，每次两两配对比赛，rating高的人获胜进入下一轮，低的人淘汰，共进行\(n\)轮。你的rating是第\(K\)高的，问你进行比赛轮数的期望值。
\(1 \le n \le 10,1 \le K \le 2^n\)
题解¶
可以把比赛过程看做一个满二叉树，每个人在叶子结点，在每个非叶子节点进行了一次比赛。
枚举轮数。假设至少进行\(i\)轮，求这样的概率。那么首先至少有\(2^i-1\)个人rating比我小，并且排在二叉树里离我比较近的\(2^i-1\)个位置。而剩下的人则随意排列。由于相对顺序会有影响，钦点我是第一个叶子结点，而剩下的人的位置不固定。这样的方案数为\(A_{2^n-K}^{2^i-1}\times (2^n-2^i)!\)，概率为\(\frac{A_{2^n-K}^{2^i-1}\times (2^n-2^i)!}{(2^n-1)!}\)。
保底会参加一轮，然后每次累加期望即可。
此题输出小数，对精度有要求。我采用的是边乘边除的方式。
E¶
upsolved by Snakes
题意¶
\(n\) 人比赛决出 \(1\) 名 winner。
每人有互不相同的 rating，二人依照 rating 决出胜负。
每轮比赛两两随机分组，每组保留胜者进入下一轮比赛。未能匹配者直接进入下一轮。这意味着若 \(n\) 人参加当前轮就有 \(\lceil n/2\rceil\) 人参加下一轮。
求不同比赛方案的数量。比赛方案不同指存在 \(a,b\) 二人在比赛某一轮中被分在同一组，但在另一比赛所有轮中并未被分在同一组。
答案对 \(2^{64}\) 取余。
\(1\leq n\leq 10^{18}\)。
题解¶
不难得到所求答案为 \(\prod_{i=0}^{\log_2 n} f\left(\lceil{n/2^i}\rceil\right)\)，其中 \(f(n)=(n-[2|n])!!\)。
问题转化为自然溢出下求奇数的双阶乘，因此无需考虑 \(2\) 作为因子的情况。
考虑倍增，若求 \(n!!\)，设小于 \(n\) 的最大的 \(2\) 的幂次为 \(b\)，再令 \(a=n-b\)，则：
不难发现 \(2|b\)，因此 \(b^{64}\equiv 0\pmod {2^{64}}\)，求和上限只需取到 \(63\) 即可。
设：
则 \(n!!=f(n,0)\)，\(f(a,i)=g(1,a,i)\)。特殊地，若 \({\lceil (b-a+1)/2\rceil -i}=0\)，取 \(g(a,b,i)=1\)。
类似上式，容易得到：
同样地，求和上限只需取到 \(63\) 即可，递归计算并保存所有计算结果即可求得 \(n!!\)，边界条件 \(f(1,0)=f(1,1)=1\)。
\(n\) 相同的 \(f(n,*)\) 可一并计算，由 \(f(b-1,*)\) 与 \(f(a,*)\) 合并到 \(f(n,*)\) 的时间复杂度为 \(O(\log^2 n)\)。
因此计算 \(n!!=f(n,0)\) 的复杂度为 \(O(\log^3 n)\)，总共需要计算 \(\log n\) 个双阶乘，因此总复杂度 \(O(\log^4 n)\)。
F¶
upsolved by
题意¶
题解¶
G¶
solved by TYB JLK
题意¶
有\(n\)个位置排成一排，\(c\)种颜色，人选择一个位置\(x\)，然后等概率随机选择一种颜色，设离人最近的这种颜色在位置\(y\)，则人移动\(|x-y|\)的距离。自主选择\(x\)，求最小期望移动距离。
\(1\le c \le n \le 10^6\)
题解¶
考虑某种颜色，则该颜色每个位置的贡献都是一段区间，用差分实现区间加等差数列即可。
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by TYB
题意¶
给出一个排列\(p\)，定义一个长度为\(n\)的字符串\(s\)是好的当且仅当\(s_i=s_{p_i}\)对\(\forall 1\le i\le n\)成立。给出一个长为\(m\)的字符串\(S\)，求\(S\)所有长为\(n\)的子串是否是好的。
\(1\le n\le m\le 5\times 10^5\)
题解¶
考虑哈希，构造一个数组\(a\)，使得\(s\)是好的当且仅当\(\sum_{i=1}^na_i s_i =0\)。由于要求某些位置两两相同，可以对每个\(a_i\)加上\(x\)，\(a_{p_i}\)减去\(x\)，\(x\)为一个随机数。以上运算都可以在模一个大质数的意义下进行，错误的概率很小，选择几个大质数，用\(NTT\)加速卷积即可。
J¶
solved by TYB
题意¶
有\(n\)个位置，每个位置上有一个数\(a_i\)，一开始人在位置\(1\)，手上的数为\(h_0\)。每次在位置\(i\)，设当前手上的数为\(h\)，人可以选择跳到\(i+a_i\)或者\(i+h\)，求跳到\(n\)的方案数。
\(1\le n\le 10^5\)
题解¶
考虑暴力，\(f_i\)表示到i的方案数，从前面满足\((i-j)%a_j\)为\(0\)的\(j\)转移，复杂度\(O(n^2)\)。
考虑每个\(f\)对后面\(f\)的贡献，用根号分治进行优化。
大于\(\sqrt n\)的\(a_i\)，可以直接暴力跳；小于\(\sqrt n\)的\(a_i\)，每种开一个差分数组转移。
注意这样会算重复，对每个位置找到下一个能跳到且\(a\)相同的位置即可。
复杂度\(O(n\sqrt n)\)。
K¶
upsolved by
题意¶
题解¶
L¶
upsolved by JLK
题意¶
有\([0,1]\)这个区间的知识，共\(n\)次机会，一个人每次选择一些内容学习，假设已经学习的（所有知识取并集）区间长度为\(x\)，那么通过考试概率为\(x\)，最后一次之前一定要通过考试。问期望学习的区间长度最短的期望。
\(1 \le n \le 10^{18}\)
题解¶
首先设每天的增量为\(a_i\)，那么\(\sum\limits_{i=1}^na_i=1\)（否则不保证能通过）。此时期望为\(\sum\limits_{i=1}^{n}(1-\sum\limits_{j=1}^ia_j)a_i\)。
打表决策点，发现从\(n\)到\(n+1\)，后面\(n-1\)个\(a_i\)是不变的，\(a_1\)被拆成了两部分。
那么可以设\(a_1\)被拆成了\(b_0,b_1\)，剩下也用\(b_i\)表示。
再记\(p=\sum\limits_{i=2}^{n}(1-\sum\limits_{j=1}^ia_j)a_i\)。
那么关于新的期望有函数\(f=b_0+(1-b_0)b_1+(1-b_0)p\)。
拆开并用\(a_1-b_0\)代替\(b_1\)，可以得到新的决策点\(b_0=\frac{a_1+p}{2}\)，也就是\(\frac{Ans_n}2\)。
带入可以得到，答案有递推式\(Ans_n=Ans_{n-1}-\frac{Ans_{n-1}^2}4\)。
场上就推到这一步，实际上这个东西在模的时候是有循环节的，大概5000位。直接暴力找到循环节就可以了。
而分母可以打表或者根据式子推出其为\(2^{2^n-2}\)。
先算出总期望，然后算分母，再算出分子即可。由于这样计算的时候分子始终为奇数，不存在约分问题。
记录¶
47min: TYB AC G
1h15min: JLK AC D
1h55min: TYB AC J
2h15min: YZW AC C
随后开了E、I、L。
E推出式子不知道如何算双阶乘。
I尝试了随机做法，TYB最后想了个假做法没写完。
L通过打表、猜想性质终于推出了式子，但不会算。
总结¶
一开始做G的时候没有想清楚，浪费了一点时间，应该先在草稿纸上推好式子或者直接求助队友。对于最后输出的问题，应该仔细读题而不是想当然。
D可能应该在第一次交之前就测一下大数据？
J当时有两种做法，应该都是对的，最后选择了空间复杂度较小，比较稳妥的做法，这个决策应该问题不大。
中期开做的人比较多的E和L，最后应该都是差一点搞出来，有点可惜。L感觉是经验不足的问题，没有想到这都能有循环节。
打完这场感觉自己确实没有数理基础……
Dirt¶
\(50\%\)
G(-1): 没注意读题，分母为1也应该输出分数
D(-1): 精度没处理好
J(-1): 找下一个相同的数写错
C(-1): 交互题没写fflush