0 xxxxppppxxxx

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 18w+

整除,模,同余

整除概念性质模概念性质整除概念若整数b除以非零整数a,商为整数,且余数 [1] 为零, 我们就说b能被a整除(或说a能整除b),b为被除数,a为除数,即a|b(“|”是整除符号),读作“a整除b”或“b能被a整除”。a叫做b的约数(或因数),b叫做a的倍数。整除属于除尽的一种特殊情况。(by 百度)当然,就可以说,如果ax=b,则a | b;性质传递性:如果a | b且 b | c则 a | c;证明:令ax=b,by=c(x,y∈Zx,y \in Zx,y∈Z)∴axy=c又∵x.

2020-10-17 12:54:46

公路修建问题

题目描述OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕。所以,OIER Association组织成立了,旨在建立OI island的交通系统。 OI island有n个旅游景点,不妨将它们从1到n标号。现在,OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。公路有,不妨称它们为一级公路和二级公路。一级公路上的车速快,但是修路的花费要大一些。 OIER Association打算

2020-10-07 13:11:11

LCA/在线(倍增)离线(Tarjan)

概念祖先公共祖先最近公共祖先方法1:暴力爬山法方法2:倍增求公共祖先求俩点的距离Tarjan概念祖先有根树中,一个节点到根的路径上的所有节点被视为这个点的祖先,包括根和它本身公共祖先对于点a和b,如果c既是a的祖先又是b的祖先,那么c是a和b的公共祖先##深度子节点的深度=父节点深度+1,一般我们定根的深度为1最近公共祖先树上两个节点的所有公共祖先中,深度最大的那个称为两个点的最近公共祖先(LCA)方法1:暴力爬山法很明显,这个方法是很想爬山,我们可以先然两个节点中,深度大的依着父亲.

2020-10-05 14:08:34

RMQ总结

RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。首先,根据题意,可以写出一个暴力...

2020-10-04 17:32:55

树的直径

树的直径概念给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。题目描述给定一个有个节点的树,树以个点条边的无向图形式给出, 求树的直径。输入格式输入的第1行为包含了一个正整数,为这棵二叉树的结点数。接下来N行,每行有个正整数,表示有一条从到的无向边。输出格式输出包括1个正整数,为这棵二叉树的直径。样例样例输入101

2020-10-04 14:54:54

树的重心

树的重心首先,我们要知道,什么是重心树的重心定义为,当把节点x去掉后,其最大子树的节点个数最少(或者说成最大连通块的节点数最少),那么节点x就是树的重心。他有以下几个性质1、删除重心后所得的所有子树,节点数不超过原树的1/2,一棵树最多有两个重心,且相邻;2、树中所有节点到重心的距离之和最小,如果有两个重心,那么它们距离之和相等;3、两个树通过一条边合并,新的重心在原树两个重心的路径上;4、树删除或添加一个叶子节点,重心最多只移动一条边。还有,一棵树,重心最多2个,n%2= =0有2个,n%

2020-10-04 14:54:05

没有上司的晚会

最大独立子集 没有上司的晚会题目描述Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会,要求与会职员的快乐指数最大。但是,没有职员愿和直接上司一起参加宴会。输入格式第一行一个整数N。(1≤N≤6000)接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。最后一行输入0,0。输出格式

2020-10-04 14:53:12

树形DP总结基础

概念应用例题最大独立子集 没有上司的晚会题目描述分析树的重心题目描述分析树的直径概念题目描述分析概念给定一棵有N个节点的树(通常是无根树,也就是有N-1条无向边),我们可以任选一个节点为根节点,从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时,一般就以节点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP的状态表示中,第一维通常是节点编号(代表以该节点为根的子树)。大多数时候,我们采用递归的方式实现树形动态规划。对于每个节点x,先递归在它的每个子节点上进行DP,在回溯时,从子节点.

2020-10-04 14:51:10

年功序列c++

题目描述在虚拟国度里多了很多 Virtual oier,为了树立对后辈的威信,从第 11 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。虚拟国度的创始人 oier Chtholly 感觉非常有趣,于是他决定观测 11 到 nn 这些人,他观测到了一些有趣的现象:虚拟国度里有一些凳子,如果 aa 是 的先辈则 能在 前面得到凳子Chtholly的观测可以构成 mm 个序列,每个序列有 kk 个元素 a1,a2,a3,⋅⋅⋅⋅⋅⋅,aka1a 2a3,⋅⋅⋅⋅⋅⋅,a k。表示在

2020-08-18 19:26:41

木棒poj1011

题目描述乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。输入格式输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。输出格式为每组数据,分别输出原始木棒的可能最小长

2020-08-17 21:12:29

老鼠与猫的交易

题目有一只老鼠很喜欢奶酪,但是奶酪被分别放在N个房间里,而且这些房间都有一只猫咪看守,现在它准备和猫咪们做个交易。它有M磅的猫食,想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i]磅,同时猫咪需要F[i]磅的食物,如果老师给猫咪F[i]*a%的猫食,那么它就可以得到J[i]*a%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数,那老鼠怎样才能换得最多的奶酪呢?样例输入5 37 24 35 2样例输出13.333首先,看到这题,第一反应,贪心。。。贪心策略:首先

