HNOI2011解题报告
Author: Pengyihao
Day1 T1 数学作业
题意
给出正整数 \(n\), \(m\),要求将 \(1-n\) 这 \(n\) 个数连接起来,问连接起来的数对 \(m\) 取模的结果是多少。
\(1\leq n\leq 10^{18}, 1\leq m\leq 10^9\)
思路
如果连接的数的位数一样,那么可以用矩阵乘法进行优化。因为有 \[nowans = lastans * 10^k + now\]
这个恒定的递推式(对于位数一样的数),所以可以分段矩阵乘法。
因为只有 \(lg(n)\) 个位数,所以可以解决这个问题。
代码
|
|
Day1 T2 勾股定理
这个题目有点问题,我在网上看题解的时候,发现这题的做法其实是不靠谱的,意思是说这是一道玄学的题目。
对于题目所给的数据范围,标程不一定都能在合理的时间内跑出答案。
所以我就跳过了这道题目。
Day1 T3 赛车游戏
思路
首先可以用拉格朗日乘数法证明,如果要达到最优成绩,那么每条路上的速度要尽可能相等。
于是就可以二分这个速度,然后计算耗油量。
注意如果某条路上耗油量为负数,那么就不能在这条路上用当前二分的速度来计算,因为可能耗油量为负数。
所以我们可以把这条路上的速度设置为令耗油量为0的速度。
这样就可以正确地计算耗油量和跑的时间了。
代码
|
|
Day1 T4 括号修复
思路
首先对于一个括号序列,如何计算它最少需要改多少个括号呢?
我们发现如果把可以匹配的括号一层一层去掉,那么最后一定会变成下面这个样子:
))))))))(((((((((
就是左边一连串的括号,右边一连串的括号。
假设左边有 \(l\) 个括号,右边有 \(r\) 个括号。
那么一共要改
\[\lfloor \frac{l+1}{2}\rfloor + \lfloor\frac{r+1}{2}\rfloor\]
个括号。
根据“维修数列”这一题的经验,我们可以用splay来维护括号序列。
用+1表示’(‘,用-1表示’)’,那么左边的括号数量就是从左开始的最小子段和,右边的括号数量就是从右开始的最大子段和。
操作1:直接打标记。
操作2:直接打标记。
操作3:变换一下从左开始的最小、最大子段和,从右开始的最小、最大子段和。
操作4:直接取值。
怎么合并标记呢?
当打区间赋值标记的时候,可以直接清空反转标记。
当打反转标记的时候,要将赋值标记乘上-1。
代码
|
|
Day2 T1 任务调度
这是一道随机出答案的题目,所以我没有做,直接跳过了。
Day2 T2 XOR和路径
思路
这是一个简单的概率DP。
因为是XOR,所以我们可以逐位求出期望。
假设当前在处理第 \(k\) 位,设 \(f[i]\) 表示从 \(i\) 到 \(n\) 异或值为 \(1\) 的概率。
则对于 \(i\) 的一个连出去的边所指向的节点 \(j\),如果边权为 \(1\),则对 \(f[i]\) 的贡献为
\[\frac{1-f[j]}{deg[i]}\]
如果边权为 \(0\),则对 \(f[i]\) 的贡献为
\[\frac{f[j]}{deg[i]}\]
最后别忘了 \(f[n]=0\)。
代码
|
|
Day2 T3 数矩形
思路
这又是一道玄学题。
我们找到每条线段的中点,然后按照中点为第一关键字,线段的长度为第二关键字进行排序。
然后对于每个线段,暴力找前面所有跟它中点重合且长度相等的线段……
这样就可以过了。
代码
|
|
Day2 T4 卡农
思路
我们可以先算出可以记片段之间顺序的方案数,因为两两不同,所以最后除以 \(m!\) 就可以了。
设 \(f[i]\) 表示前 \(i\) 个片段满足题意的方案数。
如果前 \(i-1\) 个片段已经决定了,那么第 \(i\) 个片段也可以由奇偶关系决定了。
那么答案就为 \(P(2^n-1, i-1)\) 减去不合法的方案。
这里的 \(P(2^n-1, i-1)\) 可以递推求。
不合法的方案只有两种可能:
前 \(i-1\) 个片段已经满足偶数要求了,那么第 \(i\) 个片段必须是空集合,不符合规定。 所以要减去 \(f[i-1]\)。
被决定出来的第 \(i\) 个片段重复了。 那么与它重复的那个片段有 \(i-1\) 个位置可以选择。 并且如果除了这两个片段之外,其它的片段均满足偶数条件,那么这两个片段一定相同。 而这个片段本身也有 \(2^n-1-(i-2)\) 种可能。 所以要减去 \(f[i-2]\times (i-1)\times (2^n-1-(i-2))\)
所以就可以直接求了。
代码
|
|