题解1203 div cf
CF859G 题解
总结题意 显然可以转化为序列问题嘛。 给出序列 \(A\{a_i\}\),你需要通过若干次操作使其归零。 操作: 选定 \(d | n\)、\(k\)、\(r\),对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。 题解 很明显,加减相互抵消,对于所有 \(d\)、\( ......
USACO铂金题解
USACO 铂金题解 USACO 2018 Platium B. Sort It Out 很巧妙的转换 注意到操作并不会影响没有被选中的牛的相对顺序 所以没有被选中的一定单调递增 要使得选中的尽可能少,就要选尽可能长的没有被选中的序列,即原序列的 \(LIS\) 所以原题等价于求原序列第 \(k\) ......
Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) B. Kuroni and Simple Strings
Problem - 1305B - Codeforces 啦啦啦,这题题目有点长,概括一下就是,希望将所有()匹配的括号去掉 问你需要操作多少次 双指针,一个i一个j,从前往后记录匹配的括号 如果发现: 1. 括号匹配 2. i<j ok,就放入ans (⊙o⊙)…,最后记得sort一遍ans,第一 ......
[ARC140B] Shorten ARC 题解
分析 自然,我们可以想到利用贪心去解题。 我们可以证明,$\texttt{ARC}$ 左右两边 $\texttt{A}$ 和 $\texttt{C}$ 个数多的比少的变为 $\texttt{R}$ 贡献能更多,第奇数次操作比第偶数次能使操作次数更多。 于是,我们可以得出这样的一个算法: 若为奇数次操 ......
UVA1328题解
前情提要 本题解重在使大家理解。 本题需要 KMP,相信阅读本篇的大佬都会吧。 没学过也没关系,点这里。这是一篇我喜欢的讲解,不喜勿喷。 分析 看见本题的第一感就是会与 KMP 中的 $next$ 数组有关。 我们通过下面证明可以得出:满足 $i \bmod len = 0$,且 $S[1 \sim ......
CF1851D
貌似我与大家后面的判断不太一样? 分析 由于前缀和的定义,我们可以知道他们的差分便是原数组,下面的差分数组,是题目给出的前缀和的差分。 于是,我们可以用个桶将 $1 \sim N$ 出现的数存起来。 随后判断每个数是否出现过,若没出现过,使计数器加一。 这里我们假设输出 YES。因为前缀和少了一个数 ......
哈理工新生赛题解
A小亮的睡眠时间 思路:求一下一共花了多少时间思考,注意思考时间大于睡觉时间上限的特殊情况。 #include <iostream> using namespace std; int main() { int n; scanf("%d", &n); int sum = 0; int cur; int ......
CF1089K King Kog's Reception 题解
题目传送门 前置知识 线段树 解法 第一眼感觉和 luogu P1083 [NOIP2012 提高组] 借教室 很像。本题同样采用线段树维护,\(sum_{l,r}(1 \le l \le r \le 10^6)\) 表示从 \(l \sim r\) 时刻内骑士拜访的总时间,\(maxx_{l,r} ......
ABC326G 题解
blog。简单最小割。 发现 \(L_{i,j}\le5\),所以对 Level 拆点。初始源点 \(S\xrightarrow{0} \text{Lvl}1_i, S\xrightarrow{c_i} \text{Lvl}2_i,\text{Lvl}3_i,\text{Lvl}4_i,\text{ ......
[ABC327G] Many Good Tuple Problems 题解
题意 对于一对长度均为 \(M\) 且元素值在 \(\left[1, N\right]\) 之间的序列 \((S, T)\),定义其为好的当且仅当: 存在一个长度为 \(N\) 的 \(01\) 序列 \(X\),使得其满足如下条件: 对于任意 \(i \in \left[1, M\right]\) ......
CF1621G
传送门 description 长度为 \(n\) 的序列 \(a\) 的一个严格上升子序列的权值为该子序列中严格比序列 \(a\) 中该子序列右边最大值小的数的个数,求序列 \(a\) 的所有严格上升子序列的权值和。 \(n\leq 2\times 10^5\) solution 离散化。 先转化 ......
Codeforces Round 905 (Div. 2) C. You Are So Beautiful
题面翻译 给定数列 \(a\),定义一个子序列 \(S\) 是合法的当且仅当从 \(a\) 中有且仅有一种选法能选出子序列 \(S\)(选法相同定义为最终选出的位置集合相同)。 求其有多少非空合法子序列,满足它占据了 \(a\) 中一端连续的区间。 \(n\leq 10^5\)。 思路 判断区间合法 ......
CF390B Inna, Dima and Song Solution
转裁自我的洛谷博客 :https://www.luogu.com.cn/blog/653832/solution-cf390b 题目传送门 思路: 如果 $b_i \le 1$ 则无解。 如果 ceil((double)b[i]/2)>a[i],即最好情况下,两个人的音量平均,但是较大的音量还是大于 ......
CF1721A Image题解
转裁自我的洛谷博客:https://www.luogu.com.cn/blog/653832/Code-of-CF1721A-Image 题意简述 给你一个2×2的矩阵,每次可以将一个或两个字母变成任意的其他字母,问最少用几步能将矩阵中的字母变成一样的。 思路 可以先分类讨论可能会出现的情况(如下表 ......
CF1874F Jellyfish and OEIS
题意 给定一个序列 \(m\) ,你需要求出满足以下性质排列 \(p\) 的个数,对大质数取模: 对于任意 \(l,r\) ,\(p_{l...r}\) 为一个 \([l,r]\) 的排列与 \(r \le m_l\) 不同时成立。 Sol 考虑从题目的奇怪限制入手(也只能从这里入手),我们记一个区 ......
Educational Codeforces Round 157 (Rated for Div. 2)
添加链接描述 B题直接前缀后缀预处理一下没了 C 首先题目保证有解,那么我们可以确定"("和")"的数量,显然前面全部填(后面的全部填)肯定是合法的,然后交换两个最近的,影响最小,判断一下即可。 D题首先根据%k余数判断是否有解, 然后肯定是直接往下走到最大,然后走过去,rmq预处理即可。 ......
Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction
原题链接 解读一下题意:给一个长度n-1的数组,让你找到一个长度为n的数组b,并且是0到n-1的全排列,使得bi异或bi+1对于ai。 这道题乍一看没什么思路,但是仔细一想会发现其实考察的就是异或的性质。我们可以发现:如果a异或b等于c,那么abc任意两个异或都能得到另外一个,所以只要初始的b0确定 ......
【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.
原题链接:P9688 Colo. 很显然,能够共存的颜色一定不会相交,所以可以记录每个颜色最左边的位置和最右边的位置,我们对于每个颜色只考虑,这个颜色左边的可以和这个颜色共存的额颜色 用f[i][j]表示当前考虑i这种颜色,选i这种颜色,然后在i这种颜色之前(包括这种颜色)一共选了j种颜色的最大价值 ......
CF1875D
很简单的题。虽然没在考场上做出来 分析 我们经过思考,容易得出以下结论: 如果当前 $mex = x$,则下一个删的数一定小于 $x$。 如果 $mex = 0$,那么我们就可以不往下算了,因为它们对答案的贡献为 $0$。 我们设 $f[i]$ 表示当 $mex = i$ 时,$m$ 的值。 则有: ......
CF755F
前言 随机跳题跳来的。本来以为很简单,结果花了我这个蒟蒻三个多小时。果然还是太蒻了呀。还有题目中的拖拉机是什么呀? 于是,题解记之。 题意 传送门 分析 我们容易发现,若把每个人当做一个点,那么给人送礼物,则是向这个人连一条边。 看不懂?直接上图! 上图表示的是: 5 2 3 4 1 5 2 这一组 ......
B3610 [图论与代数结构 801] 无向图的块 题解
题目传送门 前言 本题解内容均摘自我的 Tarjan 学习笔记 。 解法 Tarjan 与无向图 无向图与割点(割顶) 在一个无向图中,不存在横叉边(因为边是双向的)。 一个无向图中,可能不止存在一个割点。 割点(割顶):在一个无向图中,若删除节点 \(x\) 以及所有与 \(x\) 相关联的边之后 ......
手机浏览器中实现可拖动div
var touchStartX = 0; var touchStartY = 0; var moveX = 0; var moveY = 0; var div = document.getElementById('yourDivId'); // 获取你要拖动的div div.addEventList ......
CF213E Two Permutations
CF213E Two Permutations 题解 下文的 \(a+x\) 表示 \(a_1+x,a_2+x,...a_n+x\) 这个序列。 发现 \(n,m\) 不大,所以可以枚举 \(x\),然后快速判断是否合法。 考虑如何快速判断一个 \(x\) 是否合法。 注意到 \(a,b\) 都是排 ......
CF 杂题集1 2200~2400
upd on 2023.11.02 初稿 upd on 2023.11.04 修正部分表达 感觉这一套题质量都很不错,有比较好的思维难度,又不是特别难(当然,对于我来说很难),而且有一些比较好的思路和套路。 题目链接均为洛谷链接。 CF1474D Cleaning 摘要: 性质:考虑端点,发现一定可 ......
Educational Codeforces Round 157 (Rated for Div. 2)
Preface 懒狗闪总好久没打CF了,而且桂林回来后也没摸过键盘了,今天打的那叫一个手生 本来都不知道今天晚上有比赛,后面ztc叫我打我想着反正不熄灯就小号摆着打 最后赛后10min写出E题就很难受,感觉状态正常点就能出5个题了(或者来个2h15min的场就好了) A. Treasure Ches ......
NEFU OJ Problem1356 帽儿山奇怪的棋盘 题解
帽儿山奇怪的棋盘 题目: Time Limit:1000ms Memory Limit:65535K Description 军哥来到了帽儿山,发现有两位神人在顶上对弈。棋盘长成下图的模样: 每个点都有一个编号:由上到下,由左到右,依次编号为 1、2……12。两位神人轮流博 弈,每一轮操作的一方可以 ......
Educational Codeforces Round 157 (Rated for Div. 2)
A. Treasure Chest 分类讨论一下,只有两种情况。 走到钥匙处,然后走到箱子处 走到箱子处,移动箱子,走到钥匙处,走回箱子处 对于第二种情况可以直接枚举箱子被移动到的位置 #include <bits/stdc++.h> using namespace std; #define int ......
T392582 我有抑郁症【题解】
题目描述 要求有多少个序列满足: 令 \(v=1\sim n\) 从 \(v\) 号点开始,走到 \(p_v\),…,最后走回 \(v\) 记录每个点被走到的次数(起点算,终点不算,反正只算一次) \(i\) 号点走到的次数恰好是 \(i\) 答案对 \(998,244,353\) 取模 Solut ......
CF1842G
第一次听没听懂,补个笔记。弄懂这种奇妙拆贡献后感觉非常厉害。 答案的形式为:\(\prod (a_i + k \cdot v)\),这些 \(v\) 是前面的操作带来的影响。 我们考虑一个个加入这个 \((a_i + k \cdot v)\),并且维护很多个等价类,使得这个值可以根据分开等价类的那个 ......
Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction
题目链接 题意 给你 \(n-1\) 个整数 \(a_1, a_2, \dots, a_{n-1}\) 。 你的任务是构造一个数组 \(b_1, b_2, \dots, b_n\) ,使得: 从 \(0\) 到 \(n-1\) 的每个整数都在 \(b\) 中出现一次; 对于从 \(1\) 到 \(n ......