0 CQBZ_xiaofang

尚未进行身份认证

我要认证

保加利亚希望中学附属光明小学优秀毕业生

等级
TA的排名 20w+

2020牛客NOIP赛前集训营-普及组(第二场) 题解

T1 面试描述题目描述牛牛内推了好多人去牛客网参加面试,面试总共分四轮,每轮的面试官都会对面试者的发挥进行评分。评分有 A B C D 四种。如果面试者在四轮中有一次发挥被评为 D,或者两次发挥被评为 C,就不会通过面试。如果面试者没有一次被评为 D,并且有三个或以上的 A,则会获得 special offer。其余情况会获得普通 offer。现在告诉你一些面试者的发挥,请你算一算,他们的面试结果分别是什么。输入描述:第一行输入一个 T,代表面试者的个数。接下来有 T 行,每行都有一个长度为

2020-10-21 14:10:50

数论作业一

1.证: 设这个数为2n+1;则:(2n+1)2(2n+1)^2(2n+1)2= 4n2+4n+14n^2+4n+14n2+4n+1(2n+1)2(2n+1)^2(2n+1)2 -1=4n2+4n4n^2+4n4n2+4n=4n(n+1)若 2|n则 8|4n若 n%2==1;则 2|(n+1)∴ 8|4(n+1)∴ 得证2.证:当n是偶数时,则令=2k;∴ 3n+13^n+13n+1=32k+1=3^{2k}+1=32k+1=9k+1=9^k+1=9k+1=(1+.

2020-10-17 16:37:10

[HNOI2006]公路修建问题题解

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

2020-10-07 19:26:03

[JLOI2011]飞行路线题解

题目描述Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?输入格式数据的第一行有三个整数,n,m,k,分别表示城市数,航线数和免费乘坐次数。第二行有两个整数,s,t,

2020-10-07 19:19:30

[Usaco2018 Dec]Teamwork 题解

题目描述题目描述在Farmer John最喜欢的节日里,他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物,他想要获得他的奶牛们的帮助。你可能能够想到,奶牛们本身也不是很擅长包装礼物,而Farmer John即将得到这一教训。FarmerJohn的N头奶牛(1≤N≤104)排成一行,方便起见依次编号为1…N。奶牛i的包装礼物的技能水平为si。她们的技能水平可能参差不齐,所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过K头的连续的奶牛(1≤K≤103),并且一头奶牛不能属于多于一个小

2020-10-07 18:34:46

迷路[SCOI2009]题解

题目描述原题来自:SCOI 2009Windy 在有向图中迷路了. 该有向图有 nnn个节点,Windy 从节点 000 出发,他必须恰好在TTT时刻到达节点 N−1N-1N−1。现在给出该有向图,你能告诉 Windy 总共有多少种不同的路径吗?注意:Windy 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。输入格式第一行包含两个整数NNN,TTT;接下来有 NNN行,每行一个长度为NNN的字符串。第iii行第jjj列为 0表示从节点iii到节点jjj没有边,为111到999表示从

2020-10-06 19:17:00

堆栈游戏题解

题目大意题目描述Mirko在玩堆栈游戏。开始他有一个空的堆栈,编号为0.在第i步(1<=i<=300000),他会选择一个编号为v的堆栈,复制一份并做如下操作:a v 表示将v号堆栈复制一份,新栈的编号为i,并将元素i压入新栈的栈顶。b v 表示将v号堆栈复制一份,新栈的编号为i,将新栈的栈顶元素弹出。c v w 将v号堆栈复制一份,编号为i,并比较第v号和第w号堆栈中有多少相同的数。输入格式第一行一个整数n,表示有n步。接下来n步,每步表示一个操作,如上所述。输出格式:

2020-10-05 16:02:37

LCA总结

目录写在前面0. 一些定义1. 暴力爬山法方法举个栗子核心代码:2.基于倍增的暴力爬山法方法预处理倍增优化-第一部分倍增优化-第二部分代码3.Tarjan算法方法举个栗子代码今天,咱们来讲一讲LCA算法写在前面对于LCA,笔者也并没有说做到百分之百的掌握掌握了就不用谢博客了呀,所以若有什么错误的地方,希望各位看官可以指出;0. 一些定义首先,我们需要明白一些定义,这些定义可以帮我们更好的理解算法祖先:有根树中,一个节点到根的路径上的所有节点被视为这个点的祖先,包括根和它本身;公共祖先:对于点

2020-10-05 14:53:05

树形DP总结

作为一名合格的 OIer ,一定要有自我总结的意识,一定要通过写博客的方式来验证自己的掌握程度————沃.茨基硕德今天,带大家来看一下树形DP树形DP,顾名思义,则是在树上做D动态规划:在树上设计动态规划算法时,一般就以节点从深到浅(子树从小到大)的顺序作为DP的阶段。DP的状态表示中,第一维通常是节点编号(代表以该节点为根的子树)。大多数时候,我们采用递归的方式实现树形动态规划。对于每个节点x,先递归在它的每个子节点上进行DP,在回溯时,从子节点向节点x进行状态转移。废话有点多,因为这种定义性

2020-10-04 15:26:05

树的直径

定义给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。思路我们设1号节点为根节点,那么最短路径则是到根节点最远的一个节点与次远的一个节点的距离之和代码#include<bits/stdc++.h>using namespace std;const int MAXN=100005;const int MAXM=100000

2020-10-04 15:09:17

树的重心

解释:树的重心定义为树的某个节点,当去掉该节点后,树的各个连通分量中,节点数最多的连通分量其节点数达到最小值思路首先,我们得明白一个性质:删除重心后所得的所有子树,节点数不超过原树的1/2;这不是废话通过这个性质,我们可以对重心进行求解树上任选一点i,进行DFS,并统计该点所有子树的大小和以它为根的子树的大小,这样也就可以得到一个点所有子树的大小及的大小,如果它的大小大于了原树的一半,就说明它不是重心还有一个问题,如果这个点不是根节点,那么删掉后剩下的连通块不止有他的子树,还有他上面的部分,

2020-10-04 15:06:23

没有上司的舞会题解

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

2020-10-04 14:55:23

多校联赛普及组 叶子清除计划题解

题目描述⼩Y同学是⼀位数据结构⼤师同时也是⼀位园艺⼤师。秋天到了,⼩Y同学需要对学校内的⼀棵树展现他顶尖的修叶⽔平。学校内的这棵树是⼀颗拥有nnn个点的⽆根树,每次⼩Y会删去所有的叶⼦节点(即度数小于等于1的节点),直到所有的点都被删除了为⽌。⼩Y现在想问你对于每个点,求出它是第⼏次操作中被删除的。输入格式第⼀⾏⼀个数字nnn,表⽰树上节点个数接下来n−1n−1n−1⾏,每⾏两个数字uuu,vvv,表⽰树上的⼀条边。输出格式⼀⾏nnn个数字,第iii个数字表⽰节点iii在第⼏次操作中被删除

2020-09-27 20:53:30

CSP_J 纪念品题解

题目:小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。某个纪念品 的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。每天,小伟可以进行以下两种交易无限次:任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;卖出持有的任意一个纪念品,以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。T 天之后,小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币

2020-09-23 14:08:17

八皇后O(1)算法题解

题目描述在国际象棋棋盘上(8*8)放置八个皇后,使得任意两个皇后之间不能在同一行,同一列,也不能位于同于对角线上。问共有多少种不同的方法,并且按字典序从小到大指出各种不同的放法。题解见证奇迹的时刻!!!#include<cstdio>int main(){ printf("1 5 8 6 3 7 2 4\n""1 6 8 3 7 4 2 5\n""1 7 4 6 8 2 5 3\n""1 7 5 8 2 4 6 3\n""2 4 6 8 3 1 7 5\n""2 5 7

2020-09-23 13:25:35

老死不相往来 题解

咯咯咯,鸽题目描述马孔多是一个奇怪的小镇,镇上的房子沿着一条河流的南岸而建,而且镇上的居民一辈子都只在自家附近一个固定半径的范围内活动,有些居民永远不会相互接触,即使他们生活一辈子也老死不相往来。马孔多小镇一共有n座房子,以到镇子的西端的距离算,居民家的位置为p,他们活动的范围为r,请问马孔多小镇一共会有多少对住户之间老死不相往来。输入格式第1行:一个数N,表示房子的数量(1 <= N <= 50000)第2 - N + 1行:每行2个数P, R中间用空格分隔,P表示房子的位置,R表

2020-09-01 23:01:05

木棒题解

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

2020-08-17 21:08:45

关押罪犯(并查集)题解

思路:首先,对c进行从大到小的排序;其次,开始处理,如果输入的两个罪犯在相同的监狱就说明他们会有冲突,因为进行排序了,所以输出之后直接结束代码;可如果他们两个不在同一个监狱呢?我们来想一下:如果1和3有矛盾,3和2有矛盾,#include<bits/stdc++.h>using namespace std;int pre[200005];void FuChuZhi(int n){ for(int i=1;i<=n;i++) pre[i]=i;}int F.

2020-08-16 21:43:32

最短路模板

话不多说,放代码:#include <bits/stdc++.h>using namespace std;void SPFA_scan(){ /* int n,m;bool vis[1000005];struct edge{ int v,val;};vector<edge>dis[1000005];int x,y,e;int dp[1000005];int tot[1000005];queue<int>q;*/ memset(dp,0x3

2020-08-11 18:51:44

「一本通 3.1 练习 4」Tree 题解

题目描述原题来自:2012 年国家集训队互测给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有 条白色边的生成树。题目保证有解。输入格式第一行V,E,need 分别表示点数,边数和需要的白色边数。接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色,1黑色)。输出格式一行表示所求生成树的边权和。样例样例输入2 2 10 1 1 10 1 2 0样例输出2题解:这个题要求在选取特定数量的基础上,构造一棵最小生成树。我们想一下

2020-08-16 19:57:28

查看更多

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