little 1333a artem cf

posted on 2022-10-08 22:03:07 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/488890) 神仙 min-cut，果然，flow 题的难点是想到 flow，非 flow 题的难点是不要想到 flow。 ......

很有趣的一道题。双倍经验：[P2757 [国家集训队] 等差子序列](https://www.luogu.com.cn/problem/P2757) 要找三个数构成等差序列，一个直接的想法就是枚举中间的数 $a_i$，然后看它左右两边是不是有 $a_i-k$ 和 $a_i+k$。这个枚举的过程已经不 ......

VP战报：1h 过了 A,B,C,D 然后被 E 罚坐 1h rank：210th 题解只有 A-E ## A.Forbidden Integer ### 题目描述： 你需要构造一个正整数序列，满足： 1. 对于 $i$，$a_i\le k$ 且 $a_i\not=x$。 2. $\sum a_i= ......

# 题目 给定一个长度为 $n$ 的正整数序列 $a$，问有多少对 $(i,j),i #include #include using namespace std; typedef unsigned long long ull; const int N=100011; mapuk; int v[N], ......

Mihai and Slavic were looking at a group of $n$ frogs, numbered from $1$ to $n$, all initially located at point $0$. Frog $i$ has a hop length of $a_i ......

首先题目显然可以建模为一个二分图的最大权匹配问题。我们将王子放在左侧，公主放在右侧。根据贪心的思想，将公主按价值从大到小排序，每次搜索交错树；若找到未匹配节点，直接增广，否则丢弃该节点。这样我们就得到了一个 $O(m(m+n))$ 的算法。但这个复杂度显然不够优秀，我们要寻找加速它的方法。 首先直接 ......

## Statement [传送门](https://codeforces.com/problemset/problem/1007/E) 有 $n$ 个车站，从 $1$ 到 $n$ 编号，车站 $i$ 初始有 $a_i$ 个人。 在每个小时结束的前几分钟，车站 $i$ 会新增 $b_i$ 个人。 玩 ......

# X-OR ## 题面翻译 ### 题目描述 本题是**交互题**。 有一个固定的长度为 $n$ 的排列 $P$，其值域为 $[0,n-1]$，你可以进行不超过 $4269$ 次询问，之后你需要输出这个排列 $P$。 ### 输入格式 第一行有一个正整数 $n$，表示排列的长度。 保证 $3\le ......

就我不会 *3500 /kel ## 题目描述 [here](https://www.luogu.com.cn/problem/CF1456E)。 ## 题解 做法考虑从高位往低位处理，由于**有限制的数它的值数确定的，没限制的数值不需要管，因为肯定可以是答案为 $0$。** 所以我们考虑区间 DP ......

### Statement $T$ 次给定整数 $n$，判断是否存在 $q, k \ge 2$ 使得 $1 + q + q^2 + \cdots + q^k = n$。 $1 \le T \le {10^4}$，$1 \le n \le {10}^{18}$。 ### Solution 考虑弱化问题 ......

## 题目 题目链接：https://codeforces.com/contest/1844/problem/G 给定一棵 $n$ 个点的树，每条边有一个未知的正整数边权，给出 $d_i$ 表示点 $i$ 到点 $i+1$ 的距离，求出每条边的边权或判定无解。 $n\leq 10^5,d_i\leq ......

警告： - 注意区分【强连通分量】，【边双联通分量】，【点双连通分量】。 思考： - 之前没有做到过边双连通分量的拆解； - 一个边双联通分量可以看作一个基环上不断加一条链； - 注意，这里加的链首尾可以为同一个位置。 到这步代码就好弄了。 ### 代码 ```cpp #include using ......

太神仙了。 直接子集卷积肯定是不行的，1s 的时限和 62MB 的空间摆在那里。 那就要考虑使用模 $4$ 的性质乱搞了。 我们考虑给每个 $i$，不管它符不符合条件，赋一个权值。如果 $i\ \text{and}\ j\neq 0$，它对答案是没有贡献的，否则它能贡献到 $i\ \text{or} ......

目前为止我是 Luogu 上最优解，不保证后面会不会被神仙同学刷下来，比如 @sinsop90。 upd : 现在不是了，@JWRuixi 用循环展开把我爆踩/ll。 令 $a_{i,0}$ 表示第 $i$ 层上面那个门，$a_{i,1}$ 表示右边的门，$b_{i,0/1}$ 分别表示**它们连向 ......

好像挺神奇的，也可能是我菜。 以下称前 $n-1$ 条边为「树边」，因为它们组成一棵树；后 $n-1$ 条边为「回边」，因为它们由树节点回到根。 就是对于一个询问，如果 $v$ 在 $u$ 的子树内，发现无论如何答案都要包括 $u\to v$ 的只经过树边的路径。那么只走这条路径一定是最优的，直接维 ......

大半个月前做的题，现在才写题解，/qd/qd。 贪心，选出 $k$ 个不相交子段的和的最大值，其实相当于每次把序列最大子段拎出来，加上去，然后取相反数。 证明的话可以考虑模拟费用流，$i\le n$，$S\to i$ 连边，$i\to i+1$ 连边，$i\to T$ 连边，边的流量均为 $1$，$ ......

考虑先手必胜的充要条件。 实际上，只要 $n$ 为奇数或者本质不同排列为偶数时先手必胜。 $n$ 为奇数时，先手必胜，答案就是 $k^n$。 $n$ 为偶数时，令 $a_i$ 为第 $i$ 个字符出现次数，$\sum\limits_{i=1}^ka_i=n$。反面考虑，我们相当于求 $\dbinom ......

难点在于读题。 由于每个人有 $6$ 种选法，答案其实就是某个人赢两次的方案数。 由于三个人本质没有差别，并且一种方案至多只有 $1$ 个人赢两次。所以不妨设 A 赢了两次，答案就是方案数乘 $3$。 考察 A 对于 B 和 C 的比赛，每个人的投票结果，第 $i$ 个人的投票为 $P_i$ 和 $ ......

下面认为 $m=n$。 有一个显然的暴力：对每个点 $(x,y)$，预处理出另外所有点 $(p,q)$ 是否能到达 $(x,y)$，记为 $f_{p,q,x,y}$。查询 $O(1)$，但是预处理 $O(n^4)$。用 `bitset` 优化即可做到 $O(q+\frac{n^4}{\omega}) ......

`divide and conquer`，简单分治题。 显然可以做二维前缀和，考虑令矩阵 $(l_x-1,r_x,l_y-1,r_y)\to (l_x,r_x,l_y,r_y)$，方便统计答案，其实就是左端点减一。 考虑现在按照 $x$ 坐标分治，计算所有跨过 $x=\text{mid}$ 的矩形的 ......

# CF1229F Mateusz and Escape Room 很好的题目。 对于此类在环上的问题，一个经典的思路是断环成链。我们先形式化的描述题意，即给 $i$ 向 $i + 1$ 定一个流量 $x_i$（可能为负）。限制则为 $$ \forall i, a_i + x_{i - 1} - x ......

## 格雷码 && CF1848F. Vika and Wiki 题解 本来有个GitHub上的Hexo博客的，但是我用起来不太熟练……先在博客园里写了后到时候转移过去吧。 ### 前置知识：格雷码（了解的读者可以跳过） 格雷码是所有k-bit（含k个二进制位）的数的一个排列，使得两个循环相邻（即两 ......

简单题。 $i$ 向 $i$ 后**第一个** $j$，$a_j$ 比 $a_i$ 大的点连边，不难发现最后形成了一棵森林，并且一个点的父亲 $\text{fa}_i>i$。 题目变成了取 $[l,r]$ 中的点为起点，向祖先方向走去并且终点编号 $\le r$ 的最长链长度。 考虑离线，维护从每个 ......

简单题。 先把树拍扁成序列，在 dfn 序上区间修改区间查询。 由于时限 4s，我们可以整点怪的，比如 `bitset`。 把区间内的数有/没有表示成 $01$ 序列，考虑到区间加取模相当于区间内的数全部**循环右移**，用 `bitset` 可以做到 $O(\frac m \omega)$。 然后 ......

拉插优化 dp 在卷怪们眼里已经变成套路了吗，害怕。 考虑一个 dp 的推。设 $f_{u,i}$ 表示 $u$ 子树中填 $[1,i]$ 符合题目条件的方案数，此时不强制 $u$ 选 $i$，所以有： $$f_{u,i}=f_{u,i-1}+\prod\limits_{v\in \text{son ......

参考官方题解。 你发现这个覆盖不太好考虑，考虑时间倒流，变成如下形式： > 一开始，小 A 的位置上有一个数 $a_n$，然后对于接下来 $n-1$ 步，每次小 A 可以向左走/向右走/不动，然后如果此时小 A 所站的位置上**没有数**，就写上 $a_i$，求最后形成序列的最长上升子序列长度。 考 ......

应该是一个很通用的解法。 一个显然的分段 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_{ ......

考虑如何判断一个方案是合法的，很容易想到贪心，从左到右考虑第 $i$ 棵树： - 如果这棵树能向左倒即 $[x_i-k,x_i]$ 没有被占据，就向左倒。 - 否则向右倒。 显然向左倒对之前已经倒下的树没有影响，而对后面的树来讲，这棵树向左倒能留下尽量多的空间，所以优先向左倒一定不劣。 所以考虑一个 ......

根据唯一分解定理，令 $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 ......

考虑只有一次询问的时候怎么做。 显然的 cdq 分治，每次分治区间 $[l,r]$，统计跨过 $p=\lfloor\frac{l+r}{2}\rfloor$ 的区间的个数。可以枚举区间左端点，由于右端点右移时区间或单调非降，可以双指针维护。 充分发掘题目条件，由于是区间或，还有一个很套路的性质：一个 ......