6
周五晚上又闲了,再开场gym
2023-2024 ACM-ICPC Latin American Regional Programming Contest
D
模拟
B
黑板上有3n个数字,先手每次可以选一个数,后手每次可以选一个数,再删一个数,游戏进行 n轮,黑板上没数了,游戏结束。如果先手选的数的和与后手不一样算后手赢,否则先手赢。
结论是如果每种数字的个数都是3的倍数,后手赢,否则先手赢。后手赢很显然,问题主要是要在其他情况下构造先手赢的方案。
注意到如果某个时刻,后手选的数第一次跟先手不一样了,那么先手无脑选最大/最小就能获胜。因此后手被迫每次都选跟先手一样的。因此,如果某时刻局面出现了存在一个唯一的数,先手就赢了。其次在发现,如果不是每种数字的个数都是3的倍数,先手可以保证操作后仍然不是每种数字的个数都是3的倍数。因此再最后一次操作只剩3个的时候,一定有某个数之出现了一次。选他就可以了。
I
把一个1e5小写字母字符串重复1e12次,求逆序对数
是一个等差数列求和。
M
n1e5m1e5无向图,有正边权,给定一个起点P和目标点G,你要找出所有的终点T满足:P到T的最短路是P到G的最短路长度的两倍,并且P到T的所有最短路都经过G。
把最短路DAG跑出来,然后\(dp[i]\)表示从P到i的最短路是否一定经过G。
F
给定一个N1e12,求所有的2<=b<N满足N在b进制下不考虑前导0是一个回文串。
两种情况:N在b进制下大于2位、N在b进制下恰有两位。前者跑根号log的暴力,后者对N分解质因数。
C
一个n4e5序列,每个位置有一种颜色,颜色1到k,k4e5。求最长的子段满足子段种k种颜色的个数相等。输出子段长度。
这个k种颜色个数相等,等价于k种颜色的前缀和数组相减之后等于同一个数。对k种颜色的前缀和数组再做差分,等价于这个前缀和的差分数组完全相同。用哈希维护。
G
给定平面上n1e5个曼哈顿圆(斜正方形,只包含边缘不包含内部),求这些圆的交(输出同时在这n个斜正方形上的所有点)。
曼哈顿圆实际上是4条线段,写一个线段求并就行。
J
n1e5的树,对每个点求最近的比它的标号更大的点。距离相同取标号最小。
淀粉质
下面是补题。其实下面有好几道都可做,但是敲不过来了,最后两个小时砸在HK俩若至题上了。
H
几乎是半平面交模板。但是一直写不对,有点破防。
整理一下半平面交的细节:
要加无穷远边框
用双端队列维护,两边都要弹栈
加完最后一条边之后两边要弹栈
要处理斜率相同的情况,因为这会导致两条直线没有交点。不想麻烦可以在算法开始前扫一遍去重。
K
难道我真是若至?
给定n300序列,每个位置是1到k300的数字。找一个1到k的排列满足它不是这个序列的子序列,或者输出不存在。
首先,由于1+2+...+25>300,k>=25一定有解。找解只需要每次贪心的跳序列自动机最远的点,很容易证明这样可以。
k<=24,考虑状压dp。设\(dp[s]\)表示s这个集合内的数字构成的所有排列中,在序列上对应的最近位置最远在哪里。然后转移\(dp[s]=\max_{i\in s}nextpos[dp[s-\{i\}]][i]\)。\(nextpos[i][j]\)表示\(i\)后面第一个\(j\)在哪里。没有就是\(n+1\)。然后这个dp是\(O(k2^k)\)的,但是很神奇的能过,应该是常数小。
L
好题。
给一个2e5字符串,定义合法串:
纯字母串视为变量,合法。
合法串套层括号合法
两个合法串A,B,则AcB合法。c是+、-、*、/
求给定串里有多少个子段是合法的。
这个题乍一看是牛马模拟,其实看了题解发现这个真是好题,相当考验简化问题的能力。
首先注意到所有字母换成a不影响,所有运算符换成+不影响。现在串里面只有a+()四种符号了。
然后注意到合法当且仅当:
串不以+开头或结尾
串内部括号是合法括号序列
串内没有以下七种子串:(), (+, +), ++, )(, )a, a(
那么我们把全串按照七种不合法字串的出现位置断开,断成很多截,每一截就没有不合法字串了,只需要考虑前两种限制的计数。这个就相当简单了,CDQ分治,或者二分rmq之类的都可以做。
E
n3e5树,根是R给定。然后选点,每个点必须在父亲选后才能选。假定选点顺序是排列\(p\),最大化\(\sum_{i=1}^ni\times p_i\)。
什么陈年老提还考,经典的树上并查集根爹合并的老套路。
A
【Lazytag】