题解1328e cf

题目翻译 有一场选举，要从 \(N\) 名候选人中选出一名获胜者，候选人编号为 \(1, 2, \ldots, N\)，共有 \(M\) 张选票。 每张选票正好投给一位候选人，其中 \(i\) 票投给了候选人 \(A_i\)。 选票将按照从第一张到最后一张的顺序进行统计，每张选票统计完毕后，将更新并 ......

题目翻译 给你两个字符串：\(S\) 由大写英文字母组成，长度为 \(N\)；\(T\) 也由大写英文字母组成，长度为 \(M\)，小于 \(N\)。有一个长度为 \(N\) 的字符串 \(X\)，它只由 # 字符组成。请判断是否有可能通过执行以下任意次数的操作使 \(X\) 与 \(S\) 匹配： ......

题目大意： 给你一个字符串 \(s\)。你要在其中找到多少个 ABC 的子串，例如 AABCBC 算两个，删掉中间的 ABC 后，前面的和后面的加起来也是一个 ABC，所以就算两个。 思路分析： 首先很容易写出暴力，把一个 ABC 提取出来后把后面的元素往前移，然后再重复操作，但是我们发现时间复杂度 ......

分析： 这一道题很容易发现可以用并查集来维护 （不知道为什么其他人都用了图论），\(a_i\) 与其对应的 \(b_i\) 代表着 \(a_i\) 这个集合里不能存在着 \(b_i\)。 根据只有存在两个集合，所以我们会发现，若 \(x\) 与 \(y\) 不在一个集合且 \(x\) 与 \(z\) ......

题目大意 给你 \(n\) 个字符串 \(s\)，和一个字符串 \(t\)。 问你，有多少组是 \(s_j\) 拼在 \(s_i\) 后面所组成的新字符串中，\(t\) 是其子序列。 思路 分析：\(5 \times 10^5\) 的数据肯定需要 \(O(n)\) 或 \(O(n \log n)\) ......

前言 一个下午，一个晚上，一个早上，可以算是一天了吧，终于调出了这道题，纪念一下吧！！！ 食用更佳。 这道题其实就是一道简简单单的 BFS 模（du）板（liu）题。 说难不难，简单不简单，虽然没有难的算法，但是就是码量一百多行，比较难调。 题目难度绿，思维难度橙，代码难度蓝。真是个绝世好题。 题目 ......

