标签 - 模板

? 解题记录 ? ? 模板 ? ? 排序 ?    2024-03-26 17:49:23    2    0    0
看到网上有许多快速排序和快速选择的代码,但是相当一部分都有些错误,这里放一下自己的写法 快速排序模板题:https://www.luogu.com.cn/problem/P1177 快速选择模板题:https://vjudge.net/problem/POJ-2388 #include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int maxn = 1e6 + 5;int n, a[maxn];void kth_element(int * l,
? 解题记录 ? ? 模板 ? ? 动态规划 ? ? 树链剖分 ?    2018-12-10 11:15:59    630    0    0
题目描述给定一棵n个点的树,点带点权。 有m次操作,每次操作给定x,y,表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式:   第一行,n,m,分别代表点数和操作数。 第二行,V1​,V2​,...,Vn​,代表nn个点的权值。 接下来n−1行,x,y,描述这棵树的n−1条边。 接下来m行,x,y,修改点x的权值为y。   输出格式:   对于每个操作输出一行一个整数,代表这次操作后的树上最大权独立集。 保证答案在int范围内   输入输出样例输入样例#1: 复制10 10 -11 80
? 解题记录 ? ? AC自动机 ? ? 洛谷 ? ? 模板 ?    2018-04-04 17:05:09    528    0    0
题目背景这是一道简单的AC自动机模板题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意 题目描述给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。 输入输出格式输入格式:   第一行一个n,表示模式串个数; 下面n行每行一个模式串; 下面一行一个文本串。   输出格式:   一个数表示答案   输入输出样例输入样例#1: 复制2 a aa aa 输出样例#1: 复制2 说明subtask1[50pts
? 解题记录 ? ? 洛谷 ? ? 模板 ? ? FFT|NTT ?    2017-12-16 20:49:50    574    0    0
题目描述给出两个n位10进制整数x和y,你需要计算x*y。 输入输出格式输入格式:   第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。   输出格式:   输出一行,即x*y的结果。(注意判断前导0)   输入输出样例输入样例#1: 复制1 3 4 输出样例#1: 复制12 说明数据范围: n<=60000 来源:bzoj2179 本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。 寻找了很久,最终还是发现算法导论的FFT讲解的是最详细的,前置技能:复数四则运算,矩阵
? 解题记录 ? ? 洛谷 ? ? Splay ? ? Treap ? ? 模板 ? ? 平衡树 ?    2017-11-22 23:30:14    484    0    0
题目背景这是一道经典的Splay模板题——文艺平衡树。 题目描述您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1 输入输出格式输入格式:  第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n   输出格式:  输出一行n个数字,表示原始序列经过m次变换后的结果   输入输出样例
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 分块 ? ? Splay ? ? 模板 ? ? 平衡树 ?    2017-10-24 19:21:49    745    0    0
题目描述如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式输入格式:   第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k 操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和   输出格式:   输出包含若干行整数,即为所有操作2的结果。   输入输出样例输入样例
题目描述如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式输入格式:   第一行包含4个正整数N、M、R、P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。 接下来一行包含N个非负整数,分别依次
? 解题记录 ? ? 洛谷 ? ? 哈希 ? ? 模板 ?    2017-09-16 15:46:05    484    0    0
题目描述如题,给定N个字符串(第i个字符串长度为Mi,字符串内包含数字、大小写字母,大小写敏感),请求出N个字符串中共有多少个不同的字符串。 友情提醒:如果真的想好好练习哈希的话,请自觉,否则请右转PJ试炼场:)输入输出格式输入格式:   第一行包含一个整数N,为字符串的个数。 接下来N行每行包含一个字符串,为所提供的字符串。   输出格式:   输出包含一行,包含一个整数,为不同的字符串个数。   输入输出样例输入样例#1:5 abc aaaa abc abcc 12345 输出样例#1:4 说明时空限制:1000ms,128M 数据规模: 对于30
? 解题记录 ? ? 洛谷 ? ? 树状数组 ? ? 差分 ? ? 模板 ?    2017-09-09 21:08:49    855    0    0
题目描述如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数数加上x 2.求出某一个数的和 输入输出格式输入格式:   第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含2或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k 操作2: 格式:2 x 含义:输出第x个数的值   输出格式:   输出包含若干行整数,即为所有操作2的结果。   输入输出样例输入样例#1:5 5
? 解题记录 ? ? 洛谷 ? ? 可持久化数据结构 ? ? 线段树 ? ? 模板 ?    2017-09-09 19:23:12    442    0    0
题目背景这是个非常经典的主席树入门题——静态区间第K小 数据已经过加强,请使用主席树。同时请注意常数优化 题目描述如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。 输入输出格式输入格式:   第一行包含两个正整数N、M,分别表示序列的长度和查询的个数。 第二行包含N个正整数,表示这个序列各项的数字。 接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r]内的第k小值。   输出格式:   输出包含k行,每行1个正整数,依次表示每一次查询的结果   输入输出样例输入样例#1:5&nbs