蓝桥 题解2017
CF689E 题解
很无语。 一开始脑抽,把交集和并集的概念搞混了。 后面猛然一想:并集?这不是大水题么。 然后 coding,ans 还忘记取模了。 回归正题,求的是 在 \(n\) 条线段中取 \(k\) 条线段,其中有多少个点被 \(k\) 条线段覆盖,求所有方案的答案和。 规约为贡献计算。 考虑点的贡献,假设本 ......
CF1651F 题解
首先是数学表达这道题 考虑第 \(i\) 个怪物。 它跑完自己的全程扣得血是: \[\sum\min\{c_j,m_{j,lst} + \Delta t \times r_j\} \]\(\min\) 有点难搞,没啥好性质。 考虑拆开为两个部分: \[\sum c_j + \sum (m_{j,ls ......
CF1838C题解
显然 \(1\) 不是质数,除二外偶数不是质数。 然后分类讨论 对于 \(m\) 为偶数,构造 \[\begin{bmatrix} 1 & 2 & 3 & \cdots & m \\ m+1 & m+2 & m+3 & \cdots & 2m \\ &&\cdot\\ &&\cdot\\ &&\cd ......
CF773A 题解
真的是蓝题?这真的不是小学数学题? 我们是要求满足(其中 \(a\) 为正确数,\(b\) 为总数) \[\frac{x + a}{y + b} = \frac{p}{q} \]的最小 \(b\)。 我们可以先把右式的分子分母变化到与 \(\frac{x}{y}\) 类似的大小。 int bs1 = ......
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\) ......
[ARC140B] Shorten ARC 题解
分析 自然,我们可以想到利用贪心去解题。 我们可以证明,$\texttt{ARC}$ 左右两边 $\texttt{A}$ 和 $\texttt{C}$ 个数多的比少的变为 $\texttt{R}$ 贡献能更多,第奇数次操作比第偶数次能使操作次数更多。 于是,我们可以得出这样的一个算法: 若为奇数次操 ......
UVA1328题解
前情提要 本题解重在使大家理解。 本题需要 KMP,相信阅读本篇的大佬都会吧。 没学过也没关系,点这里。这是一篇我喜欢的讲解,不喜勿喷。 分析 看见本题的第一感就是会与 KMP 中的 $next$ 数组有关。 我们通过下面证明可以得出:满足 $i \bmod len = 0$,且 $S[1 \sim ......
哈理工新生赛题解
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]\) ......
CF1721A Image题解
转裁自我的洛谷博客:https://www.luogu.com.cn/blog/653832/Code-of-CF1721A-Image 题意简述 给你一个2×2的矩阵,每次可以将一个或两个字母变成任意的其他字母,问最少用几步能将矩阵中的字母变成一样的。 思路 可以先分类讨论可能会出现的情况(如下表 ......
P6883 [COCI2016-2017#3] Kroničan
一眼丁真:一道简单的入门的小清新状压好题。 分析 根据题意,每一个杯子只有有水或没水这两种状态。很容易想到用二进制去表示。有水为 $0$,没水为 $1$。 举个例子,有两个杯子所有杯子都没有水,那么状态为 $11$。 设 $dp[i]$ 表示从初始状态到状态 $i$ 所需的最小代价。 另外我们可以想 ......
B3610 [图论与代数结构 801] 无向图的块 题解
题目传送门 前言 本题解内容均摘自我的 Tarjan 学习笔记 。 解法 Tarjan 与无向图 无向图与割点(割顶) 在一个无向图中,不存在横叉边(因为边是双向的)。 一个无向图中,可能不止存在一个割点。 割点(割顶):在一个无向图中,若删除节点 \(x\) 以及所有与 \(x\) 相关联的边之后 ......
NEFU OJ Problem1356 帽儿山奇怪的棋盘 题解
帽儿山奇怪的棋盘 题目: Time Limit:1000ms Memory Limit:65535K Description 军哥来到了帽儿山,发现有两位神人在顶上对弈。棋盘长成下图的模样: 每个点都有一个编号:由上到下,由左到右,依次编号为 1、2……12。两位神人轮流博 弈,每一轮操作的一方可以 ......
T392582 我有抑郁症【题解】
题目描述 要求有多少个序列满足: 令 \(v=1\sim n\) 从 \(v\) 号点开始,走到 \(p_v\),…,最后走回 \(v\) 记录每个点被走到的次数(起点算,终点不算,反正只算一次) \(i\) 号点走到的次数恰好是 \(i\) 答案对 \(998,244,353\) 取模 Solut ......
P3784 [SDOI2017] 遗忘的集合
传送门 description 对于一个元素都 \(\leq n\) 的正整数集合 \(S\)(不含相同元素),\(f(i)\) 表示使用集合 \(S\) 里的数加和为 \(i\) 的方案数,每个元素可以被使用多次,两个方案不同当且仅当存在一个元素在两种方案中使用次数不同。 现给定 \(n\) 和 ......
【每日例题】蓝桥杯 c++ 串的处理
串的处理 题目 题目描述在实际的开发工作中,对字符串的处理是最常见的编程任务。本题目即是要求程序对用户输入的串进行处理。具体规则如下: 1.把每个单词的首字母变为大写。 2.把数字与字母之间用下划线字符(_)分开,使得更清晰 3.把单词中间有多个空格的调整为1个空格。输入描述 用户输入的串中只有小写 ......
【每日例题】蓝桥杯 c++ 最大降雨量
最大降雨量 题目 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。由于沙之国长年干旱,法师小明准备施展自己的一个神秘法术来求雨。这个法术需要用到他手中的49张法术符,上面分别写着1至49这49个数字。法术—共持续7周,每天小明都要使用—张法术符,法术符不能重复使用。每周,小明 ......
【每日例题】蓝桥杯 c++ 最小的或运算
最小的或运算 题目 问题描述给定整数a,b,求最小的整数工,满足a|a = ba,其中|表示或运算。输入格式第—行包含2个正整数a,b.输出格式输出共1行,包含1个整数,表示最终答案。样例输入样例输出评测数据规模对于所有测评数据,0<a,b <264. 最小的或运算 思路分析 1.要求最小的x满足a ......
【每日例题】蓝桥杯 c++ 奖学金
奖学金 题目 蓝桥杯 奖学金 题目分析 由题目可知,该题涉及到五个属性:学号,语文分数,数学分数,英语分数,总分;由于我们需要通过输入语文、数学、英语分数,经过操作后,输出学号与总分,所以我们可以通过结构体进行存储。 下面是有关结构体的信息:结构体信息 2.下面是排序优先级的要求: 先按总分从高到低 ......
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 ......
[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\) ,因此我们考虑抽象建图。我们把两个点的贡献两两建成一张图,最终的答案显然是把这个图划分 ......