Q779’s Blog

洛谷P3694 邦邦的大合唱站队 题解 题目链接：P3694 邦邦的大合唱站队 题意： BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。 \(n\) 个偶像排成一列，他们来自 \(m\) 个不同的乐队。每个团队至少有一个偶像。 现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。 请问最少让多少偶像出列？ 输入格式： 第一行 \(2\) 个整数 \(n,m\)。 接下来 \(n\) 行，每行一个整数 \(a_i(1\le a_i \le m)\) ，表示队列中第 \(i\) 个偶像的团队编号。 输出格式： 一个整数，表示答案。 数据范围： \(1\le n\le 10^5,~ m\le 20\) 可以发现，我们并不关心换了哪些人，而在乎换了多少人。 例如一个段应当放满 \(\mathtt{B}\) 的人，结果里面 \(\mathtt{B : C : D} = \mathtt{3 : 2 : 3}\) ，那我们肯定是把剩下那五个换成后面...

OI易错点-图论 一、图论基础 【易错点】 ❗️新建虚拟结点 \(\boldsymbol{0}\) ，会向至多 \(n\) 个结点连边，空间要开 \(\boldsymbol{2}\) 倍 ❗️ 无向图+链式前向星， \(\boldsymbol{2}\) 倍空间 多组数据不要忘了清空 pos 邻接矩阵处理重边 down(g[u][v], w) （无向图别忘了 g[v][u] ） ❗️树的欧拉序长度为 \(3n\) ，因此线段树要开 \(12n\)❗️ 【算法相关】 自环要写 if(u==v)continue; 处理！ ❗️树上dp题获取子节点个数，不可以直接用 vec[u].size() ，因为可能有重边❗️ 二叉树的树高并不是固定 \(\mathcal{O}(\log n)\) 的，链也满足二叉树的定义，概念不要混淆了。 二、最短路算法 【易错点】 \(\text{Dijkstra}\) 不要忘记把起点入队 \(\text{Floyd}\) 相关问题注意 \(\text{INF}\) 值的设置不能过大 如 0x3f3f3f3f3f3f3f3f 在 f[i][j]+g[i...

note[11] 解方程：\(a^2 + a^3 = 392\) 解1： 容易发现 \(a = 7\) 是一个解。考虑因式分解（会用到 多项式除法）： \[ \begin{aligned} & a^2+a^3-392=0 \\[6pt]& (a-7)(a^2+8 a+56)=0 \end{aligned} \] 转化为解方程 \(a^2+8 a+56 = 0\) ，易得原方程解为 \[ a_1 = 7,~a_2 = -4+2\sqrt{10}i,~a_3 = -4-2\sqrt{10}i \] 解2： 朴素的死算方法。 首先用 note 4 讲到过的方法消掉二次项，令 \(b = a + \frac{1}{3}\) 得 \[ b^3-\frac{1}{3} b-\frac{10582}{27}=0 \] 根据卡尔达诺公式(Cardano formula)，得 \[ p = -\frac{1}{3}, ~q =-\frac{10582}{27} \] 则方程的解为 \[ \begin{aligned} & a_1=u+v-\frac{1}{3}=\sqr...

note[10] 问：甲有 \(101\) 个硬币，乙有 \(100\) 个硬币，两人随机撒在地面上，甲比乙正面朝上多的概率是多少 解：答案为 \(\frac{1}{2}\) 证明1： 考虑“甲比乙正面朝上多”和“甲比乙反面朝上多”这两个事件。 因为甲的硬币总数比乙多，这两件事至少发生一个。 然而，这两个事件又不可能同时发生，否则甲至少要比乙多两个硬币才行。 所以，要么甲比乙正面朝上多，要么甲比乙反面朝上多。 根据对称性，这两个事件是等可能的，所以概率各为 \(\frac{1}{2}\)。 证明2： 甲先投 \(100\) 枚，记此时甲乙朝上硬币数量相等概率为 \(p\) ， 则甲此时比乙多的概率为 \(\frac{1}{2}(1-p)\) ， 故甲投下第 \(101\) 枚硬币后朝上硬币比乙多的概率为： \[ \frac{1}{2}(1-p) + \frac{1}{2}p = \frac{1}{2} \] 参考文献： [1] https://www.zhihu.com/question/444606927/answer/1749535576 [2] https://www.z...

洛谷P5094 [USACO04OPEN] MooFest G 加强版 题解 题目链接：P5094 [USACO04OPEN] MooFest G 加强版 题意： 每一年，约翰的 \(n\) 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 \(i\) 的听力为 \(v_i\) ，这表示如果奶牛 \(j\) 想说点什么让她听到，必须用高于 \(v_i \times \mathrm{dis}(i,j)\) 的音量。因此，如果奶牛 \(i\) 和 \(j\) 想相互交谈，她们的音量必须不小于 \(\max (v_i,v_j) \times \mathrm{dis}(i,j)\)。其中 \(\mathrm{dis}(i,j)\) 表示她们间的距离。 现在 \(n\) 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 \(x_i\)。如果每对奶牛都在交谈，并且使用最小音量，那...

洛谷P8867 [NOIP2022] 建造军营 题解 题目链接：P8867 [NOIP2022] 建造军营 题意： A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。 A 国的国土由 \(n\) 座城市组成，\(m\) 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。 众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。 A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出...

洛谷P5507 机关 题解 题目链接：P5507 机关 题意： cxy 成功脱单后，在npy家里发现了一扇暗门，但是这扇门是锁着的 这扇门上有一个机关，上面一共有 \(12\) 个旋钮，每个旋钮有 \(4\) 个状态，将旋钮的状态用数字 \(1\) 到 \(4\) 表示 每个旋钮只能向一个方向旋转（状态：\(1\to 2\to 3\to 4\to 1\) ），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出） 当所有旋钮都旋转到状态 \(1\) 时，机关就打开了 由于旋钮年久失修，旋转一次很困难，而且时间很紧迫（指想和npy去贴贴） 因此她希望用最少的旋转次数打开机关，这个任务就交给你了 输入格式： \(12\) 行，每行 \(5\) 个整数，描述机关的状态 第 \(i\) 行第一个整数 \(s_i\) 表示第 \(i\) 个旋钮的初始状态是 \(s_i\) 接下来 \(4\) 个整数 \(a_{i,j},j=1,2,3,4\) 表示这个旋钮在状态 \(j\) 时旋转，会引起第 \(a_{i,j}\...

洛谷P1363 幻象迷宫 题解 题目链接：P1363 幻象迷宫 题意： 幻象迷宫可以认为是无限大的，不过它由若干个 \(n \times m\) 的矩阵重复组成。矩阵中有的地方是道路，用 . 表示；有的地方是墙，用 # 表示。cxy 和 q779 所在的位置用 S 表示。也就是对于迷宫中的一个点 \((x,y)\) ，如果 \((x \bmod n, ~y \bmod m)\) 是. 或者 S，那么这个地方是道路；如果 \((x \bmod n,~y \bmod m)\) 是 #，那么这个地方是墙。cxy 和 q779 可以向上下左右四个方向移动，当然不能移动到墙上。 请你告诉 cxy 和 q779，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，cxy 就只好启动城堡的毁灭程序了……当然不到万不得已，她不想这么做。。。 输入格式： 输入包含多组数据，以EOF结尾。 每组数据的第一行是两个整数 \(n,m\) 。 接下来是一个 \(n\times m\) 的字符矩阵，表示迷宫里 \((0,0)\) 到 \((n-1,m-1)\) 这个矩阵单...

C++语法 vector 这篇文章来讲下我在 OI 中遇到的 vector 的用法，本文基于 C++14 。 一、vector 底层相关 vector 是封装动态数组的顺序容器，并且是连续存储的，因此除了迭代器，还可以通过指针访问。 vector 的存储是自动管理的，按需扩张收缩，因此内存占用会较多于静态数组。 vector 所用的方式不是在每次插入元素时，而只在额外内存耗尽时重分配，也就是装不下的时候再扩充一定量。 我们可以用 capacity() 函数查询分配的内存总量，还可以用 shrink_to_fit() 返回多出的内存给系统。 vector<int> a(15); // 初始化为15个元素 vector<int> b; // 初始为空 // capacity（意思是“容量”） 查询占用内存，返回的是元素个数 // 值得注意的是，占用内存分配方式取决于标准库的实现方式，不过一定有 占用内存 ≥ 使用内存 cout << (int)a.capacity() << ' ' << (int)b.capacity() <...

洛谷P2886 [USACO07NOV]Cow Relays G 题解 题目链接：P2886 [USACO07NOV]Cow Relays G 题意： 给定一张 \(T\) 条边的无向连通图，求从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。 输入格式： 第一行四个正整数 \(N,T,S,E\) ，意义如题面所示。 接下来 \(T\) 行每行三个正整数 \(w,u,v\) ，分别表示路径的长度，起点和终点。 输出格式： 一行一个整数表示图中从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。 数据范围： 对于所有的数据，保证 \(1\le N\le 10^6\)，\(2\le T\le 100\)。 所有的边保证 \(1\le u,v\le 1000\)，\(1\le w\le 1000\)，无重边。 这道题考察了无向图邻接矩阵的性质。 如果矩阵 \(A\) 表示走了 \(x\) 步的最短路，矩阵 \(B\) 表示走了 \(y\) 步的最短路， \[ C_{i,j} \downarrow A_{i,k} + B_{k,j} \] 矩阵 \(...

洛谷P5789 [TJOI2017]可乐 题解 题目链接：P5789 [TJOI2017]可乐（数据加强版） （双倍经验：P3758） 题意： 加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 \(1\) 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 \(0\) 秒时可乐机器人在 \(1\) 号城市，问经过了 \(t\) 秒，可乐机器人的行为方案数是多少？ 输入格式： 第一行输入两个正整数 \(N,M\) ，\(N\) 表示城市个数，\(M\) 表示道路个数。 接下来 \(M\) 行输入 \(u,v\) ，表示 \(u,v\) 之间有一条双向道路。 最后输入时间 \(t\) 。 输出格式： 输出可乐机器人的行为方案数，答案可能很大，请输出对 \(2017\) 取模后的结果。 数据范围： \(n,m\leq 100,~t\leq 10^9\) 。 朴素的无向图邻接矩阵快速幂，自爆的话，加个虚点“天堂”就好啦~ 注意每个点要连自环，并且向虚点的...

洛谷P3216 [HNOI2011]数学作业 题解 题目链接：P3216 [HNOI2011]数学作业 题意： 小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题： 给定正整数 \(n,m\)，要求计算 \(\text{Concatenate}(n) \bmod \ m\) 的值，其中 \(\text{Concatenate}(n)\) 是将 \(1 \sim n\) 所有正整数 顺序连接起来得到的数。 例如，\(n = 13\) , \(\text{Concatenate}(n) = 12345678910111213\)。 小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。 输入格式： 一行两个正整数 \(n,m\)。 输出格式： 输出一行一个整数表示答案。 数据范围： \(1\le n \le 10^{18},~1\le m \le 10^9\)。 设 \(f_{i}\) 表示前 \(i\) 个数拼起来的答案，则 \[ \large f_{i} = f_{i-1} \times 10^{\...