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

From EOJ Wiki
Jump to navigation Jump to search
Line 31: Line 31:
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
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 ==
 
== Problem F ==

Revision as of 17:14, 29 January 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

Unsolved.

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

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved.

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

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

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

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

Problem K

Unsolved.