nesting 762f tree cf
CF1839A题解
分析 可以很容易地想到如果只有1要求的话答案就是 \(\lceil \frac{n}{k} \rceil\)。 最优策略显然是在每个整除分块的第一位放一个1。 思考加入2条件如何修改。 显然当最后一块的大小不为1时,大于1的部分后缀和为0。 所以需要在最后一位加入一个1。 所以答案为\(\begin ......
CF981E Addition on Segments
将操作按右端点从小到大排序,这样对于当前值相同的点,只有最右边的那一个是有用的。 令 \(f_i\) 表示当前值为 \(i\) 最靠右的点的位置,转移直接暴力判断能否取 \(\max\) 即可,时间复杂度 \(O(nq)\)。 这个东西看起来就不好优化。 不妨调换状态和值,令 \(f_{i,j}\) ......
Codeforces Round 905 Div 1 (CF1887)
A1. Dances (Easy version) 把 \(a,b\) 序列都从小到大排序,\(a\) 贪心删大的,\(b\) 贪心删小的,二分答案并 \(O(n)\) \(\text{check}\)。 Code ```cpp const int N=1e5+5; int T,n,m; int a ......
数据结构与算法 | 二叉树(Binary Tree)
"二叉树"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树”表示每个节点最多可以分支成两个子节点。 ......
CF229E 题解
前言 基本是官方题解的思路。 分析 先考虑不用纠结的情况。假设第 \(n+1\) 大价值的物品的价值小于第 \(n\) 大的。 此时物品名称集合可以确定。 对于每类名称,恰好拿到的概率为 \(1/\dbinom{k_i}{a_i}\),\(a_i\) 为选择的物品数量,\(k_i\) 为总数。 对于 ......
题解 CF1876E - Ball-Stackable
输在 D 上了,呜呜呜。 首先显然环是没有用的,因此我们只用考虑简单路径。 先思考一个弱化版:如果所有边都已经定向了怎么做。对于每条路径 \(u\to v\),如果它是一个括号序列,那么我们就用并查集将这条路径上第一条边和最后一条边合并起来,那么颜色数就是并查集连通块数。考虑如何快速合并这个连通性。 ......
CF1886D Monocarp and the Set
Link 此题目可以从两个方向考虑,正着和倒着,倒着考虑比较容易,首先把所有的数放到一块,如果是'<'或者'>',就是去掉最左边或者最右边的数,这样显然只有一种可能,答案不变。 如果是'?',那么显然可以去掉中间的任意一个,所以答案就是\(\times l-2\),那么对于\(s_n-i\)位置的\ ......
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees( DFS )
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees 思路: 在输入树的边的同时记录他们的输入顺序 从 1 开始跑 DFS ,遇到未连上的边时 , 有两种情况(用 q 表示当前点的顺序序号) 1.边的顺序在这个点连上之前,那么 DFS 的 ......
[CF444E] DZY Loves Planting
DZY Loves Planting 逆天题。 想到二分,判断用网络流,但是好像 n 有点大。 我们想尽量让每个点的 g 能大于下界,所以我们尽量往大的边走,其实就是尽量不走小的边。 所以考虑将边从小到大排序,每次合并两端的连通块,如果剩下点的 x 总和小于总点数就只能内部消化。 又因为这已经是最劣 ......
CF1634F
知识点:差分 Link:https://codeforces.com/contest/1634/problem/F 差分的本质是递推。 简述 给定两长度为 \(n\) 的数列 \(a, b\),模数 \(p\),要求进行 \(q\) 次操作,每次操作为 c l r 的形式,表示将数列 \(c\) 的 ......
CF1100E Andrew and Taxi
套路题又来咯,最大值最小先直接上个二分答案\(lim\) 对于图中的边,若它的权值\(>lim\)的话这条边的方向就确定了,那么直接把这些边连出来跑个拓扑排序看看有没有环即可 如果有环则当前答案一定不合法,否则我们总存在如下的构造方法: 先把权值\(>lim\)的边得到的图的拓扑序搞出来,对于所有权 ......
CF1003E Tree Constructing
很trivial的构造题 首先上来判掉一些显然无解的情况,然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来 考虑在链上接一些点使得直径不会变长,对于链上的某个点,它最多能接上的链的长度就是它到两个端点距离的最小值 不妨设计递归函数求解,设solve(x,dis,lim)表示在 ......
CF1437F
好神奇的 dp 题。 description 给定数组 \(a\),求其有多少个排列满足 \(y_i=\max(a_1,a_2,\dots,a_{i-1})\) \(\forall i\in [1,n]\cap\mathbb{Z},2a_i\leq y_i ~\texttt{OR}~ 2y_i\le ......
CF367C Sereja and the Arrangement of Numbers
这题首先上来会发现题目中的很多信息都是假的,核心就是问要构造一个\(x\)个点的完全图至少要多长的序列 我们把序列中相邻的两个元素看作图上的一条边,则可以把问题转化为:给一个\(x\)个点的完全图,问至少要走多长的路径才可以遍历图中的所有边至少一次 简单讨论下会发现当\(x\)为奇数时,此时图中每个 ......
CF723F st-Spanning Tree
小清新贪心+分类讨论,因为边的数组开小了WA了好久…… 首先我们贪心地选出不包含\(s,t\)的边,用这些边尽量地将除了\(s,t\)外的\(n-2\)个点连通 接下来考虑每个连通块,由于题目保证图初始连通,因此只有三种情况,即要么其中仅有和\(s\)相连的边;仅有和\(t\)相连的边;或者同时有向 ......
CF260D Black and White Tree
刚开始想复杂了,后面再细想了下发现是个傻逼题 考虑一下构造策略,每次从两种颜色集合中分别取出一个数\(u,v\),考虑连边\(u\leftrightarrow v\),边权为\(\min(s_u,s_v)\) 并在每次操作后将\(s_u,s_v\)中较小的那个直接删掉,并把较大的那个值减去\(\mi ......
CF821D Okabe and City
也是一个很经典的优化最短路的题,感觉在暑假前集训做过类似思想的题来着 首先发现我们可以把所有有路灯的点以及终点看作关键点,很显然我们只关心关键点之间的边权以及最短路 不难发现对于两个关键点\(i,j\),如果\(i,j\)相邻,则它们之间有边权为\(0\)的边;否则若\(|x_i-x_j|\le 2 ......
CF612E Square Root of Permutation
挺有意思的一个构造题,不过这种排列置换相关的套路感觉都太明显了 首先考虑把原图的每个置换环求出来,稍作观察会发现所有长度为奇数的置换环都可以很容易地构造出对应的\(q\)数组 但长度为偶数的置换环就不能单独构造了,但我们发现可以把两个长度相同且为偶数的置换环交错着合并来得到一个合法的\(q\)数组 ......
CF1137F Matches Are Not a Child's Play
哈人*3400,是不是贺过了个 1F (? 单点编号 \(\to max + 1\),动态维护 prufer 序列删除了哪些点。 看似不可做,但是不难发现我们一个点被更改其他点的相对次序不会改变,反而 \(x \to max\) 这条链的删除次序到了最后面。 然后我们以权值最大点为根,不难发现每次只 ......
CF424C的题解
简单题。CF 评分才 *1600。 可以直接先把 \(Q\) 拆成两部分。 \[\begin{aligned} \large a&=\oplus^n_{i=1}p_i\\ \large b&=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (i\bmod j)\\ \large ......
CF580B的题解
见到有单调性、有限制的区间问题,很自然地就会想到用尺取去做。 先按工资升序排序,然后套上尺取就行了。 不会尺取的可以根据这道题去学。 时间复杂度 \(O(n\log n)\)。 #include<cstdio> #include<algorithm> #define ll long long usi ......
[题解]CF1881G Anya and the Mysterious String
思路 发现如果一个字符串中有长度大于等于 \(2\) 回文子串,必定有长度为 \(2\) 的回文子串或长度为 \(3\) 的回文子串,并且形如:aa 和 aba。 所以考虑用线段树这两种情况。维护一段区间的最左、次左、最右、次右的元素,同时用两个标记变量 \(f_1,f_2\) 分别表示这个区间中是 ......
[ABC207F] Tree Patrolling 题解
[ABC207F] Tree Patrolling 弱智 DP 题,设 \(f(i,j,0/1/2)\) 表示在点 \(i\),子树中有 \(j\) 个点被覆盖,且 \(i\) 点自身状态是未被覆盖/被自身覆盖/被某个儿子覆盖,然后树上背包更新就行了。 代码: #include<bits/stdc+ ......
AT_tdpc_tree 木 题解
木 弱智 DP 题,直接设 \(f_i\) 表示 \(i\) 子树内染色的方案数,然后每次合并一个点与它的儿子即可(具体而言,因为儿子间独立,所以方案数就是二项式系数)。 需要注意的是因为第一条边可以在任意位置,所以要以每个点为根各 DP 一次。但是这样每条边会被算两次,所以乘以 2 的逆元即可。 ......
CF1542E2 Abnormal Permutation Pairs (hard version) 题解
Abnormal Permutation Pairs (hard version) 两个限制:字典序小、逆序对大,一个显然的想法就是确保一对关系,统计另一对关系。 确保哪一对呢?我们想了想,决定确保字典序小,因为字典序是可以贪心的。 具体而言,我们考虑两个排列自第 \(i\) 位开始出现了不同。这样 ......
CF568E Longest Increasing Subsequence 题解
Longest Increasing Subsequence LIS 问题有两种主流 \(O(n\log n)\) 解法,最常见的树状数组法,以及不那么常见的二分法。然后考虑本题,发现一个神奇的思路就是求出 LIS 后倒序复原出数组。 进一步思考后发现,因为本题是 LIS(Longest Incre ......
CF1257E The Contest
用桶存,做一遍前缀和,令 \(b_{x,y}\) 表示序列 \(x\) 包含 \(1\sim y\) 的数字个数。考虑枚举第一个序列保留的前缀 \(1\sim i\),对于第三个序列,如果其保留了后缀 \(j\sim n(i<j)\),考虑哪些数需要被移掉,那么答案就是: \[b_{1,n}-b_{ ......
CF914B题解
一道简单的博弈论。 思路 我们可以先记录每张牌的个数,如果这个牌的个数为奇数,则 Conan 胜利,如果全部为偶数,Agase 胜利。 证明 如果说所有牌为偶数,那么无论 Conan 取哪张牌,Agasa 都可以和他取一样的,最终让 Conan 失败。 如果不满足,那么 Agasa 会无法操作。 A ......
题解 CF1651F【Tower Defense】
一个塔防游戏。
一共有 $n$ 个塔按 $1 \sim n$ 的顺序排成一列,每座塔都有魔力容量 $c_i$ 和魔力恢复速率 $r_i$。对于一座塔 $i$,每过一秒它的魔力 $m_i$ 会变为 $\min(m_i+r_i, c_i)$。每座塔初始时满魔力。
一共有 $q$ 个怪物,每个怪物有两... ......