题解 部分1851 cf
P5015题解
博文T2航站楼 ✈ P5015标题统计 数组及变量准备 变量 string n 输入的标题 int cnt=0 计数器 预先准备 getline函数: 可用于输入带空格的字符串,格式如下 getline(cin,字符串名,结束字符); 思路 getline输入字符串\(n\) getline(cin ......
1.9模拟赛 T3题解
简要题意 求一个抽象函数,满足 \(∀𝑥 ∈ ℤ, 𝑓(𝑥) + 𝐶 = 𝑓(2𝑓(𝑥) − 𝑥 + 1)\),给定 \(n\) 个点,使得 \(\sum |f(x_i)-y_i|\) 最小,输出最小值 思路 对这个函数进行一次迭代,可以得到 \(f(x+2C)=f(x)+2C\) ......
CF1886E I Wanna be the Team Leader 题解
Problem - E - Codeforces I Wanna be the Team Leader - 洛谷 差一点就想到了/ll 遇到困难?排序肯定不会变差! 性质:每个项目分配的程序员肯定是一段(显然) \(m\) 很小?考虑设 \(dp_{i,S}\) 表示考虑前 \(i\) 个人选项目集 ......
CF1886D Monocarp and the Set 题解
Monocarp and the Set - 洛谷 Problem - D - Codeforces 非常之降智 加入一个数让他满足他是最大值需要判断前面加入的那些数中最大的是哪个,但删除一个数让他满足是最大值只需要直接把他删掉即可 因此我们要反着考虑这个问题: 如果当前是 <,则删除最小的数,有一 ......
【题解】LibreOJ 3089 「BJOI2019」奥术神杖
先考虑这个权值 \(\sqrt[c]{\prod\limits_{i = 1}^c V_i}\)。 感觉找不到好的方法算出精确值,但是能发现只用比大小。 于是考虑取个对数成 \(\frac{1}{c}\times \ln(\prod\limits_{i = 1}^c V_i) = \frac{1}{ ......
[AGC004F]Namori题解
简要题意 略 思路 先考虑树的的情况,直接黑白染色,统计子树和的绝对值即可 再考虑奇环,发现这时会有两个同色相邻点,只需把多余的操作,在这两个点处理掉即可 最后考虑偶环,先断掉一条边,最后再考虑这条边的贡献,推一下柿子,就变成了初中数学题,取中位数即可 code #include<bits/stdc ......
GB28181视频汇聚平台EasyCVR级联后,部分通道视频无法播放是什么原因?
视频汇聚监控EasyCVR平台可以实现不同厂家、不同协议、不同型号的摄像机、设备及平台获取摄像机视频流后,以统一、标准的视频格式和传输协议,将视频流推送至云平台,完成海量安防视频资源轻量化接入、分发,实现设备和平台的互联互通,形成感、存、知、用一体化的综合性大平台,让用户随时随地“可视、可测、可控”... ......
[Noi Online #1 入门组] 跑步 题解
[Noi Online #1 入门组] 跑步 \(m = \sqrt{n}+1\) 对于大于 \(m\) 的数,采用另外一种方式 \(x > m\) --> 其数量 \(< m\) 记 \(g[i][j]\) 表示用了 \(i\) 个大于等于 \(m\) 的数 和为 \(j\) 的方案数 初始状态 ......
CF1511G Chips on a Board
不难发现这是个 Nim 游戏,于是对每对 \((L_i, R_i)\) 所求转化为: \[\bigoplus_{i = 1}^n (a_i - L_i)[a_i \ge L_i] \]暴力做时间复杂度就是 \(\mathcal O(n^2)\),考虑优化。 感觉好像可以倍增?设 \(f(i, k)\ ......
HDU1823 Luck and Love 题解
Question Luck and Love 小 \(w\) 征婚,收到很多女生报名,小 \(w\) 想找到最有缘分的女生,有 \(t\) 组操作 I H A L,\(H\) 表示身高,\(A\) 表示活泼度,\(L\) 表示好感度 Q H1 H2 A1 A2 表示身高和活泼度的范围,需要在这个范围 ......
[CF1063F] string journey
String Journey 题面翻译 对于一个字符串数组 \(t_1, \ldots, t_k\),若对于每一个 \(t_i\) 都是 \(t_{i-1}\) 的真子串的话,即 \(t_i\) 是 \(t_{i - 1}\) 的子串且 \(t_i \ne t_{i-1}\),则称为有序串组,列如 ......
P5309 [Ynoi2011] 初始化 题解
题目链接:初始化 这种 ynoi 的老题就是卡常。来简单说说这题的思维切入口。 看到形如 \(y+k \times x\) 的结构,自然而然思考一下如果我们是暴力更新会有怎么样的效果。我们容易发现,如果 \(x\) 比较大,暴力更新的次数 \(\dfrac{n}{x}\) 也不会很大的,但 \(x\ ......
洛谷P1250 种树 题解 差分约束求最小解集
题目链接:https://www.luogu.com.cn/problem/P1250 题目大意:略 解题思路:差分约束 求 最长路。 关于为什么求最长路可以看一下这边博客:《关于差分约束系统中跑最长路还是最短路的澄清》 博客的核心思想就是一句话: 要想求最小解集跑最长路;要想求最大解集跑最短路。 ......
CF1707E Replace
由题意可以发现一个性质: \[f[(l, r)] = \bigcup_{i = l}^{r - 1} f[(i, i + 1)] \]进而可以推广至: \[f^k[(l, r)] = \bigcup_{i = l}^{r - 1} f^k[(i, i + 1)] \]证明显然,即若 \([l_1, ......
POJ3667 Hotel 题解
Question POJ3667 Hotel 旅店有 \(n\) 间连续的房间,操作有两种 D 入住,查询数量为 \(D\) 的连续房间,并且要最靠左,若能找到,则返回这个区间的左端点并占用这些房间,找不到则返回 \(0\) X D 退房,从房间 \(X\) 开始,退出连续长度为 \(D\) 的房间 ......
HDU1540 Tunnel Warfare 题解
Question HDU1540 Tunnel Warfare 在一条线上有 \(n\) 个村庄,两个相邻的村庄之间用地道连接,做 \(m\) 次操作 D x 第 \(x\) 个村庄被摧毁,它的地道也一同被摧毁 Q x 查询第 \(x\) 个村庄所能到达的村庄总数(包括村庄 \(x\)) R 重建刚 ......
学习Spring Boot 注解,这一篇就够了(附带部分注解实例讲解)
大纲 一、web mvc开发时,对于三层的类注解 1.1 @Controller 1.2 @Service 1.3 @Reponsitory 1.4 @component 二、依赖注入的注解 2.1@Autowired 2.2 @Resource 2.3 @Resource、@Autowired的区 ......
CF1919H Tree Diameter
某人在换根时根还设置成 \(1\) 交了整整 \(11\) 发,我不说是谁。 先考虑一下 \(2\) 询问的实际用途,因为我们可以用它来确定深度,根据树上交互题的常见技巧,我们通过这种方式确定了一个拓扑序,只要能在拓扑序的前缀中快速查询一个点的父亲,就可以求出这棵树。 考虑先以一条边为根,那么其会有 ......
1.8模拟赛 T2题解
简要题意 略 思路 先考虑啥样的 \(T\) 可能合法,就大概类似于一个一边删除,一边加入的操作,如果能删空,那就合法 但这样的 \(T\) ,不一定能作为答案,只有能将多余的数删除时才合法 那就用同样的策略,判断是否合法即可 接着考虑 \(T\) 的方案数咋求,设 \(dp_{i,j,k}\) , ......
1.8模拟赛 T1题解
简要题意 给定一棵有根树,操作分别为:将某个点到根路径上全部点颜色改为 \(c\);询问某个点到根路径上不同颜色数。 \(n\le10^5\) 思路 考虑对修改根号重构,那对于某次询问的路径,实际上就是前面有至多 \(\sqrt m\) 个相同颜色段,再拼上后面一段树上的颜色,也就是和修改中点的最深 ......
【题解】Codeforces 1876G Clubstep
首先考虑暴力的贪心。 从 \(r\) 到 \(l\) 依次遍历,若 \(a_i < x\) 则一直进行题目中的操作。 正确性是能保证的,因为选后面的 \(j\) 只能 \(+ 1\),而选 \(i\) 可以 \(+2\),且 \(i\) 前面的部分都是 \(+1\)。 考虑转化一下,把对 \(i\) ......
【题解】Codeforces 1852D Miriany and Matchstick
首先考虑到第一行是固定的,先去掉第一行的贡献。 接下来会有一个 \(O(n^2)\) 的 \(\text{DP}\)。 考虑设 \(f_{i, 0 / 1, j}\) 为考虑了 \(1\sim i\) 列的放置,第 \(i\) 列填 \(\text{A / B}\) 且对数为 \(j\) 是否可行。 ......
题解 P10055【[CCO2022] Rainy Markets】
首先尽量把所有人放在左边的车站,然后再尽量放在右边的车站,求出此时 \(i\) 位置车站有多少空位留给 \(i+0.5\) 位置的人,记为 \(f_i\)。也就是: \[f_i\gets\max\{b_i-\max\{p_{i-1}-f_{i-1},0\},0\} \]然后从右向左贪心。对于第 \( ......
使用IDEA将部分代码抽出来变成一个新的方法 快捷键不是Ctrl + Alt + M 填写方法名称即可
使用IDEA将部分代码抽出来变成一个新的方法 快捷键不是Ctrl + Alt + M 填写方法名称即可 前言 从java开发角度来说,一个方法一般不宜过长,通常都是50到100行左右。太长的方法不管从阅读还是维护上来说都是不利的。但在实际开发中,一方面可能需要优化祖传代码,另一方面我们自己也经常 ......
CF1864H Asterism Stream【概率 DP,矩阵优化】
给定一变量,初始为 \(1\),每次等概率随机进行以下两种操作之一: 令 \(x\) 加一。 令 \(x\) 乘二。 求期望多少次操作之后 \(x\) 会 \(\ge n\)。 \(T\) 组数据,\(T\le 100\),\(n\le 10^{18}\)。 对着 aw 老师的题解学的,感觉太深刻。 ......
CF331A1&CF331A2
不难发现一件事:对于在 \(i\) 之后能跟 \(i\) 匹配的 \(j\),最好的办法显然是使得 \(j\) 最大。则用前缀和统计整个和,并且用前缀和维护负数和,在枚举 \(i\) 统计出最小答案时在后面计算出满足最大答案的条件并输出即可。 ac records #include<bits/std ......
P10033 题解
不喜欢特判?不喜欢分讨?不喜欢被卡 corner?不喜欢证明?不喜欢动脑子? 那就看这篇题解! 感性思路 首先感性地感受一下题目宽泛的限制条件题解区各种花式的构造方法就不难想出,符合条件的序列实在很多,那不是随便构造?但是随便上随机化还是很容易被卡而且常数太大,又不想写屎山分讨被 corner 卡到 ......
CF864F Cities Excursions
题意:给定一张有向图,询问 \(s, t\) 两点间字典序最小路径上的第 \(k\) 个结点。 首先要验证 \(s, t\) 间是否连通,所以建反图,枚举 \(1 \sim n\),跑 dfs。这部分时间复杂度 \(\mathcal O(n^2)\)。 确定了哪些点跟 \(t\) 连通后,\(s\) ......