ZHUYINGYE_123456的博客

原创 2022.11.06 洛谷 P6587 超超的序列

洛谷 P6587 题解

原创 2022.10.30 洛谷 P7732 [JDWOI-2] 红黑树 常见错因分析

错因分析

原创 2022.08.21 吉司机线段树略讲

优化 吉司机线段树 势能

原创 2022.08.01 洛谷P7845 「dWoi R2」Change

不可以到达的点对答案没有任何贡献，所以把所有不可以到达的节点和它的所有相连的边删去，留下所有可以到达的节点，建立一个新的图（这个图一定是原图的子图）。不一定可以到达所有的节点，所以我们可以先进行一次拓扑排序（或者bfs，随便怎么叫），求出。结合贪心，现在的问题就是求出新图中从。干讲可能不好理解，加上代码后就好多了。到它可以到达的每一个点的距离和。的所有路径中必须经过的离。的最近必经之路，考虑节点。所以，再来一次拓扑排序即可。首先是一个贪心，离起始点。距离最小的边），记为点。的所有路径的交集中离。...

原创 2022.07.19 洛谷 P6588 『JROI-1』 向量

前三个操作都是线段树的基本操作，重点考虑第四和第五个操作。相当于把所有的向量都相乘一次，减去自己乘自己，再除以。（至于每个操作是什么意思，请自行百度向量的基本运算）根据这条性质，我们就可以用线段树维护了。的横纵坐标的绝对值不大于。事实上，根据叉乘的几何含义，保证任意时刻任意的向量。很遗憾，叉乘没有交换律。类似，为纵坐标的和。...

原创 2022.07.18 洛谷 P6722 「MCOI-01」Village 村庄

显然，我们不需要考虑原图的每一条边，我们考虑最难满足限制的那条边就可以了（它都符合条件，其它一定符合）。判断是否存在这样的一个节点，它到直径两端的点的距离是否都大于等于。为无根树的根，求出每个点之间的距离，暴力建图，然后判断是否是二分图即可。（这篇题解的说法可能不太严谨，但做法是对的，严谨的证明请大家看看其它题解）个节点的树，你需要根据这棵树建立一棵新的图。，我们发现对于直径上任何一点，它到直径两端（即点。因此，我们不能只判断直径上的点是否符合条件。注意，不能只判断直径上的点是否满足限制。...

原创 2022.05.04 洛谷 P8320 Sunset

P8320 [JROI-4] Sunset\color{green}{\texttt{P8320 [JROI-4] Sunset}}P8320 [JROI-4] Sunset[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Analysis]\color{blue}{\texttt{[Analysis]}}[Analysis]设 d1⋯id_{1 \cdots i}d1⋯i​ 中不同的数的个数为 ωi\ome

原创 2022.04.10 洛谷 P1272

[Problem]\color{blue}{\texttt{[Problem]}}[Problem]给定一棵有 nnn 个节点的有根树。每次操作可以删除树上两个点 (u,v)(u,v)(u,v) 间的连边。求最少需要几次操作可以从树上剥离出一个恰好有 PPP 个节点的子树。1≤P≤n≤1501 \leq P \leq n \leq 1501≤P≤n≤150。[Analysis]\color{blue}{\texttt{[Analysis]}}[Analysis]很明显应该是树上背包问题。剥

原创 2022.01.30 洛谷P8087

P8087 [JROI-5] Interval\color{green}{\texttt{P8087 [JROI-5] Interval}}P8087 [JROI-5] Interval[Problem]\color{blue}{\texttt{[Problem]}}[Problem]1≤n≤4×106,1≤fi≤1×1091 \leq n \leq 4 \times 10^{6},1 \leq f_{i} \leq 1 \times 10^{9}1≤n≤4×1

原创 2022.01.22 洛谷 P4449 于神之怒（加强版）

