shicj's blog

一、文件 文件名不要打错 保存关闭文件之后用命令行按规定指令编译 检查输入输出文件 ⋆\color{red}\star⋆ 测试大样例之前用规定指令编译 cerr 调试一定要删 关闭所有窗口 二、题目 必须计算空间复杂度 ⋆\color{red}\star⋆ 注意溢出和越界 -fsanitize=address,undefined 注意时间常数，进行极限数据测试 不确定的算法写完如果有时间要对拍 大模数必须复制，注意是否素数 ⋆\color{red}\star⋆ 必须用scanf&prinf输入输出 ceil()、floor()、pow()返回值是double的 unordered_map、unordered_map更快 三、算法 DP一定要计算空间 ⋆\color{red}\star⋆ 线段树不要忘记pushup和pushdown 考前看一下模板 ⋆\color{red}\star⋆ 没思路依次想这些方法：DP、贪心、二分答案、数学、图论、猜结论、先写暴力再优化 随机化可能有用 多种贪心、错解取最优 ⋆\color{red}\star⋆...

第三课 集合 [返回目录][洛谷专栏链接] 1. 集合的概念 概念 指定的某些对象的全体（研究对象是元素） 特性 确定性，互异性，无序性 元素与集合的关系 属于（∈\in∈） 不属于（∉\notin∈/​） 集合的分类 有限集，无限集，空集（） 常见数集 R\RR 实数集 Q\mathbb QQ 有理数集 Z\ZZ 整数集 N\NN 自然数集 C\ComplexC 复数集 N∗=N+\N^*=\N_+N∗=N+​ 正整数集 R+\R^+R+ 正实数集 集合的表示方法 列举法 A={1,2,3}A=\{1,2,3\}A={1,2,3} 描述法 A={x∣y=x2−x+1}=RA=\{x|y=x^2-x+1\}=\RA={x∣y=x2−x+1}=R B={y∣y=x2−x+1}=[34,+∞)B=\{y|y=x^2-x+1\}=[\dfrac{3}{4},+\infty)B={y∣y=x2−x+1}=[43​,+∞) C={(x,y)∣y=x2−x+1}=C=\{(x,y)|y=x^2-x+1\}=C={(x,y)∣y=x2−x+1}=...

八上历史第1~2单元整理 1. 时间线 1839.6.3−1836.6.25\color{red}1839.6.3-1836.6.251839.6.3−1836.6.25 虎门销烟 1840−1842\color{red}1840-18421840−1842 鸦片战争 1842\color{green}18421842 签《南京条约》 1843\color{green}18431843 签《虎门条约》 1844\color{green}18441844 签《望厦条约》、《黄埔条约》 1856−1860\color{red}1856-18601856−1860 第二次鸦片战争 1856\color{green}18561856 炮轰广州 1858\color{green}18581858 攻大沽炮台，签《天津条约》、《通商章程善后条约》 1860\color{green}18601860 火烧圆明园，签《北京条约》 1851−1864\color{red}1851-18641851−1864...

第二课 函数的基本性质 [返回目录][洛谷专栏链接] 1. 单调性 定义 一般地，设函数 f(x)f(x)f(x) 的定义域为 III，区间 D⊆ID\subseteq ID⊆I： 如果 ∀x1,x2∈D\forall x_1,x_2 \in D∀x1​,x2​∈D，当 x1<x2x_1<x_2x1​<x2​ 时，都有 f(x1)<f(x2)f(x_1)<f(x_2)f(x1​)<f(x2​)，那么称函数 f(x)f(x)f(x) 在区间 DDD 上单调递增。当 f(x)f(x)f(x) 在它的定义域上单调递增时，称它为增函数。 如果 ∀x1,x2∈D\forall x_1,x_2 \in D∀x1​,x2​∈D，当 x1<x2x_1<x_2x1​<x2​ 时，都有 f(x1)>f(x2)f(x_1)>f(x_2)f(x1​)>f(x2​)，那么称函数 f(x)f(x)f(x) 在区间 DDD 上单调递减。当 f(x)f(x)f(x)...

第一课 函数的概念及其表示 [返回目录][洛谷专栏链接] 1. 函数的概念 一般的，设 A,BA,BA,B 是非空的实数集（R\RR），如果对于集合 AAA 中的任意一个数 xxx，按照某种确定的对应关系 fff，在集合 BBB 中都有唯一确定的数 yyy 和它对应，那么就称 f:A→Bf:A\to Bf:A→B 为从集合 AAA 到集合 BBB 的一个函数，记作 y=f(x),x∈Ay=f(x),x\in A y=f(x),x∈A 其中，xxx叫做自变量，xxx 的取值范围 AAA 叫做函数的定义域；与 xxx 值相对应的 yyy 值叫做函数值，函数值的集合 {f(x)∣x∈A}\{f(x)|x\in A\}{f(x)∣x∈A} 叫做函数的值域。 函数的三要素（两域一关系）：定义域、值域、对应关系（对应法则） 映射（教材已删去）：与函数类似，但映射研究任意非空集合，函数是特殊是映射。 例题：存在函数 f(x)f(x)f(x) 满足，对任意 x∈Rx\in \Rx∈R 都有（）？ A....

