题解p1060 noip 2006
UVA753 A Plug for UNIX 题解
Link UVA753 A Plug for UNIX Question 有 \(n\) 个插座,\(m\) 个设备和 \(k\) 种转换器,每种转换器有无限多个。转换器可以插着转换器用,每个插座或插头的类型可能不同,求最少剩多少个不匹配的设备 Sulotion 先考虑转换器连用的情况,用边表 \( ......
CF1850E Cardboard for Pictures 题解
题意: 思路: 问题转化为:求解满足 $ \sum_{i = 1}^n (a_i + 2w)^2 = c $ 的 $ w $ 。 观察,等式左侧 $ \sum_{i = 1}^n (a_i + 2w)^2 $ 随 $ w $ 的增大而增大,而 $ c $ 不变,因此考虑二分 $ w $ 的值。 ......
CF1809D Binary String Sorting 题解
题意: 思路: 贪心: 单调不降的 $ 01 $ 字符串,一定是一串连续的 $ 0 $ 再加上一串连续的 $ 1 $ 。由于每次操作的代价很大,所以需要在操作次数尽可能少的情况下,尽可能多地使用交换操作。 由于 $ 1 $ 次交换操作,只能减少 $ 1 $ 个逆序对,当存在多个逆序对时,优先通过删除 ......
ucup hefei 题解
比赛链接 B 很有意思的题 首先题目的要求为可以拆分成 \(2\) 个不相交的不降子序列 根据 \(dilworth\) 定理,最小链覆盖 \(=\) 最长反链,所以要求最长反链 \(\le 2\) 即原序列的逆序列的最长不降子序列长度 \(\le 2\) 不难得到一个 \(dp\) 做法为: 令 ......
线性代数题解
前言 写完了这道题我好想刚明白一点最小割???UU好闪,拜谢UU。 题解 首先,我们可以发现若第 \(i\) 行的 \(B\) 没选,那么第 \(i\) 列的 \(B\) 也不选,所以此时对于行和列是等价的。 若 \(A_i\) 是 \(0\),则会减少贡献 \(\sum_{j}B_{i, j}\) ......
P8594 「KDOI-02」一个仇的复 题解
我会组合数! 首先发现同一列只有被不同的横块填或被一个相同的竖块填,且用竖块填完1列之后,会分成两个封闭的长方形,而长方形内部则用横块来填充。 先考虑一个子问题,某个 \(2 \times n\) 长方形内只用 \(k\) 个 \(1 \times x\) 的横块填的方案数,显然有 \(\sum\l ......
CF603题解
CF603 Codeforces Round 334 (Div. 1) CF603A link CF603A题意 现有一个长度为 \(n\) 的 01 串, 可以进行一次区间翻转 ( 起点终点随意, 并且区间里的值 1 变 0, 0 变 1 ), 得到一个新的 01 串, 使得得到的新的 01 串中 ......
[NOI Online #1 入门组] 跑步 题解
[NOI Online #1 入门组] 跑步 题解 突然发现之前打过 NOI Online,啥都不会的情况下这题竟然拿了 70pts。 思路 题意就是统计对于 \(n\le 10^5\),把它进行无序正整数划分的方案数。 对于 70pts,我们考虑 DP:\(f_{i, j}\) 表示对于 \(1\ ......
CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
题意: 思路: 由于 $ k ∈ [1,3] $ ,分类讨论: 当 $ k = 1 $ 时,有人结点自身即为好结点,每种情况的期望为 $ \frac{1}{n} $ , $ n $ 种情况的期望和为 $ 1 $ 。最终答案即为 $ 1 $ 。 当 $ k = 2 $ 时,$ 2 $ 个有人结点之间的 ......
ABC325G offence 题解
给出一个长为 \(n\) 的字符串和非负整数 \(k\)。你可以进行以下操作若干次,使得最终字符串长度最小。 选择一个字串 of。然后删掉 of 以及这之后的 \(i\) 个字符。\(i\) 由你决定,但要满足 \(0\leq i\leq k\)。 输出这个最小长度。\(1\leq n,k\leq ......
[AGC032D] Rotation Sort 题解
题目链接 点击打开链接 题目解法 题目中的操作可以理解为一个点移动位置 首先给出一个结论:每个点只会动至多一次 考虑 \(dp\) 一个比较妙的状态设定是 \(f_i\) 表示 \(i\) 不动的方案数 不妨枚举 \(j\) 表示上一个不动点,限制是 \(j<i\) 且 \(p_j<p_i\) 中间 ......
[AGC037D] Sorting a Grid 题解
题目链接 点击打开链接 题目解法 从后往前推一下,可以得到 \(C\) 一定要把每一行的数都归位到那一行,\(B\) 一定要每一列的目标行数互不相同 考虑构造 \(B\) 这个限制看起来略有些网络流,所以考虑如何建图 令 \(a_{i,j}\) 的目标行数为 \(ln_{i,j}\),我们由 \(i ......
[ARC125E] Snack 题解
题目链接 点击打开链接 题目解法 这题看起来很 \(flow\),不难想到边数 \(nm\) 的建图方法: 具体来说,边为 \((S,i,c_i)(i\in [1,m])\),\((i,j,b_i)(i\in [1,m],\;j\in [1,n])\),\((j,T,a_i)(j\in [1,n]\ ......
P9686 Judg. 题解
P9686 Judg. 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问(记得 @ 这个蒟蒻) Part 2 更新日志 2023-10-02 15:50 文章完成 2023-10-04 12:37 文章通过审核 Part 3 解析 一道简单模拟 ......
P9517 drink 题解
P9517 drink 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问(记得 @ 这个蒟蒻) Part 2 更新日志 2023-08-12 18:06 文章完成 2023-08-14 15:53 文章通过审核 Part 3 解析 这道题考场上 ......
P8679 [蓝桥杯 2019 省 B] 填空问题 题解
P8679 [蓝桥杯 2019 省 B] 填空问题 题解 题目传送门 欢迎大家指出错误并联系这个蒟蒻 更新日志 2023-05-25 21:02 文章完成 2023-05-27 11:34 文章通过审核 2023-06-20 21:03 优化了文章代码格式 试题 A :组队 【解析】 本题是一道经典 ......
P8741 [蓝桥杯 2021 省 B] 填空问题 题解
P8741 [蓝桥杯 2021 省 B] 填空问题 题解 题目传送门 欢迎大家指出错误并联系这个蒟蒻 更新日志 2023-05-09 23:19 文章完成 2023-05-09 23:20 通过审核 2023-06-20 21:03 优化了文章代码格式 试题 A :空间 【解析】 本题考察计算机存储 ......
P8684 [蓝桥杯 2019 省 B] 灵能传输 题解
P8684 [蓝桥杯 2019 省 B] 灵能传输 题解 Part 1 提示 题目传送门 欢迎大家指出错误并私信这个蒟蒻 欢迎大家在下方评论区写出自己的疑问(记得 @ 这个蒟蒻) Part 2 更新日志 2023-06-20 21:46 文章完成 2023-07-03 08:57 文章通过审核 20 ......
[ABC254E] Small d and k 题解
题目传送门 一道暴力题。 度数和 \(k\) 那么小?直接暴力 \(n\) 遍 bfs,注意 bfs 的队列只能 push 距离不超过 \(3\) 的点。但有个问题,每次 bfs 都需要清空一次距离数组,这样子的时间复杂度是 \(O(n^2)\) 的。但也不难想到,距离数组中被赋值的地方不会很多,记 ......
[ARC141D] Non-divisible Set 题解
题目链接 点击打开链接 题目解法 很思维的题,需要用好所有的特殊性质 暴力的做法是建出图,然后求包含点 \(i\) 的最长反链,但这明显过不了 上面的做法没用到 \(a_i<2m\) 的性质 如何用?把 \(a_i\) 拆分成 \(q\times 2^k\;(k\) 为奇数\()\) 的形式,那么对 ......
[ARC141E] Sliding Edge on Torus 题解
题目链接 点击打开链接 题目解法 比较套路的题 首先画个图,然后把 \(y-x\) 相同的变成一个点(使 \(y>x\)) 然后再两个点之间连有权边 那么问题就变成求新图的每个连通块中形成的原图的连通块数量 手玩几个数据发现,原图的连通块数量即为新图的所有环长的 \(\gcd\),再和 \(n\) ......
【题解】Trees and XOR Queries Again - Codeforces 1902F
https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分(也可以用其他种类的LCA算法),然后从数的异或表示很容易想到线性基。 然后因为是无修改的,所以可以轻重链剖分+ST表+线性基。具体来说就是: 先进行轻重链剖分。然后把每次 ......
[AGC061C] First Come First Serve 题解
题目链接 点击打开链接 题目解法 易知总情况数为 \(2^n\) 考虑重复计算的情况为:存在 \([l_i,r_i]\),满足没有 \([l_j,r_j](i\neq j)\) 选在此区间中 可以得到一个容斥的 \(dp\) 做法 这个转移虽然感觉很显然,但卡了我一个晚上,一直调不出 令 \(f_i ......
[CF1902] Educational Codeforces Round 159 A~E 题解
[CF1902] Educational Codeforces Round 159 A~E 题解 A. Binary Imbalance 很快观察到如果有不同的相邻元素,那么一定有解,意味着如果全是 1 无解,其他有解 B. Getting Points 题面很长,可以发现,最好的偷懒方式一定是把所 ......
CF1833G Ksyusha and Chinchilla 题解
题意: 思路: 当 $ n \not \equiv 0 \space (mod \space 3) $ 时,无解; 当 $ n \equiv 0 \space (mod \space 3) $ 时,设 $ size_u $ 表示以 $ u $ 为根的子树还剩余的节点个数,自根节点向叶子节点递归,返回 ......
CF1681D Required Length 题解
题意: 思路: $ BFS $ : 对于每一个数 $ x $ ,枚举其数位 $ num \space (0 \le num \le 9) $ ,将 $ x $ 与 $ num $ 的乘积 $ y $ 放入队列。重复该过程,直至 $ y $ 的位数与 $ n $ 相同。 剪枝: $ 1 $ . 对于重 ......
CF1695C Zero Path 题解
题意: 思路: 设 $ minv $ 表示路径最小权值和, $ maxv $ 表示路径最大权值和。 当且仅当路径长度 $ n + m - 2 \equiv 0 \space (mod \space 2) $ 且 $ minv \le 0 \le maxv $ 时,一定有权值和为 $ 0 $ 的路径; ......
[ARC120E] 1D Party 题解
提供二分+DP做法。 Solution 题意 给出 \(n(\le 2\times 10^5)\) 个单调递增偶整数 \(a_i\),求最小的 \(k\) 满足每一个 \(i\) 都可以在 \(k\) 时刻之前(含)与相邻的数相遇。每个单位时间可以移动一个单位距离。 思路 启发式思考 在想到正解之前 ......
CF1163B2 Cat Party (Hard Edition) 题解
题意: 思路: 对于满足条件的区间 $ [1,x] $ ,有如下三种情况: $ 1 $ . 所有元素出现次数都为 $ 1 $ ; $ 2 $ . 除了一个元素出现次数为 $ 1 $ 之外,其余元素出现次数都相等; $ 3 $ . 除了一个出现次数比其他数的出现次数多 $ 1 $ 的元素之外,其余元素 ......