2015 Jakarta Regional Analysis

今天我们做了亚洲区域赛雅加达赛区的题目,感觉简单题蛮多的,有四道中等偏难的题我们就不会了……感觉平时的区域赛训练只是为了保持手感,难题的突破还是需要靠刷专题的。

A. Arithmetical CAPTCHA

签到题,枚举三个符号的情况即可

B. Udin and Ucok

知识点

博弈

题目大意

有$n$个球排成一行,有两个人轮流操作,每个人每次从当前存在的球中选择一个,将它和它相邻的左右两个球(如果有相邻的)拿走,球被拿走后两边不会合并。直到一个人不能再操作为止,这个人就会输。问是否先手必胜。

做法

首先,我们可以大出sg表,在sg表打好后,我们可以发现,除了前面有几项是特殊的外,其他的都以$34$为循环节。

C. Counting Partition

未解决

D. An ICPC Problem without Statement

知识点

贪心? + 枚举

题目大意

给出$n$个数,每个数的范围为$-2 \dots 2$,再给出两个数$A$、$B$,要从这$n$个数中选择$p$个($A \leq p \leq B$),使得它们的乘积最大。输出方案。

等待Ruclion更新

E. Awesome Cipher Machine

未解决

F. Problem on Group Trip

签到题,按题意做就行

G. Dungeon Trap

知识点

最短路

题目大意

给出$n \times m$的地图,地图上有两个格子为分别为A和B,其他的格子中为$0 \dots 9$的数字,格子中数字为$0$表示该格子不能走。我们每次可以取出一个格子中的数(相应格子中的数会变为0),直到A与B不再联通后就不能再取了,问最后我们能取出的数字的和最大为多少。

做法

我们考虑最后剩余的数字和,题意相当于要使剩余的格子中的数字最小,也就是找一条从A到B的路径,使得该路径上的数字和减去该路径上的数字的最大值最小。由于每个格子上的数字不超过$9$,我们可以枚举最大值是几,之后再找出满足最大值为我们枚举的值的从A到B的最短路。为了找出这样的最短路,我们需要从A和B分别求一遍最大值不超过我们枚举的值的单源最短路,之后再将它们合并。

H. Harvest Season

未解决

I. National Disaster

J. Alien Abduction 3

未解决

K. Amplified Energy

知识点

dp + log优化

题目大意

给出n个分数组成的数列,再给出m个单独的分数,我们要从中挑出一段连续的数列,可以选择用m个单独的分数来替换其中的某几个分数(每个数只能用一次),要求替换后的数列的乘积最大,输出方案。

做法

经典的dp题目。注意n个数相乘可能会太大,由于不要求输出最大值,我们可以采用取log的方式来优化。

L. Summation and Divisor

知识点

性质

题目大意

给出$n$行,每行$m_i$个数,我们从每行中取出一个数,把它们加起来,则一共有$\prod m_i$种情况,我们要求所有情况的最大公约数

做法

我们最开始想枚举所有的情况来计算最大公约数,但是发现情况数太多,根本枚举不完。后来想到了化为判定问题的解法:我们先随便找出一个和,那么最终结果一定在这个和的约数中,因此我们只需枚举它的约数,再判定即可。

判定的方法大概为:首先,每一行模当前数的余数必须一样,其次,每行的模当前数的余数的和必须能被当前数整除。

文章目录
  1. 1. A. Arithmetical CAPTCHA
  2. 2. B. Udin and Ucok
    1. 2.1. 知识点
    2. 2.2. 题目大意
    3. 2.3. 做法
  3. 3. C. Counting Partition
  4. 4. D. An ICPC Problem without Statement
    1. 4.1. 知识点
    2. 4.2. 题目大意
  5. 5. E. Awesome Cipher Machine
  6. 6. F. Problem on Group Trip
  7. 7. G. Dungeon Trap
    1. 7.1. 知识点
    2. 7.2. 题目大意
    3. 7.3. 做法
  8. 8. H. Harvest Season
  9. 9. I. National Disaster
  10. 10. J. Alien Abduction 3
  11. 11. K. Amplified Energy
    1. 11.1. 知识点
    2. 11.2. 题目大意
    3. 11.3. 做法
  12. 12. L. Summation and Divisor
    1. 12.1. 知识点
    2. 12.2. 题目大意
    3. 12.3. 做法