1009g cf

# CF1815 > `Div. 1` 确实难，`Virtual Contest` 上只完成了两道题，想出来了三道题。 ## A. Ian and Array Sorting 秒切题……考虑将前 $n - 1$ 个数变成一样的一个数 $x$。显然可以完成。 然而考虑此时最后一个数。如果 $\ge x ......

来个垃圾做法。 首先这个树没啥用，我们只需要找到两条路径的交与方向即可。分类讨论即可得到，略掉了。 把距离找出来之后，我们可以将运动路径写成序列，那么我们现在相当于有两个分成五段的序列，其中有两端为 $1 \to d$ 与 $d \to 1$。我们枚举几种情况，分别是 $1 \to d, 1 \to ......

# CF1834 题解 ### A 考虑答案与元素位置无关，只与$1$和$-1$的个数有关。要求$1$必须多于或等于$-1$，并且$-1$个数为偶数。分讨： 序列中$num(1) \geq num(-1)$，只需要看$num(-1)$正负性，奇数1步，偶数0步 序列中$num(1) using na ......

# CF1834 > Virtual Contest 做了 5 道题，非常不错。 ## A.Unit Array 秒切题，判断个数，然后判断一下奇偶即可。 提交： ## B.Maximum Strength ### 题目描述 每一种材料的力量由一个十进制整数表示。 对于一个武器，由**两种**材料构 ......

# A.Destroyer 开个桶记录个数，看满不满足单调不上升即可。 # B.Astrophysicists > 辛辛苦苦写了这么久的文章就没了？？？？烦死了。 > 自己做 Virtual Contest 的时候这道题打表打了半天（~~20min~~）才搞定…… ## 题目大意 有 $n$ 个人， ......

# 题目 题目链接：https://codeforces.com/contest/1842/problem/F 给定一棵 $n$ 个点的树，你可以选择其中 $k$ 个点染黑，定义一条边的价值为割去这条边之后，剩下两颗树的黑点数量差；一棵树的价值为所有边的价值之和。 对于 $k\in [0,n]$，求 ......

`*`：不错的题。 ### Codeforces Round 618 #### CF1299C Water Balance \*2100 注意到答案序列一定是单调递增的，证明：如果不是单调递增的则一定可以通过一次操作将字典序变小。 故，使用单调栈维护当前最靠右区间的权值，如果两个相邻区间合并后字典序 ......

## A [题面](https://codeforces.com/contest/1834/problem/A) 分类讨论即可 点击查看代码 ``` #include #define ull unsigned long long #define ll long long #define pii pa ......

本文网址：https://www.cnblogs.com/zsc985246/p/17509039.html ，转载请注明出处。 ## 传送门 [CF1580D Subsequence](https://codeforces.com/contest/1580/problem/D) ## 题目大意 有 ......

题意： 给定一个长度为n且均为0的数组，q次单点修改（从0改为1），以及m个基于该数组的区间。 规定好区间为：区间内1的个数严格大于0的个数。 上述m个区间若存在一个好区间则为合法，问按顺序进行q次单点修改过程中最早出现合法的单次修改编号，若无则输出-1。 马后炮思考： 对于m个区间，其实际关系是无 ......

猜它是一个 multi-sg，只用算出每个位置的 sg 值。不过注意到这是一个图，你要求 mex 肯定不会太大，毛咕咕一下不会超过 $\sqrt{m}$。并且根据均摊，你求 mex 的复杂度是 $O(m)$ 的。接下来相当于你有一个数 $v$ 每次选一个点异或上它的 sg 值，求最后是 $0$ 的概 ......

# CF1144G Two Merged Sequences ## 题意 现在给你一个长度为$n$的序列 你要把它拆成一个严格递增序列和一个严格递减序列 如果不可行输出$NO$ 如果可行输出$YES$并输出每个数属于递增序列还是递减序列 ## 题解 感觉脑子瓦特了，感觉这个 $dp$ 的状态设计是比 ......

# CF603E Pastoral Oddities ## 题意 给定一张 $n$ 个点的无向图，初始没有边。 依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。 若存在，则还需要最小化边集中的最大边权。 ## 题解 感觉自己找性质的能力还是太弱了。 首先有一个 ......

好好好。 求一个点到一个集合内点的距离和，这相当于在考虑若干条路径的长度，我们可以考虑使用点分治，建出点分树，这样每次查询时只需要对于这个点到根上的每个分治中心，找到所有经过这个中心的路径和即可。容易拆成每个点到分治中心的距离之和加上点数乘分治中心到查询点的距离，那么我们直接拿前缀和维护一下这个东西 ......

# CF Round 881 (Div. 3) > Div. 3 果然简单，虽然但是，我还是有 1 道题没有想出来。 ## A.Sasha and Array Coloring 排序双指针向内即可。 ## B.Long Long > 好啊，就是这道题没想出来。 `Virtual Contest` 上 ......

