看起来咕了很多题的题解,不管了。
320. cf804f Fake bullions
缩点。每个强连通分量内模 gcd 相同的点就是同一个点。因为图是个链,可以暴力转移。
321. cf833e Caramel Clouds
一开始想的是二分答案,然后是答辩分类讨论。。
考虑把数轴劈成若干个段,每一段被覆盖的集合相同。那就对于这个段的右端点求出最优解,查询的时候二分。
怎么求解?考虑两个任务,如果不交,分别记 \({c_1}_i\) 表示只有 \(i\) 覆盖的长度,答案就是 \({c_1}_i + {c_1}_j\)。否则答案是 \({c_2}_{i,j} + {c_1}_i + {c_1}_j\)。这样的 pair 不会很多,暴力维护即可。
322. cf1237g Balanced Distribution
把没有被操作覆盖的间隔劈开。对于劈开的每一段,存在 \(\lceil { len-1 \over k-1} \rceil\) 的方法。你发现,如果 \(len_1,len_2\) 有一个模 k-1 不等于 0,把它们拼起来不劣。所以答案要么是一大段,要么全都模 k-1 为 1。瞎几把倍增。
323. arc146f Simple Solitaire
会不了一点。挂个日本队长链接。
感性理解,是要数一个序列,贡献挺奇怪(?。(:。
然后瞎几把容斥,再瞎几把 dp,发现转移是个矩阵(?。):。
最后瞎几把搞起来就行了(?。):。):。
324. The 1st Universal Cup. Stage 4: Ukraine
感觉快似了,来场 ucup 冷静一下。打完感觉更似了。
A
B
E
I
K
F
D
G
J
C
N
设 \(f(x,a,b,c,d)\) 表示有多少个 -2,-1,1,2,从 1 开始走,不能走到 \(\leq 0\) 和 \(> x\) 的地方,走到 \(x\) 的方案数。发现 \(a\) 一定等于 0 ,并且每一个 -1 都一定是 2 -1 2 搭配。所以 \(f(x,a,b,c,d)\) 可以用组合数求出。
假装最终走到的点 \(>0\)。发现一旦走到了某个 > 0 的点,就一定不会走到 \(<0\) 的点了。所以 < 0 的点一定是一开始的一段,要么是 -1 2,要么是 -2 -2 -2 -1 2 2 2 2,要么是 -2 -2 1 2 2。在终点也差不多。所以枚举起点和终点的 \(O(1)\) 种状态,直接算即可。
L
很吊的构造题。
考虑奇数,令 \(n = 2k + 1\)。把所有点在模 \(n\) 意义下进行,对于每个 $i $ 依次连如下边:\((i,i+1),(i-1,i+2),...,(i-k,i+k+1)\)。发现这玩意是对的!
至于偶数,就每隔 \(n-1\) 条边把那个点瞎几把塞进来就行。
H
好像之前模拟赛做过这个题(?????。
看不懂题解,不是很想管了。
325. xsy5163 开拓(explore)
怎么又是树上打怪题。没活了是吧。
326. lg3598 Koishi Loves Number Theory
我草我们机房有原题哥。太牛逼了。
直接进行一个大力 minmax 容斥,然后发现 \(gcd(x^i - 1,x^j - 1) = x^{gcd(i,j)} - 1\)。做完了。
327. cf1305h Kuroni the Private Tutor
考虑如何判定一个两边都确定的方案是否合法?网络流,看能不能满流。发现一组割形如 \(\sum_{i \in A} a_i + \sum_{i \in B} b_i + (n - |A|)(m - |B|)\),所以是按照 \(a,b\) 分别排序,然后可以凸包 \(O(n)\) 检验。
再考虑一边确定,一边不确定。发现令 \(g ( A) = \min f(A,B)\) 是可以预处理的。所以转化成了对 \(a\) 前缀和的限制。发现可以贪心确定 \(b\),所以有一边已经确定了。
考虑原问题,相当于维护一个折线,满足和为 \(t\),每个前缀和有限制。所以加的数越前越好。这是个贪心,再拼上二分就可以了。
328. lg8969 幻梦 | Dream with Dynamic
大概是说,进行一次 popcount 操作之后,就会值域很小。所以维护一个 \(p_{u,i} ( i \leq \log v)\) 表示 \(i\) 这个,在经过 \(popcount\) 操作之后变成的数。然后大概能均摊。
329. arc145d Non Arithmetic Progression Set
一个合法的序列平移显然合法,所以只需要造出一个模 \(n\) 对的合法的序列即可。
考虑一个序列,把每个数写成三进制后只有 0 和 1,这个序列就是合法的。至于模 \(n\) 的限制,就把这个序列整体乘 3,最后一位就可以乱填了。
330. arc145e Adjacent XOR
发现对 A 差分这个事情非常蠢,不如改成对 B 前缀和。显然是从后往前做。那就相当于 \(\oplus_{j = 1} ^ i b_j = a_i\)。把 \(a_i\) 变成若干个从前往后的基的和。对于最靠后的基的位置 \(p\),如果 \(b\) 里已经有奇数个基,就不用管了。如果有偶数个,就做一个 \(op(p+1)\),可以让基变化一。从后往前可以保证操作没问题,总操作次数一个 log。
331. arc145f Modulo Sum of Increasing Sequences
单位根反演,很牛逼的一个题!
式子很长懒得写了。
332. arc144d AND OR Equation
333. lg8350 [SDOI/SXOI2022] 进制转换
考虑枚举阈值 \(c1,c2\) ,令 \(i = x_12^{c1} + x_0 = y_13^{c2} + y_0\)。试图计算 \(x_0 - y_0 = x_12^{c1} - y_1 3^{c2}\),然后把贡献拆开,发现相当于两个多项式的点积。注意到其中第一个多项式的有用的值域很小,所以暴力计算第二个多项式,第一个多项式形式非常好看,可以使用倍增求出。
334. xsy5267 西坤丝 (sequence)
厉害的构造题。
大力猜想,最大值应该会长成 \(0000111110000111110000111\),就是若干段 0,1,1 的长度恰好是 \(k\)。然后发现这玩意能取到上界。再发现最小值和这玩意差不多。
335. xsy5268 地皮 (dp)
大概是对一个连通块的标志性东西计数。
这里的标志性东西是最长的列和最长的行的交点,也就是 \(a_i + b_j\) 最小的点。
发现限制可以写成二维数点,就做完了。
336. xsy5269 古拉符 (graph)
暴力建图再拼个暴力可以获得 70。
模拟题面建图可以获得 100。
337. xsy5270 泪音 (rain)
弱智题。显然每一位独立,然后转移是个线性递推,矩乘随便搞搞就过了。
338. xsy5257 购买饮料 (buy)
无解是容易的。以 \(a\) 个为单位买,要求是当前钱数不小于某个数,每次买完会亏某个数。剩下的小东西模拟即可。
339. xsy5258 多边形(polygon)
大力猜想,三种颜色都有和不存在相邻同色点是充要条件。证明可以归纳。
那就写个分治,每次从 \(cnt\) 最小的颜色里选一个点,连一条能连的边。连不了的点至多只有一个。注意复杂度别假了,把复杂度写对点,让它看起来是 \(O(n \log n)\) 的就行了。
340. xsy5259 二分图最大权匹配(match)
发现 \(|x_1 - x_2| + |y _ 1 + y_2|\) 其实就是四种正负号组合取 max。这样就可以建出一个费用流图了,大概是左右各 \(n\) 个点,中间 4 个点。
然后模拟即可。
341. xsy5260 飞毯(carpet)
2022 shenyang B。写过了。https://www.cnblogs.com/ZHANG-SHENG-HAO/p/17798882.html 这里的 290 B。
342. arc144e GCD of Path Weights
343. arc143d Bridges
唐。那就把 \(A_i\) 和 \(B_i\) 连边,环上按照环的顺序连,其他瞎几把连就行了。
344. arc143e Reversi
对于一条边 \((u,v)\),\(u\) 和 \(v\) 中谁先操作是确定的。
具体地,考虑一个叶子 \(u\)。如果 \(u\) 是黑点,说明 \(fa\) 比 \(u\) 先操作。否则 \(u\) 比 \(fa\) 先操作,并更新 \(fa\) 的状态。选一个字典序最小的拓扑序即可。
345. xsy5260 机器人(robot)
\(2^n\) 枚举每种可能的情况,模拟即可。
346. xsy5261 旅行(tour)
考虑是个图怎么做。大概就是线段树分治,对于颜色 \(c\),加入 \((u,v)\) 首先会让连通块个数加一。然后如果 \(u\) 被某条 \(c\) 边连接着,会让连通块个数减一。\(v\) 同理。最后如果 \(u,v\) 在同一个连通块里,就再加回来。
发现基环树一个环,所以用并查集维护连通性很蠢。那就做完了。
347. xsy5262 点餐(order)
按照 \(b\) 排序,记 \(w(i,k)\) 表示 \(i\) 是 \(b\) 最大的点,选 \(k\) 个物品的最小代价。发现这个代价满足决策单调性。拼个分治就过了。
348. qoj #7106. Infinite Parenthesis Sequence
记 \(f(k,i)\) 表示第 \(k\) 次的字符串里第 \(i\) 个左括号的位置。如果我们能求出 \(f(k,i)\),套个二分就能获得答案。注意我们只需要关心 \(i\) 的相对顺序,所以随便点个东西作为第 \(0\) 个左括号。
枚举是 \(()\) 还是 \(((\),综合一下,发现 \(f(k,i) = min(f(k-1,i) + 1,f(k-1,i+1) - 1)\)。
化简,发现 \(f(k,i) = min_{j = i} ^{i + k} f(0,j) + K - 2(j-i) = K + 2i + min_{j = i} ^{i + k} f(0,j) - 2j\)。
记 \(F(j) = f(0,j) - 2j\)。发现 \(F(j + m) = F(j) + n - 2m\)。根据 \(n - 2m\) 的正负性,可以把范围缩小到 \([i,i + m)\) 或者 \((i + k - m,i + k]\),然后平移就变成了一个 rmq 问题。
349. lg8361 [SNOI2022] 倍增
如果能构造出一个长为 \(n\) 的答案,那往进位的地方塞 \(B - 1\),就可以获得 \(n+1\) 位的答案。
所以变成对于每个 \(B\) 构造出一个最短的答案。打表发现这个答案长度不会超过 \(9\)。
令答案长度为 \(L\),先枚举 \(L!\) 种置换环,然后枚举 \(2^L\) 个是否进位,对于每个置换环是一个模 \(B\) 的方程组,这样可以 $O(L) $ 判断是否合法。
350. lg7962 [NOIP2021] 方差
操作是交换差分,然后发现单谷。发现在当前序列前面或者后面塞一个差分,额外需要的信息只是当前序列的和。大力 dp 就行了。
351. xsy5271 种树(plant)
每个连续段分别考虑,概率是 \(f(A,B)\)。
352. xsy5272 汪了个汪(wow)
每一轮会把 \(mx -mn \rightarrow \lceil {mx - mn \over 2} \rceil\)。暴力模拟即可。
353. xsy5273 建造食堂(canteen)
傻逼。
354. xsy5274 赛比(hctam)
注意到每个 \(2 \times 2\) 的矩阵有且仅有一个值。然后就可以 dp 了。设 \(f_{i,S,j}\) 表示第 \(i\) 行,左右集合是 \(S\),\([0,j)\) 在下,\([j,n]\) 在上的方案数。暴力 dp 是 \(O(2^n n^3 m)\) 的,发现中间的转移相当于超集和,fmt 一下就过了。
355. lg7560 [JOISC 2021 Day1] フードコート
考虑把询问转化,变成加入 \(i\) 队列的第 \(j\) 个人是什么颜色的。假装只有加入和询问,可以用线段树维护所有询问,每次是区间减,找出 \(\leq 0\) 的位置即可。
然后发现有离开事件。所以我们要维护当前被踢了多少人。这相当于总数减当前个数,而当前个数可以被写成区间加和区间取 max。因为是单点查,所以不用 beats。
356. lg7562 [JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)
357. cf1336f Journey
358. lg7963 [NOIP2021] 棋局
鉴定为史。
大概就是倒着考虑,维护 2,3 边的连通块。答案就是 3 + 2 - 同一行/列的在 3 里面 + O(1) 个特殊点,然后就是一坨。
考场上遇到这种题就跟它爆了 /cy。
359. lg7915 [CSP-S 2021] 回文
枚举第一个选哪个,就变成了两个栈。注意到每次必须选某个同时出现于栈顶和栈底的数,选字典序最小的,选不了就无解。手玩发现如果这样选不可能把有解变成无解。
360. lg7916 [CSP-S 2021] 交通规划
显然有个显然的网络流做法。
然后考虑把连续的黑白段拼起来,一个割相当于从 \(i\) 走到 \(j\) 的边。那就相当于一组匹配,并且匹配不能交。区间 dp 即可。
361. The 1st Universal Cup. Stage 15: Hangzhou
A
H
D
E
C
B
362. EC-Final 2022
M
F
J
C
I
一个关键的结论是,当第一次 tp 之后一定走的是最短路。
然后用类似 dijkstra 的方法更新即可。
H
你吗,怎么是模拟题。
L
\(n,m\) 有 \(<3\) 的数特殊处理。
然后声称 \(a_{i,j} = a_{i \bmod 4 ,j \bmod 4}\)。枚举 \(4!\) 种排列暴力 check 就行了。
A
B
厉害题,但是懒得写代码了。
假装 0 比 1 多,对于每对相邻的 0,统计它们之间 1 的个数,记作数组 \(c\)。
若 \(c\) 中只有 0/1,答案是简单的最小循环节,容易求。
若 \(c\) 中有 \(>1\) 的数,只需统计经过多少轮之后变为只有 0/1 的情况。将 \(c\) 中的非零连通块提出,发现一次操作是先将连通块整体右移一位,然后在连通块前加一个 1,并把连通块末尾 -1。容易发现 1 的数量单调不降,当原连通块结尾 $>1 $ 时连通块长度增加。所以一定会在有限步内完成,大约 \(O(n)\) 步。
然后暴力模拟即可。