Difference between revisions of "CCPC-Wannafly Winter Camp Day1 (Div 1)"

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by the same user not shown)
Line 7: Line 7:
 
不怎么温暖的签到。
 
不怎么温暖的签到。
  
题意:在平面上,有$(1,0)-(n,0),(1,k)-(n,k),(0,0)-(0,k),(n,0)-(n,k)$四条线段,以及若干$(i,0)-(i,k)$的线段。在$(1,0)-(n,0),(1,k)-(n,k)$上各有一些需要经过的点,只能在线段交点上拐弯或掉头,求出一条从给定在$(1,0)-(n,0)$上的起点出发,经过$(1,0)-(n,0),(1,k)-(n,k)$上所有给出的点,并回到起点的最短路径。
+
题意:在平面上,有 $(1,0)-(n,0),(1,k)-(n,k),(0,0)-(0,k),(n,0)-(n,k)$ 四条线段,以及若干 $(i,0)-(i,k)$ 的线段。在 $(1,0)-(n,0),(1,k)-(n,k)$ 上各有一些需要经过的点,只能在线段交点上拐弯或掉头,求出一条从给定在 $(1,0)-(n,0)$ 上的起点出发,经过$(1,0)-(n,0),(1,k)-(n,k)$上所有给出的点,并回到起点的最短路径。
  
题解:在一般情况下,最优的情况是选择两条能包含所有点的与$y$轴平行的线段构成的环,但在特殊情况下可能是由两条往返于起点的重合边与一个环构成,需要对于$(1,0)-(n,0),(1,k)-(n,k)$上有无点的情况,以及起点在$(1,0)-(n,0)$上所有点的左右两侧或是中间的情况,共$3 \times 3 = 9$种情况分类讨论。
+
题解:在一般情况下,最优的情况是选择两条能包含所有点的与 $y$ 轴平行的线段构成的环,但在特殊情况下可能是由两条往返于起点的重合边与一个环构成,需要对于 $(1,0)-(n,0),(1,k)-(n,k)$ 上有无点的情况,以及起点在 $(1,0)-(n,0)$ 上所有点的左右两侧或是中间的情况,共 $3 \times 3 = 9$ 种情况分类讨论。
  
 
== Problem B ==
 
== Problem B ==
Line 15: Line 15:
 
Solved.
 
Solved.
  
题意:有一个$n \times m$的地图,每个位置上有一个$<=10$的数字,当时刻能被数字整除时会掉落一颗糖,现在从起点出发,每秒能向上下左右移动一格,要收集到一定数量的糖后到达终点,求花费时间的最小值。
+
题意:有一个 $n \times m$ 的地图,每个位置上有一个 $<=10$ 的数字,当时刻能被数字整除时会掉落一颗糖,现在从起点出发,每秒能向上下左右移动一格,要收集到一定数量的糖后到达终点,求花费时间的最小值。
  
题解:如果糖数很小,可以用$dp$求解。因为数字$\le 10$,每$2520$秒都是一个$dp$性质完全相同的周期,因此先处理每一个位置在$2520$秒对其他所有位置的贡献,得到矩阵,再通过矩阵快速幂找到小于花费时间最小值的最大的能被$2520$整除的时刻,最后再$dp$一次找到具体位置。
+
题解:如果糖数很小,可以用 dp 求解。因为数字 $\le 10$ ,每 $2520$ 秒都是一个 dp 性质完全相同的周期,因此先处理每一个位置在 2520 秒对其他所有位置的贡献,得到矩阵,再通过矩阵快速幂找到小于花费时间最小值的最大的能被 2520 整除的时刻,最后再 dp 一次找到具体位置。
  
答案可能会超过$long long$范围,可以用大整数模板,也可以用一些其他方法表示出答案。
+
答案可能会超过 long long 范围,可以用大整数模板,也可以用一些其他方法表示出答案。
  
 
== Problem C ==
 
== Problem C ==
Line 80: Line 80:
 
Solved.
 
Solved.
  
