AcWing.3786 二叉排序树
你需要写一种数据结构,来维护一些数,其中需要提供以下操作:
插入数值 $x$。
删除数值 $x$。
题目保证:
操作 $1$ 插入的数值各不相同。
操作 $2$ 删除的数值一定存在。
输出树的前序遍历
输入格式
第一行包含整数 $n$,表示共有 $n$ 个操作命令。
接下来 $n$ 行,每行包含两个整数 $opt$ 和 $x$,表示操作序号和操作数值。
数据范围
$1 \le n \le 2000$,
$-10000 \le x \le 10000$
输入样例:
4
1 1
1 3
1 5
2 3
输出样例:
1 5
思路
插入操作:
删除操作:
对于一个二叉排序树来说,中序遍历(左中右)是有序的。
有三种情况
该节点为叶节点
该节点存在一个左节点,或者一个右节点
该节点存在左节点、右节点
重点说明一下第三种情况:由于是一颗二叉排序树,故节点$X$的左子树中最右的根节点$A$一定是左子树中最大的值,故将节点$A$的值赋值给节点$X$,再递归遍历左子树,删除节点$A$。
Code
12345678910111213141516171819202122232425262 ...
AcWing.840 模拟散列表
840.模拟散列表
维护一个集合,支持如下几种操作:
I x,插入一个数 $x$;
Q x,询问数 $x$ 是否在集合中出现过;
现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 $N$,表示操作数量。
接下来 $N$ 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
开散列方法(拉链法)
核心:如果一个位置有多个重复映射到此处的元素,就开一个链表,将所有元素都存储下来。
$Code$:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636 ...
AcWing.3302 表达式求值
题意
给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 $2^{31}-1$。
题目中的整除是指向 $0$ 取整,也就是说对于大于 $0$ 的结果向下取整,例如 $5/3=1$,对于小于 $0$ 的结果向上取整,例如 $5/(1-4) = -1$。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。
输出格式
共一行,为表达式的结果。
数据范围
表达式的长度不超过 $10^5$。
输入样例:
(2+2)*(1+1)
输出样例:
8
思想
表达式求值:
如果当前元素是数字:压入
如果当前元素是(:压入
如果当前元素是):操作到(
如果当前 ...
好技巧
高数
【来自AC群的包包】
【来自AC群的a宝】
多元微分学中偏导连续推所有,可微推其他,剩下的条件啥也推不出。
充分必要性:
如果【A可以推出B】,则【A是B的充分条件,B是A的必要条件】
理解:A能够充分的推出B,而推出B的必须要的条件是A(A是条件,B是结果)
如果【A可以推出B,B推不出A】,则【A是B的充分不必要条件,B是A的必要不充分条件】
例子
下列条件中,3阶矩阵$A$可以相似对角化的充分不必要条件为:()
A.$A$有3个不相等的特征值。
B.
C.
D.
也就是选项能$\longrightarrow$条件,条件$\not\longrightarrow$选项。
反三角函数问题
分清下面两个式子:
(1)$\sin{(\arcsin{x})}=x$
(2)$\arcsin{(\sin{x})}=x$
对于(1)$\sin{(\arcsin{x})}=x$来说,由于$\arcsin{x}$的定义域为$[-1,1]$,$\sin{(\arcsin{x})}$的主值区域也就是$\sin{x}$的定义域为$[-\infty,+\infty]$,$\sin{(\a ...
DS
考试内容
一、数据结构的有关概念
考纲要求:
1.掌握数据结构的有关概念,理解逻辑结构与物理结构之间的关系。
2.掌握数据结构的几种基本结构。
3.掌握抽象数据类型的表示与实现方法。
4.熟悉算法分析的分析方法。
考点总结:
数据结构的几种基本结构
集合(不常考)
线性结构(1:1)
树形结构(1:n)
图形结构(m:n)
数据结构的基本概念和术语
标识符只能以英文字母或下画线开头,不能以数字开头。
数据结构包括逻辑结构和存储结构两个层次
线性结构:线性表 ,栈, 队列 ,双队列,串。
非线性结构:二维数组,树,图。
它们都可以顺序存储和链式存储。
数据
数据适用以描述客观食物且能够输入到计算机储存介质中能被计算机程序识别和处理的符号的总称,它是计算机加工的“原料”。
数据元素
数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。
有时一个数据元素可以由若干数据项组成(此时往往把一个数据元素称为一条记录),数据项是具有独立含义的最小标识单位。
在某些情况下,往往也把数据元素简称为元素或结点。
数据项
数据项是数据结构中讨论的最小单位 ...
现代杨
第一章 行列式
例题
题目
回答情况
第1题
√
第2题
x x
第3题
x √
第4题
x √
第5题
x x
第6题
x √
第7题
x x
第8题
x √
第9题
x √
第10题
x x
第11题
x √
第12题
x x
第13题
x x
第14题
x √
第15题
x x
第16题
x √
第17题
x √
第18题
x x
第19题
x x
第20题
√
第21题
x √
第22题
x x
第23题
x √
第24题
x √
第25题
√
第26题
x
第27题
x
总结
第二题:变换3,4行为X型行列式。
第三题:把含有$x$的项化简为越少越好。
第四题:数学归纳法,先找$n=1,n=2,n=3$的特殊情况,找出规律,再用数学归纳法进行证明。
第五题:研究n阶行列式,先看4阶或者5阶行列式找规律。此题是"么"字型行列式。
第六题:判断A是否为可逆矩阵,就分析$|A|$是否为零。
$\begin{cases} | ...
数学公式自测
画出一下函数的大致图像
(1)$\sin{x}$
(2)$\cos{x}$
(3)$\tan{x}$
(4)$\cot{x}$
(5)$\sec{x}$
(6)$\csc{x}$
(7)$\arcsin{x}$
(8)$\arccos{x}$
(9)$\arctan{x}$
(10)$arccot{x}$
(11)$\arctan{x}+arccot{x}=\frac{\pi}{2}$
(12)三幅图:$y=x^\alpha$,当$\begin{cases} \alpha<0 \\ \alpha=0 \\ \alpha>0 \begin{cases} 0<\alpha<1 \\ \alpha=1 \\ \alpha>1 \end{cases} \end{cases} $
(13)1、心形线,2、双纽线,3、星形线,4、摆线。
心形线
注:$ρ=a(1-\cos{x})$,根据坐标变换公式$\cos{\theta}=\frac{x}{ρ}$以及$ρ=\sqrt{x^2+y^2}$可知其直角坐标方程$x^2+y^2=(x+\frac{x^ ...
mathjax-test
$f(x)$ 一阶连续可导 $\quad\Rightarrow\quad$ $\lim\limits_{x \to 0} f’(x_0 + x) = f’(x_0)$
$$ \begin{aligned} \lim\limits_{x\to0}\dfrac{\displaystyle\int_0^{x^2}f(t)dt}{x^2\displaystyle\int_0^xf(t)dt} &\xlongequal{L’} \lim\limits_{x\to0}\dfrac{2x f(x^2)}{2x\displaystyle\int_0^xf(t)dt + x^2f(x)} \\ &= \lim\limits_{x\to0}\dfrac{2f(x^2)}{2\displaystyle\int_0^xf(t)dt + xf(x)} \\ &\xlongequal{L’} \lim\limits_{x\to0}\dfrac{4xf’(x^2)}{3f(x) + xf’(x)} \\ &= \lim\limits_{x\to0}\dfrac{4f’(x^2)}{3 ...
AtCoder Beginner Contest 255 A—E
A
题目描述
给定一个的$ \ 2 \times 2 \ $矩阵$ \ A \ $,输出其中的值$ \ A_{R,C} \ $。
题目分析
时间复杂度:$O(1)$。
输入就行嘞。
$Code$
123456789101112131415int n, m;int a[10][10]; int main(){ cin >> n >> m; for(int i = 1; i <= 2; i ++ ) for(int j = 1; j <= 2; j ++ ) cin >> a[i][j]; cout << a[n][m] << endl; return 0;}
$ \ $
$ \ $
B
题目描述
有$ \ N \ $个人在位置为$(X_i,Y_i)$的位置上。
其中有$ \ K \ $个人是特殊人~~(被选中的孩子)~~,能够发射光芒。
当一个人位于$ \ (x,y) \ $坐标发射半径为$ \ R \ $的光芒时候,能够照亮以$ \ (x,y) \ $为圆心,半径为$ \ R \ $ ...
AtCoder Beginner Contest 252 A—F
本题解思路来自这两位大佬 cup-pyy 、 GoodCoder666
A
题目描述
输出一个数字对应的ASCII码。
题目分析
时间复杂度:$O(1)$。
$Code$
1234567int main(){ int n; cin >> n; cout << (char)n << endl; return 0;}
$ \ $
$ \ $
B
题目描述
高桥有$ \ N \ $个食物,第 $ \ i \ $个食物有个美味程度$ \ A_i\ $。
在这些食物中,他有$ \ K \ $个不喜欢的食物,下标分别为$i = 1,2,…,K$。
高桥会选择美味程度最大的品尝,他是否会吃到他不喜欢的食物呢?
如果吃到了输出Yes,否则输出No。
题目分析
时间复杂度:$O(n)$。
我们用$ \ a \ $数组记录每个食物的美味程度,用$ \ b \ $布尔数组记录高桥不喜欢的食物。
用$ \ maxv \ $记录美味程度最大的值。
遍历$ \ a \ $数组,如果找到
maxv == a[i] && b[i],则说明当 ...