cf-div 868 div cf
Codeforces Round 904 (Div. 2)
A. 没想到是暴力,做的很晚 B. 手玩一下即可 C. Medium Design 给定一个长为 \(n\) 的数组 \(a\) ,和若干条线段 \([l_i,r_i]\) ,你可以选择这其中的任何若干条线段,并让 \(a_l\sim a_r\) 均 \(+1\).请你计算可以得到的 \(\max( ......
「题解」Codeforces Round 905 (Div. 3)
before 终于有一篇题解是一次性更所有题的了。 A. Morning Problem A. Morning Sol&Code 根据题意模拟即可。 #include <bits/stdc++.h> typedef long long ll; int min(int a, int b) { retu ......
CF888D
分析 很容易想到从 \(0\) 开始枚举 \(a_i \neq i\) 的位置个数一直枚举到 \(k\) 计算每种情况下的答案加在一起即为答案。 对于 \(k\) 确定的情况,\(a_i = i\) 的位置共有 \(C_{n}^{n-k}\) 种情况,剩下的位置要保证 \(a_i \neq i\)。 ......
CF888B题解
分析 题意为选出最多的操作使机器人执行完仍停留在原地。 分为左右和上下两类,则每一类的可执行操作数都是操作次数最少的一种操作的二倍(因为正反操作都要执行才能抵消)。 直接统计每种操作的操作次数计算答案即可。 代码 #include <iostream> using namespace std; co ......
CF888A题解
分析 因为一个数不可能同时大于并小于它两边的数,所以两种数的集合不存在交集。 所以分别扫一遍两种数的个数加在一起即可。 代码 #include <iostream> using namespace std; constexpr int MAXN(1000007); int a[MAXN]; int ......
CF1555E题解
分析 观察到题面是求最小极差,想到 two-pointers。 按 \(w_i\) 大小排序,然后发现一个子段的子段的答案肯定不优于原子段。 和CF1777C以及NOI2016区间一样,选取合法左端点然后选取最大合法右端点。 值得注意的是,本题要求首尾相接,所以为了避免选取的线段无交集,将 \(r\ ......
CF1572F Stations 题解-Segment Tree Beats
20231025 CF1572F Stations 题解-Segment Tree Beats 吉司机线段树好题!!!CF3400。 传送门 Statement 有 \(n\) 个广播站,第 \(i\) 个广播站高度为 \(h_i\),范围为 \(w_i\)。初始 \(h_i=0,w_i=i\)。广 ......
CF1777E题解
分析 看到求最大值最小,不难想到二分。 很容易想到二分最大可取边长度。 思考如何check。 首先如果存在一点 \(u\) 符合条件,那么我们很难判断那条边该翻哪条边不该翻,很难去check。 那么大胆假设对于每个点 \(u\),每条边的方向只会确定为一个状态。 尝试证明。 假设存在边 \(a, b ......
CF1132C Painting the Fence 题解
@目录DescriptionSolutionCode Description 有一面长为 \(n\) 的墙以及 \(q\) 个工人,第 \(i\) 个工人粉刷 \(l_i\) 到 \(r_i\) 的墙面,现在要去掉两个工人,问剩余 \(q-2\) 个工人最多能粉刷多少墙面。 Solution 注意数 ......
题解 CF903G【Yet Another Maxflow Problem】
加边 \(A_n\stackrel{0}{\to}A_{n+1}\),\(B_0\stackrel{0}{\to}B_1\)。称形如 \(A_i\to A_{i+1}\) 的边为左部边,形如 \(B_j\to B_{j+1}\) 的边为右部边,形如 \(A_i\to B_j\) 的边为中间边。 根据 ......
CF1467E Distinctive Roots in a Tree
突然发现深究一些树上问题还是挺有意思的哈。 显然对于同一种权值的任意两个结点,其两端的部分都是不合法的。 维护两个标记表示子树内均不合法与子树外均不合法即可。但相同权值的点对数量是 \(O(n^2)\) 的,我们要优化这个过程。 发现很多点对都是无用的。DFS 下去,遇到一个 \(x\) 权值的结点 ......
CF1854E Games Bundles 题解
乱搞题 设个 \(dp[i]\) 表示和为 \(i\) 的子序列个数,那么转移是容易的, \(dp[j]+=dp[j-i]\) ,然后就判下 \(dp[60]+dp[60-i]\) 是否大于 \(m\) ,发现这样子搞对于比较大的数可能达不到 \(m\) 的限制,因为这样子转移,默认的是一个数只选一 ......
CF1878B题解
CF1878B Aleksa and Stack 题目翻译 给定 \(n\),试构造一个长度为 \(n\) 的严格上升正整数序列 \(a_1, a_2, a_3, ..., a_n\) 使得 \(\forall i \in [3, n], (a_{i - 1} + a_{i - 2}) \nmid ......
Codeforces Round 905 div2 F题
记答案为\(ans_i\),表示从1到i次修改出现的字典序最小的数组a, \(c\)数组表示\(ans_i\)出现之后,所有修改的累加和。用一个vector存一下\(ans_i\)之后的所有修改。从1到q遍历每一次修改时,对\(c\)数组进行区间赋值操作,如果\(c\)数组中第一个不为0的数<0,那 ......
VK Cup 2016 - Round 1 (CF639)
A. Bear and Displayed Friends 这是 Div2 的题,不写。 B. Bear and Forgotten Tree 3 这种东西怎么评蓝的? Description 给定 \(n,d,h\),构造一棵有 \(n\) 个点,直径为 \(d\),高度为 \(h\) 的树。 \ ......
「解题报告」Codeforces Round 653 (Div. 3)
A. Required Remainder You are given three integers \(x, y\) and \(n\). Your task is to find the maximum integer \(k\) such that \(0 \le k \le n\) that ......
CF1777C题解
分析 看到题面里面的子序列觉得很恶心,如果是子段感觉就会比较好做。 如果直接填上子序列中间的空隙就可能会取一些比必须要取的数更大或者更小的数,影响我们的答案。 那么就可以直接排序,使得子序列中间的空隙的数必然 \(\geq\) 左端且 \(\leq\) 右端,不会影响我们的答案(因为极差只看最大最小 ......
[题解]CF1223F Stack Exterminable Arrays
CCF 出的原题观摩一下。 思路 首先可以用一个 Trie 来维护。 在这里对本文中的一些变量做一下说明。 \(p\) 表示当前维护的 Trie 中,指向的元素编号。 \(t_i\) 表示在 Trie 中编号为 \(i\) 的元素在原序列中的值。 \(f_i\) 表示在 Trie 中编号为 \(i\ ......
CF809D Hitchhiking in the Baltic States-平衡树+DP
CF809D Hitchhiking in the Baltic States-平衡树+DP Statement 给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\),现在你要确定这 \(n\) 个数,使得 \(a_i\in[l_ ......
Codeforces Round 905 (Div. 2)
Preface 周日晚上Div1,2,3同乐,但我不想打Div1,同时第三个号由于只打了两场没够到Div2的门槛,因此刚好打不了Div2,遂玩了一晚上LOL 今天补了下这场题感觉难度偏低,E之前的题都比较签,F刚开始没想到转化成差分最小准备去写扫描线+线段树了,后面发现其实可以写的很简单 A. Ch ......
CF1887D Split
左侧最大值小于右侧最小值,其实就是左侧的值全部小于右侧,即,我们可以在区间 \([l,r]\) 内找到一个阈值 \(x\) 和一个位置 \(i<r\),满足 \(\forall j\in[l,i],a_j\le x\) 且 \(\forall j\in(i,r],a_j> x\)。 考虑刻画出所有 ......
CF1887C Minimum Array
一个很直接的思路是,维护当前可行决策集合 \(S\in\{0,\dots ,q\}\),从 \(1\) 到 \(n\) 分别考虑每一个 \(a\),排除一些决策,最终得到答案。 既然要排除决策,我们当然需要知道对于当前的 \(a_i\),前 \(j\) 个操作之后的值都是多少,如果能得到这个,且这些 ......
CF1887E Good Colorings
矩形的四个角颜色不同是个很难描述的条件,不妨利用行列二元关系转化,将 \((x,y)\) 颜色为 \(c\) 改为在 \(x\) 和 \(y\) 之间连接边权为 \(c\) 的边,则四角颜色不同就被我们转化为了,存在一个边权各不相同的四元环。 此时把特殊条件【初始给定 \(2n\) 个格子 \(2n ......
CF1887B Time Travel
早到可以选择停留在原地,所以我们一定会尽早地到达每一个节点,这样一定不劣。 考虑若我们最早可以在 \(t_u\) 时刻到达节点 \(u\),则对于边 \((u,v)\),我们一定会在它最早的解锁时刻由 \(u\) 向 \(v\) 扩展。实现时可以使用 dijkstra,并对每张图的出现时刻用 set ......
CF1777B题解
分析 首先计算单个排列中的逆序对数量。 我们发现这东西可以分为两类,一类是两个数在原排列和倒着的排列(这里称为“反排列”),另一类是两个数一个在原排列,一个在反排列的。 对于第一类,我们发现,原排列中的顺序对是反排列中的逆序对,所以原排列的所有数对要么在原排列中是逆序对,要么在反排列中是逆序对,所以 ......
CF1777A题解
分析 发现操作2不会改变数的奇偶性,故无视。 那么操作就是单纯删一个数。 对于一个连续出现 \(x\) 个奇偶性相同的数的序列,需要删 \(x - 1\) 个数(因为只剩下一个数就不会和相邻的数奇偶性相同了)。 觉得找序列太麻烦,观察到连续出现 \(x\) 个奇偶性相同的数的序列有 \(x - 1\ ......
CF1523D Love-Hate 题解
抽象化题意: 一共有 \(m\) 个元素,给定 \(n\) 个集合,每个集合的元素不超过 \(15\) 个,求出一个元素个数最多的集合 \(S\) 是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集。 其中$ p $ $ (1 \le n \le 2 \cdot 10 ......
Educational Codeforces Round 127(CF1671 D~E) 题解
D. Insert a Progression 题目链接 可以瞪出来的一个结论就是当我们在位置 \(p\) 插入了一个数 \(x\) 时,如果存在一对 \(l,r\) 满足 \(l<p\),\(r>p\) 且 \(x\in[a_l,a_r]\),那么我们插入的这个 \(x\) 就不会对序列的答案产生 ......
Codeforces Round 886 (Div. 4) 题解
link 我为什么还要 vp div4 场。。。 A 直接找最大的两个判断一下。 void solve() { int a[3]; cin >> a[0] >> a[1] >> a[2]; sort(a, a + 3); if(a[2] + a[1] >= 10) cout << "YES\n"; ......