【OI考古】图论 | 最近公共祖先 LCA
最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。
以人的肉眼看来,一棵树上任意两点的 LCA 位置是显然的,然而对于计算机来说,最朴素的算法便是遍历整棵树来寻找 LCA,当询问次数很多的时候,朴素算法的效率将非常低下。本文将介绍几种常见的快速求解 LCA 的算法。
模板题:洛谷 P3379 | [模板] 最近公共祖先(LCA)
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,SN,M,SN,M,S ,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N−1N-1N−1 行每行包含两个正整数 x,yx, yx,y ,表示 xxx 结点和 yyy 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 MMM 行每行包含两个正整数 a,ba, ba,b ,表示询问 aaa 结点和 bbb 结点的最近公共祖先。
输出格式
输出包含 MMM 行,每行包含一个正整数,依次为每一个询问的结果。
输入输出样例
输入 #1
123 ...
【OI考古】数据结构 | 线段树
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 nlognn\log_{}{n}nlogn 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。
线段树维护的信息,需要满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用懒惰标记时,标记也要满足可加性(例如取模就不满足可加性,对 333 取模然后对 444 取模,两个操作就不能合并在一起做)。
加法线段树
模板题:洛谷 P3372 | [模板] 线段树 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
将某区间每一个数加上 kkk 。
求出某区间每一个数的和。
输入格式
第一行包含两个整数 n,mn, mn,m 分别表示该数列数字的个数和操作的总个数。
第二行包含 nnn 个用空格分隔的整数,其中第 iii 个数字表示数列第 iii 项的初始值。
接下来 mmm 行每行包含 333 或 444 个整数,表示一个操作,具体如下:
1 x y k:将区间 [x,y][x, y][x,y] 内每个数加上 kkk 。
2 x y:输出区间 [x, ...
【Codeforces】 题解 - Round 707 (Div.2)
本文合作者:laybxc
赛事信息
名称
出题人
开始时间
时长
官方题解
Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)
4qqqqAkulyatAleks5dDebNatkhEndagorionGlebsHPKiKoSNebuchadnezzarNiceClockSiberianZloboberalexX512biectioncdkrotch_egorgrphilisaf27ismagilov.codemeshanyavintage_Vlad_Makeevvoidmaxwrg0ababd
Mar/13/202117:05 (UTC+8)
02:30
Codeforces Round #707 Editorial
A. Alexey and Train
题目
题目描述
从时间0开始出发,要依次经过在一条直线上的 nnn 个站点,问到达站点n的时间。
每个站点 iii 都有对应的时间 ai,bi,tia_i,b_i,t_iai,bi,ti
从站点 i−1i ...
在Windows下编写C++对拍程序(真随机数)
对拍,即将相同的数据输入两个不同程序,比对其输出结果。可以用于在ACM/OI等比赛中用暴力算法检测标算的正确性,寻找使程序出错的样例数据。
随机数生成器
要编写好用的对拍程序,首要的是要编写一个随机数生成器,便于产生多样化的数据。
朴素随机数生成器
相信很多人都见过下面这种写法:
1234567891011121314151617181920//DataGenerator_naive.cpp#include <iostream>#include <cstdio>#include <ctime>using namespace std;int main(int argc, char *argv[]){ int seed = time(NULL); srand(seed); //以下代码可以生成10个随机整数 int n = 10; for (int i = 1; i <= n; i++) { printf("%d ", rand()); } retu ...
【Codeforces】 题解 - Round 706 (Div.2)
本文合作者:laybxc
赛事信息
名称
出题人
开始时间
时长
官方题解
Codeforces Round #706 (Div. 2)
Daniel_yuanImakfsmg23333waaitg
Mar/10/202120:05 (UTC+8)
02:00
Tutorial (en)
A. Split it!
题目
题目描述
给出一个长度为 nnn 的字符串 sss 和一个整数 kkk ,问其能否划分为如下形式:
s=a1+a2+⋯+ak+ak+1+R(ak)+R(ak−1)+⋯+R(a1)s=a_1+a_2+\dots+a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\dots+R(a_1)s=a1+a2+⋯+ak+ak+1+R(ak)+R(ak−1)+⋯+R(a1)
其中, R(x)R(x)R(x) 表示将 xxx 反转得到的字符串。
输入格式
第一行是一个整数 t(1≤t≤100)t(1≤t≤100)t(1≤t≤100) ,表示数据组数。
每组数据第一行有两个整数 n,k(1≤n≤100,0≤k≤⌊n2⌋)n,k(1≤n≤100, ...
【Codeforces】 题解 - Round 705 (Div.2)
本文合作者:laybxc
赛事信息
名称
出题人
开始时间
时长
官方题解
Codeforces Round #705 (Div. 2)
74TrAkToRAlFlen
Mar/06/202122:05 (UTC+8)
02:15
Tutorial
A. Anti-knapsack
题目
题目描述
给定 n,kn,kn,k ,请选择 1−n1-n1−n 的若干个整数,使得这些整数的和的子集都不等于 kkk ,问最多能选出几个整数且分别是多少。
输入格式
第一行是一个整数 t(1≤t≤100)t(1≤t≤100)t(1≤t≤100) ,表示数据组数。
每组数据有两个整数 n,k(1≤k≤n≤1000)n,k(1≤k≤n≤1000)n,k(1≤k≤n≤1000)
输出格式
对于每组数据
第一行输出一个整数 mmm ,表示最多能选出的整数数量。
第二行输出这些选出的整数,顺序任意。
解决方案:
思路:
显然对 i∈[1,n]i ∈[1,n]i∈[1,n] , i>ki>ki>k 时 iii 这个数肯定可以直接选
i=ki=ki=k 显然不行
...
【OI考古】动态规划 | 动态规划基础
动态规划(Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。
最长上升子序列(LIS)
给出一个序列 a1,a2,...,an−1,ana_1, a_2, ...,a_{n-1}, a_na1,a2,...,an−1,an ,求其最长不下降(或上升)子序列。
求最长上升子序列(LIS)的算法是Yukko介绍给我的第一个算法。
解决方案( O(n2)O(n^2)O(n2) )
状态设计:
dp[i]dp[i]dp[i] 表示以第 iii 个数结尾的最长上升子序列的最长长度。
状态转移方程:
dp[i]=max(dp[j])+1(1≤j<i,且a[i]>a[j])dp[i]= max(dp[j])+1 \quad (1≤j<i, 且a[i]>a[j])dp[i]=max(dp[j])+1(1≤j<i,且a[i]>a[j])
1234567891 ...
【OI考古】图论 | 最短路算法
解决单源最短路径问题的几种算法,是Yukko最早给我介绍的几类算法之一。
最短路算法的基本功能,是求解带边权的有向或无向图中任意两点之间最短或最长的路径及其距离。
模板题:洛谷 P4779 | [模板]单源最短路径(标准版)
题目描述
给定一个 nnn 个点, mmm 条有向边的带非负权图,请你计算从 sss 出发,到每个点的距离。
数据保证你能从 sss 出发到任意点。
输入格式
第一行为三个正整数 n,m,sn, m, sn,m,s 。 第二行起 mmm 行,每行三个非负整数 ui,vi,wiu_i, v_i, w_iui,vi,wi ,表示从 uiu_iui 到 viv_ivi 有一条权值为 wiw_iwi 的有向边。
输出格式
输出一行 nnn 个空格分隔的非负整数,表示 sss 到每个点的距离。
输入输出样例
输入 #1
12345674 6 11 2 22 3 22 4 11 3 53 4 31 4 4
输出 #1
10 2 4 3
说明/提示
1≤n≤1051≤n≤10^51≤n≤105 ;
1≤m≤2×1051 \leq m \leq 2\times 10^ ...
CS231n | 课程作业 Assignment1 | K近邻算法 KNN
KKK 近邻算法(k-Nearest Neighbor)是CS231n课程介绍的第一个算法,此算法和神经网络没有任何关系,实际中也极少使用,但学习使用KNN算法可以获得对图像分类方法的基本认知。
先决条件
在开始写作业前,你需要做一些准备工作。
Jupyter Notebook先决条件
你可以在这里下载官方提供的CS231n Assignment1的 Jupyter笔记本。
在Anaconda Prompt Powershell中输入conda activate cs231,接着cd到assignment1目录下,输入jupyter notebook开启Ipython笔记本,打开knn.ipynb即可开始本次作业。
在开始之前,需要注意,由于Jupyter Notebook的某种bug,CIFAR-10的路径变量cifar10_dir需要赋值为绝对路径,同时在路径前加上r来忽略转义,像下面这样:
12# Load the raw CIFAR-10 data.cifar10_dir = r'D:\Users\VonBrank\Documents\GitHub\code-lear ...
【OI考古】数论基础 | 快速幂、最大公约数、线性筛素数
介绍几种入门级的数论算法