做题记录1.0 一些零碎的做题记录。 CF1635D Infinite Set 题意 给定一个数组 aaa。构造一个集合 SSS。它里面的元素 xxx 至少满足以下一条: xxx 在 aaa 中; x=2y+1x=2y+1x=2y+1 且 yyy 在 SSS 中; x=4yx=4yx=4y 且 yyy 在 SSS中。 给出 ppp,问 SSS 中小于 ppp 的元素有多少个,答案对 109+710^9+710 2023-08-03 ACM #训练
做题记录2.0 这里的题目相对会更难一些。 CF1856D More Wrong 题意 给定一个长度为 nnn 的排列。每次询问一个区间 [l,r][l,r][l,r],代价为 (r−l)2(r-l)^2(r−l)2,返回该区间内逆序对的数量。要求找出区间内最大元素的下标,总代价不超过 5×n25\times n^25×n2。 数据范围:2≤n≤20002\leq n\leq 20002≤n≤2000。 题解 单 2023-08-03 ACM #训练
2023 CCPC Henan Provincial Collegiate Programming Contest https://codeforces.com/gym/104354 B. Art for Rest 题意 给定一个序列 aaa。定义 aka_kak 为将 aaa 划分为 ⌈nk⌉\lceil\dfrac{n}{k}\rceil⌈kn⌉ 段,每段升序排序后得到的序列。求有多少个 k∈[1,n]k\in [1,n]k∈[1,n] 满足 aka_kak 单调不降。 题解 容易想到对每个 kkk 2023-07-30 ACM > 2023省赛
2023 Hubei Provincial Collegiate Programming Contest https://codeforces.com/gym/104337 E. Inverse Counting Path 题意 构造一个 n×nn\times nn×n 的 010101 矩阵。要求从左上角走到右下角,每次向右或向下且只经过 111 的路径恰有 xxx 条。 数据范围:n≤30,x≤109n\leq 30,x\leq 10^9n≤30,x≤109。 题解 很酷炫的一道题! 首先,有一种 2023-07-30 ACM #构造 #2023省赛
The 10th Shandong Provincial Collegiate Programming Contest https://codeforces.com/gym/104459 *G. Heap 题意 有一个初始序列,现将每个元素插入堆中。每个元素插入时会按照大根堆或小根堆的规则插入。给出初始序列和最终序列,问每次插入是将它视作大根堆还是小根堆,若有多种可能,输出字典序最小的。 题解 由于每次插入只会影响从当前位置到根的路径上的点,所以直接模拟就可以了。倒序枚举每个元素,找到当前元素最终落在了路径上的哪 2023-07-29 ACM #线段树 #贪心 #欧拉回路 #数论
The 2019 ICPC China Shaanxi Provincial Programming Contest https://codeforces.com/gym/104460 * A. Digit Mode 题意 令 m(x)m(x)m(x) 为 xxx 数码中出现次数最多的最大的数,求 ∑i=1nm(i)\sum\limits_{i=1}^nm(i)i=1∑nm(i)。答案对 109+710^9+7109+7 取模。 题解 感觉是很难的数位dp啊! 设 nnn 有 rrr 位。我们考虑前 p−1p- 2023-07-23 ACM #构造 #数位dp #最短路 #分类讨论 #马拉车 #dfs序 #树上差分
UESTC 2023 Summer Training 雄关漫道真如铁,而今迈步从头越。 Day1 ### E. Jewel of Data Structure Problems 题意 定义一个数组是奇的当且仅当它的逆序对数为奇数。定义一个排列的美丽度为它的最长奇子序列的长度,如果不存在则为 −1-1−1。给出一个排列 ppp 和 qqq 次更新,每次更新交换排列中两个数的位置。要求输出每次更新后 ppp 的美丽度。 题解 用到了一些关于逆序对的性质 2023-07-10 ACM #训练
AtCoder Beginner Contest 309 F - Box in Box 题意 给出 nnn 个长方体。问是否存在两个长方体,其中一个的长宽高均严格小于另一个。 题解 三维偏序问题。由于题目中是严格小于,所以直接套cdq分治好像不太正确。可以这样考虑:先按照 xxx 进行排序,然后建一棵线段树,代表区间 [1,y][1,y][1,y] 上 zzz 的最小值。每次查询的时候在小于 yyy 的区间上查询。注意,当相同的坐标全部查询完后才能进 2023-07-09 ACM #线段树
AtCoder Beginner Contest 278 G - Generalized Subtraction Game 题意 给定 n,l,rn,l,rn,l,r,你需要和交互器博弈。 有一个长度为 nnn 的区间,你和交互器轮流操作。 每次操作,操作的一方选择一个没有被染黑并且长度在 lll 和 rrr 之间的区间,把它染黑。 无法操作的一方寄了,另一方获胜。 题解 直接求SG函数的话是 O(n3)O(n^3)O(n3) 的,需要进行优化。 2023-07-09 ACM #博弈
AtCoder Beginner Contest 279 感觉ABC的质量还是很高的啊。 F - BOX 题意 有 nnn 个盒子,一开始盒子 iii 内装有小球 iii。每次执行以下三种操作之一: 将盒子 yyy 内的所有小球放入盒子 xxx。 记当前所有盒子内的小球个数为 kkk,将小球 k+1k+1k+1 放入盒子 xxx。 询问小球 xxx 在哪个盒子中。 题解 一道并查集应用的好题。 由于询问操作和合并操作,很容易能想到并查集。但是直接 2023-07-07 ACM #dp #并查集 #生成函数