博弈论

本文不是题解。

这里，先放一个我做的 PPT：link。如果有补充，放在下面。

Yurchiu 2021-07-03, 22:52:12

一些关于树套树的题目

树套树，顾名思义，就是要将两种或多种树形数据结构结合起来，解决一些单独无法解决的问题。

Yurchiu 2021-07-02, 22:09:36

主席树

一些知识

主席树，原名可持久化线段树，发明人黄嘉泰（hjt），其姓名拼音缩写和我国的一位曾任国家主席的人的姓名拼音缩写相同，故得名。

主要思想：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构。

Yurchiu 2021-07-02, 18:32:52

动态开点线段树

线段树的时间复杂度可达 log 级别。而未优化的空间复杂度为 4N 级别，因此有时需要动态开点让空间压缩。

这里的动态开点线段树使用数组写，开一个节点数组作为内存池。

Yurchiu 2021-07-02, 16:30:56

扫描线

接下来利用一个例题来介绍扫描线。

P5490 【模板】扫描线

求 $n$ 个矩形的面积并。矩形以给定左下角坐标 $(x_1, y_1)$ ，右上角坐标 $(x_2, y_2)$ 的方式给出。

$1 \le n \le {10}^5$ ， $0 \le x_1 < x_2 \le {10}^9$ ， $0 \le y_1 < y_2 \le {10}^9$ 。

Yurchiu 2021-07-02, 15:01:03

一些关于线段树的题目

P4868 Preprefix sum

题意

给一个长度 $n$ 的序列 $a$ ，有两种操作（共 $m$ 次）：

把 $a_i$ 改成 $x$ ；
查询 $SS_i$ 。

Yurchiu 2021-06-28, 23:06:09

P3960 [NOIP2017 提高组] 列队

题意

《 $900$ 亿人一起军训》

Yurchiu 所在的方阵中有 $n \times m$ 名学生（ $n$ 行 $m$ 列）。初始时，第 $i$ 行第 $j$ 列的学生的编号是 $(i-1)\times m + j$ 。

Yurchiu 2021-06-27, 20:36:53

一些关于树状数组的题目

规定：update 是树状数组的更新操作，query 是树状数组的查询操作。

P1908 逆序对

题意

给定一段正整数序列，求逆序对的数目。注意序列中可能有重复数字。序列长度 $n\le5\times10^5$ ，序列数字不超过 $10^9$ 。

Yurchiu 2021-06-24, 23:36:47

一些关于二进制的题目

P7071 [CSP-J2020] 优秀的拆分

题意

对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， $n$ 被分解为了若干个不同的 $2$ 的正整数次幂。给定正整数 $n$ ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。 $1\le n\le10^7$ 。

Yurchiu 2021-06-24, 22:34:26

P5665 [CSP-S2019] 划分

题意

link。给定有 $n$ 个正整数的序列，求出一个最优划分（划分出的各个区间称为“段”，第 $i$ 段中数字之和为 $x_i$ ，段数为 $m$ ），满足：

各段连续。
$\forall i \in (1,m]$ ， $x_{i-1}\le x_i$ 。
$\sum\limits_{i=1}^m x_i^2$ 最小。

Yurchiu 2021-06-23, 21:20:58

单调队列

一些知识点单调队列是一个具有单调性的队列，常常被用来以 O(n)O(n)O(n) 的复杂度维护移动的区间最值。要点：可以手动队列。设定 head 和 tail 两个指针，head<=tail 成立则队列不为空。维护单调性，双端队列。维护时效性，过时弹出，否则压入。模...

Yurchiu 2021-06-22, 21:38:09

差分约束

差分约束系统如果一个不等式组由 nnn 个变量和 mmm 个约束条件组成，形成 mmm 个形如 xj−xi≤kx_j-x_i\leq kxj−xi≤k（i,j∈[1,n]i,j\in[1,n]i,j∈[1,n] 且 kkk 为常数）的不等式，则称其为差分约束系统。换句话说，解决差分约...

Yurchiu 2021-06-17, 12:53:52

《幽默报 007》

此文章已被 Yurchiu 加密。请输入密码查看qwq。

Yurchiu,Internet 2021-06-05, 22:24:12 加密

2021，初中毕业

毕业时的文案今年是 2021 年，初四，毕业季。心中如有千言。回想过去。那年盛夏，我们初见。一个个微笑的脸庞，映现于眼帘，存之于心间。我们的班级，重组过；我们的老师，改换过。我们的友情，却，从未淡去。也许，存在疏亲之分，抑或，存在男女之别；但，我们是一个集体！黑...

Yurchiu 2021-06-04, 21:54:12

经典 DP 问题

最长公共子序列一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 #include<bits/stdc++.h> using namespace std; namespace _yz { co...

Yurchiu 2021-05-03, 22:17:59

«1…3 456 7…11 »

By Yurchiu.

Yurchiu's Blog

一些知识

P5490 【模板】扫描线

P4868 Preprefix sum

题意

题意

P1908 逆序对

题意

P7071 [CSP-J2020] 优秀的拆分

题意

题意