Difference between revisions of "2019 Multi-University,HDU Day 7"
| Line 146: | Line 146: | ||
题解：设从 $l$ 到 $r$ 的期望为 $g(l,r)$，只要发现这种期望满足减法，也就是 $g(l,r)=g(1,r)-g(1,l)$，这道题就做出了一半。 | 题解：设从 $l$ 到 $r$ 的期望为 $g(l,r)$，只要发现这种期望满足减法，也就是 $g(l,r)=g(1,r)-g(1,l)$，这道题就做出了一半。 | ||
| − | 对每一层，我们可以根据 $p_i$ 算出回到 $x_i$ 的期望次数 $a_i$，那么从 $i$ 层到 $i+1$ 层的期望就是 $a_i \cdot (g(x_i,i)+c_i)+c_i$。从小到大算出每一个 $g(1,i)$ | + | 对每一层，我们可以根据 $p_i$ 算出回到 $x_i$ 的期望次数 $a_i$，那么从 $i$ 层到 $i+1$ 层的期望就是 $a_i \cdot (g(x_i,i)+c_i)+c_i$。从小到大算出每一个 $g(1,i)$，对每个询问输出 $g(1,r)-g(1,l)$。 |
Revision as of 08:01, 11 August 2019
Problem A
Solved by Xiejiadong && Kilo_5723.
题意：给定 $a,b,c$，求 $n,m,k$ 使得 $a\cdot 10^n+b\cdot 10^m=c\cdot 10^k$。
Kilo_5723: 我们发现，补零到 $a,b,c$ 长度相等之后，可能的情况只有四种：$b \mid (c-a),b \mid (10\cdot c-a),a \mid (c-b),a \mid (10\cdot c-b)$。逐个判断。
Xiejiadong:
首先我们把 $a,b,c$ 末尾的 $0$ 都去掉得到 $A,B,C$ ，方便处理。去掉的 $0$ ，我们显然是和以通过调整相对大小补回来的。
我们考虑 $C\cdot 10^k$ ， $k>0$ 的情况只存在于 $A+B$ ，因为如果是 $A\cdot 10^n+B=C\cdot 10^k(n>0,k>0)$ 的情况，显然 $B$ 的末尾是存在 $0$ 的，这和我们上面已经去掉了末尾的 $0$ 矛盾。
那么接下来，显然就是 $k=0$ 的情况，这样的话，显然 $n=0$ 或者 $m=0$ ，因为 $C$ 的最后以为是非 $0$ 的。
确定一个数和 $C$ 末尾对齐以后，另一个要么是和 $C$ 首位对齐，要么就是和 $C$ 第二位对齐（发生了进位）。
还有一种情况是， $A$ (不失一般性)和 $C$ 长度相等，这个时候 $B$ 的位置是不确定的，但我们可以通过从 $A$ 的末尾开始和 $C$ 比较，不相同的最后以为就是 $B$ 的末尾所在的位置。
Problem B
Problem C
Solved by Xiejiadong.
题意：对于一个字符串 $s$ 的子串 $s'$ ， $f(s')$ 的值就是把 $s$ 中所有的 $s'$ 完整出现过的位置中 $s'$ 的每一个字符出现过的位置全部拿出来，所得到的线段条数。求满足 $f(s')=k$ 的字典序最小的串。
题解：$f(s')$ 就是把 $s'$ 出现过的位置的集合拿出来，如果相邻两个位置之差不超过 $|s'|$ ，显然对答案的贡献 $+1$ 。
于是我们用 SAM 跑出 endpos 集合，然后想办法维护相邻元素的差。
满足 $f(s')=k$ ，一定是 endpos 集合中第 $k$ 大元素满足大于 $|s'|$ ，因为这样的话，可以保证出现的位置中一定有至少 $k$ 个重合，如果有 $k+1$ 大，还需要满足第 $k+1$ 大的间隔小于等于 $|s'|$ 。
考虑用主席树维护间隔。
SAM 跑出后缀树以后，按照 dfs 序编号，然后自底向上维护 endpos 集合。 endpos 集合需要启发式合并，每次插入一个新的元素，维护插入新元素以后所产生新的间距，在主席树上修改就好了。
需要的是字典序最小的串，所以我们建立 SAM 的时候需要按照字典许大小插入。
在符合要求的位置打上标记，显然同一个位置，我们一定选择长度最短的。
按照字典序 dfs 找到第一个符合要求的输出即可。
主席树内存需要比较大，但开的太大程序又跑得慢，需要卡一卡。
Problem D
Solved by Xiejiadong && Kilo_5723.
感谢 Kilo_5723 重写凸包， F0RE1GNERS 的凸包锅了，让我自闭了一晚上。
题意：要求支持加点、删点、求最小的点积。
题解：最小的点积的两个点一定都在凸包上。
简单证明：假设里两个点都不在凸包上，考虑把一个点换成凸包上的点（不动的那个点），不管你是要点积最大还是最小，你都可以把那个不动的点跟原点拉一条直线，然后把所有的点投影到这条直线上，要找的无非就是这条直线最前面或者最后面的两个点。这两个点不可能是不在凸包上的点。同理我们可以把另一个点移到凸包上。
于是这道题目变成了动态维护凸包。但是数据保证是随机的。
- 随机可以保证凸包上点的个数的期望是 $logn$ ，每次加点把原来凸包和新的点跑凸包；
- 删掉凸包上点的概率是 $\frac{logn}{n}$ ，出现这种情况的时候，暴力重建，重建次数是 $\frac{qlogn}{n}$ 。
于是总的复杂度是 $O(qlog^2n)$ 。
Problem E
Solved by László Tóth
论文名称： Counting Solutions of Quadratic Congruences in Several Variables Revisited
László Tóth
Journal of Integer Sequences, Vol. 17 (2014), Article 14.11.6
复现了波论文。
Problem F
Solved by Kilo_5723 && Xiejiadong.
题意：求复习最少需要的时间，使得无论试卷怎么分布都能至少做出 $k$ 题。
题解：
Xiejiadong：大概想了想，很难想清楚。但一定和 $\frac{m}{n-k+1}$ 有关，然后看了眼样例，猜了个结果，就对了。于是怂恿出题人改了改样例。
Kilo_5723：换位思考，考虑如果我们是出题人会怎么让学生做不出 $k$ 题。
显然，我们会挑出学生复习得最少的 $n-k+1$ 道题，让每道题的难度都等于他复习的时间。
因此，回到学生视角，我们要让自己复习的最少的 $n-k+1$ 题复习时间总和 $>m$，构造方式显然。
Problem G
Solved by Xiejiadong.
题意：钱在一个区间 $[a,b]$ 内（未知），每次可以选择取 $x$ 元钱：
- 如果卡内余额不足 $x$ ，花费 $b$ ，卡内余额不动；
- 如果卡内余额大于 $x$ ，花费 $a$ ，卡内余额减少 $x$ 。
题解：可以发现，区间是没有用的，可以调整成 $[0,r-l]$ 。
但是又会发现，本来 $0$ 开头的的和本来不是 $0$ 开头的计算方式不同。
可以先二分确定对当前区间取钱的近似最优位置，然后暴力找。
也可以直接三分确定最优位置。
确定最有位置的方法是计算取 $mid$ 的时候，两边哪边花费比较大就向哪边倾斜，以获取平衡的最小代价。
Problem H
Solved by Weaver_zhu.
Problem I
Solved by Kilo_5723.
题意：求三维任意柱体体积交。
题解：我们只关心两个多边形被 $y=y_0$ 直线截取的长度 $len(y_0)$ ，因此把两个多边形都按照节点 $y$ 坐标排序，统计有向边的斜率和，特判有向边与 $y=y_0$ 平行的情况。
我们发现， $len(y_0)$ 是一个分段函数，且每一段都是一次函数。
现在，我们要求 $len1(y_0)\cdot len2(y_0)$ 的积分，可以从左到右枚举两个函数的每一段，然后求两个一次函数的积分，加到答案里。
注意在统计斜率和时，要删除已经不在答案中的有向边。
Problem J
Solved by Kilo_5723.
Problem K
Solved by Kilo_5723.
题意：从第 $i$ 层花费 $c_i$ 有 $p_i$ 的概率上升到 $i-1$ 层，否则会回到第 $x_i(x_i\le i)$ 层，每次询问求从第 $l$ 层上升到第 $r$ 层的期望花费。
题解：设从 $l$ 到 $r$ 的期望为 $g(l,r)$，只要发现这种期望满足减法，也就是 $g(l,r)=g(1,r)-g(1,l)$，这道题就做出了一半。
对每一层，我们可以根据 $p_i$ 算出回到 $x_i$ 的期望次数 $a_i$，那么从 $i$ 层到 $i+1$ 层的期望就是 $a_i \cdot (g(x_i,i)+c_i)+c_i$。从小到大算出每一个 $g(1,i)$，对每个询问输出 $g(1,r)-g(1,l)$。