题解1545 cf
Peaks 题解
Peaks题解 浅提离线算法 将询问按照 \(x\) 排序,在最小生成树加边的过程中,每加一条边就把所有 \(x\) 小于当前边权的询问处理掉。 求第 \(k\) 大可以用平衡树搞定,将并查集合并时也将平衡树进行启发式合并(启发式合并也就是小的合并到大的上面) 在线做法 其实题目描述已经很明显了,D ......
[AGC030C] Coloring Torus 题解
非常巧妙的一道构造题,发现对于所构造的 \(n\) 有上限,那么对于 \(K<=500\) 的情况,很好构造,每行全是一个数就行了,对于 \(K>500\) 的情况,显然每行都是 \(1,2,...,n\) 的循环同构构造就行了,也可以理解是斜着填,然后对于剩下的 \(K-500\) 个数,每次选择 ......
CF1861F Four Suits【网络流,贪心】
有 \(n\) 个人,\(4\) 种不同的卡牌,初始第 \(i\) 个人有 \(a_{i,j}\) 张第 \(j\) 种卡牌。 你是局外人,手里第 \(j\) 种卡牌有 \(b_j\) 个,你现在要把你的卡牌分给这 \(n\) 个人,使得分完之后每个人手里的卡牌总数相等,保证有解。 第 \(i\) ......
CF149E Martian Strings
感觉这题 SA 做法绝对不止 \(\color{orange} *2300\)。 洛谷 CF 给出字符串 \(s\),以及 \(m\) 个询问串 \(p_i\),每次询问是否能找到两个不交的区间 \([a,b],[c,d]\) 使得 \(\overline{s_as_{a+1}\dots s_bs_ ......
cf1322BPresent(基数排序+双指针+拆位)
cf1322BPresent 首先拆位是显然的,对于两个数a[i],a[j],除了考虑当前位上的数,我们还要考虑是否会产生进位,我们可以利用基数排序+双指针,因为我们每次都是将低位的排好序了,所以我们可以用双指针计算进位,然后分类计算一下,当前为为1的情况即可。 #include<cstdio> # ......
370场leetcode2题题解
100115.找到冠军Ⅰ 一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。 给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i ......
[CF1895F] Fancy Arrays
Fancy Arrays 洋洋强到爆炸啊。 根据某个差分数组可以得出最小值的位置(即使有多个也会因为差分数组有区别而对应不同原序列),所以钦定最小值后可以得出所有 \(a_i\geq0\) 的方案数,不难得出区间为 [0,x+k],并且最小的大于 x 的数一定合法。 然后减去所有值都在 [0,x) ......
[CF1781F] Bracket Insertion
Bracket Insertion 托利斯特老了/kk 我一开始想的是 () 的权值为1,)( 的权值为-1,树上 dp 满足某子树由若干条类似斯特兰数方案的链构成。 但是有概率使得权值计算很难处理。 所以考虑把合法方案最终状态表示出来。 套路地设 ( 的权值为1,) 的权值为-1。 可以发现若新加 ......
Exhausted? 题解(线段树)
Exhausted? 题解 前言: 看本篇题解,您如果想要掌握所有知识点的话,请您先去了解下什么是霍尔定理,当然如果可以的话,可以去看看我的这个博客。 涉及的算法和思想知识点: 线段树、扫描线。 霍尔定理。 较少的容斥原理。 正文: 理论分析: 从简单入手:我们想想,要是值域再小一点的话,我们可以怎 ......
题解 P6880 [JOI 2020 Final] オリンピックバス
洛谷。 题意 应该显然,注意最多只能翻转一条边,并且可以不翻转。 分析 首先观察数据范围 \(2\le N \le 200\),\(1\le M \le 5\times 10^4\),可以发现我们的 \(N\) 和 \(M\) 并不是同级的,因此,在众多的最短路算法中,我们应当选择不加堆优化的 di ......
【题解】NOIP2021 - 方差
NOIP2021 - 方差 https://www.luogu.com.cn/problem/P7962 想当年我第一次站在 noip 赛场上,过了 T1 剩下三题就一题不会了……幸好这题拿了点分水了个一等。 观察操作:若对于连续的三个数 \(a,b,c\),对 \(b\) 进行一次操作后就变成了 ......
题解 P6879 [JOI 2020 Final] スタンプラリー 3
传送门。 前置知识 区间 dp。 题意 一个周长为 \(L\) 的圆,在初始点的顺时针方向依次排列着 \(N\) 物品,第 \(i\) 个物品在顺时针 \(X_i\) 米处,可以在 \(T_i\) 前收集到这个物品。 此时,从初始点出发,时间为 \(0\),允许顺时针或逆时针移动,问最多可以收集到多 ......
2023联合省选 题解
目录D1T1 P9166 [省选联考 2023] 火车站D1T2 P9167 [省选联考 2023] 城市建造D1T3 P9168 [省选联考 2023] 人员调度D2T1 P9169 [省选联考 2023] 过河卒D2T2 P9170 [省选联考 2023] 填数游戏D2T3 P9171 [省选联 ......
cf1709E. XOR Tree(启发式合并入门)
cf1709E. XOR Tree 贪心是显然的,关键是如何合并两棵子树的信息,可以采用启发式合并。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vecto ......
题解 P6878 [JOI 2020 Final] JJOOII 2
好久没写题解,水一篇。 题意 题意显然。 分析 看到这道题,我们就应该进行一个小贪心,对于最左边某一字符,直到最右边的这一字符,我们不会在中间删除同样的字符,不然则可以保留这一字符,将两边往内缩。 也就是说,我们确定了最左边的 J 后,那么留下最后一个 J 必然是当前这个 J 的后面的第 \(K-1 ......
ARC_068F Solitaire题解
非常骚的一道题 首先看数据范围就很像dp(而且在dp专题里),尝试直接dp,发现不太行 手玩一波样例,发现答案是 2的若干次方乘一个系数。我们发现 “若干”=n-k-1,这是巧合吗!? 思索一番,会发现当我们取完k个数后 剩下的n-k个数 取法就为 2^(n-k-1) ,为什么呢? 可以把每次操作看 ......
APIO 斑斓之地题解
APIO 斑斓之地题解 洛谷题解区域应该有我的这篇博客哦 前言: 这一道题目涉及到的算法主要是主席树,思想主要是平面图(欧拉定理)以及简单的容斥原理。如果您想要真正掌握这道题所涉及的知识点,请您先去了解这个定理以及明晰主席树的代码打法。 正文: 注明:为了表示方便,我们把蛇蛇经过的点叫做黑点吧。不经 ......
[CSP-J 2023] 公路 题解
题目传送门 一道 dp 题。 好像大家写的都是贪心,这里给出一种 dp 的写法。 在 dp 之前,我们需要明确以下几个东西: 状态的表示,状态转移方程,边界条件跟答案的表示。 状态的表示 \(dp_i\) 表示到达第 \(i\) 个站点所需要的最少钱数,\(w_i\) 表示在使用最少钱数到达第 \( ......
Dasha and Nightmares 题解
题目传送门 一道字符串题。 既然两个字符串拼接后有一种字符不能出现,那么可以枚举这个字符,我们就只需要关注没有出现过这种字符的字符串了。 剩下的字符串仅会出现 \(25\) 种字符,而我们并不关心字符串里字符的顺序,仅关心字符出现的个数的奇偶性,因此我们可以把字符串看做是一个长度为 \(25\) 的 ......
[ABC326C] Peak 题解
题目传送门 一道二分题。 首先非常显然,你选择的这个区间左端点在 \(a_i\) 上肯定更优,因此我们可以枚举左端点 \(l\)。然后剩下的就是使用二分求出有多少个 \(a_i\) 满足 \(l\le a_i< l+m\),具体可以使用 std :: upper_bound 实现。 Code #in ......
2023年11月第一周题解-------数组
1. 问题A:LY学长的随机数 解题思路 第一种思路是先去重后排序 第二种思路是先排序再去重 解题方法 暴力遍历 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #i ......
cf1834E. MEX of LCM(维护右端点计算区间lcm)
cf1834E 首先可以估计一下答案的量级,因为小于答案的质数都要必须要出现,5e6以内的质数大概就是3e5,所以答案不超过5e6。 我们维护以i右端点的lcm的值,这些值的数量不会太多,因为每次增长都至少×2,所以是log级别。 每次新加的时候记得更新和去重即可。 #include<cstdio> ......
CF1196B
题意: n个数,分割成k个部分,使得每份和都为奇数 做法: 一个序列的和的奇偶性和偶数没关系,所以只需要考虑奇数的个数 现在考虑两个问题: 1.如果奇数的个数小于最终要求的k,那么就无法完成分类(即是如果一个数一块也不行) 2.如果奇数的个数,记为cnt,cnt的奇偶性和k的奇偶性不同,例如cnt为 ......
CF1644D Cross Coloring
CF1644D Cross Coloring 题意: 在一个 \(n\) 行 \(m\) 列的网格里执行 \(q\) 次操作,每次操作在 \(k\) 种颜色中 (没有初始颜色) 选择一种给第 \(x_i\) 行和第 \(y_i\) 列染色且覆盖原有颜色,问最终染色方案数 做法: 因为后染的色会覆盖先 ......
CF689E 题解
很无语。 一开始脑抽,把交集和并集的概念搞混了。 后面猛然一想:并集?这不是大水题么。 然后 coding,ans 还忘记取模了。 回归正题,求的是 在 \(n\) 条线段中取 \(k\) 条线段,其中有多少个点被 \(k\) 条线段覆盖,求所有方案的答案和。 规约为贡献计算。 考虑点的贡献,假设本 ......
CF1651F 题解
首先是数学表达这道题 考虑第 \(i\) 个怪物。 它跑完自己的全程扣得血是: \[\sum\min\{c_j,m_{j,lst} + \Delta t \times r_j\} \]\(\min\) 有点难搞,没啥好性质。 考虑拆开为两个部分: \[\sum c_j + \sum (m_{j,ls ......
CF1838C题解
显然 \(1\) 不是质数,除二外偶数不是质数。 然后分类讨论 对于 \(m\) 为偶数,构造 \[\begin{bmatrix} 1 & 2 & 3 & \cdots & m \\ m+1 & m+2 & m+3 & \cdots & 2m \\ &&\cdot\\ &&\cdot\\ &&\cd ......
CF773A 题解
真的是蓝题?这真的不是小学数学题? 我们是要求满足(其中 \(a\) 为正确数,\(b\) 为总数) \[\frac{x + a}{y + b} = \frac{p}{q} \]的最小 \(b\)。 我们可以先把右式的分子分母变化到与 \(\frac{x}{y}\) 类似的大小。 int bs1 = ......
CF859G 题解
总结题意 显然可以转化为序列问题嘛。 给出序列 \(A\{a_i\}\),你需要通过若干次操作使其归零。 操作: 选定 \(d | n\)、\(k\)、\(r\),对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。 题解 很明显,加减相互抵消,对于所有 \(d\)、\( ......