zj_yuneng-CSDN博客

原创【codechef October Challenge 2014】 Stringology is Magic

codechef 真的是太菜了。上面一道水题，14年之后就没人A了。以前A的人都是T的，跑的比我慢到不知道到哪里去了。（还有随便一个全a串就卡成一百多秒的“AC”程序。。。）发个链接：原题地址我的代码：#include <cstdio>#include <cstring>#include <iostream>#include ...

2018-07-28 19:39:40 2836 4

原创欢迎使用CSDN-markdown编欢迎使用Markdown编辑器写博客欢迎使用Markdown编辑器写博客欢迎使用Markdown编辑器写博客欢迎使用Markdown编辑器写博客

欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl

2018-04-19 19:12:06 458 1

转载图论题集收藏

===================以下是最小生成树+并查集======================================【HDU】1198 Farm Irrigation 并查集★（好题）1598 find the most comfortable road 枚举+最小生成树★★1811 Rank of Tetris 并查集+拓扑排序★★3

2017-08-12 17:35:09 1112 3

原创【模板】二叉树的遍历

题目描述：已知一棵二叉树，分别求它的先序编历，中序编历、后庀编历（结点数N输入格式：第一行树结点个数，从第二行开始，每行三个数，第一个数是结点，第二个数是左孩子，第三个数是右孩子输出格式：第一行先序编历，第二行中序编历，第三行后序编历，数与数之间有一个空格样例输入：51 2 32 4 53 0 04 0 0

2017-06-13 08:25:36 530

原创【模板】哈夫曼树构造

题目描述：构造哈夫曼树：给出一列数，构造一棵二叉树，分别以这些点为叶子的权值，使所有叶子的权值和它到树根的距离（边数）的乘积之和为最小。输入格式：第一行一个正整数n第二行n个整数输出格式：所有叶子的权值和它到树根的距离（边数）的乘积之和的最小值样例输入：44 2 7 1样例输出：24数据

2017-06-12 18:03:36 845

原创【模板】树的直径 DP （模板题：XJOI数字转换）

题目描述：如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。输入格式：输入一个正整数n。输出格式：输出最多的步数

2017-06-05 08:35:36 861

原创【模板】最小费用最大流（增广路）（模板题：洛谷P3381）

题目描述如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。输入输出格式输入格式：第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），

2017-05-31 17:25:24 891 3

原创【模板】欧拉函数表

题目描述：输出1~N所有数的欧拉函数。phi（x）=小于n的正整数中与n互质的数的数目。样例输入：5样例输出：1 1 2 2 4数据范围：1#include#define Max 1000001 using namespace std;int euler[Max];int n;void Init(){

2017-05-29 15:44:00 2693

原创【模板】线性筛素数

题目描述：输出1~N的所有质数。样例输入：5样例输出：2 3 5数据范围：2#includeusing namespace std;int prime[1000000];bool f[1000000];int main(){ int n,cnt=0;cin >>n; for (int i=0;i<=n;++i) f[i]=tr

2017-05-29 15:36:03 386

原创【模板】快速幂取模

题目描述：快速幂取模。求a^b mod m的值。样例输入：2 3 5样例输出：3数据范围：1#include #include using namespace std;typedef long long LL;LL quick(LL a,LL b,LL m){ LL d,t;

2017-05-29 15:29:17 279

原创【模板】ISAP网络最大流（模板题：洛谷P3376）

题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。输入输出格式输入格式：第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）输出格式：一行，包含一个正整数，即为该网络的最大流

2017-05-29 15:19:23 377 1

原创【模板】匈牙利算法二分图匹配（模版题：洛谷P3386）

题目背景二分图题目描述给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数输入输出格式输入格式：第一行，n,m,e第二至e+1行，每行两个正整数u,v，表示u,v有一条连边输出格式：共一行，二分图最大匹配输入输出样例输入样例#1：1 1 11 1输出样例#1：1

2017-05-29 15:11:11 849 1

原创【模板】拓扑序列（模版题：XJOI P1064）

题目描述求AOV网的拓扑序列，输出按字典序最小的一个。输入格式第一行二个正整数n（节点数），m（边数）以下m行每行一个整数对描述一条边输出格式AOV网的拓扑序列，按字典序最小的一个样例输入6 8 1 3 2 3 2 4 2 5 3 4 3 6 4 6 5 4样例输出1 2 3 5 4 6#include<iostream>#include<queue>using namespac

2017-05-29 14:53:33 506

原创【模板】Kruskal 最小生成树

题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz输入输出格式输入格式：第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi输出格式：输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

2017-05-27 13:20:47 229

原创【模板】Prim+堆优化最小生成树

题目描述如题，给出一个无向图，求出最小生成树。输入输出格式输入格式：第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi输出格式：输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz输入输出样例

2017-05-27 13:05:46 443

原创【模板】Floyd双源最短路径

题目描述用费洛伊德(Floyed)算法求任意两点最短路径。输入格式：第一行三个整数n,m,q；以下m行每行三个整数a,b,c，表示a，b之间有双向边，且边的权值为c以下ｑ行每行两个整数a,b,表示查询a,b之间的最短距离。样例输入：５　７　２１　２　６１　４　２１　５　２３２　３　４２　４　３３　４　２０３

