Q779’s Blog

洛谷P1835 素数密度 题解 题目链接：P1835 素数密度 题意： 给定 \(L,R\)，请计算区间 \([L,R]\) 中素数的个数。 输入格式： 第一行，两个正整数 \(L\) 和 \(R\)。 输出格式： 一行，一个整数，表示区间中素数的个数。 数据范围： \(1\leq L\leq R < 2^{31}\)，\(R-L\leq 10^6\)。 z注意到 \(\sqrt{R}\) 只有约 \(V=50000\) 的数量级 我们可以预处理出小于 \(50000\) 的质数，然后用这些质数暴力埃氏筛。 时间复杂度 \(\mathcal{O}\left(\frac{V}{\ln V} \log (R-L)\right)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f const int _ = 50000; void up(int &x,int y) { x < y ? x =...

[AGC022E] Median Replace 题解 题目链接：[AGC022E] Median Replace 题意： 有个长度为 \(N\)（\(N\) 为奇数）的 \(\texttt{01}\) 串 \(s\)，其中有若干位置是 \(\texttt{?}\)。 一次操作可将 \(3\)​ 个连续的字符替换成这三个数的中位数。 求有多少将 \(\texttt ?\) 替换成 \(\texttt0\) 或 \(\texttt1\) 的方案使得进行 \(\frac{N-1}{2}\) 次操作后的字符串可以是 \(\texttt1\)​。 输入格式： 一行，给定 \(s\) 。 输出格式： 一行，答案 数据范围： \(1\leq N\leq300000\) 且 \(N\) 为奇数。 做多替换三个的题了，还以为是把每个位置都换成中位数……（我就说大早上写题会弱智吧） 容易发现，如果一个字符串由 \(a\) 个连续的 \(\mathtt{1}\) 和 \(b\) 个连续的 \(\mathtt{0}\) 拼接而成，则当 \(a > b\) 时一定合法。 考虑维护一个从栈顶到栈...

洛谷P2482 [SDOI2010] 猪国杀 题解 题目链接：P2482 [SDOI2010] 猪国杀 题目描述 游戏背景 《猪国杀》是一种多猪牌类回合制游戏，一共有 \(3\) 种角色：主猪，忠猪，反猪。每局游戏主猪有且只有 \(1\) 只，忠猪和反猪可以有多只，每只猪扮演 \(1\) 种角色。 游戏目的 主猪 / \(\texttt{MP}\)：自己存活的情况下消灭所有的反猪。 忠猪 / \(\texttt{ZP}\)：不惜一切保护主猪，胜利条件与主猪相同。 反猪 / \(\texttt{FP}\)：杀死主猪。 游戏过程 游戏开始时，每个玩家手里都会有 \(4\) 张牌，且体力上限和初始体力都是 \(4\) 。 开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从 \(1 , 2, 3 \ldots n , 1 \ldots\) 的顺序）依次行动。 每个玩家自己的回合可以分为 2 个阶段： 摸牌阶段：从牌堆顶部摸 \(2\) 张牌，依次放到手牌的最右边； 出牌阶段：你可以使用任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。当然，要满足如下规则： 如果没有猪...

CF248E Piglet’s Birthday 题解 题目链接：Piglet’s Birthday 题意： 小猪今天过生日了。他的朋友小熊维尼想要给他最好的礼物 —— 一个蜂蜜罐。当然，小熊明白他不可能把整个罐子都送给小猪。事实上，他很可能会把罐子里的蜂蜜全都吃掉。因此，当小熊计划在路上吃一点小吃时，罐子最开始应该有尽可能多的蜂蜜。 前一天，小熊维尼补充了他的蜂蜜储备。小熊维尼家里有 \(n\) 个货架，每个货架上可能有一些，也可能一个蜂蜜罐都没有。在一天中，小熊维尼来到蜂蜜货架上 \(q\) 次；在第 \(i\) 次来到货架 \(u_{i}\)，从中取出一些罐子 \(k_{i}\)，尝试了每个罐子的蜂蜜后，将所有这些罐子放在某个货架 \(v_{i}\) 上。当小熊选择罐子时，他遵循自己的直觉。这意味着在货架 \(u_{i}\) 上所有 \(k_{i}\) 个罐子的集合中，他等概率地选择一个。 现在小熊记得他对蜂蜜罐执行的所有动作。他想要带着前一天没有尝试过的罐子参加聚会。为此，他必须知道没有一罐蜂蜜尝试过的货架数量 \(m\) 的数学期望。为了更好地评估自己的机会，小熊维尼...

C++语法 #define 预处理 #define 预处理指令用于创建符号常量。 该符号常量通常称为宏，指令的一般形式是： #define macro-name replacement-text 基础用法包括但不限于 #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define ls(at) ((at) << 1) #define sq(x) ((x) * (x)) // #define int long long 相当于把文件中的所有 int 都替换成 long long 高级一些的用法是利用 # 和 ## 运算符 #define TOSTR(x) #x // TOSTR(q779 is sb) 等价于 "q779 is sb" #define For(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++) // 一个从 a 到 b 的 for 循环 实例： #include <bits/stdc++.h> using namesp...

C++语法 异常处理 异常是程序在执行期间产生的问题。C++ 异常是指在程序运行时发生的特殊情况，比如尝试除以零的操作。 异常提供了一种转移程序控制权的方式。C++ 异常处理涉及到三个关键字：try、catch、throw。 throw: 当问题出现时，程序会抛出一个异常。这是通过使用 throw 关键字来完成的。 catch: 在您想要处理问题的地方，通过异常处理程序捕获异常。catch 关键字用于捕获异常。 try: try 块中的代码标识将被激活的特定异常。它后面通常跟着一个或多个 catch 块。 如果有一个块抛出一个异常，捕获异常的方法会使用 try 和 catch 关键字。 try 块中放置可能抛出异常的代码，try 块中的代码被称为保护代码。 使用 try/catch 语句的语法如下所示： try { // 保护代码 }catch( ExceptionName e1 ) // ExceptionName 是类型 { // catch 块 }catch( ExceptionName e2 ) { ...

CF280C Game on Tree 题解 题目链接：Game on Tree 题意： 给定一棵有根树，结点编号从 \(1\) 到 \(n\)。根结点为 \(1\) 号结点。 对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 \(1\) 号结点后游戏即结束。 要求求出删除所有结点的期望操作次数。 输入格式 第一行，一个正整数 \(n(1 \le n \le 10^5)\) 表示结点数量。 接下来 \(n-1\) 行每行两个数，表示树上的一条连接 \(a_i\) 与 \(b_i\) 的边 \((a_i,b_i)\) 保证给定的数据是一棵树。 输出格式 输出一个实数，表示期望操作次数。答案误差在 \(10^{-6}\) 之内则认为正确。 显然，当且仅当一个节点比它的所有的祖先都要优先删除时，它会对操作次数产生 \(1\) 的贡献 于是我们可以单独考虑每个点对答案的期望贡献。 设 \(f_i\) 为点 \(i\) 直接选中时对答案的期望贡献，则 \[ f_i = \frac{1}{p} \times 0 + p...

UVA12004 Bubble Sort 题解 题目链接：Bubble Sort 题意： \(T \le 1000\) 组询问，每次给定 \(n(1 \le n \le 10^5)\) ， 问 \(1\) 到 \(n\)​ 的 \(n\) 个数的排列中逆序对个数的期望，以分数的形式输出，比如 1/2 。 这题只有入门吗？好好好，我菜就是了，我只会 dp 。 设 \(f_i\) 为 \(i\) 个数的排列的逆序对个数的期望。我们考察 \(i\) 的位置，则 \[ f_i = \frac{1}{i}\left(f_{i-1} + 0\right) + \frac{1}{i}\left(f_{i-1} + 1\right) + \cdots + \frac{1}{i}\left(f_{i-1} + i-1\right) \] 整理一下 \[ f_i = f_{i-1} + \frac{i-1}{2} \] 即（直接把每个 \(f_i\) 全部写出来就能找到规律了） \[ f_i = \frac{i(i-1)}{4} \] 时间复杂度 \(\mathcal{O}(T)\) 代码： #...

C++语法 继承与多态 & 虚函数 继承与多态听起来挺高级的，其实还挺简单的。 一、C++ 继承 面向对象程序设计中最重要的一个概念是继承。 继承允许我们依据另一个类来定义一个类，这使得创建和维护一个应用程序变得更容易。 这样做，也达到了重用代码功能和提高执行效率的效果。 当创建一个类时，我们不需要重新编写新的数据成员和成员函数 只需指定新建的类继承了一个已有的类的成员即可。 这个已有的类称为基类，新建的类称为派生类。 继承代表了 A is a (what) B 的关系。例如，哺乳动物是动物，狗是哺乳动物，因此，狗是动物，等等。 用代码表示上图： // 基类 class Animal { // eat() 函数 // sleep() 函数 }; //派生类 class Dog : public Animal { // bark() 函数 }; 1. 基类 & 派生类 一个类可以派生自多个类，这意味着，它可以从多个基类继承数据和函数。定义一个派生类，我们使用一个类派生列表来指定基类。类派生列表以...

C++语法 Lambda 函数与表达式 C++11 提供了对匿名函数的支持,称为 Lambda 函数(也叫 Lambda 表达式)。 Lambda 表达式把函数看作对象，因此它可以像对象一样使用 比如可以将它们赋给变量和作为参数传递，还可以像函数一样对其求值。 Lambda 表达式本质上与函数声明非常类似。 具体形式如下: [capture](parameters) mutable ->return-type{body} [capture]：捕捉列表。捕捉列表总是出现在 lambda 表达式的开始处。事实上，[] 是 lambda 引出符。编译器根据该引出符判断接下来的代码是否是 lambda 函数。捕捉列表能够捕捉上下文中的变量供 lambda 函数使用。 (parameters)：参数列表。与普通函数的参数列表一致。如果不需要参数传递，则可以连同括号 () 一起省略。 mutable：mutable 修饰符。默认情况下，lambda 函数总是一个 const 函数，mutable 可以取消其常量性。在使用该修饰符时，参数列表不可省略（即使参数为空）。 -...

高斯消元的线性技巧 朴素的高斯消元是 \(\mathcal{O}(n^3)\) 的，算法原理参考 浅谈高斯消元 而在一些题目中，比如 洛谷P5516 [MtOI2019] 小铃的烦恼 ，实际上我们有一种线性的技巧。 设 \(a_i,b_i,c_i\) 都是关于 \(i\) 的函数或常数，\(k\) 为常数，递推式（通常是概率或者期望的dp式子） \[ f_0=0,~f_n=k\\f_i = a_if_{i-1}+b_if_{i+1}+c_i (1\le i < n) \] 所对应的矩阵形如 \[ \begin{bmatrix} 1 & -a_1 & & & & & c_1\\[6pt] -a_2 & 1 & -b_2 & & & & c_2\\[6pt] & -a_3 & 1 & -b_3 & & & c_3\\[6pt] & & & \ddots && &\vdots\\[6...

洛谷P5516 [MtOI2019] 小铃的烦恼 题解 题目链接：P5516 [MtOI2019] 小铃的烦恼 题意： 小铃每天都会整理一次铃奈庵的书籍。这次桌子上有 \(n\) 本魔法书，这些书一次排成一排，每本书有一个魔法属性和编号。 最开始这些书的魔法属性都是一样的，但是因为被人多次使用，魔法属性发生了变化，小铃想让所有书的魔法属性重新全部相同。 这次小铃找到了雾雨 魔理沙(Kirisame Marisa)帮忙整理书籍，每次魔理沙可以释放选定魔法，魔法会随机选择两本书 \(a,b\) ( \(a\) 不等于 \(b\) )。 选定这两本书后，魔理沙会释放转移魔法，使得有 \(p_{a,b}\ \left(p_{a,b}\in (0,1]\right)\) 的概率，第 \(b\) 本书的魔法属性变成第 \(a\) 本书的魔法属性。也就是说有 \(1-p_{a,b}\) 的概率，使得你即使选定了 \(a,b\) 两本书，但是魔法属性的转移不成功，意味着这次操作是无效的 。 注意 \(p_{a,b}\) 是对于转移是否成功的概率，和随机选择两本书的操作互不影响。 现在小铃想知道...