题意:有$n$个$1 \times a_i$,下端对齐的长条,每次可以选择一个区间$[l,r]$和一个高度$h$,如果$[l,r]$内所有长条的初始高度都小于等于$h$,则取走$[l,r]$内所有长条高度$\le h$的部分。最多可以执行$k$次此操作,求能取走的长条段的最大总长。
+
题意:有 $n$ 个 $1 \times a_i$,下端对齐的长条,每次可以选择一个区间 $[l,r]$ 和一个高度 $h$ ,如果 $[l,r]$ 内所有长条的初始高度都小于等于 $h$ ,则取走 $[l,r]$ 内所有长条高度 $\le h$ 的部分。最多可以执行 $k$ 次此操作,求能取走的长条段的最大总长。
  
题解:我们考虑图形中$[l,r]$高度$h$最低的一列,这一列将整个图形分成了两部分。我们会发现,最优解有两种情况,第一种是包含取走$[l,r]$中小于等于$h$的部分,另一种不包含次操作。而无论哪种情况,剩余的操作都可以通过递归处理左右两部分找出。我们设$dp[k][i][j]$代表第$k$个区间中执行$i$次操作,取走区间中总宽为$j$的部分的最大收益,可以得出从左右子区间推到父区间的$dp$方程。如果左右子区间长度分别为$x,y$,每次状态转移都要花去$x^2 \times y^2$的时间,看似每次是$O(n^4)$的,但实际上所有转移花费的时间总和远远小于$O(n^5)$,可能是$O(n^4)$并且常数非常小,不会$TLE$。
+
题解:我们考虑图形中 $[l,r]$ 高度 $h$ 最低的一列,这一列将整个图形分成了两部分。我们会发现,最优解有两种情况,第一种是包含取走 $[l,r]$ 中小于等于$h$的部分,另一种不包含此操作。而无论哪种情况,剩余的操作都可以通过递归处理左右两部分找出。我们设 $dp[k][i][j]$ 代表第 $k$ 个区间中执行 $i$ 次操作,取走区间中总宽为 $j$ 的部分的最大收益,可以得出从左右子区间推到父区间的 dp 方程。如果左右子区间长度分别为 $x,y$,每次状态转移都要花去 $x^2 \times y^2$ 的时间,看似每次是$O(n^4)$的,但实际上所有转移花费的时间总和远远小于 $O(n^5)$ ,可能是 $O(n^4)$ 并且常数非常小,不会 TLE。
  
 
== Problem I ==
 
== Problem I ==
Line 88: Line 88:
 
Solved.
 
Solved.
  
题意:定义一个长度$=2k+1(k>=1)$的序列是好的,当且仅当其奇数项递减,且偶数项小于两边的奇数项。给出一个$n$的排列,求出其中中好的子序列的数量。
+
题意:定义一个长度$=2k+1(k>=1)$的序列是好的,当且仅当其奇数项递减,且偶数项小于两边的奇数项。给出一个$n$的排列$\{ a_n \}$,求出其中中好的子序列的数量。
  
在长途旅行的路上,坑待填。
+
题解:设$dp_i$代表以$i$为奇数项末尾的好的子序列的数量,我们会发现,$dp_i$是所有$j<i$且$a_j>a_i$的$dp_j \times (j$到$i$之间小于$a_i$的数的个数$)$。如果按$a_i$从大到小处理答案,就可以对$dp$数组直接求和,但需要乘上小于$a_i$的数的数量,因此用线段树维护$dp_i$,$i$后方还未被处理过的数的个数,和$dp_i \times (i$后方还未被处理的数的个数$)$的区间和。如此即可按$a_i$从大到小计算出每个位置的$dp_i$。
  
 
== Problem J ==
 
== Problem J ==

Latest revision as of 18:56, 24 April 2019

CCPC-Wannafly Winter Camp Day1 (Div 1)

Problem A

Solved.

不怎么温暖的签到。

