题解1203 div cf

[题目链接](https://codeforces.com/problemset/problem/724/G) 不妨先看一道更为基础的题：[CF845G](https://codeforces.com/problemset/problem/845/G)以及[它的题解](https://www.cnb ......

## [$DZY$ $Loves$ $Colors$](https://codeforces.com/problemset/problem/444/C) ### 一、题面翻译 有一个 $n$ 个元素组成的序列，每个元素有两个属性：颜色 $c_i$ 和权值$w_i$。$c_i$ 初始为$i$，$w_i ......

题目链接：[https://www.luogu.com.cn/problem/P3038](https://www.luogu.com.cn/problem/P3038) 题目大意： 一棵树维护两种操作： 1. 一条路径上每条边边权 $+1$； 2. 查询路径上的边权和。 解题思路： 树链剖分模板题 ......

题目链接：[https://www.luogu.com.cn/problem/P2292](https://www.luogu.com.cn/problem/P2292) 题目大意： 给定 $n(\le 20)$ 个模式串 $s_i(|s_i| \le 20)$，有 $m(\le 50)$ 次询问， ......

给一个正整数 $n$ ，找到一个序列 $a_1, a_2, \cdots, a_n$ 满足 $$ \bigoplus_{i=1}^{n} a_i = \frac{\sum_{i=1}^{n} a_i}{n} $$ 。 一个原始的问题： $\bigoplus_{i=1}^{n}a_i=\sum_{i= ......

[传送门](https://www.luogu.com.cn/problem/P9594) 简要题意： 给定 $m$ 条线段，每条线段由四个正整数参数 $l_i,r_i,c_i,w_i$ 描述，其中 $l_i,r_i$ 是这条线段的端点，$c_i$ 是这条线段的种类，$w_i$ 是这条线段的权值。 ......

在 Codeforces 上看到了这题的 $\mathcal{O}(n ^ 4 / \omega)$ 做法，和大家分享一下。 [原版 Solution 链接](https://codeforces.com/blog/entry/119504?#comment-1060285) 记 $d$ 为原字符串 ......

考虑 `dp`，设 $f_{i,0/1}$ 表示考虑到前 $i$ 位，且第 $i$ 位填入 A/B 可能的答案集合，显然地朴素转移时间复杂度 $O(n^2)$。 试分析 `dp` 性质，观察发现所有 `dp` 中得到的集合为区间内抠去至多一个点。 > > 证明 > 我们首先来观察转移过程是怎样的。第 ......

给一个长为 $n$ 的排列 $p$ 和一个正整数 $k, (k \leq n)$ 。在一步操作中，可以： * 选择 $k$ 个不同的元素 $p_{i_1}, p_{i_2}, \cdots, p_{i_k}$ 。 * 将他们移除然后排序，并拼接到剩余数组末尾 找到最小的操作数使得整个排列为增序。 典 ......

## $a$ ```cpp int a[N]; void solve(){ int n=read(); for(int i=1;i=5?"Penta Kill":"Shut Down"); //puts(ans>0?"Yes":"No"); } ``` ## $b$ 想了很久，感觉没有不用最短路算法 ......

给一个长为 $n$ 的数组 $a$ ，统计出所有二元组 $(a_i, a_j)$ 数量，满足以下条件： * $1 \leq j view ``` #include void solve() { int n; std::cin >> n; std::vector a(n); for (int i = ......

有三个字符串 $s_1, s_2, s_3$ ，每个字符串只有 $a, b$ 组成。三个字符串顺序连接在了一起。满足以下条件之一： * $s1 \leq s_2, s_3\leq s_2$ * $s1 \geq s_2, s_3\geq s_2$ 以上为字典序比较。 给出连接的三个字符串，输出一组可 ......

给一个正整数 $n$ ，问能否构造出任意一个一个长为 $n$ 的排列满足 $\forall l,r,\ 1 \leq l view ``` #include void solve() { int n;std::cin >> n; if (n == 1) std::cout > _; while (_ ......

给一个无序排列 $p_1, p_2, \cdots, p_n$ 。为了排序这个排列，选一个常数 $k(k \geq 1)$ 并且在排列上做一些操作。 * 一次操作可以选择 $i, j, (1 \leq j view ``` #include typedef long long ll; ll gcd( ......

定义一个数的幸运值是这个数的数位的最大值减去最小值，如 $luckiness_{769} = 9 - 6 = 3$ 。给出 $l$ $r$ ，求 $[l, r]$ 中最幸运的数，若最幸运的数有多个，任意一个为答案。 考虑拆分数位，然后枚举。以 $O(d)$ 的复杂度计算幸运值。则线性扫一遍的复杂度为 ......

给一个长为 $n$ 的数组 $a$ 。回到 $q$ 个询问。 * 让 $a_l, a_{l + 1}, \cdots, a_r$ 变为 $k$ ，$\sum_{i = 1}^r a_i$ 是否为奇数。 每个询问独立。 显然每个学问独立可以使用前缀和计算区间和，单个询问中 $pre_{1, l - 1 ......

给一个长为 $n$ 的数组 $a$ ，定义 $a$ 的 $score$ 为 $a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n$ 的 $MEX$ 。 找到 $a$ 的 最小 $score$ 如果 $a$ 可以被重排。$(0 \leq a_i \leq 2 \t ......

给一个长为 $n$ 的正整数数组 $a$ ，在一步操作中，你可以选择任一个数并且 $add\ 1$ 。要求最多执行 $2n$ 步操作使 $a$ 满足 $\forall i, i \in[1, n - 1], a_{i} \nmid a_{i + 1}$ 。输出任一个在操作数限制内可以得到的合法数组。 ......

给一个正整数 $n$ ，找一段最长的 $[l, r]$ ，满足 $\forall i, i \in [l, r],\ s.t.\ i | n$ 。输出这一段区间的长度，即 $r - l + 1$ 。 这题是一个准结论题，需要一些知识点和观察的基础。 放在 $900$ 的位置是因为结论存在的区间太容易 ......

给一个长为 $n$ 的数组 $a$ ，给一个长为 $n$ 的乱序数组 $b$ ，给一个正整数 $k$ 。要求重排 $b$ 使得 $\forall i, |a_i - b_i| \leq k$ 。输出其中一种 $b$ 的排列方式。 一个性质题。（div2 前几题很喜欢有序数组的经典性质） 总结一下有序 ......

给一个长为 $n$ 的排列（无序）$p$，为 $p_1, p_2, \cdots, p_n$ 。一个正整数 $k$ 。 允许执行任意次以下操作： * 选择两个数 $p_i$ $p_j$ 满足 $|i - j| = k$ ，并且 $swap(p_i, p_j)$ 。 允许最多执行一次特殊操作： * 选 ......

给一个长为 $n$ 的排列，对于它的每一个排列 $p$ ，复制一份并 $reverse$ 拼到原排列的后面得到 $a = \left [p, p_{reverse} \right ]$ 。 求 $p$ 的所有排列对应的 $a$ 的逆序对数之和，结果对 $1E9+7$ 取模。 **逆序对贡献**： * ......

给一个 $n \times m$ 的网格，每个格子对应一个坐标 $(a, b)$ 。如果存在一个各自的坐标为 $(c, d)$ 且满足 $|a - c| + |b - d| = 1$ ，则称 $(a, b)$ 与 $(c, d)$ 相邻。 给出 $k + 1$ 个点，初始坐标分别为 $(x_0, y ......

给三个点 $A, B, C$ ，两个人一开始都在 $A$ 点，一个人希望最快到达 $B$ ，另一个人希望最快到达 $C$ ，且他们希望尽可能走一条路径。则这条路径最长是多长。 经典的高维可以由低维叠加的问题。 * 坐标问题 * 动态规划问题 并非所有高维问题都可由低维叠加，但任何二维问题都可由一维叠 ......

给一个长度为 $n$ 的字符串 $s$ ，只包含字符“”。 一个长度为 $n + 1$ 的数组 $a$ 与 $s$ 是兼容的当且仅当对于任意 $i$ ： 1. $s_i$ is $$ ，当且仅当 $a_i > a_{i - 1}$ 定义一个数组的 $cost$ 为这个数组中不同数的个数。 求一个 $ ......

给 $n$ 条一维线段，一条端点为 $l, r$ 的线段可以覆盖 $\forall i, l \leq i \leq r$ 。定义 $f(x)$ 为点 $x$ 被线段覆盖的次数。一个点 $x$ 称为是 “完美的” 如果 $y \neq x, f(x) > f(y)$ 。 给一个点 $k$ ，询问是否 ......

————哪有岁月安好，只是有人为你负重前行 给一个长为 $n$ 的数组 $a$ ，称一个数组 $b$ 是 $good$ 的如果满足以下条件： 1. $\forall i, a_i \neq b_i$ 2. $\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}b_i$ 判断对于一个 $a ......

有 $n$ 个值，分别为 $a_1, a_2, \cdots, a_n$ 。希望做两个操作 1. 移除一些（可能是 $0$ 个）问题 2. 重排列剩下的问题 一组值是好的当且仅当任意对于 $\forall i, j,\ 1 \leq i,j \leq n,\ |i - j| = 1,\ s.t.\ ......

1.挖地雷 Description 在一个地图上有N个地窖（N 点击查看代码 ``` #include using namespace std; const int N = 20; int connect[N][N], mark[N], a[N], n;//mark用于标记该地窖是被访问过 int ......

### 题目大意 $n$ 次询问，每次给定一个点 $(x,y),x\ge 0, y\ge 0$，问有多少种对角线长为偶数的正方形使得在用该正方形正密铺第一象限的情况下该点位于正方形顶点上。 **正密铺第一象限** 指将第一个正方形的角与 $x$ 轴和 $y$ 轴接触。此后的正方形都与至少一个已放置的 ......