2017-05-27 10:10:41 1286

原创【模板】Ford单源最短路径

题目描述：用迪杰斯特拉（Dijkstra）算法求单源最短路径，并输出路径（按字典序输出最小的一条）。输入格式：第一行而个整数s，t第二行而个整数n，m以下m行每行三个整数a,b,c，表示a，b之间有边，且边的权值为c样例输入：1 35 71 2 61 4 21 5 23

2017-05-27 08:23:38 297

原创【模板】Spfa单源最短路径

题目描述如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入输出格式输入格式：第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。输出格式：一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点

2017-05-27 08:11:09 544

原创【模板】LCA Tarjan算法（模板题：洛谷P3379）

题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

2017-05-27 07:48:32 730

原创【模板】三分法（模板题：洛谷P3382）

题目描述如题，给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。输入输出格式输入格式：第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示。第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数。输出格式：输出为一行，包含一个实数，即为x的值。四舍五入保留5位小数。

2017-05-27 07:43:30 506

原创【模板】Dijkstra+前向星+堆优化（模板题：洛谷P3371）

题目描述如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入输出格式输入格式：第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。输出格式：一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径

2017-05-26 16:00:05 933

原创【模板】 Dijkstra单源最短路径（模板题：XJOI P1061）

迪杰斯特拉（Dijkstra）法求单源最短路径用迪杰斯特拉（Dijkstra）算法求单源最短路径，并输出路径（按字典序输出最小的一条）。输入格式：第一行而个整数s，t第二行而个整数n，m以下m行每行三个整数a,b,c，表示a，b之间有边，且边的权值为c输出格式：s到t的最短路，并输出路径（按字典序输出最小的一条）。

2017-05-26 15:40:18 1239 1

原创【模板】线段树区间加+乘，区间求和（模板题：洛谷P3373）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.将某区间每一个数乘上x3.求出某区间每一个数的和输入输出格式输入格式：第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表

2017-05-26 15:25:48 531

原创【模板】线段树区间加，区间求和（模板题：P3372线段树1）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1：格式

2017-05-26 15:17:55 245

原创【模板】线段树单点修改，区间求和（模板题：洛谷P3374）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1：格式：1

2017-05-26 15:08:29 317

原创【模板】树状数组区间修改，区间求和（模板题：洛谷P3372线段树1）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1：格式

2017-05-26 14:57:41 489

原创【模板】树状数组区间修改，区间求和（模板题：洛谷P3368树状数组2）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数数加上x2.求出某一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含2或4个整数，表示一个操作，具体如下：操作1：格式：1

2017-05-26 14:50:28 559

原创【模板】树状数组单点修改，区间求和（模板题：洛谷P3374树状数组1）

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1：格式：1

2017-05-26 14:43:49 307 1

原创【模板】Treap （模板题：洛谷P3369普通平衡树）

题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入x数删除x数(若有多个相同的数，因只删除一个)查询x数的排名(若有多个相同的数，因输出最小的排名)查询排名为x的数求x的前驱(前驱定义为小于x，且最大的数)求x的后继(后继定义为大于x，且最小的数)输入输出格式输入格式：第一行为n，表示

2017-05-26 14:20:54 612 3

原创【模板】Splay二叉树排序

题目描述排序（二叉树排序）输入输出格式输入格式：n个数，和一个无序序列。输出格式：输出一行n个数字，表示原始序列排序后的结果输入输出样例输入样例#1：5 3 5 2 1 4输出样例#1：1 2 3 4 5说明N,M

2017-05-26 13:49:16 262 2

原创【模板】Spaly区间翻转（模板题：洛谷P3391文艺平衡树）

题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是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

2017-05-26 13:38:21 385

原创【模板】二叉堆（模板题：洛谷P3378堆）

题目描述如题，初始小根堆为空，我们需要支持以下3种操作：操作1： 1 x 表示将x插入到堆中操作2： 2 输出该小根堆内的最小数操作3： 3 删除该小根堆内的最小数输入输出格式输入格式：第一行包含一个整数N，表示操作的个数接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：操作1： 1 x操作2： 2操作

2017-05-26 13:30:52 280

原创【模板】左偏树（模板题：洛谷P3377左偏树/可并堆）

题目描述如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）输入输出格式输入格式：第一行包含两个

2017-05-26 13:20:44 648

原创【模板】莫队（模板题：洛谷P2009HH的项链）

题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。输入输出格式输入格式：

2017-05-26 13:09:42 223 1

原创【模板】带修改莫队（模板题：洛谷P1903数颜色）

带修改莫队讲解~阅前提示：拥有普通莫队的基础知识；理解莫队的思想；~简介：莫队支持的是离线操作，普通莫队只支持查询操作；而带修改莫队还支持单点修改操作。~原理：普通莫队每一个询问有L，R，ID三个属性；因为只有查询操作，所以改变其查询顺序并不会影响算法的正确性；而加入单点修改后，就不能任意改变顺序，这会影响最终答案；带修改莫队的思路就是在查询中加

2017-05-25 18:38:25 736 5

原创我的第一篇博客

这是2017年5月25日，我在此写下了第一篇博客。

2017-05-25 16:40:55 254

Dance Of Faith