题意:在平面上,有 $(1,0)-(n,0),(1,k)-(n,k),(0,0)-(0,k),(n,0)-(n,k)$ 四条线段,以及若干 $(i,0)-(i,k)$ 的线段。在 $(1,0)-(n,0),(1,k)-(n,k)$ 上各有一些需要经过的点,只能在线段交点上拐弯或掉头,求出一条从给定在 $(1,0)-(n,0)$ 上的起点出发,经过$(1,0)-(n,0),(1,k)-(n,k)$上所有给出的点,并回到起点的最短路径。

题解:在一般情况下,最优的情况是选择两条能包含所有点的与 $y$ 轴平行的线段构成的环,但在特殊情况下可能是由两条往返于起点的重合边与一个环构成,需要对于 $(1,0)-(n,0),(1,k)-(n,k)$ 上有无点的情况,以及起点在 $(1,0)-(n,0)$ 上所有点的左右两侧或是中间的情况,共 $3 \times 3 = 9$ 种情况分类讨论。

Problem B

Solved.

题意:有一个 $n \times m$ 的地图,每个位置上有一个 $<=10$ 的数字,当时刻能被数字整除时会掉落一颗糖,现在从起点出发,每秒能向上下左右移动一格,要收集到一定数量的糖后到达终点,求花费时间的最小值。

题解:如果糖数很小,可以用 dp 求解。因为数字 $\le 10$ ,每 $2520$ 秒都是一个 dp 性质完全相同的周期,因此先处理每一个位置在 2520 秒对其他所有位置的贡献,得到矩阵,再通过矩阵快速幂找到小于花费时间最小值的最大的能被 2520 整除的时刻,最后再 dp 一次找到具体位置。

答案可能会超过 long long 范围,可以用大整数模板,也可以用一些其他方法表示出答案。

Problem C

Solved.

温暖的签到

题意:给两个long long范围之内的数$A, B>=5$,求一种拆分使得$\sum_{i=1}^{n}{a_i}=A,\sum_{i=1}^{n}{b_i}=B,gcd(a_i,b_i)=1$如果有多个输出n最小的一个

思路:随机就完事了。。特判完$n=1$就随机划分成两个数直到找到解为止,不可能无解

Problem D

Unsolved.

Problem E

Solved.

题意:共有$n$个结点,第$i$个节点有一个价值$f_i$,若$i$为奇数,则$i$与$i \times 3+1$之间有边,否则$i$与$i/2$之间有边。如果一条边上两个顶点$x,y$都被取走,则损失$d_{min(x,y)}$的价值,可以取任意多的点,求可获得的最大价值。

题解:先考虑只有$i$和$i/2$之间有边的情况,可以用$dp$求解。构造一棵完全二叉树,设$dp_{i_1},dp_{i_0}$代表取或不取第$i$个节点时,$i$的子树所能取得的最大价值。根据性质,有且仅有一个节点与其左子节点之间存在边,以此构造$dp$转移方程。

接下来加入$i$与$i \times 3+1$之间的边。我们只要枚举所有的$i \times 3+1$取和不取的情况。因为$n<=100$,这样的节点不会超过$17$个,因此枚举次数少于$2^{17}$。枚举之后,只要在$dp$转移的过程中,将所有非法状态设为$-inf$,并对所有的奇数$i$,如果$i \times 3+1$已经被取,则$dp_{i_1}-=d[i]$即可。

Problem F

Solved.

签到

题意:爬山,一开始在1号山上,体力为k。每上升1m减少一点体力,下降1m增加一点体力。给出每个山的高度和它们之间的路径,可以减少山的高度,减少l花费l*l。总代价为路径长度和减少山高度的花费,求1到n的最少花费。

思路:显然体力和山的高度的和不变,所以体力根本不大需要关注。如果到点k体力不够就减少高度使得体力刚好够到k,这个花费应该加到终点为k的边的长度上。剩下的就是最短路了。

Problem G

Solved.

题意:有一个$x \times y$的大矩阵,每一个元素都是相同的$n \times m$的小矩阵,求出大矩阵中最大公约数不为$1$的最大子矩阵。

题解:最大子矩阵可能的情况一共有四种,每种情况各有一些小矩阵中的元素被选中:

$(n \times x) \times (m \times y)$:此时小矩阵中所有元素都被选中。

