CF508D Tanya and Password（欧拉路径） 2019-10-15 题解 题目链接 CF 题意简述 有一个字符串 S[1..n+2]，告诉你 ∀1≤i≤n,S[i..i+2]（所有长为 3 的子串），求任意一个满足条件的 S。 1≤n≤2⋅105，字符集为大小写字母 + 数字。 阅读更多
gym102268D Dates（贪心，二分图匹配，线段树） 2019-10-11 题解 题目链接 CF 题意简述 给你一张二分图：左边 t 个位置，第 i 个位置上有 ai 个点；右边 n 个带权的点，第 i 个点与位置在 [li,ri] 之间的所有左边的点有连边；匹配权值为匹配中右边点的权值之和；求最大权匹配。 1≤n,t≤3⋅105，保证 li≤li+1, ri≤ri+1。 阅读更多
CF878E Numbers on the blackboard（贪心，并查集） 2019-10-08 题解 题目链接 CF 题意简述 对于一个数列，每次操作可以将相邻的两个数 x 和 y 合并成一个数 x+2y，定义一个数列的权值为进行操作直至只剩一个数能得到的最大值。 多组询问，每次给定一个区间，求这个区间的权值。 数列值域 −109∼109，数列长度和询问个数不超过 105。 阅读更多
BJOI2019 删数（贪心，线段树） 2019-09-16 题解 题目链接 洛谷 LOJ BZOJ 题意简述 一个数列是“可删除的”，当且仅当可以通过这种操作将其清空：将数列中等于这个数列长度的数删去。 如，[1,2,4,4] 是“可删除的”，第一次操作删成 [1,2]，第二次操作删成 [1]，第三次操作清空。 定义一个数列的权值为至少需要进行的单点修改数目，使得这个数列变成“可删除的”。 现在给你一个数列 a1..n，以及 m 次修改操作，你需要在每次修改后回答这个数列的权值。 修改操作有三种： 单点修改。 全局加一。 全局减一。 1≤n,m≤150000，数列初始值以及单点修改成的值在 [1,n] 内，但全局修改可能使数列中的元素超过这个范围。 阅读更多
CF1209F Koala and Notebook（BFS，最短路） 2019-09-16 题解 题目链接 CF 题意简述 给你一张 n 个点 m 条边的无向连通图，一条路径的权值是路径上的边的编号（十进制）顺次连接而成的数字。求 1 到每个点的最短路，输出 对 109+7 取模。 2≤n≤105, n−1≤m≤105。 阅读更多
CF516D Drazil and Morning Exercise（up and down，并查集） 2019-09-10 题解 题目链接 CF 洛谷 题意简述 给定一棵 n 个点带边权的树，定义 d(u) 为树上离它最远的点到它的距离，q 次询问，每次询问给定 l，求一个最大的树上连通块 V′ 的大小，满足 ∀u,v∈V′，|d(u)−d(v)|≤l。 1≤n≤105, 1≤q≤50。 阅读更多
LOJ6519 魔力环（Burnside引理，容斥原理） 2019-09-05 题解 题目链接 LOJ 洛谷 题意简述 你需要给 n 颗珠子的项链染 m 颗黑色，n−m 颗白色，不能有连续的一串黑色珠子长度超过 k，求旋转同构下本质不同的染色方案数。 1≤m,k≤n≤105 阅读更多