Difference between revisions of "2018 ACM-ICPC Asia Qingdao Regional Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 14: Line 14:
  
 
Solved by Xiejiadong. 00:47:23(+)
 
Solved by Xiejiadong. 00:47:23(+)
 +
 +
题意:可以进行两次区间反转操作,变成目标串的方案数。
 +
 +
题解:只有两次操作,显然,最多由两段不连续的不同,否则无法达到。
 +
 +
如果由两段不连续的不同,方案数为$6$,样例就给出了。
 +
 +
如果由一段连续的不同,显然,其中两个端点是这个区间的端点,另两个端点应该连续或者相同,那么方案数就是$2*(n-1)$。
 +
 +
如果没有任何的不同,那么方案个数就是把一模一样的一段重复两次,方案数就是$\frac{n*(n+1)}{2}$。
  
 
== Problem D ==
 
== Problem D ==
Line 22: Line 32:
  
 
Solved by Xiejiadong. 02:26:09(+1)
 
Solved by Xiejiadong. 02:26:09(+1)
 +
 +
题意:每次可以小车可以从位置$0$开始,每次向左或者向右浇灌一个位置一个单位,每个位置获得浇灌都能获得$a[i]$的价值,现在最多只能移动$m$次小车,使得价值最低的位置最高,求这个价值。
 +
 +
题解:显然地二分答案。关键就是怎么验证答案。
 +
 +
二分答案以后,我们可以做一个转换,变成每一个位置最少需要浇灌几次。
 +
 +
比较容易发现,每次做一段,来回做一个区间的价值,其实可以直接在相邻的两个之间移动达到。
 +
 +
这样,我们就不断的利用后一个位置来把前一个位置浇灌完成,统计个数是否$\ge m$即可。
 +
 +
这道题目非常坑的一点是,统计次数的时候,中间过程会超过$long long$。
  
 
== Problem F ==
 
== Problem F ==

Latest revision as of 12:34, 17 November 2018

One,Two,Three,AK

Xiejiadong:罚时的锅全是我的。

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Xiejiadong. 00:47:23(+)

题意:可以进行两次区间反转操作,变成目标串的方案数。

题解:只有两次操作,显然,最多由两段不连续的不同,否则无法达到。

如果由两段不连续的不同,方案数为$6$,样例就给出了。

如果由一段连续的不同,显然,其中两个端点是这个区间的端点,另两个端点应该连续或者相同,那么方案数就是$2*(n-1)$。

如果没有任何的不同,那么方案个数就是把一模一样的一段重复两次,方案数就是$\frac{n*(n+1)}{2}$。

Problem D

Solved by oxx1108. 01:30:36(+1)

Problem E

Solved by Xiejiadong. 02:26:09(+1)

题意:每次可以小车可以从位置$0$开始,每次向左或者向右浇灌一个位置一个单位,每个位置获得浇灌都能获得$a[i]$的价值,现在最多只能移动$m$次小车,使得价值最低的位置最高,求这个价值。

题解:显然地二分答案。关键就是怎么验证答案。

二分答案以后,我们可以做一个转换,变成每一个位置最少需要浇灌几次。

比较容易发现,每次做一段,来回做一个区间的价值,其实可以直接在相邻的两个之间移动达到。

这样,我们就不断的利用后一个位置来把前一个位置浇灌完成,统计个数是否$\ge m$即可。

这道题目非常坑的一点是,统计次数的时候,中间过程会超过$long long$。

Problem F

Solved by oxx1108. 04:03:37(+2)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by dreamcloud. 00:52:53(+)

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Solved by Xiejiadong. 00:21:53(+2)

不怎么温暖的签到。

签到失败。

统计数位对应的权值和,要注意$0$的问题。