0x00 题目翻译 一棵有 nnn 个节点的秘密树，索引从 111 到 nnn ，并要求你使用以下类型的查询来猜测它： “? a b” - Misuki 会告诉你哪个节点 xxx 使 ∣d(a,x)−d(b,x)∣|d(a,x) - d(b,x)|∣d(a,x)−d(b,x)∣ 最小，其中 d(x,y)d(x,y)d(x,y) 是节点 xxx 和 yyy 之间的距离。如果存在多个这样的节点，那么 Misuki 会告诉你哪个节点能使 d(a,x)d(a,x)d(a,x) 最小化。 用最多 15n15n15n 次查询找出秘密树的结构！ 0x01 解题思路 由距离差最小值，想到中点，由 15n15n15n 次查询，想到 O(nlog⁡n)O(n\log n)O(nlogn)，于是自然想到类似二分的思想。 什么时候可以确定一条边呢？当我们查询到两个相邻节点（中间有边）时，答案必定是这两个节点中的一个。反推，如果查询到答案是传入的两个点中的一个，这两个点中间有一条边。 这是只需要以 (n−1)×log⁡n(n-1)\times\log n(n−1)×logn 次查询，确定...

我认为这题应该评黄。 0x00 题目大意 给你一个 n×mn\times mn×m 矩阵，里面元素构成排列，你可以交换任意一列任意一行，求任意次操作后两个矩阵能否相同。 0x01 解题思路 看到题面，可能没有什么思路，我们来按题目模拟一下。 设原始矩阵为： (a1,1a1,2⋯a1,ma2,1a2,2⋯a2,m⋮⋮⋱⋮an,1an,2⋯an,m) \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m}\\ \end{pmatrix} ...

A 给定 a,b,ca,b,ca,b,c，输出从 aaa 时 bbb 分到 aaa 时 ccc 分的所有时间。 样例输入 119 10 15 样例输出 12345619 1019 1119 1219 1319 1419 15 B 有 nnn 根绳子，每根长 aia_iai​，现在可以拼接相邻的几根绳子为一根，要求最终拼出的每根绳子长度都不超过 mmm，求最终最少合并出多少根。 样例输入 124 61 3 4 2 样例输出 12 C 有 nnn 个学生，输入每个学生的 ididid 和成绩，有 qqq 次查询，输入一个 ididid，输出对应的成绩。 样例输入 1234567841 9023 10044 605 952231 样例输出 1210090 D 输入一个字符串，去除里面的元音字母（a,e,i,o,ua,e,i,o,ua,e,i,o,u），输出。 样例输入 1helloworld 样例输出 1hllwrld E 有 nnn 堆火柴，每堆 aia_iai​ 个，现在两人轮流，每次在一堆中取出若干火柴，率先取完者获胜，求是否有先手必胜策略。 样例输入1 1222...

通过简单修改自定义内容，可实现区间加减乘除，max，min，取反以及其他功能，但暂时无法实现多操作（因为tag处理顺序不确定，要自己写） 对象 类型 说明 typename T 参数 线段树的数据类型 stduct node 内部 定义了l，r，v，tag T dat[] 参数 线段树的原始序列 void pushup(int x) 内部 pushup void build(int x,int l,int r) 函数 初始化，传入1,1,n void pushdown(int x) 内部 pushdown void update(int x,int L,int R,T v) 函数 更新，传入(1,l,r,v) T query(int x,int L,int R) 函数 查询，传入(1,l,r) T op(int x,int y) 自定义 pushup的操作符 T q_op(int x,int y) 自定义 query的操作符 T tot_init 自定义 query累计变量初始值 void apply(int x,T...

0x00 题目翻译 最初数轴上由 nnn 个点 x1,x2,x3,…,xnx_1,x_2,x_3,\dots,x_nx1​,x2​,x3​,…,xn​，每次随机取两个，把它们拿走后再把它们的平均数 xi+xj2\dfrac{x_i+x_j}{2}2xi​+xj​​ 放回数轴，最后剩下一个点，求这个点坐标的期望。 0x01 解题思路 1. 猜想结论 ansn=∑i=1nainans_n=\dfrac{\sum_{i=1}^{n}a_i}{n} ansn​=n∑i=1n​ai​​ 2. proof 3.对输出的处理 要求输出 p×q−1p\times q^{-1}p×q−1，这里我们需要用乘法逆元。 显而易见 998244353998244353998244353 是质数，乘法逆元可以通过 q998244353−2q^{998244353-2}q998244353−2 得到，需要快速幂。 0x02 AC...