显然有一个 $|S|\log |S|$ 的 dp 做法，但是瓶颈在给字符串排序。也就是真正的瓶颈在于求 lcp。AFewSuns 给出了一种不需要科技的做法，orz。 第一个排序的部分，令 $t_{i,j}$ 代表第 $i$ 个字符串去掉第 $j$ 个字符后的字符串，要给所有 $t_{i,j}$ 排 ......

题目链接 这题其实还行。 如果能想到二分答案就会比较简单，我们来看如何写 check 函数。 把当前所有的单点修改存起来，然后依次遍历每个区间，观察这个区间内被单点修改的点的个数是否严格大于该区间长度的一半即可。 我们需要一个支持单点修改区间查询的工具，首先想到树状数组，但前缀和就够用了。 时间复杂 ......

题目链接：[http://codeforces.com/problemset/problem/321/C](http://codeforces.com/problemset/problem/321/C) 解题思路： 点分治模板题。 每次找到重心给他分配一个字符，分治往下走的时候分配的字符ASCII码 ......

[压位 trie](https://www.cnblogs.com/xx019/p/17503466.html) 好厉害。 显然加一个数很好维护，删一个数有点不好做，考虑回滚莫队。用平衡树维护数的集合，每次插入之前用前驱/后继与插入数的差更新一下答案，可以 $O(n\sqrt{n}\log n)$， ......

终于过了，感觉还是有点东西的。 首先我们有一个很好想的 $O(n(\ln A+\sqrt{A})\log n)$ 的做法。首先这个式子能写成 $p_i=\sum\limits_{j=1}^i\sum\limits_{k=1}^i\left(a_j-a_k\left\lfloor\dfrac{a_j} ......

CF1400E Clear the Multiset 一道经典简单的分治 由贪心可知，对于一段区间[L,R]，一共有两种处理方式 1.一个一个减，次数为l-r+1 2.先区间减，直到最小的减没了，在考虑最小值隔开的两个区间。如果有多个最小值，其实也不影响，再往下分的时候一定会分开。区间答案就是 $m ......

有个粒子初始在 $0$ 位置，$1\cdots n$ 位置分别为有一个对撞器，如果在 $0$ 位置则向右，如果在 $n + 1$ 位置则向左。每个对撞器有一个 $01$ 串，初始所有对撞器的指针都在开头，当粒子走到 $i$ 位置时，对撞器所指的值为 $0$ 则不改变方向，否则反向，指针指向下一个位置 ......

# CF771C Bear and Tree Jumps [link](https://codeforces.com/problemset/problem/771/C) 赛时脑子抽了没想出来，其实思路已经沾边了，但是……唉，还是太菜了 qwq。 ## 题意： 给你一颗有 $n$ 个点的树，和每次能走 ......

题目链接：https://codeforces.com/contest/1450/problem/E 题解： 题目中的等式关系为 $a_u-a_v=1$ 和 $|a_u-a_v|=1$ 首先，等式关系不好处理，考虑化成不等式 第一种：$a_u-a_v\leq 1$ 且 $a_v-a_u\leq -1 ......

虽然是一道绿题，但是感觉推式子时的一些细节还是值得学习的，并且还是有点 $2$ $hard$ $4$ $me$...... >一个圆上有 $N$ 个可染色的点，编号 $1\to N$。$N$ 号点和 $1$ 号点相邻。 你可以用 $M$ 种颜色将这些点染色。要求不能出现有三个同色点围成直角三角形。 ......

题目链接 题意是输出所有区间满足其内部每个数要么出现 $3$ 次要么不出现的个数。 因为是区间，数量很多，发现贡献是可以抵消的，直接无脑预处理前缀的桶。 然后枚举左端点，统计答案，怎么处理呢？ 疯狂地向右扩展，直到区间内有数字出现了 $3$ 次以上（这样是对的，待会儿证明，另外扩展到前一个就够了，不 ......

#### A. Sasha and Array Coloring [题目链接](https://codeforces.com/contest/1843/problem/A) 题目大意：将数组分为若干个集合每个集合非空，求每个集合内最大和最小元素之差的和的最大值 数组排序后将最大和最小元素划为一个集合 ......

CF1827E Bus Routes 很有思维含量的一道题。 任意钦定一个根 $rt$，对于每个节点，如果它不能到达，那么他的子树内所有点一定也不能到达，因此，我们只用考虑每一个叶子节点的情况。对每个叶子节点 $u$，设 $low_{u}$ 表示他能通过一条路线到达的最浅的祖先。对于任意两叶子节点， ......

# 正题 题目链接:[https://codeforces.com/contest/1773/problem/K](https://codeforces.com/contest/1773/problem/K) ## 题目大意 要求构造一张 $n$ 个点的无向图满足。 - 不存在重边和自环，且图连通 ......

[题目链接](https://codeforces.com/problemset/problem/519/E) # 题目 见链接。 # 题解 **知识点：倍增，LCA，树型dp。** 要找到距离两点 $u,v$ 相同的点个数，我可以分类讨论： 1. $u,v$ 是同一个点，那么全部点都可以。 2. ......