题解codeforces round 1805

# 写一下$3$月$28$日起开始做的题目感受: ## 1. CF1793B Fedya and Array: 普及- *1100 ### [Luogu链接](http://www.luogu.com.cn/problem/CF1793B) ### [CF链接](https://codeforces ......

# Codeforces Round 690 (Div. 3) https://codeforces.com/contest/1462 ## A. Favorite Sequence 按题意输出 ```CC #include using namespace std; const int N = 1e ......

## Tales of a Sort > ### 题解 >* 找到最大的能够产生逆序对的数即 ......

关于这场div2，只能说一言难尽 C题可以二分的，赛时看到n 点击查看代码 ``` #include #define int long long using namespace std; const int N=1e6+7; int mod=1e9+7; int a[N]; int n,k; voi ......

思维妙妙题。 赛时的错误做法： - 找到每个点往后进位变优的位置，最多 $O(\log)$ 个； - 然后从前往后能变优就变优，往后贪心进位。 hack 数据： ``` 0 1 3 3 5 100 2 1 0 2 2 ``` 输出：`100` 这样子由于 $1$ 到 $2$ 不优，而 $1$ 到 $ ......

# A. Tales of a Sort 关键就是找逆序对 记一组逆序对下标为 $l,r$，则求出最大的 $a_l$ 即可 # B. Good Arrays 记要构造的 Good Array 为 $b$ 前置：$\forall 1\le i\le n,b_i=1$ 然后 $O(n)$ 扫一遍看一下有 ......

# A. The Man who became a God 求出相邻两个元素的差值，去掉前 $m$ 个大的差值以后的差值和即为答案 # B. Hamon Odyssey 由按位与的性质可以知道，**前缀与和** 的值只会越来越小，只要和为 $0$ 的时候我们就清空按位与前缀和，增加一下次数，如果最终 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1856D "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/D "CF 传送门") 直接求最大值不好求。我们可以采用一个交互常见的套 ......

## RiOI R2 赛后反思 赛时开了一个 T1, 但是 $0pts$, 然后就跑去跟人对线然后复盘（主要是我的锅，我忘记对线怎么开始的了）到了吃饭（雾 不过本来我也不会做，不能怪人家 赛后是 shenshen 教我 T1 + 看的若归老师的反思捏 推歌：歌爱ユキ&稲葉曇《キミに回帰缐》（希望没打 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1856E1 "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/E1 "CF 传送门") 考虑局部贪心，假设我们现在在 $u$，我们希 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1856E2 "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/E2 "CF 传送门") 考虑局部贪心，假设我们现在在 $u$，我们希 ......

**链接：** https://codeforces.com/contest/1856/problem/E1 **题目大意：** 给定一棵以节点 $1$ 为根的树，树的大小不超过 $n(1\leq n\leq 5000)$ ，给树的节点赋各不相同的权值（可以简化为某个 $[1,n]$ 的排列），使得 ......

[[abc313D Odd or Even]](https://atcoder.jp/contests/abc313/tasks/abc313_d)。 好有趣捏。 我们考虑 $N=K+1$。 设 $s_i$ 为 $\displaystyle\sum_{j\neq i}a_j\bmod 2$。 因为 ......

## 1.题意简述： 给定一个N行N列的非负整数方阵，从左上角(1,1)出发，只能向下或向右走，且不能到达值为0的方格，求出一条到达右下角的最佳路径，所谓最佳路径是指途径的数的乘积的末尾连续的0最少。 ## 2.样例解释： ```cpp 4 1 3 0 0 0 8 2 25 6 5 0 3 0 15 ......

# [【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2](https://www.luogu.com.cn/contest/122184) ## T1 [P9496 「RiOI-2」hacker](https://www.luogu.com.cn/problem/P9 ......

# [2023年多校联训NOIP层测试4](http://www.accoders.com/contest.php?cid=4467) # 爆零了  ## T1 [幸运数字] ......

# Codeforces Round 882 (Div. 2) ## A The Man who became a God > 给定一个数组 $\{x_1,x_2,\cdots,x_n\}$ 和一个整数 $k$，记 $f(l,r)=\sum_{i=0}^{i \le r-l} |x_{l+i}-x_ ......

