cf-div 872 div cf
CF633G Yash And Trees
简单题。 先把树拍扁成序列,在 dfn 序上区间修改区间查询。 由于时限 4s,我们可以整点怪的,比如 `bitset`。 把区间内的数有/没有表示成 $01$ 序列,考虑到区间加取模相当于区间内的数全部**循环右移**,用 `bitset` 可以做到 $O(\frac m \omega)$。 然后 ......
CF995F Cowmpany Cowmpensation
拉插优化 dp 在卷怪们眼里已经变成套路了吗,害怕。 考虑一个 dp 的推。设 $f_{u,i}$ 表示 $u$ 子树中填 $[1,i]$ 符合题目条件的方案数,此时不强制 $u$ 选 $i$,所以有: $$f_{u,i}=f_{u,i-1}+\prod\limits_{v\in \text{son ......
CF1530H Turing's Award
参考官方题解。 你发现这个覆盖不太好考虑,考虑时间倒流,变成如下形式: > 一开始,小 A 的位置上有一个数 $a_n$,然后对于接下来 $n-1$ 步,每次小 A 可以向左走/向右走/不动,然后如果此时小 A 所站的位置上**没有数**,就写上 $a_i$,求最后形成序列的最长上升子序列长度。 考 ......
CF1175G Yet Another Partiton Problem
应该是一个很通用的解法。 一个显然的分段 dp: > $f_{j,i}$ 表示前 $i$ 个数分 $j$ 段的方案数,$f_{j,i}\gets \min\limits_{k=0}^{i -1}f_{j-1,k}+w(k+1,i)$。 可以滚动数组,$f_{i}\gets \min\limits_{ ......
CF1821F Timber
考虑如何判断一个方案是合法的,很容易想到贪心,从左到右考虑第 $i$ 棵树: - 如果这棵树能向左倒即 $[x_i-k,x_i]$ 没有被占据,就向左倒。 - 否则向右倒。 显然向左倒对之前已经倒下的树没有影响,而对后面的树来讲,这棵树向左倒能留下尽量多的空间,所以优先向左倒一定不劣。 所以考虑一个 ......
CF1285F Classical?
根据唯一分解定理,令 $x=p_1^{q_1}p_2^{q_2}\cdots p_m^{q_m},y=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$,则 $\text{lcm}(x,y)=p_1^{\max(q_1,k_1)}p_2^{\max(q_2,k_2)}\cdots ......
CF1004F Sonya and Bitwise OR
考虑只有一次询问的时候怎么做。 显然的 cdq 分治,每次分治区间 $[l,r]$,统计跨过 $p=\lfloor\frac{l+r}{2}\rfloor$ 的区间的个数。可以枚举区间左端点,由于右端点右移时区间或单调非降,可以双指针维护。 充分发掘题目条件,由于是区间或,还有一个很套路的性质:一个 ......
CF1264D Beautiful Bracket Sequence
这里是加强版,$n\le 10^6$。 考虑到最后删剩下括号序列形如 `(((...(()))...))`,想到枚举分界点。 设 $p$ 为当前枚举的分界点,$l$ 为 $[1,p]$ 内 `(` 的个数,$r$ 为 $[p+1,n]$ 内 `)` 的个数,$x$ 为 $[1,p]$ 内 `?` 的 ......
CF98E Help Shrek and Donkey
第一次做这种非合作博弈均衡的题。 显然,当双方均有牌的情况下,先手是不可能直接指定桌牌的:正确的概率为 $\frac{1}{m+1}$,错误的概率为 $\frac{m}{m+1}$,显然 $\frac{m}{m+1}\ge\frac{1}{m+1}$。 于是先手指定桌牌的情况只能是 $n=0$ 或 ......
CF1605F PalindORme
不知道是怎么想到的。ntf 实在是不平凡的。/bx/bx/bx 你考虑如何判断一个序列是 $\text{good}$ 的。设重排后序列 $t_i$ 前缀 $[1,i]$ 和后缀 $[n-i+1,n]$ 按位或等于 $w_1$,$[1,i+1]$ 和 $[n-i,n]$ 按位或等于 $w_2$。不难发 ......
CF449D Jzzhu and Numbers
有一个很蠢但是很好写的做法。 就是你先令 $t_i$ 为与起来恰好为 $i$ 的方案数,然后 $g_i$ 为与起来子集中有 $i$ 的方案数。 然后 $g_S=\sum\limits_{T\subseteq S}t_T$,反演一下变成 $t_{S}=\sum\limits_{T\subseteq S ......
CF940E Cashback
首先我们发现在删的数的数量相等的情况下,尽量细分是不劣的。 所以我们可以假设每一段长度至多为 $c$,同时长度严格 $c]$。 复杂度 $O(n)$。 [评测记录。](https://codeforces.com/contest/940/submission/189160602) ......
CF878D Magic Breeding
CF 评分有毒吧,暴力题上 *2900。 先口胡一下,代码等会再写。 首先考虑 $a_{x,y}\in \{0,1\}$,那 $n$ 个属性对应的人的状态只有 $2^k$ 个,可以把状态相同的属性都合并成一个属性。 取 $\max$ 和 $\min$ 操作就变成了两个人与/或起来。我们可以对每个属性 ......
CF1062E Company
对于一个询问 $[l,r]$,假设 $\text{lca}(l,l+1,...,r)=u$。 如果删去了点 $x$,使得 $\text{lca}$ 从 $u$ 下移到了点 $v$,说明 $x$ 一定在 $u$ 的子树内并且不在 $v$ 的子树内。 这样顺序好像不太对,这样说吧: 如果你想让答案从 $ ......
CF1770F Koxia and Sequence
#### 题意 给定非负整数 $n,x,y$,对于所有满足 $\sum\limits_{i=1}^{n}a_i=x$ 并且 $\text{OR}_{i=1}^{n}a_i=y$ 的 $\{a_n\}$,求 $\bigoplus\limits_{i=1}^{n}a_i$ 的异或和。 $n\le 2^{ ......
CF1083F The Fair Nut and Amusing Xor
#### 简要题意: 给你两个序列 $a,b$,一次操作可以将 $a$ 的某一个长度为 $k$ 的子区间全部异或上任意值,$f(a,b)$ 为使得 $a$ 和 $b$ 相同的最少的操作数量。 支持单点修改 $a,b$,并在开头和每次修改后输出 $f(a,b)$ 的值。 $n,k,q\le 2\tim ......
CF1761D Carry Bit
#### Description 设 $f(x,y)$ 是 $x+y$ 的二进制进位数(即 $f(x,y)=g(x)+g(y)-g(x+y)$ ,其中 $g(x)$ 是 $x$ 的二进制表示中 $1$ 的个数)。 给定两个整数 $n$ 和 $k$ ,求出满足$0 \leq a,b #define i ......
CF1361E James and the Chase
#### Description 给定一个有 $n$ 个点 $m$ 条边的**有向强连通图**。称一个点是**好的**当且仅当它到其他点都有且只有一条**简单路径**。如果好的点至少有 $20\%$ 则输出所有好的点,否则输出 `-1`。 $\sum n\leq 10^5,\sum m\leq 2\ ......
CF576E Painting Edges
根据不知从何而来的传统,考前需要写数据结构。 ### Part 1 如何判断二分图 你要是用染色法暴力过了这道题那就只能说是真神仙…… 但是我们可以使用染色的思想。 考虑到颜色数不多,可以开 $k$ 个**拓展域并查集**,对于原图每个点我们拆成两个:$i$ 和 $i+n$,如果 $i+n$ 和 $ ......
CF1603D Artistic Partition
首先如果 $2^k>n$,答案为 $n$。 否则 $k\le \log_2n$,然后就可以令 $dp_{i,j}$ 表示前 $i$ 个数分 $j$ 段的最小答案。 $dp_{i,j}=\min\limits_{k=1}^{i}\{dp_{k-1,j-1}+c(k,i)\}$。 考虑到: $$\beg ......
CF1464F My Beautiful Madness
一发最优解祭( ### Description 给定一棵树,节点 $1$ 到 $n$ 标号,$q$ 个操作,你需要维护一个路径**可重**集合 $P$,操作一共三种: 1. 向 $P$ 集合加入 $u\to v$。 2. 在 $P$ 集合中删掉 $u\to v$(保证操作之前有加入,并且**只删一个 ......
CF1152F2 Neko Rules the Catniverse (Large Version) 题解
发现挨位考虑填哪个不太现实,考虑值域。 令 $dp_{i,j,st}$ 表示考虑到 $i$,此时序列长度为 $j$,$i-m$ 到 $i-1$ 填空状态为 $st$ 的方案数,考虑选/不选数即可: $dp_{i,j,st}\times (\text{popcount}(st)+1)\to dp_{i ......
CF1407E
[In Luogu](https://www.luogu.com.cn/problem/CF1407E) 从 $1$ 出发染色不好处理,考虑从 $n$ 出发进行染色,尽可能让每一条路不可经过,这样也是最大化其他点到 $n$ 的最短路。 如果当前为 $u$,点 $v$ 和 $u$ 有边,如果只有一种颜 ......
CF1178A 题解
[题目链接](https://www.luogu.com.cn/problem/CF1178A) ### 题意简述 有 $n$ 个政党参加了选举,每个政党获得了 $a_{i}$ 张选票,Alice 的政党是一号政党,她需要与其他政党组成一个联盟,满足以下条件: 1. 联盟中的总票数必须**严格大于* ......
CF1842G Tenzing and Random Operations 思考
借鉴了一下 namelessgugugu 的想法,妙妙题。 [link](https://www.luogu.com.cn/blog/namelessgugugu/solution-cf1842g) 这个神奇工具的构造确实挺妙的,非常好的思维题,在此记录一下 ### 代码 ```cpp #inclu ......
CF1662C European Trip
[CF1662C European Trip](https://www.luogu.com.cn/problem/CF1662C) 没有限制怎么做?邻接矩阵 $k$ 次方。 有限制? 设 $A$ 为邻接矩阵, $I$ 为单位矩阵,$deg_u$ 为 $u$ 的度数,步数为 $k$ 是的答案矩阵 $R ......
Codeforces Round 882 div.2 A
Smiling&Weeping 总有人间一两风,填我十万八千梦 A. The Man who became a God time limit per test 1 second memory limit per test 256 megabytes input standard input outp ......
Codeforces Round 885 (Div. 2)
# Preface 打的就是依托答辩居然也能上分,看来手稳还是重要的说 D题半场开香槟以为随便写,然后没想到怎么处理这个局部没有三分性的函数,直接GG 后面听学长一说其实分成四种函数分别求最值即可直接恍然大悟,只能说还是太菜太菜 而且F好像是个蓝桥杯的某个题的弱化版,我说比赛的时候怎么那么多人艹过去 ......
「CF1831E」Hyperregular Bracket Strings 题解
本文网址:https://www.cnblogs.com/zsc985246/p/17565768.html ,转载请注明出处。 ## 前言 没见过的套路,写篇题解记录一下。 ## 题目大意 给定 $n$ 和 $k$ 个区间 $[l_i,r_i]$,你需要找出满足以下条件的**合法**括号序列个数: ......