2023省选游记
DAY-1
省选前基本没有复习,都在做其他事情。最后周五晚上开了虚拟机想写点板子,结果也没写动,就写了个 A+B。不过把 NOI Linux 2.0 好好试了试,最后在考试前十个小时发现还是 Code::Blocks 最好用(只有CB有补全)。
DAY1
提早了三刻钟到,站了半个小时,然后在要进考场的时候看到了xpt()。进了考场,老师说 Linux 和 Windows 都可以随便选,四周环视了一圈,都是用 Windows 的,不过我还是用了 Linux。打开 Code::Blocks 的时候没找到哪里调编译选项,调了 5 分钟。
T1 一开始不会做,思考了 x=1x=1x=1 的部分分之后想出来了。期望得分:100分。
T2 图论题,不会做,只会枚举每条边是不是新增的然后判断。复杂度 O(n2m)O(n2^m)O(n2m),期望得分:10分。
T3 背景是一棵树,打一个贪心和一个链的特例,期望得分:36分。
DAY2
T1 不会做,只打了第一个特例。期望得分:20分。
T2 感觉和CF某题很像,打了40分部分分。
T3 完全不会,只能输出1。期望得分:2分。
总期望得分 100+10 ...
拓扑排序
介绍
拓扑排序可以将一个有向无环图(DAG)的节点进行排序,排序后即可依次进行处理,使得排在前面的节点不能依赖于排在后面的节点,这样就可以满足 DP 的无后效性,进行 DP 求解某些问题。
Kahn 算法
Kahn 算法的步骤如下:
从图中入度为 0 的节点的集合中任取一个,并加入拓扑序;
删除该顶点和所有与其相连边;
重复 1-2 步,直到图中没有入度为 0 的节点。若此时图中还有边,说明图中有环。
如以下伪代码:
\begin{algorithm}
\caption{Kahn's Algorithm}
\begin{algorithmic}
\STATE $ L \leftarrow $ Empty list that will contain the sorted elements
\STATE $ S \leftarrow $ Set of all nodes with no incoming edge
\WHILE{$S$ \textrm{is not empty}}
\STATE remove a node $n$ from $S$
\STATE ...
字符串与正则
字符串
python 中,字符串(str)是一种不可变的序列结构。
字符串创建
定义字符串的方法有以下几种:
单引号、双引号
在 python 中,单双引号是完全等价的,在某些语言中,可能会区分字符和字符串,但在 python 中,字符就是长度为 1 的字符串。
12str1 = "Hello, world!"str2 = '114.514'
三引号
使用三个双引号或单引号可以创建多行字符串。三引号允许一个字符串跨多行,字符串中可以包含换行符、制表符以及其他特殊字符。
123mstr = """line1,line2,line3!"""
字符串转义
使用反斜杠可以转义字符。
转义字符
描述
ASCII码
\’
单引号
39
\"
双引号
34
\\
反斜杠
92
\n
换行
10
\t
制表符
9
123str1 = "line1\nline2"str2 = "He said, \"H ...
字典补充
字典回顾
在Python中,字典是一个无序的、可变的数据类型,用于存储键(keys)和值(values)之间的映射关系。字典使用键来访问数据,与列表不同,不是使用索引来访问数据。
字典的主要特点包括:
字典由一系列键(keys)和值(values)组成,每个键映射一个值。
字典中的键必须是 不可变 对象,如字符串、数字、元组等,而值可以是任意对象。
字典是无序的,不支持索引,可以通过键查找值。
字典使用大括号{}来表示,每个键值对之间用逗号分隔。
字典是可变的,可以添加、删除、修改键值对。
字典长度可以使用内置的len()函数来计算,即键值对的个数。
字典操作
创建字典
12345#创建一个空字典my_dict = {}#带键值对的字典my_dict = {'name': 'John', 'age': 25, 'city': 'New York'}
访问字典的值
12my_dict['name'] #输出 ...
树链剖分
本篇文章中,存树的方式统一采用链式前向星。
链式前向星实现
12345678910int head[N];int nxt[N<<1],to[N<<1];int cnt=1;void add_edge(int u,int v){ nxt[cnt] = head[u]; to[cnt]=v; head[u]=cnt; cnt++;}
树链剖分的概念
将一棵树分割为若干条链,将维护路径问题转化为维护若干条链上信息。
我们介绍一种分割方式——重链剖分。
重链剖分可以将树上任意一条路径分割为 O(logn)O(\log n)O(logn) 条连续的链,每条链上 dfs 序连续,因此可以采用线段树等维护路径上的信息。
对于重链剖分,给出一些定义:
重子节点:子结点中子树最大的节点。若有多个最大的,任意其一为重子节点。
轻子节点:剩余的子节点
重边:到重子节点的边
重链:若干条重边首尾相连形成重链。特别的,对于单个子节点,也认为是一条重链。
这样即可将整棵树划分为若干条重链。
实现
重链剖分通过两次 dfs 实现。
第一次 ...
网络流初步(2)—— 最小割
最小割
最小割问题可以简单的这样描述:给定一张带权有向图,除去几条边,使 sss 到 ttt 不连通。求去除的边的权值和最小值。
形式化定义一下:对于图 G=(V,E)G=(V,E)G=(V,E),将点划分为 SSS 和 T=V−ST=V-ST=V−S 两个集合,其中源点 s∈Ss\in Ss∈S,汇点 t∈Tt\in Tt∈T。我们定义割 (S,T)(S,T)(S,T) 的容量为所有从 SSS 到 TTT 的边的容量之和,即 c(S,T)=∑u∈S,v∈Tc(u,v)c(S,T)=\sum_{u\in S,v\in T}c(u,v)c(S,T)=∑u∈S,v∈Tc(u,v),最小割问题就是求一个割,使得割的容量 c(S,T)c(S,T)c(S,T) 最小。
最大流最小割定理
最大流最小割定理:f(s,t)max=c(s,t)minf(s,t)_{\max}=c(s,t)_{\min}f(s,t)max=c(s,t)min。
即对于一个网络,其最大流与最小割在数值上相等。我们在处理最小割问题时,直接求最大流即可。
求割边数
洛谷P1344 [USACO4.4]追查坏牛奶Pol ...
网络流初步 —— 最大流算法
概念定义
网络:带权有向图 G=(V,E)G=(V,E)G=(V,E)。
容量:边 (u,v)∈E(u,v)\in E(u,v)∈E 的权值,记作 c(u,v)c(u,v)c(u,v)。
源点、汇点: s∈v,t∈v,(s≠t)s\in v , t \in v ,(s\neq t)s∈v,t∈v,(s=t)。
流量:设 f(u,v)f(u,v)f(u,v) 满足
容量限制:对每条边流量不超过容量,即f(u,v)≤c(u,v)f(u,v)\le c(u,v)f(u,v)≤c(u,v)
斜对称性:每条边容量与其相反边容量为0,即f(u,v)=−f(v,u)f(u,v)=-f(v,u)f(u,v)=−f(v,u)
流守恒性:除源点和汇点,流入每个点的流量与流出每个点的容量相同,即
∀x∈V−{s,t},∑(u,v)∈Ef(u,x)=∑(u,v)∈Ef(x,v)\forall x \in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(u,v)\in E}f(x,v)
∀x∈V−{s,t},(u,v)∈E∑f(u,x)=(u,v ...
IOI2022 D2T1 数字电路
题目链接-UOJ760
题意
给定一颗有根树,有 nnn 个非叶子节点和 mmm 个叶子节点,000 为根。叶子节点编号为 n,…,n+m−1n,\dots,n+m-1n,…,n+m−1。
叶子节点有一个 {0,1}\{0,1\}{0,1} 中的权值。
对于非叶子节点,权值由如下步骤确定:
对于节点 uuu,设其儿子节点数量为 cuc_ucu,则任取该节点参数 lu∈[1,cu]l_u\in[1,c_u]lu∈[1,cu]。
若 uuu 的儿子节点权值为 111 的个数大于 lul_ulu ,则其权值为 111,否则为 000。
现在有 qqq 次修改,每次给定区间 [l,r][l,r][l,r],反转编号在 [l,r][l,r][l,r] 中的叶子节点的权值(异或 111)。 求出有多少种确定每个非叶子节点参数方式,使根节点的权值为 111。答案对 109+202210^9+2022109+2022 取模。
分析
考虑非叶子节点 uuu,设有 xxx 个儿子权值为 111,yyy 个儿子权值为 000。那么,参数 lul_ulu 在 [1,x][1,x][1,x] 范围 ...
树形数据结构及其应用(2)
前文我们讲了树状数组与线段树基本的实现,本文我们讲线段树的一些优化。
动态开点线段树
我们知道,如果使用二叉树实现,需要给线段树开大小为 4n4n4n 的数组。为了节省空间,我们可以不一次性建好树,而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时,才建立代表这个区间的子结点。我们用ls和rs记录儿子的编号。(结点只有在需要的时候才被创建)
时间复杂度仍为 O(logn)O(\log n)O(logn)
经过 mmm 次操作后,节点的数量规模为 O(mlogn)O(m\log n)O(mlogn),并且最多也只会创建 2n−12n-12n−1 个节点,没有浪费。
区间修改
12345678910111213void modify(int& o,int l,int r){ if(!o)o=++cnt; if(ql<=l&&r<=qr){ t[o] += qk*(r-l+1); add[o] += qk; return; } pushdow ...
树形数据结构及其应用
树状数组
一种简单的数据结构。可以做到 O(logn)O(\log n)O(logn) 单点修改,O(logn)O(\log n)O(logn) 区间查询。
维护差分数组可做到 O(logn)O(\log n)O(logn) 区间修改,O(logn)O(\log n)O(logn) 单点查询。
每个元素管理的区间为[i-lowbit(i)+1,i],lowbit为二进制数的最低位1以及之后的0所组成的数。
123int lowbit(int x){ return x&(-x);}
在补码规则下,x的相反数的二进制表示为~x+1,对x取反后+1,把末尾的0(取反为了1)全部进位到了最低位1的位置,进行位与后得到的便是最低位。
洛谷P3374 【模板】树状数组 1
1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;#define ll long longco ...