Difference between revisions of "2019 Multi-University,HDU Day 7"

From EOJ Wiki
Jump to navigation Jump to search
 
(25 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{#allow-groups:user}}
 
 
 
== Problem A ==
 
== Problem A ==
  
 
Solved by Xiejiadong && Kilo_5723.
 
Solved by Xiejiadong && Kilo_5723.
  
题意:给定$a,b,c$,求$n,m,k$使得$a\cdot 10^n+b\cdot 10^m=c\cdot 10^k$。
+
题意:给定 $a,b,c$,求 $n,m,k$ 使得 $a\cdot 10^n+b\cdot 10^m=c\cdot 10^k$。
  
Kilo_5723:
+
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:
+
Xiejiadong:
  
 
首先我们把 $a,b,c$ 末尾的 $0$ 都去掉得到 $A,B,C$ ,方便处理。去掉的 $0$ ,我们显然是和以通过调整相对大小补回来的。
 
首先我们把 $a,b,c$ 末尾的 $0$ 都去掉得到 $A,B,C$ ,方便处理。去掉的 $0$ ,我们显然是和以通过调整相对大小补回来的。
Line 23: Line 21:
 
== Problem B ==
 
== Problem B ==
  
Solved by La´szlo´ T´oth
+
== Problem C ==
 +
 
 +
Solved by Xiejiadong.
 +
 
 +
题意:对于一个字符串 $s$ 的子串 $s'$ , $f(s')$ 的值就是把 $s$ 中所有的 $s'$  完整出现过的位置中 $s'$ 的每一个字符出现过的位置全部拿出来,所得到的线段条数。求满足 $f(s')=k$ 的字典序最小的串。
  
论文名称:
+
题解:$f(s')$ 就是把 $s'$ 出现过的位置的集合拿出来,如果相邻两个位置之差不超过 $|s'|$ ,显然对答案的贡献 $+1$ 。
Counting Solutions of Quadratic Congruences in Several Variables Revisited
+
 
La´szlo´ T´oth
+
于是我们用 SAM 跑出 endpos 集合,然后想办法维护相邻元素的差。
Journal of Integer Sequences, Vol. 17 (2014), Article 14.11.6
+
 
 +
满足 $f(s')=k$ ,一定是 endpos 集合中第 $k$ 大元素满足大于 $|s'|$ ,因为这样的话,可以保证出现的位置中一定有至少 $k$ 个重合,如果有 $k+1$ 大,还需要满足第 $k+1$ 大的间隔小于等于 $|s'|$ 。
 +
 
 +
考虑用主席树维护间隔。
 +
 
 +
SAM 跑出后缀树以后,按照 dfs 序编号,然后自底向上维护 endpos 集合。 endpos 集合需要启发式合并,每次插入一个新的元素,维护插入新元素以后所产生新的间距,在主席树上修改就好了。
 +
 
 +
需要的是字典序最小的串,所以我们建立 SAM 的时候需要按照字典许大小插入。
  
复现了波论文。
+
在符合要求的位置打上标记,显然同一个位置,我们一定选择长度最短的。
  
== Problem C ==
+
按照字典序 dfs 找到第一个符合要求的输出即可。
  
Unsolved.
+
主席树内存需要比较大,但开的太大程序又跑得慢,需要卡一卡。
  
 
== Problem D ==
 
== Problem D ==
  
Unsolved.
+
Solved by Xiejiadong && Kilo_5723.
 +
 
 +
感谢 Kilo_5723 重写凸包, F0RE1GNERS 的凸包锅了,让我自闭了一晚上。
 +
 
 +
题意:要求支持加点、删点、求最小的点积。
 +
 
 +
题解:最小的点积的两个点一定都在凸包上。
 +
 
 +
简单证明:假设里两个点都不在凸包上,考虑把一个点换成凸包上的点(不动的那个点),不管你是要点积最大还是最小,你都可以把那个不动的点跟原点拉一条直线,然后把所有的点投影到这条直线上,要找的无非就是这条直线最前面或者最后面的两个点。这两个点不可能是不在凸包上的点。同理我们可以把另一个点移到凸包上。
 +
 
 +
于是这道题目变成了动态维护凸包。但是数据保证是随机的。
 +
 
 +
* 随机可以保证凸包上点的个数的期望是 $logn$ ,每次加点把原来凸包和新的点跑凸包;
 +
 
 +
* 删掉凸包上点的概率是 $\frac{logn}{n}$ ,出现这种情况的时候,暴力重建,重建次数是 $\frac{qlogn}{n}$ 。
 +
 
 +
于是总的复杂度是 $O(qlog^2n)$ 。
  
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
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 ==
 
== Problem F ==
Line 54: Line 88:
 
Xiejiadong:大概想了想,很难想清楚。但一定和 $\frac{m}{n-k+1}$ 有关,然后看了眼样例,猜了个结果,就对了。于是怂恿出题人改了改样例。
 
Xiejiadong:大概想了想,很难想清楚。但一定和 $\frac{m}{n-k+1}$ 有关,然后看了眼样例,猜了个结果,就对了。于是怂恿出题人改了改样例。
  
Kilo_5723:
+
Kilo_5723:换位思考,考虑如果我们是出题人会怎么让学生做不出 $k$ 题。
 +
 
 +
显然,我们会挑出学生复习得最少的 $n-k+1$ 道题,让每道题的难度都等于他复习的时间。
 +
 
 +
因此,回到学生视角,我们要让自己复习的最少的 $n-k+1$ 题复习时间总和 $>m$,构造方式显然。
  
 
== Problem G ==
 
== Problem G ==
Line 78: Line 116:
 
== Problem H ==
 
== Problem H ==
  
Unsolved.
+
Solved by Weaver_zhu.
 +
 
 +
题意:红绿灯模拟题,左转和直走有代价,右转没代价,求出远点开始向y轴正方向时走到 $(x, y)$ 的最小代价
 +
 
 +
题解:这里用了一个近似乱搞的做法。本质上看起来还是个线性规划问题,因为转向的次数是近似固定的。首先配合左转和右转,一个左转完全可以替代直走,因此我们可以准确求出笔直向前走 $x$ 步的最小代价。之后是考虑在坐标轴上,方法是枚举开局走的几步。很容易推出只有很少的走法是有意义的。比如在 $x$ 正半轴上,显然应该直接右转然后笔直走。之后再考虑第一象限。要么笔直走,再右转(尽量直走),要么右转再左转(尽量直走),要么是先右转或先直走的不停左转右转走锯齿(尽量右转)。注意这里的直走指的是我们刚刚求得的子问题。因为线性规划问题就是尽量选性价比最高的方案,所以这样搞感觉是对的?(不会证明。之后考虑其他象限,当然也是枚举开始的有效走法,比如第二象限可以左转或者直走再右转三次。然后把他转成第一象限。写法上把它们写成自问题就很好搞
  
 
== Problem I ==
 
== Problem I ==
Line 96: Line 138:
 
== Problem J ==
 
== Problem J ==
  
Unsolved.
+
Solved by Kilo_5723.
 +
 
 +
题意:两个人手里有一些牌,每张牌有一个颜色。如果一个人出了一种颜色的牌,对手就不能再出相同颜色的卡。第一个玩家先出牌,先不能出牌的人败北,现在两个人都知道对手的手里有什么牌,问谁会获胜。
 +
 
 +
题解:每个人优先出的牌的颜色肯定是场上没出过的,对方也持有的,并且两个人手中持有数量最多的牌。对方持有的越多意味着可以封掉更多的牌,而自己手里的越多意味着可以防止自己更多的牌被封掉。
 +
 
 +
因此,对所有两个人手里都持有的颜色的牌数进行统计,从大到小依次分配给第一,第二个玩家。如果此时第一个玩家手里的牌数 $>$ 第二个玩家,则第一个玩家胜利,否则第二个玩家胜利。
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by Kilo_5723.
 
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)$。

Latest revision as of 09:07, 12 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.

题意:红绿灯模拟题,左转和直走有代价,右转没代价,求出远点开始向y轴正方向时走到 $(x, y)$ 的最小代价

题解:这里用了一个近似乱搞的做法。本质上看起来还是个线性规划问题,因为转向的次数是近似固定的。首先配合左转和右转,一个左转完全可以替代直走,因此我们可以准确求出笔直向前走 $x$ 步的最小代价。之后是考虑在坐标轴上,方法是枚举开局走的几步。很容易推出只有很少的走法是有意义的。比如在 $x$ 正半轴上,显然应该直接右转然后笔直走。之后再考虑第一象限。要么笔直走,再右转(尽量直走),要么右转再左转(尽量直走),要么是先右转或先直走的不停左转右转走锯齿(尽量右转)。注意这里的直走指的是我们刚刚求得的子问题。因为线性规划问题就是尽量选性价比最高的方案,所以这样搞感觉是对的?(不会证明。之后考虑其他象限,当然也是枚举开始的有效走法,比如第二象限可以左转或者直走再右转三次。然后把他转成第一象限。写法上把它们写成自问题就很好搞

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)$。