P6239 [JXOI2012] 奇怪的道路 首先，拿到题面，\(n \le 30\)，\(k \le 8\)，这不就暴搜吗。再想想，紫题会给你暴搜的机会吗？所以进一步思考，发现这其实是一道 DP，而且数据这么小，肯定是给状压 DP 的样子。 经过一定思考，发现我们可以直接线性枚举 \([1,n]\ ......

P3161[CQOI2012]模拟工厂题解。题目 其实发现这是一道状压，发现这道题是一道数学题，其实就很简单了。对于每一次的订单我们可以设： \(time\) 为距离下一个订单的时间。 \(num\) 为这个订单要生产的数量。 \(x\) 为生产能力。 \(y\) 的时间可以用来提高工厂的生产力。那 ......

题解 前言 个人认为官方题解写得最为详细、干净、清楚，如果有意向阅读外文版的题解的话，还是推荐去读一读： Editorial - AtCoder Regular Contest 117 本文属于转载（？），有一些自己的思考过程，希望有帮助。 题意 有多少个长度为 \(2N\) 的序列 \(A\) 满 ......

题意 给定一张图，走出当前边的时间为 \(i\)。 \(q\) 次询问，问 \(s\) 是否能在 \(l \to r\) 中走到 \(t\)。 Sol 考虑将边从大到小插入图中。 注意到当前边只能对起点造成贡献。 复杂度 \(O(n \times \max\{n, m\})\) Code #incl ......

# [rt](https://www.luogu.com.cn/problem/P9779)# 题目##### 有一道共 n 个选项的不定项选择题，它的答案至少包含一个选项，由于题目与选项的内容晦涩难懂，你打算通过尝试每一种可能的答案来通过这道题。##### 初始时所有选项都没有被勾选，你可以执行任 ......

[国家集训队] middle 题目描述 一个长度为 \(n\) 的序列 \(a\)，设其排过序之后为 \(b\)，其中位数定义为 \(b_{n/2}\)，其中 \(a,b\) 从 \(0\) 开始标号，除法下取整。 给你一个长度为 \(n\) 的序列 \(s\)。 回答 \(Q\) 个这样的询问：\ ......

我们注意到对如图倒三角形上的所有点操作都会影响到目标点。 那么我们可以维护两个前缀和，第一个前缀和表示如下的点是否操作 第二个前缀和表示这些点是否操作 这样我们求出了前缀和之后，将两个前缀和异或一下就知道该点是否要操作了。 #include<bits/stdc++.h> using namespac ......

定义 \(path(x,y,z)\) 表示 从 \((0,0,0)\) 走到 \((x,y,z)\) 的方案数。 显然的经过容斥得到，若 \(r1\le r2,c1\le c2,h1\le h2\)，则 \(ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1 ......

非常好题目。 思路 考虑题目需要求一个连通块的背包。 点分治是平凡的，很容易想到，因为要统计的东西恰好可以把树分成几段。 但点分治操作时的背包确实卡了一下。 以前也没有见过这样的做法。 我们考虑如果直接做树上背包的话。 复杂度是绝对受不了的。 因为合并两个多重背包是基于值域的。 无法体现在树上的优势 ......

原题链接 CF283A Cows and Sequence 题目简述 给定一个初始为空的序列 \(a\)，并给出 \(3\) 种操作方式： 将 \(a_1 \sim a_x\) 均加上 \(y\)； 将 \(a\) 序列末尾增加一个正整数 \(x\)； 将 \(a\) 序列的最后一个数字给去掉； 现 ......

原题链接 CF624B Making a String 题目简述 现在有 \(n\) 个字母，要将这些字母拼成一个尽可能长的字符串，但是每个字母出现的次数不能相等，求这个字符串长度的最大值。 解题思路 首先输入 \(n\)，再输入每个字母出现的次数，最后建造一个桶，存储桶内的每个数字，使得桶内每个数 ......

原题链接 CF1221B Knights 题目简述 在一个 \(n \times n\) 的棋盘上放置黑马和白马，给出一个放置方式，使得黑马和白马之间的冲突数最多。 解题思路 这道题是一道贪心构造题，因为马每一步有 \(8\) 种移动方案，而我们假设将这个棋盘进行黑白交替染色，则会得到下图： 不难得 ......

原题链接 CF1585B Array Eversion 题目简述 现在有一个长度为 \(n\) 的序列 \(a\)，每次操作将 \(a\) 中不大于序列 \(a\) 中最后一个数的元素按照在 \(a\) 序列中的顺序放入 \(b\) 序列中，大于序列 \(a\) 中最后一个数的元素同样按照在 \(a ......

原题链接 CF468A 24 Game 题目简述 现在有一个序列 \(n\) 包含 \(n\) 个整数 \(1 \sim n\)，如果我们能经过加减乘三种操作让这个序列只剩下 \(24\)，如果可以，输出 YES 并给出构造方案，否则输出 NO。 解题思路 首先不难看出，如果 \(n\) 小于 \( ......

纪念一下第一次补完 div1 的所有题 这个 1E 相较于其他的 1E 并不算太难。本题解部分参考官方题解。 先观察到一条边是好的当且仅当它的值和一个端点的值相同。 原因很简单，要求两端点值不同，若边权跟点权也不同，那么三个值分别只能为 \(1,2,3\)，又因为 \(1 \oplus 2 \opl ......

感谢 _lgswdn 大佬的耐心讲解，让我学了这题 \(O(n^3)\) 的高妙做法（数据范围可以加个零） 此题解主要为 _lgswdn 题解的具体阐释以及帮作者理清思路开始写题。 首先把原图压缩一下，如何相邻两端都是上升/下降，就将它们合并，这样可以把原图变成一上一下的特殊形状方便分析。 将原图分 ......

CF1475C Ball in Berland Ball in Berland - 洛谷 题意 在毕业典礼上，有\(a\)个男孩和\(b\)个女孩准备跳舞，不是所有的男孩和女孩都准备结伴跳舞。 现在你知道\(k\)个可能的舞伴，你需要选择其中的两对，以便使没有人重复地出现在舞伴里，求可能的数量。 思 ......

传送门 description 给定 \(n,m,P,k\)。一个 \(n+2\) 行 \(m\) 列的网格图第 \(2\) 至 \(n+1\) 行每秒每行左右两端的方格都有 \(P\) 的概率消失。求 \(k\) 秒后第一行和最后一行联通（上下左右四个格子联通）的概率。 \(n,m\leq 1.5 ......

原题 我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃 题意 题意概述： 给定非严格递增序列 \(a_{n}\) 可以进行若干次操作，求序列方差的最小值的\(n^2\)倍 方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2 ......

比赛链接:arc168 A 题意： 读入一个由<和>构成的字符串，在最开始，最后，字符之间可以填上任意数字，任意两个相邻数字之间必须满足字符代表的大小关系。求问最后填入的数字组成的数组最少有多少对逆序对。 题解： 签到。 <可以不去考虑，因为不会对答案造成影响。 >如果不是在连续段内，也可以不去考虑 ......

CF1506C Epic Transformation Epic Transformation - 洛谷 算是今天的题目里边思维难度最高的一道了，但是代码真的简单的要死 题意 你有一个长度为 \(n\) 的序列 \(a\)，你可以对其进行下列操作： 选择 \(i,j\) 满足 \(*a_i\neq ......

Fighting Tournament 题目传送门 另：多测不清空，WA两行泪 题意 Burenka正准备去观看一年中最有趣的体育活动 —— 她朋友Tonya组织的格斗锦标赛。 有 n 名运动员参加了大赛，标号分别为为 1，2，... ，n 。第 i 名运动员的实力是 $a_i（1 \le a_i ......

CF1728C Digital Logarithm 题目传送门 很奇妙的一道题，我想到了正解，但是又没有完全想到 题意 我们定义 $f(x)$ 表示取出 $x$ 在十进制下的位数。( 如 $f(114514) = 6, ; f(998244353) = 9$ )。形式化讲，就是 $f(x) = \l ......

CF1766D Lucky Chains 有某位特别爱RE的同学问的老师，由此引发了一场血案 主打的就是一坚持不懈（悲 题意 给出两个正整数 $(x,y)$，满足 $(x,y),(x+1,y+1),(x+2,y+2),\dots,(x+k,y+k)$ 都是互质的，直到 $(x+k+1,y+k+1)$ ......