2022牛客多校第一场
本文字数: 2.3k 阅读时长 ≈ 2 分钟
难度:
check-in:G
easy:A D
Medium - easy : C I
Medium : J
Medium - hard : H
Hard : B E F
very - hard : K
统计结果:
A:1334 / 3358 (一血:12)
B:23 / 239 (一血:45)
C:17 / 85 (一血:70)
D:960 / 6414 (一血:30)
E:28 / 222 (一血:45)
F:18 / 135 (一血:46)
G:1482 / 4184 (一血:3)
H:39 / 291 (一血:13)
I:310 / 590 (一血:18)
J:31 / 783 (一血:18)
K:0 / 36 (一血:无)
Educational Codeforces Round 131
本文字数: 1.1k 阅读时长 ≈ 1 分钟
Codeforces补题
本文字数: 3.2k 阅读时长 ≈ 3 分钟
2021CCPC女生赛
本文字数: 1.5k 阅读时长 ≈ 1 分钟
算法笔记(04):基础dp
本文字数: 1.2k 阅读时长 ≈ 1 分钟
本文参照邓丝雨所写的dp进阶之路所作的笔记,在此%%邓丝雨姐姐
1.介绍
1.1 基本思想
dp的核心是对一类求最优解问题的算法,其核心是将一个问题分解成若干个子问题,通过每一次最优决策,求得出一个最优解。
1.2 适用条件
三点:
1.具有相同的子问题:首先,我们必须要保证这个问题能够分解出若干个子问题,并且能通过这些子问题来解决这个问题。
2.满足最优化原理(最优子结构):一个最优决策的子决策也是最优的。
3.具有无后效性:他要求每一个问题的决策,不能对未来问题产生影响,如果产生影响,就无法保证决策的最优性,这就是无后效性。
1.3 解题步骤
确定问题的子问题;
确定状态
推出状态转移方程(关键)
确定边界
优化
1.4 方法
- 根据dp的三要素,从而确定方向
1.1:先确定阶段的问题 :数塔问题
1.2 : 先确定状态的问题 :常见问题
1.3 : 先确定决策的问题 :背包问题
2. dp
2.1 线性dp
2.1.1 LIS问题
LIS问题即最长上升子序列(Longest increasing Sequence):给定一个长为N的数列A,求严格递增的子序列的最长长度是多少?
2.1.1.1 dp,O(n²)解法
首先每个单独的数列是一个子序列,长度为1,因此赋初值f[i]=1;
在此基础上,对i而言,设立一个j从最左扫描到i,去记录每一个比当前值a[i]小的数,通过f[i]来维护当前值。
以 {3 1 2 1 8 5 6}为例子
a[i] 3 1 2 1 8 5 6
len 1 1 2 1 3 3 4
对应的例子是
{3}
{1}
{1,2}
{1}
{1,2,8}
{1,2,5}
{1,2,5,6}
状态转移方程为:
$$\displaystyle dp[j]=\max_{1\leqslant i <j且len(i)<len(j)} dp[i]+1$$
1 | for (int i = 1; i <= n; i ++ ) |
2.1.1.2 贪心+二分 O(nlogn)解法
状态表示:dp[i]表示长度为i的上升子序列的最后一个元素的最小值,类似于维护最值的单调队列。
状态转移:
- 若a[i] > a[len] ,那么dp[++len] = a[i],即把当前的元素追加到后面,使得上升子序列len+1。
- 2反过来,则在dp中查找大于等于a[i]的第一个数的下标pos,令dp[pos] = a[i]。
最后结果就是dp[len](最长上升子序列的内容)
1 | int n,dp[N],a[N]; |
算法笔记(03):树状数组与线段树
本文字数: 2.7k 阅读时长 ≈ 2 分钟
lowbit
就
x&(-x)
树状数组
维护一个数组 a_1,..,a_n ,在 O(logn) 满足以下作用
1.单点加
2.查询前缀和
用c[n]来记录 其实应该满足$$\displaystyle c_i = a_{i - lowbit(i) + 1}$$
以前八个数来看就是:
c[1] = a[1]
c[2] = a[1] + a[2]
c[3] = a[3]
c[4] = a[1] + a[2] + a[3] + a[4]
c[5] = a[5]
c[6] = a[5] + a[6]
c[7] = a[7]
c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
1.单点加
1 | #define ll long long |
2.查询前缀和
1 | #define ll long long |
额外补充:
3.区间加的写法:
1.在区间 [l,r] 内的原数组a 加上 d
易知$$\displaystyle d_{i} = a_{i} - a_{i - 1}$$
如果对**[l , r]** 都加上 x,那么区间内差分数组实际上不会发生改变,实际上只有 $$\displaystyle d[l] += x,d[r + 1] -= x$$
coding:
1 | int l,r; |
2.在区间加的情况下进行查询
不难知道:
$$\displaystyle a_1 = d_1$$
$$\displaystyle a_2 = d_1 + d_2$$
$$\displaystyle a_3 = d_1 + d_2 + d_3$$
易发现规律:
$$\displaystyle sum = x * d_1 + (x - 1) d_2 +\cdots + d_x$$
$$\displaystyle = \sum_{i = 1} ^ {x} (x + 1 - i) d_ i$$
$$\displaystyle = (x + 1) * \sum_{i = 1} ^ {x} d_i - \sum_{i = 1} ^ {x} i* d_i$$
coding:
1 | ll ans = (x + 1) * c1.query(x) - c2.query(x) |
封装的板子如下:
1 | template <class T> |
单点修改:
1 | void f.add(int x,T v) |
复杂度:O(logN)
区间查询(Sum):
1 | T f.sum(int x) |
查询 [0,x) 的区间和
时间复杂度:O(logN)
区间查询(rangeSum):
1 | T f.rangeSum(int l, int r) |
查询 [l,r) 的区间元素和
线段树
建树+查询
1 | const int N = 201000; |
单点修改
1 | //节点为id,对应区间为[l,r],修改a[pos] -> val |
查询最小值
1 | int query(int id, int l, int r, int ql, int qr) { |
懒标记
Educational Codeforces Round 124 (Rated for Div. 2)
本文字数: 3.8k 阅读时长 ≈ 3 分钟
第283场周赛解答
本文字数: 4.9k 阅读时长 ≈ 4 分钟
第73场双周赛解答
本文字数: 5.3k 阅读时长 ≈ 5 分钟