Zechariah

题解

/ 注册

全部文章 / 题解（共19篇）

题解 | D. Half Turns

D. Half Turns Solution 看不懂题解写的什么…… n和m都为偶数，是一定可以构造出解的。我们假设n≤mn\le mn≤m，然后分类：当n=2n=2n=2时，按照如下方式构造即第一列和最后一列都是拐弯点，中间可以放2的倍数个拐弯点。接下来考虑n=6的时候，按照如下方式构造...

2022-08-22

1 579

题解 | F. Traveling

F. Traveling Solution 构造题，注意细节。考虑怎么样构造用的边数最少，然后如果m更大就加一些不影响任何最短路的边，如果两两连边还是不够m条就输出No。首先考虑直接从1到n的最短路，显然必须有d[1]=d[n]=min{d[i]}d[1]=d[n]=min\{d[i]\}d[1...

2022-08-12

6 570

题解 | K.Great Party

K.Great Party Solution 关键是需要推出一个结论：当堆数为奇数时有必胜策略。这样就只需要考虑偶数，偶数堆时谁让堆数-1谁就会输，因此将所有堆的石子数-1，就变成了nim博弈，那么本题就转化成了求区间内区间异或和不为0或长度为奇数的子区间个数，显然求区间内异或和为0的长度为偶数的子...

2022-08-08

10 680

题解 | I. Board Game

I. Board Game Solution 考虑一组k+xk+xk+x个人实际上可以看成kkk和xxx两组，枚举分出多少组kkk，剩余的人就平均分到mmm组中。本题实际上定位应该是签到，但是数据有问题。时间复杂度O(m)O(m)O(m)。题目数据有问题，下面代码中注释掉的if应该要加上，表...

2022-08-05

1 431

题解 | A. Falfa with Polygon

A. Falfa with Polygon Solution 考虑我们选出的凸包，从1到n看就只有一条边是从较大编号连到较小编号，考虑dp出fk[i][j]f_{k}[i][j]fk[i][j]表示长度为k的从iii开始到jjj结束的子序列的最大长度，其与i、j两点长度的和就是凸包的周长。写出f...

dp

2022-07-29

2 608

题解 | F. NIO with String Game

F. NIO with String Game Solution 考虑离线，对所有t串（包括后面添加的字符）建出一棵trie树，按从a到z的顺序遍历子节点进行dfs，就可以把dfs序对应成字典序，这样就相当于每次需要在trie上找到s对应的位置，求dfs序比它小的位置上有多少个t串。对于操作一、四...

2022-07-29

3 461

题解 | C. Link with Nim Game

C. Link with Nim Game Solution 根据nim博弈，对于先手必胜的情况，每次只需要拿走若干石子后异或和是0即可；先手必败的情况，为了使得拿的次数最多，每次只拿一个且让对手也只拿一个是最优的。比较难算一点的是第一步可选的方案数，对于先手必胜的情况，记sss为所有石子的异或和...

2022-07-28

1 489

题解 | E. Falfa with Substring

E. Falfa with Substring Solution 考虑容斥，设Gn,kG_{n,k}Gn,k表示长度为nnn的字符串中有至少kkk个bitbitbit子串的方案数，则有 Gn,k=(n−2kk)26n−3kG_{n,k}=\begin{pmatrix}n-2k\\k\end{pm...

NTT

2022-07-28

3 640

题解 | H. Take the Elevator

H. Take the Elevator Solution 上行下行两个方向显然分开考虑，一次上下取两者需要移动距离的较大值。考虑上行时，上升高度取决于最大的bib_ibi，因此考虑将bib_ibi大的先满足，在取满mmm个bib_ibi最大的之后，考虑用大根堆维护已选乘客的aia_iai...

2022-07-28

3 400

题解 | C. Grab the Seat!

C. Grab the Seat! 题解观察数据范围发现qqq很小，O(n)O(n)O(n)的复杂度可以通过，考虑对每次询问分别独立地去求解。观察出一个重要性质：一个被占的座位与屏幕两端连线所夹的区域以外都是会被挡住的点（动手画一画就能看出来）。实际上，一个被占的座位所去掉的点可以被分成三个部...

贪心暴力

2022-07-19

3 735