题解codeforces round div3
哈理工新生赛题解
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]\) ......
Codeforces Round 905 (Div. 2) C. You Are So Beautiful
题面翻译 给定数列 \(a\),定义一个子序列 \(S\) 是合法的当且仅当从 \(a\) 中有且仅有一种选法能选出子序列 \(S\)(选法相同定义为最终选出的位置集合相同)。 求其有多少非空合法子序列,满足它占据了 \(a\) 中一端连续的区间。 \(n\leq 10^5\)。 思路 判断区间合法 ......
CF1721A Image题解
转裁自我的洛谷博客:https://www.luogu.com.cn/blog/653832/Code-of-CF1721A-Image 题意简述 给你一个2×2的矩阵,每次可以将一个或两个字母变成任意的其他字母,问最少用几步能将矩阵中的字母变成一样的。 思路 可以先分类讨论可能会出现的情况(如下表 ......
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确定 ......
B3610 [图论与代数结构 801] 无向图的块 题解
题目传送门 前言 本题解内容均摘自我的 Tarjan 学习笔记 。 解法 Tarjan 与无向图 无向图与割点(割顶) 在一个无向图中,不存在横叉边(因为边是双向的)。 一个无向图中,可能不止存在一个割点。 割点(割顶):在一个无向图中,若删除节点 \(x\) 以及所有与 \(x\) 相关联的边之后 ......
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 ......
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 ......
CF1866D Digital Wallet 题解
Problem - 1866D - Codeforces Digital Wallet - 洛谷 不妨为选数钦定一个顺序:不同行之间无影响,列从左到右取一定不劣。 设计状态:设 \(dp_{i,j}\) 表示前 \(i\) 次操作操作到第 \(j\) 列的最大答案 转移:因为对于同一列不互相影响, ......
P9817 题解
这里提供一个非常暴力但是期望复杂度很低的算法。 不难想到要么就是全部放 \(1\),要么就是取出一个最大的质数,然后对于剩下的部分继续按照这样的策略求答案。 因为质数间隔不大,然后暴力判断质数复杂度是 \(O(\sqrt n)\) 的,再加上 IOI 的 buff,我们可以直接考虑从大到小枚举质数, ......
[ARC104F] Visibility Sequence 题解
题意 对于一个长度为 \(N\) 的序列 \(H\),可以通过如下方式构造一个序列 \(P\): 若存在 \(j \in \left[1, i\right)\),使得 \(H_j > H_i\),则 \(P_i = \max\limits_{j \in \left[1, i\right) \land ......
CF1866M Mighty Rock Tower 题解
Problem - 1866M - Codeforces Mighty Rock Tower - 洛谷 先考虑一个 \(O(n^2)\) 的 dp 设计状态: \(dp_i\) 表示搭 \(i\) 层的期望 转移:\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j ......
[ARC104E] Random LIS 题解
题意 给定一个长度为 \(N\) 的序列 \(A\),按照下列方式生成一个长度为 \(N\) 的序列 \(X\): \(\forall i\in[1,n]\),\(X_i\) 在 \([1,A_i]\) 中的整数中均匀随机生成。 求其最长上升子序列长度的期望,对 \(10^9+7\) 取模。 \(1 ......
Codeforces Round 855 (Div. 3) G. Symmetree AHU树哈希
(https://codeforces.com/contest/1800/problem/G) 题目如下: 大意是:给定一颗以1为根节点的树,然后判断这棵树是不是对称的。这里使用AHU算法进行树哈希,在递归的时候对每一个子节点为根的子树求出一个编号,然后在map里面记录。通过判断子树的编号是否一样来 ......
[ARC098F] Donation 题解
[ARC098F] Donation 题解 题目描述 给定一张 \(n\) 点,\(m\) 边的无向图,到达一个点需要拥有 \(a_i\) 的权值,对于一个点操作需要消耗 \(b_i\) 的权值,询问最少需要多少权值才能够对每个点都进行一次操作(权值在任何时候都不能小于 \(0\))。 题目分析 提 ......
CF1245D Shichikuji and Power Grid 题解
Problem - D - Codeforces Shichikuji and Power Grid - 洛谷 首先这题显然不可能是 dp 我们发现第二个式子是困难的,但题目竟然给 \(n \leq 2000\) ,因此我们考虑抽象建图。我们把两个点的贡献两两建成一张图,最终的答案显然是把这个图划分 ......
CSP-S2023 全场题解
lock 这题就是个模拟吧,赛时被迷惑了以为是什么不可做题,仔细看只有 \(10^5\) 种状态,那就枚举好了。 我们分别从状态串出发,枚举它能达到的答案,加到 set 取个并集,不过注意给定的状态不能是密码,要减掉。注意不要直接计数器减减,不然如果有相同的算在状态里面的会多减,我考场代码就这么被 ......
NOIP 提高组 题解
NOIST2023 涂色游戏 对于每一行每一列记录一个时间戳,对于每个格子颜色即为时间戳较大的颜色。 幂次 考虑暴力,我们发现 \(O(\sqrt[3]{n})\) 的复杂度是可以接受的,所以可以枚举 \(\sqrt[3]{n}\) 内的数然后暴力往上乘,可以用一个 unordered_map 判重 ......
CF827D Best Edge Weight 题解
Problem - 1867D - Codeforces Cyclic Operations - 洛谷 差一点就想出来了 首先 \(b_i\) 构建出来的肯定是一个章鱼森林,而且手玩一下样例就会发现我们每次要找到一个大小为 \(K\) 的环后让里面的点重新指向,一直重复这些操作直到所有点都被找到。 ......
[ARC104B] DNA Sequence 题解
题意 对于一个只含有 A,C,T,G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等,C 的数量和 G 的数量相等。 给定一个长度为 \(N\) 的字符串 \(S\),求其有多少个非空子串是匹配的。 \(1 \le N \le 5000\)。 题解 \(\mathc ......
[ARC104C] Fair Elevator 题解
题意 有 \(N\) 个区间 \([a_i,b_i](a_i<b_i)\),都是 \([1,2n]\) 内的整数且互不相同(\(a_i\ne b_j,a_i\ne a_j,b_i\ne b_j\))。 现在给定一些 \(a\) 和 \(b\) 的值,剩下不知道的用 \(-1\) 表示。问是否存在一种 ......
[ARC104D] Multiset Mean 题解
题意 给定 \(N,K\) 和 \(M\)。对于每个大小在 \([1,N]\) 中的 \(x\),求每个元素大小在 \([1,N]\) 中,平均数为 \(x\) 且相同元素不超过 \(K\) 个的可重集的数量,对 \(M\) 取模。 \(1 \le N,K \le 100\),\(M\) 为质数。 ......
CF580E Kefa and Watch 题解
花了一个半个下午+半个晚上终于调出来了...... 0. 题面 长度为 \(n\) 的字符串,每个字符是 \(\mathtt{0} \sim \mathtt{9}\) 的数位,\(m + k\) 种操作: 格式为 1 l r c,表示将 \(l \sim r\) 赋值为 \(c\),保证 \(0 \ ......
Codeforces Round 906 (Div. 2) Doremy's Drying Plan E1.&E2
传送门 先考虑\(E1\) 只需要删除两条线使得不被覆盖的点数最多。 观察到点数只有\(200000\) 那么我们完全可以先将被至少\(3\)条线覆盖的点删掉。 考虑枚举一条线,枚举这条线覆盖的点寻找另外一条线覆盖这些点中的最大值,然后再找没覆盖这些点之外的线的最大值即可。 复杂度容易证明是线性的。 ......