Luogu P4449\color{green}{\texttt{Luogu P4449}}Luogu P4449[Problem]\color{blue}{\texttt{[Problem]}}[Problem]求∑i=1n∑j=1mgcd⁡(i,j)k\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)^{k}i=1∑n​j=1∑m​gcd(i,j)k对 (1×109+7)(1 \times 10^{9}+7)(1×109+7

原创 2022.01.25 THUSC2016 成绩单

Luogu P5336 & Ybt 1766\color{green}{\texttt{Luogu P5336 \& Ybt 1766}}Luogu P5336 & Ybt 1766[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]看到 nn

原创 2022.01.23 高手训练自训 ybt1742 导线问题

Ybt 1742 hamon\color{green}{\texttt{Ybt 1742 hamon}}Ybt 1742 hamon[Problem in short]\color{blue}{\texttt{[Problem in short]}}[Problem in short]给定序列 a1⋯na_{1 \cdots n}a1⋯n​，求其最长严格上升子序列的长度及数量（对 1234567891234567891234

原创 2022/01/02 CF1282E The Cake Is a Lie

CF1282E The Cake Is a Lie\color{green}{\texttt{CF1282E The Cake Is a Lie}}CF1282E The Cake Is a Lie[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]

原创 20211203 CF1611

B\color{green}{\texttt{B}}B[Solution]\color{blue}{\texttt{[Solution]}}[Solution]下面讨论认为 a>ba>ba>b（如果 a<ba<ba<b，直接交换就好了）。如果 a≥3ba\geq 3ba≥3b，那么最多只能分 bbb 组（每组一名程序员和三名数学家）。其他情况下，我们先把每个组分一个程序员和一名数学家，然后再把数学家两两分到一组，再把程序员两两分到一组，如果都有剩余，再把一名数学

原创 2021.09.11 CF1547G How Many Paths & Luogu P5546

CF1547G How Many Paths\color{green}{\texttt{CF1547G How Many Paths}}CF1547G How Many Paths[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]首先，如果一个点 uuu 有自环且 111 能到达 uuu

原创 2021.08.31 CF1558E Up the Strip

the last blog of the summer holiday of 2021CF1558E Up the Strip\color{green}{\texttt{CF1558E Up the Strip}}CF1558E Up the Strip[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[S

原创 2021.08.20 CF1552F Telepanting

CF1552F Telepanting\color{green}{\texttt{CF1552F Telepanting}}CF1552F Telepanting[Problem]\color{blue}{\texttt{[Problem]}}[Problem]有一只初始在位置 000 的蚂蚁，它每秒钟会向右走 111 一个单位长度。在地图上有 nnn 个虫洞，第 iii 个虫洞在位置 xix_{i}xi​，如果它是活动的，它就会把蚂蚁送回到位置 yi(yi<xi)y_{i}

原创 2021.08.18 CF1519B The Cake Is a Lie

CF1519B The Cake Is a Lie\color{green}{\texttt{CF1519B The Cake Is a Lie}}CF1519B The Cake Is a Lie[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]

原创 2021 暑假集训日记

Day 111，August 16th听老师讲思想政治，然后打了一道紫的数论题，感觉很妙，然后，放学了。下午打了 201620162016 和 201720172017 年的提高初赛题，89.589.589.5 分和 72.572.572.5 分，自我感觉还不错吧。看看能不能出一套公开赛题。...

原创 2021.08.11 关于树状数组那些并不总所周知的科技

O(n)\mathcal{O}(n)O(n) 建立一棵树状数组我们知道，树状数组每个点保存了区间 [i−low(i)+1,i][i-\texttt{low}(i)+1,i][i−low(i)+1,i] 的区间和，所以我们可以用前缀和算法求出数组的前缀和 ppp，则树状数组 ccc 第 iii 个节点的值就是：pi−pi−low(i)p_{i}-p_{i-\texttt{low}(i)}pi​−pi−low(i)​O(n)\mathcal{O}(n)O(n) 求出前缀和后，就可以再 O(n)\mathc

原创 2021.07.13 洛谷 P7392

P7392 「TOCO Round 1」奇怪的排序\color{green}{\texttt{P7392 「TOCO Round 1」奇怪的排序}}P7392 「TOCO Round 1」奇怪的排序[Problem]\color{blue}{\texttt{[Problem]}}[Problem]询问 nnn 个数的排列中有多少个排列满足执行了下列函数后变成有序。[Solution]\color{blue}{\texttt{[Solutio

原创 2021.07.12 洛谷P5583

P5583 [SWTR-01] Ethan and Sets\color{green}{\texttt{P5583 [SWTR-01] Ethan and Sets}}P5583 [SWTR-01] Ethan and Sets[Problem]\color{blue}{\texttt{[Problem]}}[Problem]nnn 个集合，每个有一些 [0,m][0,m][0,m] 间的整数和一个法力值 ttt。

原创 Yingye Zhu‘s Luogu Background

原创 2021,06.13 洛谷 P7243 最大公约数

luogu P7243\color{green}{\texttt{luogu P7243}}luogu P7243[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]稍微思考一下，就可以得到如下的性质：如果一个位置 (x,y)(x,y)(x,y) 上的数变成了 111，那么第二天它四周围尚未变成 111 的数都会变成 111

原创 2021.06.06 高考前发概率 洛谷P5389

luogu P5389 [Cnoi2019]数学课\color{green}{\texttt{luogu P5389 [Cnoi2019]数学课}}luogu P5389 [Cnoi2019]数学课[Problem]\color{blue}{\texttt{[Problem]}}[Problem]你有一个长度为 nnn 的数列 a1⋯na_{1 \cdots n}a1⋯n​，满足 ai=∑j=1ija_{i} = \sum\limits_{j=1}^{i} j

原创 2021.05.16 洛谷P7333 好久没做二分了

P7333 [JRKSJ R1] JFCA\color{green}{\texttt{P7333 [JRKSJ R1] JFCA}}P7333 [JRKSJ R1] JFCA[Problem]\color{blue}{\texttt{[Problem]}}[Problem]nnn 个数对 (ai,bi)(a_i,b_i)(ai​,bi​) 在同一个环上，你需要求出 f1⋯nf_{1 \cdots n}f1⋯n​，使得 fif_{i}fi​ 等于

原创 2021.05.04 日常总结兼一些好题的记录（六）

CF1407D Discrete Centrifugal Jumps\color{green}{\texttt{CF1407D Discrete Centrifugal Jumps}}CF1407D Discrete Centrifugal Jumps[Problem]\color{blue}{\texttt{[Problem]}}[Problem]copy from luogu[Solution]\color{blue}{\texttt{

原创 2021.04.17 日常总结——第一道自己想出来的交互题

CF1407C Chocolate Bunny\color{green}{\texttt{CF1407C Chocolate Bunny}}CF1407C Chocolate Bunny[Problem]\color{blue}{\texttt{[Problem]}}[Problem]你需要猜测一个长度为 nnn 的排列。你最多有 2×n2 \times n2×n 次机会，每次机会可以询问 aimod  aja_{i} \mod a_{j}ai​modaj​。输出

原创 2021.04.05 日常总结——一些好题的记录（五）

CF915E Physical Education Lessons\color{green}{\texttt{CF915E Physical Education Lessons}}CF915E Physical Education Lessons[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solut

原创 2021.04.03 日常总结——一些好题的记录（四）

CF1408D Searchlights\color{green}{\texttt{CF1408D Searchlights}}CF1408D Searchlights[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]（自己画的图有点丑陋，请原谅）显然，对于两个探照灯 (i,j)(i,j)(i,j)，如果 iii 在 jjj

原创 2021.03.20日常总结 一些好题的记录（四）

CF1415E New Game Plus!\color{green}{\texttt{CF1415E New Game Plus!}}CF1415E New Game Plus![Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]因为选择的顺序是任意的，所以我们可以用贪心解决问题。从大

原创 2021.03.14 一些好题的记录（三）

CF1415D XOR-gun\color{green}{\texttt{CF1415D XOR-gun}}CF1415D XOR-gun[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]如果有连续的 333 个数，它们的最高位一样，那么答案就是 111（我们可以把后面两个数异或，其最高位一定为 000，便小于第 111 个数

原创 2021.02.28 一些好题的记录（二）

CF1304E 1-Trees and Queries\color{green}{\texttt{CF1304E 1-Trees and Queries}}CF1304E 1-Trees and Queries[Problem]\color{blue}{\texttt{[Problem]}}[Problem][Solution]\color{blue}{\texttt{[Solution]}}[Solution]借鉴 NOIp2019 PJ

原创 2021.02.17 GDKOI2021 好题记 第一记

TG Day 2 T1[Problem]\color{blue}{\texttt{[Problem]}}[Problem]您先有 000 颗星，您想要有 nnn 颗星假如您现在有 iii 颗星，每玩一局游戏您有 piqi\dfrac{p_{i}}{q_{i}}qi​pi​​ 的概率变成 i+1i+1i+1 颗星，(1−piqi)\left (1-\dfrac{p_{i}}{q_{i}}\right )(1−qi​pi​​) 的概率变成 i−1i-1i−1 颗星。您最少只会有 000 颗星。问期望

原创 Yingye Zhu‘s GDKOI 2021 游记

寒假前的那个学期末突然接到要参加 GDKOI 2021 的消息，原定是要到深圳参加的。闹了点小插曲，后来还是整个机房都参加了。刚放寒假得到最新消息，因为 COVID-19，不去深圳了，留在粤北贫困山区参加线上 GDKOI 2021。PJ Day 111上午比赛，下午讲数论。题目还好，前 333 题都想出来了。然而留给 T4T_4T4​ 的时间已经不多了，虽然 T4T_4T4​ 正解也挺简单的，但是只想到了暴力，就交上去了。100+100+100+20=320100+100+100+20=3

原创 2021.02.04 一些好题的记录（一）

洛谷P6434「EZEC-1」甜品\color{green}{\texttt{洛谷P6434「EZEC-1」甜品}}洛谷P6434「EZEC-1」甜品[Problem]\color{blue}{\texttt{[Problem]}}[Problem]从 a1⋯na_{1\cdots n}a1⋯n​ 中选出 kkk 个数（不要求下标递增），使得这 kkk 个数 b1⋯kb_{1 \cdots k}b1⋯k​ 满足：l×bi≤bi+1≤r×bi(i∈[1,k))l \times b_{i} \leq b_

原创 2021.01.02日常总结——2021第一记

这是 202120212021 年的第一篇博客，让我们走进 数论 和 树论 的天地吧！洛谷P6862 [RC-03] 随机树生成器\color{green}{\texttt{洛谷P6862 [RC-03] 随机树生成器}}洛谷P6862 [RC-03] 随机树生成器[Problem]\color{blue}{\texttt{[Problem]}}[Problem]千万注意不是对 (1×109+7)\left (1 \times 10^9+7\right ).

原创 2020.12.20日常总结——概率思维好题

[SHOI2002]百事世界杯之旅\color{green}{\texttt{[SHOI2002]百事世界杯之旅}}[SHOI2002]百事世界杯之旅[Problem]\color{blue}{\texttt{[Problem]}}[Problem]有 nnn 个等可能的奖品，买一瓶饮料就可以得到一个奖品，求期望下买多少瓶饮料可以获得所有的奖品。以假分数的形式输出答案。[Solution]\color{blue}{\texttt{[Solution]}}[Solution]记 fif_ifi​ 表

原创 NOIP2020 游记

CSP 结束CSP-J/S 结束后，由于最终的政策并没有出来，我们一直以为我们初中的同学不能考 CSP 现场赛，只能考网络赛，就一直在准备网络赛。考前两个星期突然下来政策，只要过了 CSP-S 初赛的选手都可以去参加 noip。我们相当地兴奋，因为我们又可以去华南师范大学附属中学（简称华附）考试了。那可以本蒟蒻梦想的高中啊！！！考前最后两次训练连考了两次提高级的套题，一次 300300300，一次 210210210。出发这次去的人数没有上次 CSP 多，路途上就没那么有趣，就聊了聊我们亲爱的

原创 蒟蒻朱的 CSP2020 J/S 游记

第一轮考试（初赛）考前一直在复习计算机基础知识，结果一道题都没考……两项成绩都比同机房大佬低，但是还是过初赛了。考前一个月一直在 noip.ybtoj.com.cn 上练习，同时在准备期中考试。考前一周伟大的期中考试，感觉题目有一点点难，有些科目还好一点。星期五下午考完最后一科（历史）后就上大巴去广州考试了。车上听了听歌，一直在和同学们聊天。不得不说，这次粤北穷困山区去了不少人去复赛呢！差不多有一个班 505050 人了。行程非常遥远，用了 333 个多小时才到广州。坐大巴的感觉不是很