CF1398 题解
自己会做ABCDEFG，主要是这场 Edu 太水了，做起来和 Div3 感觉一样。。A选择第一个，第二个和最后一个。判断是否可行即可。B显然每次都会选择最长的 $1$ 的连续段。模拟即可。C设前缀和为 $s_i$。一个区间合法的条件是 $s_r-s_{l-1} = r-(l-1)$，推一下式子是 $s_r-r = s_{l-1}-(l-1)$，直接 map 记录一下就好了。D每次肯定会取出两...
自己会做ABCDEFG，主要是这场 Edu 太水了，做起来和 Div3 感觉一样。。A选择第一个，第二个和最后一个。判断是否可行即可。B显然每次都会选择最长的 $1$ 的连续段。模拟即可。C设前缀和为 $s_i$。一个区间合法的条件是 $s_r-s_{l-1} = r-(l-1)$，推一下式子是 $s_r-r = s_{l-1}-(l-1)$，直接 map 记录一下就好了。D每次肯定会取出两...
A我们只需要发现 $n = 1\pmod {n-1}$，就可以用如下方式构造：操作 $[1,n]$ 使得 $\forall i\in [1,n],(n-1)|a_i$操作 $[2,n]$ 可以消去所有的元素单独操作 $[1,n]$ 。注意特判 $n=1$ 就好了。B设 $sm = \sum_{i=1}^n a_i,mx = \max_{i=1}^n \{a_i\}$。注意到这个操作实际上是每...
写这个题解的原因是发现自己写了很多sb错误导致分数 $300 \to 100$ 加上发现出题人输出$10^6$个数还不提供快速输出板子加上板子就能 $3s \to 1s$ 的神奇比赛体验就来写一下这个题解。（题目还是很水的。。）题目链接A一棵树，点有点权，$1$ 号点为根。点 $i$ 的答案是从根到 $i$ 路径上点的权值组成的序列有多少个后缀最大值（维护一个单调不增的单调栈的大小），求每个...
A首先我们可以发现如果一个点是旅游城市，那么它的祖先也必然都是旅游城市（否则可以交换，答案不会变小）。所以我们现在可以看成选了一个点 $v$ ，它带来的代价就是 $sz_v-dep_v$，排个序取前 $n-k$ 大就行了。B全排列枚举 $x,y,z$ 的大小关系，枚举第二大的那个数，直接通过双指针找到比它第一个大的和比它第一个小的数即可。C这种开头和结尾加字符的还是考虑区间 dp 比较好。因...
这场细节好多啊。。A先考虑一个暴力的做法：设 $y$，那么 $x,y$ 移动后在同一个位置上当且仅当满足 $x-y = a_{y \bmod n}-a_{x \bmod n}$，符号相反不好看，于是我们令 $\forall i,a_i = -a'_i$，那么相当于要满足 $x-y = a_{x \bmod n}-a_{y \bmod n}$。现在我们考虑去枚举 $x \bmod n$ 和 $...