题解1203 div cf

CF题解合集

CF 比赛题解合集 \(\downarrow 2023.09.04\) CF1952, CF1954 1952 A. Ntarsis' Set 有一个集合,初始状态里面有数字 \(1\)、\(2\)、\(3\)、\(4\)、\(5\)、......、\(10^{1000}\)。 现在给你一个长度为 ......
题解

CF1446F Line Distance

Dqy 7。 计几结论拍脸,感觉不如原神。 Binary search is your friend. 考虑二分答案,二分一个距离 \(r\),考虑求出 \(d(O,AB)>r\) 的无序点对 \((A,B)\) 数量。 以 \(r\) 为半径作圆 \(C:x^2+y^2=r^2\)。考虑如果一个点 ......
Distance 1446F 1446 Line CF

CF1801G A task for substrings

Day 6。 好神奇的题啊,我完全不会做。 建出 \(s_1,s_2,\cdots, s_n\) 的 ACAM。 考虑在 \(r\) 处统计满足条件的数对 \((l,r)\) 的贡献。那么需要求出 \(f_r\) 表示文本串以 \(r\) 为结尾的前缀 \([1,r]\) 中,其所有后缀中模式串的出 ......
substrings 1801G 1801 task for

cf edu 1700

1430D. String Deletion 因为要最大话操作次数,所以我们每次删除的时候删除没有被删除最左侧连续相同长度大于等于 2 的部分。 想清楚贪心策略后,用快慢指针就可以\(O(N)\)实现本体。 #include <bits/stdc++.h> using namespace std; ......
1700 edu cf

Educational Codeforces Round 132 (Rated for Div. 2) B. Also Try Minecraft

