Difference between revisions of "ICL 2016"

From EOJ Wiki
Jump to navigation Jump to search
Line 39: Line 39:
 
题解:四维的曼哈顿距离可以用类似二维的方式进行切比雪夫转换。
 
题解:四维的曼哈顿距离可以用类似二维的方式进行切比雪夫转换。
  
也就是转换成 $ max\{|(x_1\pm x_2\pm x_3\pm x_4)+(x_1\pm x_2\pm x_3\pm x_4)|,|(x_1\pm x_2\pm x_3\pm x_4)-(x_1\pm x_2\pm x_3\pm x_4)|\}$ 。
+
也就是转换成 $ max\{|(x_1\pm x_2\pm x_3\pm x_4)+(y_1\pm y_2\pm y_3\pm y_4)|,|(x_1\pm x_2\pm x_3\pm x_4)-(y_1\pm y_2\pm y_3\pm y_4)|\}$ 。
 +
 
 +
用八棵线段树分别维护 $\pm$ 的八种情况即可。
  
 
== Problem J ==
 
== Problem J ==

Revision as of 10:02, 12 May 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 01:54 (+)

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 04:24 (+2)

Problem F

Solved by Weaver_zhu. 01:28 (+3)

Problem G

Solved by Xiejiadong. 00:11 (+)

Problem H

Solved by Xiejiadong. 01:45 (+1)

Problem I

Solved by Xiejiadong. 03:14 (+)

题意:支持加点、删点、和询问和一个点的曼哈顿距离最远的距离。

题解:四维的曼哈顿距离可以用类似二维的方式进行切比雪夫转换。

也就是转换成 $ max\{|(x_1\pm x_2\pm x_3\pm x_4)+(y_1\pm y_2\pm y_3\pm y_4)|,|(x_1\pm x_2\pm x_3\pm x_4)-(y_1\pm y_2\pm y_3\pm y_4)|\}$ 。

用八棵线段树分别维护 $\pm$ 的八种情况即可。

Problem J

Solved by Kilo_5723. 03:41 (+1)

Problem K

Solved by Xiejiadong. 04:07 (+)

题意:每次可以选择一个包含偶数个 $1$ 的 $0/1$ 串反转,要求构造一个方案变成目标串。

题解:对于每一个位置都是暴力的向后选取一个包含偶数个 $1$ 且满足最后一位是当前位置的子串,翻转即可。

这样做的话,显然所有的位置都是可以得到可行解。

问题主要就是最后一个 $1$ 怎么处理。显然如果前面处理完以后,最后一个 $1$ 不在它该在的位置上,这是一个不合法态。

证明这个问题的话,可以考虑一共有两个 $1$ 的字符串,且第一个位置都是 $1$ ,后面两个位置不匹配的情况。

由于翻转的时候,两个 $1$ 的相对位置不会发生变化,所以这样的状态是不可行的,上面最后一个 $1$ 的状态可以归结到这里。

Problem L

Solved by Kilo_5723. 01:22 (+1)

Problem M

Solved by Kilo_5723. 00:37 (+)