题解860 div cf
[Codeforces] CF1728C Digital Logarithm
题目传送门 很奇妙的一道题,我想到了正解,但是又没有完全想到 题意 我们定义 \(f(x)\) 表示取出 \(x\) 在十进制下的位数。( 如 \(f(114514) = 6, \; f(998244353) = 9\) )。形式化讲,就是 \(f(x) = \lfloor \log_{10} x ......
[Codeforces] 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)\) 起不互质 问 \(k\) 的 ......
[Codeforces] CF1857D Strong Vertices
Strong Vertices - 洛谷 题解是个好东西 题意 给定两个数组 \(a\) 和 \(b\),对此构造一张有向图: 若 \(a_u−a_v≥b_u−b_v\),则 \(u\) 向 \(v\) 连边。 求所有向其他所有顶点连边的顶点个数,并按从小到大顺序输出它们。 思路 先对原式进行转换: ......
[Codeforces] CF1714E Add Modulo 10
题目传送门 代码一遍AC真的很爽,样例都是一遍过 题意 每个测试点含多组测试数据。 对于每组测试数据 第1行 一个整数 \(n\) ,表示该数据个数 第2行 \(n\) 个整数,你需要判断是否符合题意的数据 对每组数据,你可以对其作若干次(可以为零)如下操作: 选取数据中的一个数 \(a_i\) 将 ......
[Codeforces] CF1475C Ball in Berland
Ball in Berland - 洛谷 题意 在毕业典礼上,有\(a\)个男孩和\(b\)个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。 现在你知道\(k\)个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。 思路 暴力 最朴素,也是简单的方法,就是通过暴力组 ......
[Codeforces] CF1705C Mark and His Unfinished Essay
题目传送门 题意 给定长度为 \(n\) 的字符串 \(s\),进行 \(c\) 次操作,每次操作将 \(s_l\) 到 \(s_r\) 复制到字符串尾。 全部操作结束后有 \(q\) 次询问,每次询问字符串 \(s\) 的第 \(k\) 位。 数据保证 \(r\) 不超过当前字符串长度,\(k\) ......
[ABC328C] Consecutive 题解
给一个长度为 \(n\) 的字符串 \(s\),\(q\) 次询问,每一次 \(l\) 和 \(r\) 区间内有多少个 \(s_i\) 等于 \(s_{i-1}\)。 \(10^5\) 的数据 \(O(N^2)\) 暴力肯定行不通。于是我们考虑预处理前缀和,处理到 \(i\) 下标以及之前有多少个 ......
[ABC329C] Count xxx 题解
插曲 因为本人看错了题面,买看到一个子串只包含一种字母,所以切完 D 和 E 才回来发现很简单。 问题翻译 给你一个长度为 \(N\) 的字符串 \(S\),由小写英文字母组成。 求 \(S\) 的非空子串中有多少个是一个字符的重复。在这里,作为字符串的两个子串是相等的,即使它们是以不同的方式得到的 ......
[ABC329D] Election Quick Report 题解
题目翻译 有一场选举,要从 \(N\) 名候选人中选出一名获胜者,候选人编号为 \(1, 2, \ldots, N\),共有 \(M\) 张选票。 每张选票正好投给一位候选人,其中 \(i\) 票投给了候选人 \(A_i\)。 选票将按照从第一张到最后一张的顺序进行统计,每张选票统计完毕后,将更新并 ......
AT_abc329_e [ABC329E] Stamp 题解
题目翻译 给你两个字符串:\(S\) 由大写英文字母组成,长度为 \(N\);\(T\) 也由大写英文字母组成,长度为 \(M\),小于 \(N\)。有一个长度为 \(N\) 的字符串 \(X\),它只由 # 字符组成。请判断是否有可能通过执行以下任意次数的操作使 \(X\) 与 \(S\) 匹配: ......
[ABC328D] Take ABC 题解
题目大意: 给你一个字符串 \(s\)。你要在其中找到多少个 ABC 的子串,例如 AABCBC 算两个,删掉中间的 ABC 后,前面的和后面的加起来也是一个 ABC,所以就算两个。 思路分析: 首先很容易写出暴力,把一个 ABC 提取出来后把后面的元素往前移,然后再重复操作,但是我们发现时间复杂度 ......
[ABC327D] Good Tuple Problem 题解
分析: 这一道题很容易发现可以用并查集来维护 (不知道为什么其他人都用了图论),\(a_i\) 与其对应的 \(b_i\) 代表着 \(a_i\) 这个集合里不能存在着 \(b_i\)。 根据只有存在两个集合,所以我们会发现,若 \(x\) 与 \(y\) 不在一个集合且 \(x\) 与 \(z\) ......
AT_abc324_e [ABC324E] Joint Two Strings 题解
题目大意 给你 \(n\) 个字符串 \(s\),和一个字符串 \(t\)。 问你,有多少组是 \(s_j\) 拼在 \(s_i\) 后面所组成的新字符串中,\(t\) 是其子序列。 思路 分析:\(5 \times 10^5\) 的数据肯定需要 \(O(n)\) 或 \(O(n \log n)\) ......
洛谷 P4872 OIer们的东方梦 题解
前言 一个下午,一个晚上,一个早上,可以算是一天了吧,终于调出了这道题,纪念一下吧!!! 食用更佳。 这道题其实就是一道简简单单的 BFS 模(du)板(liu)题。 说难不难,简单不简单,虽然没有难的算法,但是就是码量一百多行,比较难调。 题目难度绿,思维难度橙,代码难度蓝。真是个绝世好题。 题目 ......
洛谷 P6239 [JXOI2012] 奇怪的道路 题解
P6239 [JXOI2012] 奇怪的道路 首先,拿到题面,\(n \le 30\),\(k \le 8\),这不就暴搜吗。再想想,紫题会给你暴搜的机会吗?所以进一步思考,发现这其实是一道 DP,而且数据这么小,肯定是给状压 DP 的样子。 经过一定思考,发现我们可以直接线性枚举 \([1,n]\ ......
洛谷P3161 [CQOI2012] 模拟工厂题解
P3161[CQOI2012]模拟工厂题解。题目 其实发现这是一道状压,发现这道题是一道数学题,其实就很简单了。对于每一次的订单我们可以设: \(time\) 为距离下一个订单的时间。 \(num\) 为这个订单要生产的数量。 \(x\) 为生产能力。 \(y\) 的时间可以用来提高工厂的生产力。那 ......
Codeforces Round 903 (Div. 3)
Codeforces Round 903 (Div. 3) A. Don't Try to Count 大概题意给你两个字符串a,b。a串可进行的操作为将整个a串复制到之前的a串后面(直接用a+a即可),然后看操作多少次可以让b串变为a串的子串如果不能就输出-1。 #include <iostrea ......
Codeforces Round 905 (Div. 3)
Codeforces Round 905 (Div. 3) A. Morning 题意:操作:显示,向前走都为一次操作;目标:显示这四个数 思路:0->10,然后依次作差就行 #include <bits/stdc++.h> using namespace std; void solve(){ ch ......
[ARC117E] Zero-Sum Ranges 2题解
题解 前言 个人认为官方题解写得最为详细、干净、清楚,如果有意向阅读外文版的题解的话,还是推荐去读一读: Editorial - AtCoder Regular Contest 117 本文属于转载(?),有一些自己的思考过程,希望有帮助。 题意 有多少个长度为 \(2N\) 的序列 \(A\) 满 ......
CF685E Travelling Through the Snow Queen's Kingdom
题意 给定一张图,走出当前边的时间为 \(i\)。 \(q\) 次询问,问 \(s\) 是否能在 \(l \to r\) 中走到 \(t\)。 Sol 考虑将边从大到小插入图中。 注意到当前边只能对起点造成贡献。 复杂度 \(O(n \times \max\{n, m\})\) Code #incl ......
Codeforces Round 910 (Div. 2)
Codeforces Round 910 (Div. 2) A. Milica and String 解题思路: 统计给定字符串\(s\)中的\(B\)的数量,记录为\(cnt\)。 如果\(cnt == k\):输出0; 如果\(cnt < k\):从左往右数,将第\(cnt - k\)个\(A\ ......
P9779_[HUSTFC 2023] 不定项选择题_题解
# [rt](https://www.luogu.com.cn/problem/P9779)# 题目##### 有一道共 n 个选项的不定项选择题,它的答案至少包含一个选项,由于题目与选项的内容晦涩难懂,你打算通过尝试每一种可能的答案来通过这道题。##### 初始时所有选项都没有被勾选,你可以执行任 ......
Codeforces Round 909 (Div3)(本菜鸟只补到了E)
Codeforces Round 909 (Div.3) A. Game with Integers 水题,就是可以被3整除的输出“Second”,不能被3整除的输出“First” #include<iostream> using namespace std; int main() { int t; ......
【题解 P2839】 middle
[国家集训队] middle 题目描述 一个长度为 \(n\) 的序列 \(a\),设其排过序之后为 \(b\),其中位数定义为 \(b_{n/2}\),其中 \(a,b\) 从 \(0\) 开始标号,除法下取整。 给你一个长度为 \(n\) 的序列 \(s\)。 回答 \(Q\) 个这样的询问:\ ......
CF1864D 题解
我们注意到对如图倒三角形上的所有点操作都会影响到目标点。 那么我们可以维护两个前缀和,第一个前缀和表示如下的点是否操作 第二个前缀和表示这些点是否操作 这样我们求出了前缀和之后,将两个前缀和异或一下就知道该点是否要操作了。 #include<bits/stdc++.h> using namespac ......
P8737 题解
定义 \(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 ......
Codeforces Round 910 (Div. 2)
Preface 这场其实挺早之前就写完代码了,但一直没时间写博客(玩云顶新赛季玩的) 感觉F其实不难但为什么就是想不出来呢,感觉后面的题就是很难突破的说 A. Milica and String 分类讨论+枚举即可 #include<cstdio> #include<iostream> #inclu ......
P6326 Shopping 题解
非常好题目。 思路 考虑题目需要求一个连通块的背包。 点分治是平凡的,很容易想到,因为要统计的东西恰好可以把树分成几段。 但点分治操作时的背包确实卡了一下。 以前也没有见过这样的做法。 我们考虑如果直接做树上背包的话。 复杂度是绝对受不了的。 因为合并两个多重背包是基于值域的。 无法体现在树上的优势 ......
「杂题乱刷」CF283A
原题链接 CF283A Cows and Sequence 题目简述 给定一个初始为空的序列 \(a\),并给出 \(3\) 种操作方式: 将 \(a_1 \sim a_x\) 均加上 \(y\); 将 \(a\) 序列末尾增加一个正整数 \(x\); 将 \(a\) 序列的最后一个数字给去掉; 现 ......
「杂题乱刷」CF624B
原题链接 CF624B Making a String 题目简述 现在有 \(n\) 个字母,要将这些字母拼成一个尽可能长的字符串,但是每个字母出现的次数不能相等,求这个字符串长度的最大值。 解题思路 首先输入 \(n\),再输入每个字母出现的次数,最后建造一个桶,存储桶内的每个数字,使得桶内每个数 ......