2020-08-17 18:41:33

From Hero to Zero

题目描述:有一天,小明给了你两个数字n和k,现在,你需要对数字n进行一下操作:对于每一步操作,你可以选择下面其中一个项目:1.将n的值减少1.2.如果n能被k整除,可以使n/k比如:n=27,k=3,你可以进行下列操作:27→26→25→24→8→7→6→2→1→0请你计算出数字n变为0时最少需要的操作数。输入:第一行输入一个整数t(1≤t≤100),表示数据个数接下来n行,每行2个整数n和k(1≤n≤1e18,2≤k≤1e18)输出:将数字n变为0的最小次数输入样例:3-;2输

2020-08-17 18:36:27

Star Way To Heaven

题目描述小 x伤心的走上了 Star way to heaven。到天堂的道路是一个笛卡尔坐标系上一个 n*m的长方形通道 顶点在0,0 和 。小 n,m 从最左边任意一点进入,从右边任意一点走到天堂,最左最右的距离n为 ,上下边界距离m为 。其中长方形有 k个 ,每个k 都有一个整点坐标,star的大小可以忽略不计。每个star 以及长方形上下两个边缘宇宙的边界都有引力,所以为了成功到达 小w 离他们越远越好。请问小w走到终点的路径上,距离所有星星以及边界的最小距离最大值可以为多少?输

2020-08-16 20:25:03

老旧的桥

题目描述现在有个N岛屿和M坐桥。第个N桥双向连接着第A和第B个岛屿。刚开始的时候,我们可以用其中的一些桥在任何两个岛之间旅行。然而,经调查显示,这些桥都将会因老旧而倒塌,而且倒塌的顺序为从第1座桥到第M坐桥。由于剩下的桥不能够使第A个岛和第B个岛互相到达,这会使岛屿对变得很不方便。对于每一个,找出在第i座桥倒塌之后,这样不方便的岛屿对有多少?输入格式第一行有两个正整数N和M,分别表示岛屿的数量和桥的数量。接下来有M行,每一行有两个整数和,分别表示第i座桥连接的两个岛屿的编号。输出格式输

2020-08-11 22:14:15

造船

题目描述小Y想要在虚拟世界里造船。最开始 个船的完成度全部都为 。小Y第 时刻可以在 和 两艘船中选择一艘让这艘船的完成度 。由于国家政府是奇数控,所以所有偶数完成度的船只都将被摧毁,小Y想知道 时刻后能剩下来的船只最多有多少艘。输入格式第一行两个整数 和接下来 行,每行两个整数 ,样例input8 61 23 44 56 77 88 6output6题目分析首先,可以把所有的a,b合并,这样,就可以统计所有的完成度,然后/2得到加的完成度,如果,完成

2020-08-11 21:52:12

[NOIP2010]关押罪犯

题目描述S城现有两座监狱,一共关押着N名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c的冲突事件。每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力,如果

2020-08-11 21:26:28

数据备份

题目描述你在一家IT公司为大型写字楼或办公楼的计算机数据做备份。然而数据备份的工作是枯燥乏味的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上,你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,这意味着你仅能为 K 对办公楼(总计2K个办公楼)安排备份。任意一个办公楼都属于唯一的配对组(换句话说,这 2

2020-08-11 20:40:34

最短路总结(1)

最短路的定义最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径这篇文章就是介绍几种关于最短路径的几种算法弗洛伊德1.定义动态规划以”途径点集大小”为阶段,以一种nnn的算法,更新i-j的最短路,枚举,一个k点,为中转点,然后判断是直接的段还是间接的短2.邻接矩阵算法#include <cstdio>#include <cmath>#include <cstring>int n, m, ty;int

2020-08-11 18:50:05

质数距离

题目描述给定两个整数 ,求闭区间 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时,输出靠前的素数对。输入格式多组数据。每行两个数 。输出格式详见输出样例。样例样例输入2 1714 17样例输出2,3 are closest, 7,11 are most distant.There are no adjacent primes.题目分析其题目本身是很简单,但是,由于题目范围过大,素数筛的数组无法开这莫大,所以,筛法要进行特别处理其实,就是先数筛一部分可以接受的,然后

2020-08-10 21:00:30

三个朋友

题目描述给定一个字符串 ,先将字符串 复制一次~~(变成双倍快乐)~~,得到字符串 ,然后在 中插入一个字符,得到字符串 。给出字符串 ,重新构造出字符串 。所有字符串只包含大写英文字母。输入格式第一行一个整数 ,表示字符串 的长度。第二行一个长度为 的字符串,表示字符串 。输出格式一行一个字符串,表示字符串 。特别地:如果字符串无法按照上述方法构造出来,输出 NOT POSSIBLE;如果字符串 不唯一,输出 NOT UNIQUE。样例样例输入 17ABXCABC

2020-08-09 21:45:00

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。