已注销

分类

题解(9)

/ 注册

全部文章（共9篇）

题解 | #小红的括号串#

F.小红的括号串题解 Raney 引理：对于，如果，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。将括号串中的左括号视为 -1，右括号视为 1，则合法括号串需要满足序列和为 0。考虑在这个序列中加上一个 -1，再将所有数取反，此时序列满足 Raney 引理的应用条件。并且因...

2024-07-21

32 355

题解 | #Involutions#

J.Involutions 题解令为大小为的集合对应的答案。第个点可以和前个点之一配对，也可以形成不动点，因此有转移式。从组合数角度理解，分别考虑选取个配对的贡献，则有。注意到大于的项会被消去，对剩余项运用 Lucas 定理可以得到。据此考虑暴力枚举前 ...

2024-07-18

7 260

题解 | #2D Travel#

J.2D Travel 题解首先注意到两维可以独立求解。据此考虑离线处理。对于每一维，令位置集为所有当前处于位置的询问形成的集合，我们记录总偏移量，位置集偏移量，询问偏移量和每个询问所属的位置集，同时记录当前边界与。接下来对于从到每一次操作，我们依次进行如下...

2024-07-16

11 597

题解 | #小橙的圈圈#

F.小橙的圈圈题解注意到竞赛图上的三元组共有如下两类状态：其中的第一类（即三元环）很难枚举，因此考虑枚举第二类三元组。具体地，我们统计朝每个点连边的点的总数，则在这些点中任取一对，都能唯一地确定一个第二类三元组。因此第二类三元组的总数为。答案即为三元组总数减去第二类三...

2024-06-02

23 458

题解 | #粉毛天堂#

F.粉毛天堂题解 BCIO B：彩彩。 C：劈瓦。 I：“结果看见一屋子铺天盖地的二次元粉红色元气少女偶像，警察叔叔愣在那儿大半天，我另外三个朋友还在打游戏完全没反应过来”。 O：修哇。 FKNP F：承认欲求 Monster 的背面。 K：波奇。 N：波奇。 P：结束乐队。剩下的猜的...

2024-06-01

1 239

题解 | #小红的基环树删边#

F.小红的基环树删边题解注意到基环树上的环产生两个分支路线，因此到的路径最多只有条，暴搜枚举即可。代码 #include<bits/stdc++.h> using namespace std; #define N 100050 int i,j,k,n,m,t,vis...

2024-05-26

18 727

题解 | #小A的任务#

E.小A的任务题解本题的版本做法与 CCPC 2023 网络赛 L 题基本一致。对于固定的询问，在完成前个 A 类任务的情况下显然应选择到中前小的数。对应的结果可以将离散化后用可持久化线段树查询。同时，对于固定的和，当逐渐增加时，由于对应的 ...

2024-04-06

7 447

题解 | #S 老师的礼物#

E.S 老师的礼物题解 None 的判断首先将所有与连边，若连边后存在环或图的状态与冲突则答案不存在。否则，我们首先判断图的连通性。将图上的点按到的顺序在数轴上一字排开，发现两个联通块能够合并，当且仅当两个联通块对应的区间有交。证明: 令左侧联通块对应区间为，右侧联通...

2024-03-15

6 424

题解 | #现在是消消乐时间#

F 现在是消消乐时间题解注意到小球的运动轨迹只有两种：从矩形的四个角之一射出，或者回到发射点进入循环。接下来对两种情况分别讨论： 1.从某个角射出令小球的初始位置为，射出时间为，则为满足如下同余方程的最小正整数：注意到方程的答案不超过，而当取矩形的四个角时取得最大值，即 ...

2024-03-09

11 476