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

From EOJ Wiki
Jump to navigation Jump to search
Line 51: Line 51:
  
 
Solved by Xiejiadong.
 
Solved by Xiejiadong.
 +
 +
题意:钱在一个区间 $[a,b]$ 内(未知),每次可以选择取 $x$ 元钱:
 +
 +
* 如果卡内余额不足 $x$ ,花费 $b$ ,卡内余额不动;
 +
 +
* 如果卡内余额大于 $x$ ,花费 $a$ ,卡内余额减少 $x$ 。
 +
 +
题解:可以发现,区间是没有用的,可以调整成 $[0,r-l]$ 。
 +
 +
但是又会发现,本来 $0$ 开头的的和本来不是 $0$ 开头的计算方式不同。
 +
 +
可以先二分确定对当前区间取钱的近似最优位置,然后暴力找。
 +
 +
也可以直接三分确定最优位置。
 +
 +
确定最有位置的方法是计算取 $mid$ 的时候,两边哪边花费比较大就向哪边倾斜,以获取平衡的最小代价。
  
 
== Problem H ==
 
== Problem H ==

Revision as of 10:41, 6 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:

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

Solved by La´szlo´ T´oth

论文名称: Counting Solutions of Quadratic Congruences in Several Variables Revisited La´szlo´ T´oth Journal of Integer Sequences, Vol. 17 (2014), Article 14.11.6

复现了波论文。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong.

题意:钱在一个区间 $[a,b]$ 内(未知),每次可以选择取 $x$ 元钱:

  • 如果卡内余额不足 $x$ ,花费 $b$ ,卡内余额不动;
  • 如果卡内余额大于 $x$ ,花费 $a$ ,卡内余额减少 $x$ 。

题解:可以发现,区间是没有用的,可以调整成 $[0,r-l]$ 。

但是又会发现,本来 $0$ 开头的的和本来不是 $0$ 开头的计算方式不同。

可以先二分确定对当前区间取钱的近似最优位置,然后暴力找。

也可以直接三分确定最优位置。

确定最有位置的方法是计算取 $mid$ 的时候,两边哪边花费比较大就向哪边倾斜,以获取平衡的最小代价。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Kilo_5723.