题解1545 cf
[CF1641D] Two Arrays
## 题目描述 Sam changed his school and on the first biology lesson he got a very interesting task about genes. You are given $ n $ arrays, the $ i $ -th o ......
[CF1830E] Bully Sort
## 题目描述 On a permutation $ p $ of length $ n $ , we define a bully swap as follows: - Let $ i $ be the index of the largest element $ p_i $ such that ......
[CF1599A] Weights
## 题目描述 You are given an array $ A $ of length $ N $ weights of masses $ A_1 $ , $ A_2 $ ... $ A_N $ . No two weights have the same mass. You can put ......
[CF1830D] Mex Tree
## 题目描述 You are given a tree with $ n $ nodes. For each node, you either color it in $ 0 $ or $ 1 $ . The value of a path $ (u,v) $ is equal to the ME ......
[CF1854C] Expected Destruction
## 题目描述 You have a set $ S $ of $ n $ distinct integers between $ 1 $ and $ m $ . Each second you do the following steps: 1. Pick an element $ x $ in ......
弹飞绵羊题解
## 弹飞绵羊题解: ### 思路: 先注意一下装置编号是0到n-1,坑了我半天 先思考为什么可以用分块做? 总所周知,要是我不存在修改操作的话,我直接o(1)就结束了。 具体做法的话,就是从后往前扫一遍,cnt[u]=cnt[to]+1。然后直接查询就好了,特别地,直接跳出去的cnt[i]=1。 ......
CF1894 H Asterism Stream题解
### 题意 给定一个 $n$ , 有一个初始为 $1$ 的整数 $x$ , 每次有相同概率进行以下两个操作的其中一种: - 使 $x$ 加 $1$ - 使 $x$ 乘 $2$ 问期望多少步操作可以使 $x$ 大于 $n$ , 输出期望步数模 $998244353$ 的值。 其中 $1 \leq n ......
B0831 模拟赛题解
[**原题链接**](https://local.cwoi.com.cn:8443/contest/C0300/problem/A) ## 前言 先说点闲话。 本来是 8.15~8.19 放假的,由于我是借读,分校这边 23 号军训,之前军训的时候我又去复习中考了,所以得参加。我家住在外地,考虑到折 ......
CF1861A Prime Deletion
## 思路 诈骗题,看着很难,其实是一道大水题。 常识告诉我们,对于一个两位数,首位无论是几,都一定存在质数。 所以我们就把输入的字符串第一位作为质数的第一位,遍历字符串,找到刚好与第一位组成质数就行了。 ## AC code ```cpp #include using namespace std; ......
CF1861B Two Binary Strings
## 思路 ~~最近熬夜打 CF,视力下降了。没看到题目里给了第一位和最后一位必定是 $0$ 和 $1$,导致想了半天。~~ 考虑枚举字符串的位置 $i$。 首先如果遇到了两个串第 $i$ 位都是 $1$,那么可以直接覆盖中间的片段,一定能成功。 如果遇到不同的位置,考虑找到最近的 $0$ 与第一位 ......
CF1861C Sorting By Multiplication
## 思路 机翻害人,我还以为是 $1$ 和 $0$ 是对原序列排序,害得我比赛的时候都没对,恼。 首先,对于新加入的数字,我们可以先不确定是否有序,而是等到后续的 $1$ 或 $0$ 出现,再确定。 用 $num$ 表示目前有多少数字,用 $so$ 表示确定有序的数字中最后一位的位置,$nso$ ......
CF1861D Sorting By Multiplication
## 思路 先考虑不能把数变为负数的情况。 显然,当 $a_i\ge a_{i+1}$ 时,需要对 $[i+1,n]$ 的数都要乘以一个很大的数。 所以答案是 $a_i\ge a_{i+1}$ 的个数。 但是可以变为负数,考虑把一部分变为递减的,再变成负数,另一部分正常计算。 因为负数一定小于正数, ......
CF1866B Battling with Numbers
## 思路 首先对于 $p$ 和 $q$,他们都必须是 $Y$ 的倍数,不然 $\gcd$ 就不是 $Y$ 了。 再算出来 $\frac X Y$ 的值,当然如果 $X$ 不是 $Y$ 的倍数,那肯定无解。 因为此题特殊的输入方式,所以我们可以很轻易的得到 $\frac X Y$ 的质因子和个数。 ......
CF八九月杂题选做
## [1859D](HTTPS://CODEFORCES.COM/CONTEST/1859/PROBLEM/D) ## [1859E](HTTPS://CODEFORCES.COM/CONTEST/1859/PROBLEM/E) ## [1859F](HTTPS://CODEFORCES.COM/ ......
洛谷P3808 【模板】AC 自动机(简单版)题解 AC自动机模板题
题目链接:[https://www.luogu.com.cn/problem/P3808](https://www.luogu.com.cn/problem/P3808) AC自动机模板题。 示例程序: ```c++ #include using namespace std; const int m ......
【题解】P3648 [APIO2014] 序列分割
# 【题解】P3648 [APIO2014] 序列分割 对于这道题,我们很容易想出一个暴力 `DP`: 设 $f_{i,j,k}$ 表示将区间 $[i,j]$ 切割 $k$ 次的最大得分,$s_i$ 表示 $a_i$ 的前缀和。 我们可以得到一个式子: $$ f_{i,j,k} = \max_{i\ ......
CF786c分块题解
## CF786c分块题解 ### 思路: 首先思考一下如果直接硬着头皮做会怎么样? 对于每一个k,我都要遍历一遍数组贪心求解ans,导致n方时间复杂度 要发现一下性质: 1. 答案最多为ceil(n/k)。 2. 随着k的增加,答案单调不增。 3. 随着k的增加,答案越不容易改变(连续相同的答案越 ......
【牛客周赛 Round 10】A-D题解
### A https://ac.nowcoder.com/acm/contest/64272/A **题意** 游游定义一个数组为“稳定的”,当且仅当数组相邻的两个元素之差的绝对值不超过1。例如[2,3,2,2,1]是稳定的,而[1,3,2]则不是稳定的。 游游拿到了一个数组,她想求出该数组的最长 ......
8.30 模拟赛 光和影(dream) 题解
概括:大分类讨论。 首先有个重要结论,无论是三种操作中的哪一种,他的左儿子仍然在他的左子树内,右儿子在右子树内。同时,旋转一个点一次,对他更上面的点的深度没有影响。 以此,我们预处理出一个 $up_{u,0/1}$ 表示将 $u$ splay 到根上,对左子树和右子树深度的影响,由于上面的结论,这个 ......
CF838D Airplane Arrangements 题解
## 题意 一架飞机有 $n$ 个座位排成一列,有 $m$ 名乘客($m \leq n$)依次上飞机。 乘客会选择一个目标座位(两人可以选同一个目标座位),然后选择从前门或者后门上飞机,上飞机后,他们会走到自己的目标座位,如果目标座位已经有人坐了,他们会继续往前走,在走到第一个空位后坐下。如果走到最 ......
【题解】P2900 [USACO08MAR] Land Acquisition G
题目链接:[P2900 [USACO08MAR] Land Acquisition G](https://www.luogu.com.cn/problem/P2900) 我们通过题目可以得出一个较为清晰的结论: - 我们将所有的矩形排列起来,可以发现最后被完全包含在另一个矩形内的矩形是没有意义的。 ......
[ABC318G] Typical Path Problem 题解
## 题意 给定一个 $N$ 个节点和 $M$ 条边组成的简单无向联通图,给定三个节点 $A,B,C$,求是否存在一条简单路径满足 $A \rightarrow B \rightarrow C$。 ($3 \le N, M \le 2 \times 10^5$)。 ## 题解 因为简单路径要求每个节 ......
【题解】AtCoder Regular Contest 163 A-D
E 太过于 adhoc,F 太过于神仙,就不做了。 ## A.Divide String ### 题目描述: 多组数据。 给出一个长为 $N$ 的字符串,问能否将其划分为多段,使字典序**严格**上升,保证 **$\sum{N}\le2000$**。 $ 2\ \le\ N\ \le\ 2000 $ ......
题解:【ABC318G】 Typical Path Problem
[题目链接](https://www.luogu.com.cn/problem/AT_abc318_g) 无脑圆方树。建广义圆方树,对于路径 $u \to v$ 上的圆点为必须经过的割点,经过的方点连出去的任意一个点 $z$,记路径上和方点相连的两个圆点为 $x,y$,原图必定存在一条简单路径 $x ......
【动态规划】“新手动态规划合集”题解
## 动态规划三要素 阶段,状态,决策 ## 动态规划经典模型 ### LIS(最长上升子序列) 给定长度为 $N$ 的序列 $A[i]$,求出其最长上升子序列的长度。(以不严格上升为例) - 阶段:已经处理的序列长度 $i$ - 状态:$f[i]$ 表示以 $A[i]$ 结尾的 LIS 长度 - ......
[ABC318D] General Weighted Max Matching 题解
# [ABC318D] General Weighted Max Matching 题解 ## 题意 给定无向有权完全图,求最大权匹配。 ## 思路分析 注意到 $n \le 16$,我考虑状压 DP。 设当前点集 $S$ 中最大权匹配的答案是 $f_S$,我们考虑 $S$ 中“最后”一个点 $p$ ......
CF1848B Vika and the Bridge 题解
# CF1848B Vika and the Bridge 题解 ## 题目大意 ~~给个题目传送门吧,感觉题意已经很清楚了~~ [题目传送门](https://www.luogu.com.cn/problem/CF1848B) ## 分析 (~~我不会告诉你我第一眼看过去是二分~~) 因为我们只能 ......
[ABC318E] Sandwiches 题解
## 题意 给定一个长度为 $N$ 的正整数列 $A = \left(A_1, A_2, \cdots,A_N\right)$,求满足以下条件的正整数三元组 $\left(i, j, k\right)$ 的数量: - $1 \le i typedef long long valueType; typ ......
[ABC318E] Sandwiches 题解
一开始考虑枚举 $i$ 或 $k$ 来统计,发现需要 $O(n^2)$ 的时间复杂度。 因此考虑枚举 $j$,我们可以用 $l_x$ 表示满足 $i const int N=3e5+5; int n; int a[N]; int l[N],r[N]; long long ans,sum; int m ......