一个世界地图用一个长为 \(n\) 的数组表示,\(a_i\) 代表坐标 \(i\) 的高度。若下一块区域的高度为 \(y\) ,当前区域的高度为 \(x\) ,则一次行走会受到 \(max(y - x, 0)\) 点下落伤害。 有 \(q\) 个询问,每个询问独立,给定起点和终点坐标 \(s, t ......
Educational Codeforces Minecraft Round Rated

【题解】CF1830C Hyperregular Bracket Strings

我们知道,一个长度为 \(n\) 的合法括号序列的种数就是第 \(\frac n 2\) 个卡特兰数(当然 \(n\) 是奇数答案肯定就是 \(0\)) 我们可以发现一件事情,如果两个区间相互包含,那么就可以将大区间分为中间被包含的小区间的部分和外面没有被小区间覆盖的部分。 如果两个区间相交,那么就 ......
题解 Hyperregular Bracket Strings 1830C

Educational Codeforces Round 130 (Rated for Div. 2) B. Promo

有 \(n\) 件商品,第 \(i\) 件的价格是 \(p_i\) ,若买至少 \(x\) 件商品,则其中最便宜的 \(y\) 件免费。给 \(q\) 个询问,每次给出 \(x, y\) ,回答最多能免费的价值。 按大到小排序,求前缀和 \(S_{i}\) 表示买前 \(i\) 件商品需要的开销。 ......
Educational Codeforces Round Rated Promo

Codeforces Round 895 (Div. 3)

A. Two Vessels #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; using i64 = long long; void solve() { int ......
Codeforces Round 895 Div

【题解】CF1830B The BOSS Can Count Pairs

你考虑,我们观察数据范围,发现可以是 \(O(n\sqrt n) / O(n\log n)\) 的,我们又看到乘法,便有几个大概的想法: 数论分块 \(O(\sqrt n)\) 枚举其中一个乘数 还有什么……(笔者学识浅陋,读者可以帮忙补充) 我们可以找到两种 \(O(n^2)\) 做法: \(O( ......
题解 1830B Count Pairs 1830

Codeforces Round 804 (Div. 2) B. Almost Ternary Matrix

给两个偶数 \(n\) 和 \(m\) 。任务是构造任意一个二进制矩阵,\(n \times m\) 。对于任意 \((i, j)\) ,有且仅有两个邻居的颜色与 \(a_{i, j}\) 不同。邻居的定义为 \(|x - x'| + |y - y'| = 1\) 。 观察:任何 \(n \time ......
Codeforces Ternary Almost Matrix Round

Codeforces Round 807 (Div. 2) B. Mark the Dust Sweeper

需要打扫 \(n\) 个房间,第 \(i\) 个房间有 \(a_i\) 的积灰。只能使用如下魔法打扫: 选择 \(i, j, (1 \leq i < j \leq n, \min_{k = i}^{j} a_i > 0)\) 。 执行 \(a_i = a_i - 1, a_j = a_j + 1\) ......
Codeforces Sweeper Round Mark Dust

【题解】[ABC318F] Octopus(思维)

【题解】[ABC318F] Octopus 题目链接 F - Octopus 题意概述 有个机器人,它有 \(n\) 个手臂,第 \(i\) 个手臂长度为 \(l_i\)。同时有 \(n\) 个宝藏,第 \(i\) 个宝藏的坐标是 \(x_i\)。 当机器人位于 \(k\) 时,它的第 \(i\) ......
题解 思维 Octopus 318F ABC

Codeforces Round 811 (Div. 3) A. Everyone Loves to Sleep

闹钟设有 \(n\) 个时间点,第 \(i\) 个时间为 \((H_i,M_i)\) 。在 \(h, m\) 时刻入睡,响铃必须起床,问能睡多久。 使用 \(set<pair<int, int>>\) 存储闹铃时刻,然后在其中 \(lower_{bound}\) 到 \(<first \geq h, ......
Codeforces Everyone Round Loves Sleep

Codeforces Round 815 (Div. 2) A. Burenka Plays with Fractions

给两个数 \(\frac{a}{b}\) 和 \(\frac{c}{d}\) ,一次修改可以修改 \(a\) 或 \(b\) 之一,求最小修改数使得 \(\frac{a}{b} = \frac{c}{d}\) 。 若 \(\frac{a}{b} = \frac{c}{d}\) ,除式化乘式,则讨论 ......
Codeforces Fractions Burenka Round Plays

题解:【ABC319F】 Fighter Takahashi

题目链接 有过类似的 idea 啊,怎么撞了 ABC 了/fn。 注意到药最多只有十个,肯定是先尽可能的加,然后再用乘,因此从这上面入手。状压药定点的使用情况,设 \(f_S\) 表示只用掉 \(S\) 这些药最后能够到达的最大力量值,那么有解的充要条件就是存在 \(f_S \geq \max s_ ......
题解 Takahashi Fighter 319F ABC

Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 A. Mainak and Array

给一个长为 \(n\) 的正整数数组,执行以下操作严格一次。 选择 \(l, r, (1 \leq l < r \leq n)\) ,任意一个正整数 \(k\) 。 重复 \(k\) 次:让 \([l, r]\) 的数组成环,按顺时针走一次。 希望 \(a_n - a_1\) 最大,找到这个数。 分 ......
Codeforces Div and Grimoire Contest

Codeforces Round 830 (Div. 2) B. Ugu

给一个 \(01\) 字符串,需要使它变为非降的,可以执行以下操作: 选择一个下标 \(i, (1 \leq i \leq n)\) ,\(\forall j \geq i\) 的数位翻转。 经典的按无后效性翻转问题。 考虑从前往后,得到一个全 \(0\) 串。若开始存在 \(1\) ,则答案减 \ ......
Codeforces Round 830 Div Ugu

[ABC319D] Minimum Width 题解

[ABC319D] Minimum Width 题解 题意分析 给定 \(n\) 个单词,现在想像“记事本”一样把它们依次地一行一行显示出来。每个字母宽度为一,单词之间需要有空格,宽度也为一。一个单词不可以成两部分显示在两行。如果单词最后一个字母来到行末,直接换行,不用空格。 给定窗口最大高度 \( ......
题解 Minimum Width 319D ABC

[题解} CF1217D Coloring Edges

CF1217D Coloring Edges 知识点: dfs 树。 题意 给定一张有向图,现在要求为图上所有的边进行染色,使得颜色种类最少的同时,同种颜色的边无法构成环,输出最少需要的颜色种类和任意一种染色可行方案。 思路 假设该有向图中不存在环,那么我们可以直接对所有的边染为同一种颜色。因此可以 ......
题解 Coloring 1217D Edges 1217

[JOISC 2016] 雇佣计划 题解

[JOISC 2016] 雇佣计划 题解 这里补充一篇自己的 \(n \log n\) 做法。 本蒟蒻打了两棵线段树,并且进行了繁琐的分类讨论,完全被标算的树状数组吊打 qwq 题意: 给定一个序列 \(a\),有两种操作: 将 \(c\) 位置权值改为 \(d\); 给定一个权值 \(b\),定义 ......
题解 JOISC 2016

$Codeforces Round 891 (Div. 3)$

\(A. Array Coloring\) 显然需要奇数个偶数即可满足题目。 void solve(){ int n=read(),res=0; for(int i=1;i<=n;i++){ int x=read(); if(x%2)res++; } puts(res%2==0?"YES":"NO" ......
Codeforces Round 891 Div

标准题解 - 2023/9/10

01串 对于相邻的两个段和 \(S_i\) 和 \(S_{i+1}\) 两段之间移动时的差别既删除了 \(i\) 号元素,添加了 \(i+K\) 号元素。如果 \(S_i = S_{i+1}+1\) 那么说明 \(i\) 号元素是 \(1\),\(i+K\) 号元素是 \(0\)。(删除 \(1\) ......
题解 标准 2023 10

CF1570C 题解

一道纯粹的贪心题。 思路分析 通过观察,我们可以发现,每个瓶子所需要的射击次数的增长是与 \(x\) 密切相关的。 这样我们很容易想到,如果我们将耐久度大的瓶子放在后面射击,那么 \(x\) 就会较大,因而导致最终的射击次数变大。 说到这儿,思路已经显而易见了。我们可以对 \(a\) 数组根据耐久度 ......
题解 1570C 1570 CF

P5318 题解

前置知识: 链式前向星初始化 深度优先搜索和广度优先搜索 如果你还不知道链式前向星,那么请看这篇文章,请务必搞懂它。 原题传送门 看到题解区没有关于链式前向星的题解,就准备来发一波! 思路分析 分析存储方法 在图中,最常见的存储方法是以下三种: 邻接矩阵 邻接表 链式前向星 现在我们就来逐一选择一下 ......
题解 P5318 5318

P8029 [COCI2021-2022#3] Akcija 题解

注:这篇题解中涉及到的所有概念均会在其第一次出现时用 斜体 标出,有些概念给出了定义,而有些概念的含义请自行意会。 定义 状态 为选了的物品数 \(a\) 与相应总价格 \(b\) 的二元组 \((a,b)\)。相应地定义状态之间的 大小关系、最优状态 与状态和状态的 加法运算 \((a_1,b_1 ......
题解 Akcija P8029 8029 2021

CF285B 题解

不可多得的小清新模拟题! 思路分析 题目中已经暗示地很明显了,只能对 \(x\) 进行操作使得 \(x\) 变成 \(p_x\)。 而我们现在可以操作的值唯独 \(s\),所以我们的思路就呼之欲出了。 我们重复将 \(s\) 迭代为 \(p_s\)。如果 \(s=t\),那么我们就找到了答案。如果 ......
题解 285B 285 CF

$Codeforces Round 888 (Div. 3)$

\(A. Escalator Conversations\) 用 \(map\) 存楼梯的高度(差),对每个人看一下需要的楼梯高度是否存在。 int a[N]; void solve(){ int n=read(),m=read(),k=read(),h=read(); map<int,int>mp ......
Codeforces Round 888 Div

P9502 题解

普通模拟的别的题解应该都有了,现在我来介绍一种不同寻常的偷懒方法! 思路分析 确定最大值 题目要我们求 \(2^m\) 次方,常规的方法是对于 \(m\) 一个一个试过去,最终找到答案。 但是,我们可以发现,\(m\) 不就是 \(\log_2 n\) 嘛!(不考虑偶数和小于的条件下) 所以我们可以 ......
题解 P9502 9502

P9503 题解

一道简单的模拟题尽管我花了好久才写出来。 思路分析 我们可以知道,如果想让背景为某个颜色,那么颜色前面的所有幕布都需要被拉起来,而这个颜色的幕布则需要被放下。 所以我们对于每次操作,只需检查一遍它前面的幕布和这块幕布的状况即可。 程序实现 #include <bits/stdc++.h> using ......
题解 P9503 9503

CF1252A 题解

思路分析 前置知识:排列是没有重复元素的! 猜想 我们可以进行一种猜想,对于 \(x\),输出: \[\begin{cases} x+1&x<N\\ 1&x=N \end{cases}\]将代码提交上去,我们可以发现这种猜想值正确的! 证明 但是作为一名合格的 OIer我们必须证明这种做法是正确的。 ......
题解 1252A 1252 CF