$p \times (m \times y)$和$(n \times x) \times q$:此时小矩阵中一些两条边界上或是中间的连续行或列被选中。

$p \times q$$(1 \le p \le n,1 \le q \le m)$:此时小矩阵中或边界上或四角上的元素被选中。

如果我们将小矩阵复制三次,构造出$2n \times 2m$的矩阵,我们可以不考虑边界情况,只考虑其中长$\le n$,宽 $\le m$的子矩阵。如果子矩阵的长$=n$则按$n*x$,宽$=m$则按$m*y$计算面积,否则正常计算面积即可。

因此,先预处理处理后的小矩阵,每一行上连续的每一段数的最大公约数,再枚举小矩阵的左右和上边界,找到最低的下边界使得矩阵所有元素最大公倍数不为$1$即可。

这种方法的时间复杂度是$O(n^4)$,花费时间会超过$800ms$,但如果先筛去所有不可能比现答案更高的枚举情况,只要花费不到$100ms$。

Problem H

Solved.

题意:有 $n$ 个 $1 \times a_i$,下端对齐的长条,每次可以选择一个区间 $[l,r]$ 和一个高度 $h$ ,如果 $[l,r]$ 内所有长条的初始高度都小于等于 $h$ ,则取走 $[l,r]$ 内所有长条高度 $\le h$ 的部分。最多可以执行 $k$ 次此操作,求能取走的长条段的最大总长。

题解:我们考虑图形中 $[l,r]$ 高度 $h$ 最低的一列,这一列将整个图形分成了两部分。我们会发现,最优解有两种情况,第一种是包含取走 $[l,r]$ 中小于等于$h$的部分,另一种不包含此操作。而无论哪种情况,剩余的操作都可以通过递归处理左右两部分找出。我们设 $dp[k][i][j]$ 代表第 $k$ 个区间中执行 $i$ 次操作,取走区间中总宽为 $j$ 的部分的最大收益,可以得出从左右子区间推到父区间的 dp 方程。如果左右子区间长度分别为 $x,y$,每次状态转移都要花去 $x^2 \times y^2$ 的时间,看似每次是$O(n^4)$的,但实际上所有转移花费的时间总和远远小于 $O(n^5)$ ,可能是 $O(n^4)$ 并且常数非常小,不会 TLE。

Problem I

Solved.

题意:定义一个长度$=2k+1(k>=1)$的序列是好的,当且仅当其奇数项递减,且偶数项小于两边的奇数项。给出一个$n$的排列$\{ a_n \}$,求出其中中好的子序列的数量。

题解:设$dp_i$代表以$i$为奇数项末尾的好的子序列的数量,我们会发现,$dp_i$是所有$j<i$且$a_j>a_i$的$dp_j \times (j$到$i$之间小于$a_i$的数的个数$)$。如果按$a_i$从大到小处理答案,就可以对$dp$数组直接求和,但需要乘上小于$a_i$的数的数量,因此用线段树维护$dp_i$,$i$后方还未被处理过的数的个数,和$dp_i \times (i$后方还未被处理的数的个数$)$的区间和。如此即可按$a_i$从大到小计算出每个位置的$dp_i$。

Problem J

Solved.

题意:$n$个人共有$m$件物品,现在一个人要购买这些物品,使得他拥有的物品数严格大于每一个人,求最小代价。

题解:从大到小枚举剩下的人中拥有物品最多的人拥有的物品数。

首先,对每个人拥有的物品按照价格降序排列,在拥有物品最多的人拥有$k$件物品时,首先,每个人拥有的下标$>k$个的物品必须全部被选上。然后,再在剩下的物品中选取最小的若干个,使得拥有的物品数量总和$>k$。因此,我们可以用$set$维护每个人拥有的下标$\le k$的物品。每次从$k$推到$k-1$时,从集合中删去所有下标$=k$的物品,全部加到答案中,再一直将集合中最大的物品弹出,直到拥有的物品总数$=k$或集合为空。

然后,对每一次的答案取$min$,就是要输出的答案。

Problem K

Unsolved.