Q779’s Blog

洛谷P4331 [BalticOI 2004] Sequence 数字序列 题解 题目链接：P4331 [BalticOI 2004] Sequence 数字序列 题意： 给定一个整数序列 \(a_1, a_2, \cdots , a_n\)，求出一个递增序列 \(b_1 < b_2 < ··· < b_n\)， 使得序列 \(a_i\) 和 \(b_i\) 的各项之差的绝对值之和 \(|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|\) 最小。 输入格式： 第一行为数字 \(n (1≤n≤10^6)\)，接下来一行共有 \(n\) 个数字，表示序列 \(a_i (0≤a_i≤2^{31}-1)\)。 输出格式： 第一行输出最小的绝对值之和。 第二行输出序列 \(b_i\)，若有多种方案，只需输出其中一种。 数据范围： \(1\le n\le 10^6 , 0\le a_i\le 2^{31}-1\)； 本题可以转化为另一个模型，即 给定序列 \(a_i\) ，每次可以将任意元素加 \(1\) 或减 \(1\...

洛谷P3270 [JLOI2016] 成绩比较 题解 题目链接：P3270 [JLOI2016] 成绩比较 题意： G 系共有 \(N\) 位同学，\(M\) 门必修课。这 \(N\) 位同学的编号为 \(0\) 到 \(N-1\) 的整数，其中 B 神的编号为 \(0\) 号。这 \(M\) 门必修课编号为 \(0\) 到 \(M-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。 如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。在 B 神的说法中，G 系共有 \(K\) 位同学被他碾压（不包括他自己），而其他 \(N-K-1\) 位同学则没有被他碾压。D 神查到了 B 神每门必修课的排名。 这里的排名是指：如果 B 神某门课的排名为 \(R\)，则表示有且仅有 \(R-1\) 位同学这门课的分数大于 B 神的分数，有且仅有 \(N-R\) 位同学这门课的分数小于等于 B 神（不包括他自己）。 我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足 B 神的说法，也能符合 D 神查到的排名...

CF622F The Sum of the k-th Powers 题解 题目链接：The Sum of the k-th Powers 题意： 给定 \(n,k\) ，求 \[ f(n,k)=\sum_{i=1}^ni^k \pmod{10^9+7} \] 数据范围：\(1 \le n \le 10 ^ 9, 0 \le k \le 10 ^ 6\)。 考虑 \(k\) 固定时的情况。可以证明，函数 \(f(n) = \sum_{i=1}^ni^k\) 是一个 \(k+1\) 次多项式。 证明 考虑把 \(\sum_{i=1}^n i^k\) 看作 \(n^k+(n-1)^k + \cdots + (n-(n-1))^k\) 暴力展开以后，可以发现这是 \(n\) 个 \(k\) 次多项式，即 \(k+1\) 次多项式。\(\square\) 由于 \(k\) 比较小，所以考虑随便找 \(k+2\) 个点（取 \(n=1,2\cdots,k+2\) 即可）代入 因为 \(k+2\) 个点 \((x_i,y_i)\) 可以唯一确定 \(k+1\) 次多项式，根据拉格朗日插...

CF1625E2 Cats on the Upgrade (hard version) 题解 题目链接：Cats on the Upgrade (hard version) 题意： 本题和 CF1625E1 的唯一区别在于，本题有修改操作。 给定一个长度为 \(n\) 的仅包含 (、) 的字符串 \(s\)。给出如下定义： 定义某字符串是一个简单的合法括号序列，当且仅当我们可以通过若干次移除一个 . 或者一个连续的子串 () 的操作将这个字符串删空，且这个字符串不以 . 作为开头或者结尾。 定义 \(s[l\dots r]\) 为字符串 \(s\) 从第 \(l\) 个字符开始到第 \(r\) 个字符结束的子串。 定义 \(s_x\) 为字符串 \(s\) 的第 \(x\) 个字符。 一共有 \(q\) 次操作，每次操作分为如下两类： 1 l r：将 \(s_l\) 和 \(s_r\) 替换为 . 。保证 \(s[l\dots r]\) 以 ( 开头，以 ) 结尾，且中间所有字符都为 .。 2 l r：询问有多少个 \(s[l\dots r]\) 的子串是简单的 RBS。...

【生物】二分裂与无丝分裂的区别 二分裂一般为原核生物（如细菌）和单细胞真核生物的分裂方式，细胞遗传物质经过复制后，平均分配给两个子细胞，完成一次分裂形成两个大小相等的子细胞。 无丝分裂又称为直接分裂。在真核细胞分裂的方式中，无丝分裂发现最早，是一种简单而常见的分裂方式。无丝分裂主要出现在高等生物（真核细胞）已分化的细胞中，如蛙的红细胞。 无丝分裂有缢裂、芽裂、碎裂、变形虫状分裂、臂裂等多种方式。尽管不同的真核生物的无丝分裂方式存在着些微差异，但分裂过程基本相似，有的细胞在核仁先伸长横缢为两个或多个，这一点上与二分裂有所不同。随着细胞核的伸长，核仁向核的两端移动，然后在核的中部从一侧或多侧向内凹陷横缢，使核呈肾形或哑铃形，最后分裂为两个或多个子核。与此同时，细胞质也被拉长，并在子核之间发生横缢，继而在光面内质网的参与下形成细胞膜，最终分裂为两个或多个子细胞。整个过程中核膜和核仁都不消失，没有染色体和纺锤体的出现，看不到染色体的规律性变化，故称之为无丝分裂。

快速沃尔什变换 FWT 模板题链接：P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT) 题意： 给定长度为 \(2^n\) 两个序列 \(A,B\)，设 \[ C_i=\sum_{(j\operatorname\circ k) = i}A_j \times B_k \] 分别当 \(\operatorname\circ\) 是 or, and, xor 时求出 \(C\)。 输入格式： 第一行，一个整数 \(n\)。 第二行，\(2^n\) 个数 \(A_0, A_1, \ldots, A_{2^n-1}\)。 第三行，\(2^n\) 个数 \(B_0, B_1, \ldots, B_{2^n-1}\)。 输出格式： 三行，每行 \(2^n\) 个数，分别代表 \(\operatorname\circ\) 是 or, and, xor 时 \(C_0, C_1, \ldots, C_{2^n-1}\) 的值\(\bmod 998244353\)。 数据范围： \(1 \le n \le 17\)。 \(\mathcal{Part}\ 0\) 简介 在 OI 中...

CF438E The Child and Binary Tree 题解 题目链接：The Child and Binary Tree 题意： cxy 很喜欢计算机科学，而且尤其喜欢二叉树。 考虑一个含有 \(n\) 个互异正整数的序列 \(c_1,c_2\cdots,c_n\)。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合 \(\{c_1,c_2,\cdots,c_n\}\) 中，cxy 就会将其称作神犇的。 并且她认为，一棵带点权的树的权值，是其所有顶点权值的总和。 给出一个整数 \(m\)，你能对于任意的 \(1\leq s\leq m\) 计算出权值为 \(s\) 的神犇二叉树的个数吗？ 我们只需要知道答案关于 \(998244353\) 取模后的值。 参照下图以更好的理解什么样的两棵二叉树会被视为不同的。 输入格式： 输入第一行有 \(2\) 个整数 \(n,m\) \((1\leq n,m\leq 10^5)\)。 第二行有 \(n\) 个用空格隔开的互异的整数 \(c_1,c_2\cdots,c_n\) \((1\le c_i\le10^5)\)。 输出...

【生物】细菌能进行质壁分离吗？ 答案：可以。 Braun 于1852年首次描述了原生质包膜从细胞壁上收缩的现象，由 De Vries 于1877年首次创造了术语“plasmolysis”，即质壁分离，并将其定义为由外部吸水溶液（即细胞外高浓度溶液）引起的活的原生质膜与细胞壁的分离。 郑光美教授的《生物学辞典》中指出：质壁分离则指植物细胞的原生质体收缩，部分质膜与细胞壁脱离的现象。 通过中国知网以“质壁分离”为关键词搜索，基本上都只能得到植物质壁分离相关的研究。故很多中学老师以为只有有中央大液泡的植物细胞才能发生质壁分离现象。但是也有少量中文文献中提及诸如“饱和NaCl溶液中细菌发生质壁分离”。在国外则有大量关于细菌等有细胞壁结构的生物质壁分离的研究报道。 由此可见，国内外关于质壁分离的定义范围有所不同。国外关于质壁分离所指范围明显更广，包括具有细胞壁的植物、细菌、真菌、放线菌等细胞的质膜与细胞壁的分离。 综上所述，不只是具有中央大液泡的植物细胞才能发生质壁分离，细菌等具有细胞壁的细胞亦能发生质壁分离。

P10780 BZOJ3028 食物 题解 题目链接：P10780 BZOJ3028 食物 题意： cxy 这次又要出去旅游了，和上次不同的是，她这次要去宇宙探险！我们暂且不讨论她有多么 NC，她又幻想了她应该带一些什么东西。理所当然的，你当然要帮她计算携带 \(n\) 件物品的方案数。 她这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。 当然，她又有一些稀奇古怪的限制： 每种食物的限制如下： 承德汉堡：偶数个； 可乐：\(0\) 个或 \(1\) 个； 鸡腿：\(0\) 个，\(1\) 个或 \(2\) 个； 蜜桃多：奇数个； 鸡块：\(4\) 的倍数个； 包子：\(0\) 个，\(1\) 个，\(2\) 个或 \(3\) 个； 土豆片炒肉：不超过一个； 面包：\(3\) 的倍数个； 注意，这里我们懒得考虑 cxy 对于带的食物该怎么搭配着吃，也认为每种食物都是以「个」为单位（反正是幻想嘛），只要总数加起来是 \(n\) 就算一种方案。因此，对于给出的 \(n\)，你需要计算出方案数，并对 \(10007\) 取模。 输入格式： 一个整数 \(n\)，表...

C++语法 头文件全集 在算法竞赛中，建议使用 bits/stdc++.h ，俗称万能头文件。 #include <assert.h>　　　　// 设定插入点 #include <ctype.h>　　　　 // 字符处理 #include <errno.h>　　　　 // 定义错误码 #include <float.h>　　　　 // 浮点数处理 #include <fstream.h>　　　 // 文件输入／输出 #include <iomanip.h>　　　 // 参数化输入／输出 #include <iostream.h>　　　// 数据流输入／输出 #include <limits.h>　　　　// 定义各种数据类型最值常量 #include <locale.h>　　　　// 定义本地化函数 #include <math.h>　　　　　// 定义数学函数 #include <stdio.h>　　　　 // 定义输入／输出函数 #include <stdlib.h>　　　　// 定义杂项函数及内存分配函...

C++语法 无敌火车头 因为形状像火车并且看上去很无敌，所以取名为无敌火车头（确信）。 反正我自己没用过这种东西，但是看别人乱搞用这个东西，好像确实会快一些。 注意这个东西不适用于所有的 OJ ，有的 OJ 是不支持自己加编译指令的。 #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched...

C++语法 运算符优先级 建议不确定运算符优先级就都多套几个括号，尤其是位运算符。 优先级 运算符 叙述 示例 重载性 结合性 1 :: 作用域解析(C++专有) Class::age = 2; 否 由左至右 2 ++ 后缀递增 i++ – 后缀递减 i– () 函数调用或函数调用形式的类型转换 int x = f(); [] 数组访问 array[4] = 2; . 以对象方式访问成员 obj.age = 34; 否 -> 以指针方式访问成员 ptr->age = 34; dynamic_cast 运行时检查类型转换(C++专有) Y& y = dynamic_cast<Y&>(x); 否 static_cast 未经检查的类型转换(C++专有) Y& y = static_cast<Y&>(x...