- 博客(49)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 C++学习笔记：图论——拆点详解
引言拆点，玄学的东西，你值的拥有。。。详解拆点就是将一个图里的边权全部化为 1 ，就要将每一个点拆解为几个点，每个拆解后的点的边权为 1一个图的邻接矩阵其中最大的边权为 3则每一个点拆分为 i.1 ， i.2 ， i.3 的分点分点先与自己相邻的分点相连，但要把 i.1 看为原来的点即 1.1 与 1.2 连1.2 与 1.3 连拆完后的图...
2019-04-17 13:34:32
3592
2
原创 C++解题报告：电话网络——巧用树形DP
电话网络题目描述Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N顺次编号。 所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N;1 ...
2019-03-07 16:51:22
649
1
原创 C++ 数论知识总结
引言数论大法好，人间真善美。。。数论模板一. 判定质数二. 欧拉筛法三. 欧拉函数方法一方法二四. 二元一次不定方程五. 矩阵乘法六. 快速幂七. 中国剩余定理八.中国剩余定理Pro练习题一. 判定质数for(int i = 2 ; i * i <= n ; ++ｉ) ｛ if( n % i == 0 ) ...
2019-02-28 13:23:35
2415
1
原创 C++图论提高——The Unique MST （最小生成树 Kruskal算法）
题目描述（传送门）给定连接的无向图，告诉它的最小生成树是否唯一。定义1（生成树）：考虑连通的无向图G =（V，E）。G的生成树是G的子图，比如T =（V'，E'），具有以下属性：1.V'= V.2.T是连通的和非循环的。定义2（最小生成树）：考虑边加权，连通，无向图G =（V，E）。G的最小生成树T =（V，E'）是总成本最小的生成树。T的总成本是指E'中所有边缘的权重之和。...
2019-01-29 20:35:05
670
1
原创 C++解题报告：邮局（IOI 2000）—— 如何用平行四边形不等式巧妙优化DP
目录题目描述题目解析思路详解代码邮局传送门题目描述高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。你要编写一个程序，已知村庄的位置和邮...
2019-01-02 15:05:11
1007
1
原创 重新开始 杂类：C++基础
是一个作用域解析运算符，用于指定某个名字的声明或定义在哪个作用域内。两者有一个为true则结果为true，否则为false;i++ 即后加加，原理是：先自增，然后返回自增之前的值。++i 即前加加，原理是：先自增，然后返回自增之后的值。两者全部为true则结果为true，否则为false;（2）scanf("%数据类型"，&变量名称 )；printf("%数据类型"， 变量名称 )；两者相同为false，不同为true；0和任何数^，结果为其本身；任何数和自身^，结果为0。表示函数返回的值的类型是。
2023-09-02 14:37:44
609
原创 树链剖分模板
DFS1void DFS1( int x , int f , int deep ) { fa[x] = f ; dep[x] = deep ; Size[x] = 1 ; for( int i = 0 ; i < G[x].size() ; ++ i ) { int s = G[x][i] ; if( s == f ) continue; DFS1( s,x...
2019-11-14 21:52:55
160
原创 [NOI2015]软件包管理器 —— 树链剖分
题目描述Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。...
2019-10-24 13:15:33
255
原创 C++解题报告：Tokitsukaze, CSL and Stone Game[ COCI ] —— 博弈论
题目描述Irressey与yurzhang在玩一个取石子的游戏一开始，他们面前有nn堆石子，第ii堆石子有a_iai颗石头，他们轮流取石子（Irressey先取）。每一次，取石子的人会选中一个非空的石子堆并取走其中的一颗石子。如果在某个人的回合前所有的石子堆都是空的，或者在他取完后有两堆的石子数量相同（两堆都没有石子也算），则他输掉游戏。如果lrressey胜利，输出sjfnb；如...
2019-08-16 21:31:22
403
2
原创 C++解题报告：连续的“包含”子串长度——（线段树+尺取法）
题目描述区间查询和修改给定N,K,M（N个整数序列，范围1~K，M次查询或修改）如果是修改，则输入三个数，第一个数为1代表修改，第二个数为将N个数中第i个数做修改，第三个数为修改成这个数(例如1 3 5就是修改数组中第3个数，使之变为5)如果是查询，则输入一个数2，查询N个数中包含1~K每一个数的最短连续子序列的长度输入格式第一行包含整数N、K和M（1 ≤ N,M ≤ 1...
2019-07-25 15:17:19
276
1
原创 C++解题报告—— 烽火传递（单调队列优化DP）
题目描述烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。在某两个城市之间有座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续个烽火台中至少要有一个发出信号。现在输入和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。输入格式第一行是，表示个烽火台和连续烽火台数；第二...
2019-07-19 17:29:59
800
1
原创 C++解题报告——Ronald（理论+图搜索）
题目描述一个国家有n个城市，城市之间连接着双向航空线路。一位疯狂的航空公司总裁Ronald Krump经常改变航班时刻表。更准确地说，他每天都做以下事情：●选择其中一个城市●如果该城市和某个其他城市之间之前没有航线那么在这两个城市之间创建一条航线，如果该城市和某个其他城市之间之前已有航线那么取消这条航线例如，如果从城市5有航线通往城市1和2，但没有航线通往城市3和4，那么在Kru...
2019-07-18 20:52:08
592
1
原创 C++学习笔记——解析莫队算法
引言集训队队长莫涛 and 提莫队长 are coming ......莫队算法相传是国家集训队队长莫涛在一次比赛中想出的算法，所以称作莫队算法（提莫队长？？），类似于暴力维护，但却非常巧妙，而且据说是可以对区间进行各种操作,几乎万能哎，还有各种改进版本，如带改莫队，树上莫队 and so on算法思想基本思想我们先想象出两个指针curL和curR，以及我们要查询的区间...
2019-07-18 10:59:55
886
1
原创 C++解题报告——Kas（动态规划）
题目描述Kile和Pogi在街上捡到了N张钞票。在确定无法找到失主之后，两人决定将钞票平分。他们想要得到相同数量的钱，所以他们将这些钞票尽可能分成价值相等的两份。但是当钞票无法平分的时候会剩下一些。由于他们不能将剩余的钞票留在街上，他们决定去附近的赌场并将所有剩下的钞票都押上，希望最终得到两倍的赌注。幸运的是他们真的让赌注翻倍了，于是Kile和Pogi平分了赢的钱。由于极度兴奋，他们...
2019-07-17 15:01:20
759
1
原创 C++解题报告——Rima（字典树+树形DP）
题目描述Adrian对单词押韵很感兴趣。如果两个单词的最长公共后缀的长度与两个单词中较长那个的长度一样，或者等于较长单词的长度减一，则这两个单词押韵。换句话说，如果A,B的最长公共后缀LCS（A，B）≥max（|A|，|B|）-1，则A和B押韵。有一天，在阅读一套短篇小说时，他决定创造出能够使每两个相邻单词押韵的最长的单词序列，序列中的每个单词只能出现一次。但是Adrian已经厌倦了这个...
2019-07-17 12:18:17
287
1
原创 浅论 欧拉路径&欧拉回路
欧拉路径废话不扯，直接先了解一下定义如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)这需要跟哈密顿路区别一下，前者是边，后者是点如果一个图中存在具有欧拉路径但不具有欧拉回路则称为半欧拉图那么该如何求图中的欧拉路径呢分类讨论一下对于无向图无向图中，一条欧拉路径上有且仅有两个度数为奇数的点（其他点度数都是偶数），这两个点就是这条欧...
2019-07-12 20:32:44
313
原创 C++解题报告：病毒(virus)——拓扑排序
题目描述有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替...
2019-07-10 11:33:43
2317
原创 C++学习笔记：图论——缩点详解
引言缩点，哲学的东西，你必须拥有。。。缩点个人认为就是把一堆强连通的点( 即强连通分量 )，认作为一个点强连通分量就是这里面的点可以相互到达（算是个环）详解一个有向图如下可以看出有强连通分量 { 1 , 2 } , { 8 , 4 , 9 } ， { 7 } , { 6 } , { 3 } , { 5 }先走一波Tarjan，求出强连通分量用一个 c...
2019-06-26 13:50:53
4631
1
原创 C++解题报告：抢掠计划 [ APIO 2009 ] 解析
题目描述Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终...
2019-06-25 14:11:39
464
原创 C++学习笔记：Tarjan算法剖析——求 强连通分量，割点，割边，点双连通分量，边双连通分量 的详解
Tarjan算法详解目录1.Tarjan算法求强连通分量2. Tarjan算法求割点3. Tarjan算法求点双连通分量4. Tarjan算法求割边5.Tarjan算法求边双连通分量1.Tarjan算法求强连通分量了解一下 强连通分量对于一个有向图的DFS的搜索树（i 可以到 j，j 不一定能到 i），如下里面的强连通分量有 { 6 ， 7 ， 8 }...
2019-06-06 14:18:56
3890
3
原创 C++学习笔记：有向图的强连通分量
强连通图分量首先得知道这是个什么玩意儿，对于一个如下的有向图在这个有向图G中，如果有两个点可以相互到达，则两点为强连通，若图中每个点都可以相互到达，则图G为强连通图1. 一个有向图是强连通的，而且仅当G中有一条回路，它至少包含每个点一次2. 非强连通图的极大强连通子图，称为强连通分量，孤立的点也是一个强连通分量（copy课件不解释）实现方法1. Kosar...
2019-05-31 13:55:33
2452
1
原创 C++解题报告：Find the hotel 详解（RMQ）
引言最值查询RMQ，信手拈得俱天成题目描述夏天了!弗林准备再来一次。由于旅游需要三天或更多的时间，所以找到一家价格合理、离目的地尽可能近的酒店是很重要的!但是有这么多! 弗林累了，找不到。现在是你的时间了!给定hi酒店的，其中pi代表价格，di代表从旅游目的地到目的地的距离，你会发现这些酒店，要么价格更低，要么距离更短。以酒店h1为例，如果有一个酒店h1，价格和距离都较低，我们将丢弃h...
2019-05-29 14:02:08
520
原创 C++解题报告：[USACO07JAN]Balanced Lineup —— RMQ快速求解
引言最值查询RMQ，信手拈得俱天成题目描述每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 200,000) 个可能的牛的选择和所有牛的身...
2019-05-29 13:26:09
372
原创 浅析RMQ问题 + 练习题总结（区间最值查询）
引言最值查询RMQ，信手拈得俱天成（方便自己copy模板。。。）RMQ概念就是在一个给定的区间（不能修改）内，求任意 left 到 right 的这子区间内的最大值，对于这种问题，一般会用线段树或者ST表解决，但如果这个查询的次数极大，线段树就会显得乏力，所以就了解一下ST表的求解。求解思路用ST表求解这类问题，起建表时间O(n*log(n))查询时间O(1) ，速度挺不...
2019-05-24 14:14:46
531
原创 C++解题报告：详解经典搜索难题——八数码问题（ 双向BFS & A* 求解）
引言AC这道八数码问题，你和楼教主就是兄弟了。。。题目描述在一个3*3的九宫格棋盘里，放有8个数码，数码的数字分别是1~8。棋盘中还有一个位置是空着的，用0表示。可以通过在九宫格里平移数码来改变状态(即空格位在九宫格内能上下左右移动)。数码在任何情况下都不能离开棋盘。给出8个数码的初始状态（没放数码的空格用0表示）和目标状态，问从初始状态到目标状态，最少需要经过多少次移动操作。 例如...
2019-05-14 13:20:30
2099
1
原创 C++学习笔记：浅析匈牙利算法
引言匈牙利算法在手，孟非都为你亮灯。二分图&最大匹配在学习匈牙利算法之前，要先了解二分图二分图又称作二部图，是图论中的一种特殊模型。设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。感性理解：两个互不相交的子集就像男生和女生，男女有别。。。然后就是最大匹配给定一个...
2019-04-29 14:11:22
879
原创 C++迭代加深——Addition Chains（ZOJ 1937）详解
引言茕茕孑立，迭代加深。。。题目描述Addition Chains已知一个数列（其中）。对于每个，需要满足（，这里与可以相等）。现给定的值，要求的最小值（并不要求输出），及这个数列每一项的值（可能存在多个数列，只输出任一个满足条件的就可以了）。输入格式多组数据，每行给定一个正整数。输入以结束。输出格式对于每组数据，输出满足...
2019-04-26 14:22:44
617
原创 C++图论——最小生成树
板题——最优布线问题题目描述学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们中间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接...
2019-04-24 13:31:00
539
原创 C++解题报告：迷路[SCOI2009]——巧妙运用加速矩阵快速求解
引言好题一道，恶心到爆。。。迷路题目描述windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。输入输出格式输入格式：第一行包含两个整数，N T。 接下来有 ...
2019-04-16 13:52:19
623
原创 剑指offer.C++数论 gcd 巧解——运用 欧式筛法&欧拉函数 快速求解
前言数论大法好，人间真善美。。。题目描述给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对（x,y）有多少对？输入一个整数1<=N<=1000000输出一个整数样例输入4样例输出4提示【样例解释】(2,2),(2,4),(3,3),(4,2)思路拿到这道题很容易想到暴搜，但数据范围很大，所以就要...
2019-04-09 14:22:59
412
原创 浅析中国剩余定理（CRT）
中国剩余定理用来求解同余方程组的最小非负整数解，其中都互质 首先让 M 等于所有的最小公倍数，对于求解每一个的方程先设一个，再求解其逆元则会有一组最小解其通解就是如果没有看懂，可以看详细求解同余方程这一篇博客代码数论大法好，人间真善美。。。#include <iostream>#include <cstdio...
2019-04-03 13:33:12
1007
原创 剑指offer.C++ 浅析BSGS算法
前言数论大法好，人间真善美。。。BSGS算法一般用来求解成立的最小的L的解对于求解这道题，要先进行分解设 L = i * x - y ，就得到，即再移项然后就是循环一遍 y 的值，将其存入HASH表中在循环枚举 i ，求解出第一个满足这个式子的值就是最小值 ans = i * x - y板题Discrete Logging代码数...
2019-03-26 14:01:02
406
原创 C++ 数论学习 质因数分解 —— 无关的元素
引言数论大法好，人间真善美。。。题目题目描述对于给定的n个数a1，a2，...，an，依次求出相邻两数之和，将得到一个新数列。重复上述操作，最后结果将变成一个数。问这个数除以m的余数与哪些数无关？例如n=3，m=2时，第一次求和得到a1+a2，a2+a3，再次求和得到a1+2a2+a3，它除以2的余数和a2无关。输入第1行：2个整数n和m（1<=n<...
2019-03-20 13:18:25
440
原创 C++ 树形DP经典例题详解——二叉苹果树
引言这是十分经典的树形DP题，其转移方程很好想到，但有一些坑要注意题目描述有一棵苹果树，如果树枝有分叉，一定是分 2 叉（就是说没有只有 1 个儿子的结点）。这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是 1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树：现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果...
2019-03-14 16:48:07
1310
原创 C++ 树形DP入门题详解——树的最大独立集
树的最大独立集题目描述对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。输入第1行：1个整数N(1 <= N <= 6000)，表示树的结点个数，树中结点的编号从1..N接下来N-1行，每行2个整数u，v，表示树中的一条边连接结点u和v输出第1行：1个整数，表示最大独立集的结点个数样例输入Copy(如果...
2019-03-06 13:35:20
829
原创 C++ [NOIP2002]选数题解——简单数论与DFS的运用
问题 F(1413): [NOIP2002]选数时间限制:1 Sec内存限制:64 MB题目描述已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为： 3+7+12=22 3+7+19＝29 7+12+19＝38...
2019-03-01 14:23:40
960
2
原创 C++ 二元一次不定方程巧妙求解——运用扩展欧几里得算法
前言在关于数论的学习中，求解二元一次不定方程是很重要的，在学习求解二元一次不定方程之前，要先了解欧几里得算法和扩展欧几里得算法。关于数论的学习欧几里得算法欧几里得算法就是辗转相除法，欧几里得算法中 ( x , y ) 的最大公约数与 ( y , xmod y) 的最大公约数相同。证明：设 y = k*x+b ，则 b = y % x 设 d 是 ...
2019-03-01 14:04:29
3979
原创 C++ 【NOIP2011】计算系数——利用另类DP巧解
题目描述给定一个多项式(ax + by)^k，请求出多项式展开后x^n y^m项的系数。输入输入文件名为 factor.in。共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。输出输出文件名为 factor.out。输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。样例输入Copy (如...
2019-02-27 15:03:08
655
原创 C++ 如何快速求出n以内互质数的个数
题目描述如果不同的整数X和Y的最大公约数为1，则称X和Y为互质数。显然，X和Y互质等价于Y和X互质。给出整数N，求1~N之间，有多少个数对(X,Y)是互质数。例如N=5时，(1,2) , (1,3), (1,4), (1,5), (2,3), (2,5), (3,4), (3,5), (4,5)共9对数是互质数。思路很容易想到暴搜，两重循环，模拟 x 和 y ，再判定是否互质，但数...
2019-02-27 13:58:20
8328
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人