# P4426 [HNOI/AHOI2018] 毒瘤 题解 非常好虚树题目，融合了容斥的内容。 ## 简化题意 给定一张 $n$ 个点、$m$ 条边的图，求图的独立集个数。其中 $n \leq 10^5$，$n-1 \leq m \leq n+10$。 独立集：对于图 $G(U, E)$ 的一个点集 ......

# C. Vika and Price Tags [C - Vika and Price Tags](https://codeforces.com/contest/1848/problem/C) **题意：** ​ 初始两串数列$a, b$，对于第$i$个数，令$c_i=|a_i-b_i|$，然后将 ......

# [1843D.Apple Tree](https://codeforces.com/contest/1843/problem/D "Codeforces 1843D") ## Description: - 一棵树( $Tree$ 无环无重边 ) $n$ 个节点，根节点为1（节点编号 $1$~$n ......

# 比赛实况 赛前看了眼难度分布，红橙黄绿，感觉随便杀（爆我） 顺序开题，先看 A 题，没仔细读，一眼以为单次操作只能翻转一位，写了个十进制转二进制找不同，结果 `WA` 了。 再看了一眼题，发现题干定义的操作可以一次操作很多位，然后一个操作是把 0 变 1，另一个是把 1 变 0。 所以只需要看两 ......

## T1 一直没有详细看过位运算的我瑟瑟发抖。出题人给了帮助（有用但是不多）。直接讲考试想法： 首先，手玩样例后，果断猜测：将两个数转化为二进制之后，把头对齐，然后找出不同位，再加上二者位数之差。结果：$0Pts$ 之后，又想了很久，发现了 按位与等价于将原来二进制数中的1变为0，按位或等价于将原 ......

[题目传送门](https://www.luogu.com.cn/problem/CF494A) 一道贪心题。 贪心策略是除了最后一个 `#` 其他的都变成 $1$ 个 `)`，这样前面的 `)` 就尽可能的少，最后的 `#` 变成的 `)` 数量加上前面的 `)` 数量等于 `(` 的数量，这样在 ......

[题目传送门](https://www.luogu.com.cn/problem/CF513B1) 一道枚举题。 数据范围非常小，考虑暴力枚举全排列。 可以 `dfs` 两次，第一次求出能使 $f(p)$ 取得的最大值。第二次求出第 $m$ 个排列。 注意一下，第二次 `dfs` 的时候需要按字典序 ......

[题目传送门](https://www.luogu.com.cn/problem/CF778A) 一道二分题。 $|p|\le2\times10^6$，考虑 $O(n\log n)$ 的算法，而又要输出最大值，不难想到二分答案。 二分删除字母的数量，用一个数组将删掉的字母的下标存起来，然后判断删除字 ......

[题目传送门](https://www.luogu.com.cn/problem/CF1201C) 一道二分题。 熟悉的 $n \le 2 \times 10^5$，一眼二分。 在 `check(x)` 函数里，我们需要判断的是在 $k$ 次操作以内是否能将 $x$ 变为中位数。显然的，我们只需要往 ......

[题目传送门](https://www.luogu.com.cn/problem/CF1132C) 一道枚举题。 我们可以直接枚举那 $2$ 个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到，然后枚举第一个被去掉的粉刷匠，然后计算剩下的粉刷匠会将每个栅栏刷到多少次，我们只需要看只能被刷 $1$ ......

[题目传送门](https://www.luogu.com.cn/problem/CF237C) 一道二分题。 我们需要用二分在 $O(n\log n)$ 的时间复杂度内得到答案，也就是说我们的判断函数时间复杂度必须为 $O(n)$，因此考虑前缀和。 $sum_i$ 表示出现在区间 $\left[a ......

[题目传送门](https://www.luogu.com.cn/problem/CF552E) 一道枚举题。 枚举左括号和右括号的位置括号，为了答案最优，左括号只能在开头或者 `*` 的右边。右括号只能在末尾或者 `*` 的左边。每一次枚举都计算一下这个加了括号后表达式的值，最后取最大值即可。 # ......

[题目传送门](https://www.luogu.com.cn/problem/CF1092C) 一道字符串题。 我们考虑还原字符串后再一个一个的判断。很显然，这个字符串是由一个长度为 $n-1$ 的前缀和后缀组成的。因此我们可以找到这 $2$ 个长度为 $n$ 的字符串，然后枚举哪个是前缀，哪个 ......