0 cqbz_ChenJiage

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 24w+

【NOIP2009】最优贸易 题解

今天考了一道分层图,本来是一道板题,结果我被误导了,想成了 架设电话线一题,考完写炸了才发现,架设电话线只需要求出第k+1大的长度,只需要满足局部最优,但是飞行线路要使总和最小,只能用分层图,然后我翻了半天标签,找到了这道题。link但是当旁边LH看到之后,他告诉我,这是一道DP。结果我没看出来。。。分层图倒是很简单。Sulotionstep1首先,他可以在图上到处走动,所以很自然地可以建一张图,所有的边权都是0。然后这道题只与水晶球的价格有关,所以我们把点权搬到边权上面。step2因为

2020-10-07 17:31:19

假日住宿 题解

假日住宿题目描述给出一棵NNN节点的树,每个节点代表一个城市,每个城市有一个人,每个人离开自己的城市到另一个城市,每个城市只能有一个人,问这NNN个人移动距离和的最大值。输入格式输入的第一行包含一个整数T(1<=t<=10)T(1<=t<=10)T(1<=t<=10),表示测试用例的数量。每个测试用例包含几行。 第一行包含一个整数2<=N<=1052<=N<=10^52<=N<=105,代表城市数。 然后接下来的行分别包含三

2020-10-04 14:57:52

初二普及组全真模拟赛 题解

数你太美【第一周】题目描述PB 获得了两个正整数数列 ai{a_i}ai​ , bi{b_i}bi​ ,长度分别为 n , m ,其中每个数都小于 10。 定义一个正整数是“美丽的正整数”,当且仅当:这个数的十进制表示中,至少有一个 数位上的数在数列 a_i 出现过,至少有一个数位上的数在数列 b_i 出现过。现在 PB 希 望求出最小的“美丽的正整数”。输入格式第一行,两个正整数 n , m ;第二行,n 个正整数,第 i 个为 a_i ;第三行,m 个正整数,第 i 个为 b_i 。输出格

2020-09-12 13:28:27

RMQ算法总结

RMQRMQ 即范围最小值问题 (Range(Range(Range MinimumMinimumMinimum Query)Query)Query)支持查询从Al,Al+1,Al+2...,ArA_l, A_{l+1},A_{l+2}...,A_rAl​,Al+1​,Al+2​...,Ar​中的极值(Max(Max(Max ororor Min)Min)Min)算法思想设dpi,jdp_{i,j}dpi,j​为左端点为iii, 右端点为2j(1<<j)2^j(1 << j)

2020-08-24 21:41:07

Ant Trip 题解

Ant Trip分析题意很简单,爆搜的时间复杂度比较高,不考虑。应该使用欧拉回路的相关知识求解。intn()输入时将两个节点的入度都加一(无向),然后将两个节点合并在一个连通图中.for (int i = 1, u, v; i <= m; i++) { scanf ("%d %d", &u, &v); in[v] ++, in[u] ++; UnionSet(u, v);}TFW居然都不知道要将两个节点合并在一个连通图中work(

2020-08-20 20:43:03

叶子清除计划【第五周】 题解

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

2020-08-19 20:21:02

构造完全图 题解

题目链接分析假设有如下图两个集合 xxx & yyy。因为要构造一个完全图,所以应该将xxx中的s[x]s[x]s[x]个节点与yyy中的s[y]s[y]s[y]个节点一一连接即连接s[x]∗s[y]−1s[x] * s[y] - 1s[x]∗s[y]−1(此处减一是为了在后面单独处理原图中的dis[i].wdis[i].wdis[i].w)个节点,为了保证此完全图的最小生成树所以要用(s[x]∗s[y]−1)∗(dis[i].w+1)(s[x] * s[y] - 1) * (dis[i].w

2020-08-17 20:56:16

秘密的牛奶运输 题解

题目连接分析一道可以暴力水过去的次小生成树step1首先用KruskalKruskalKruskal||PrimPrimPrim求出原图的一颗最小生成树,在连边的时候,用一个visvisvis记录一下那些已经在最小生成树里面。step2提前暴力dfsdfsdfs或者bfsbfsbfs求出任意两点构成的环之间的最大权值具体操作定义函数dfs(ints,intu,intfather,intmw1,intmw2)dfs(int s, int u, int father, int m

2020-08-17 20:55:39

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

题目地址分析第一眼看到此题,感觉就是一道水题,直接加上前needneedneed小的白边就行了,再处理到n−1n-1n−1条黑边,但是,打完后突然发现有问题。。。 虽然加上了前needneedneed小的白边,但是会出现树不连通的现象,即无法构成生成树。正解思路二分一个增量midmidmid(可正可负)。跑一遍KruskalKruskalKruskal,将所有的白边都加上aaa,记录构成生成树后所用到的白边,如果数量小于needneedneed就将右端点往左移,否则往右移。最后的ansansan

2020-08-17 20:55:08

From Hero to Zero 题解

题目地址分析考试时的一道水题但是还是没拿满,按题目意思模拟即可#include <cstdio>#include <iostream>#include <algorithm>#define LL long longusing namespace std;LL t, n, k, step;int main() {// freopen("game.in", "r", stdin);// freopen("game.out", "w", stdout)

2020-08-17 20:54:38

数星星 Stars 题解

题目链接分析一道树状数组,但坑点比较多。。。首先在草稿纸上画图可以得知:星星的等级与xxx无关,至于yyy的大小有关,于是我们可以根据输入顺序一一将其插入树状数组进行维护,此星星的等级其实就是在插入前以111~星星的yyy的星星数量和。注意星星的坐标是从(0,0)(0, 0)(0,0)开始存,但树状数组不能够维护,所以要提前将所有星星的xxx加上一。(如果在求和函数中把限度跳到0就会卡死循环我就错了)代码#include <cstdio>#include <cstring&

2020-08-17 20:54:05

我的博客园博客地址

https://www.cnblogs.com/cqbz-ChenJiage/

2020-08-15 21:10:57

SCOI 滑雪与时间胶囊 题解

SCOI 滑雪与时间胶囊题目描述a180285 非常喜欢滑雪。他来到一座雪山,这里分布着MMM条供滑行的轨道和NNN个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1<=i<=n)i(1<=i<=n)i(1<=i<=n)和一高度$。a180285能从景点。a180285 能从景点。a180285能从景点i滑到景点滑到景点滑到景点j当且仅当存在一条当且仅当存在一条当且仅当存在一条i和和和j之间的边,且之间的边,且之间的边,且i的高度不小于的高度不小于的高度

2020-08-15 21:10:13

最小生成树 学习笔记1 - Kruskal

最小生成树定义Kruskal算法算法流程具体实现建立结构体存边并查集维护完整代码定义给定一个带权图,满足以下条件:1.保证图中所有的点都联通2.在满足条件1的情况下尽可能去掉多的边,使得所有的边权之和最小,即Σi=1i<=mwi\Sigma_{i=1}^{i<=m}w_iΣi=1i<=m​wi​最小。Kruskal算法Kruskal是基于贪心的思想,根据以上的定义描述依次枚举1−m1-m1−m条边,如果两个点没有存在于一个连通分量中,那么就连上这一条边。此算法的难点在于查

2020-08-05 18:34:56

图论学习笔记3

图论学习笔记3Bellman-Ford 算法松弛负边权操作负权环判定朴素实现Spfa思想实现Bellman-Ford 算法Bellman-Ford算法:DijkstraDijkstraDijkstra类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。松弛每次松弛操作实际上是对相邻节点的访问,第 n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |

2020-07-30 22:11:36

图论学习笔记2

最短路多源最短路Floyd多源最短路FloydFloydFloydFloyd是基于DPDPDP思想。设kkk为中转点,与iii, jjj都有边相连。那么可以得到dis[i][j]dis[i][j]dis[i][j]的最短路径的状态转移方程为:dis[k,i,j]=min(dis[k−1,i,j],dis[k−1,i,k]+dis[k−1,k,j]dis[k,i,j]=min(dis[k-1,i,j], dis[k-1,i,k]+dis[k-1,k,j]dis[k,i,j]=min(dis[k−1

2020-07-29 21:15:21

图论学习笔记1

图论学习笔记 图的基本概念图的存储结构邻接矩阵邻接表存点加边图的遍历深度优先广度优先图的基本概念图:由**顶点(vertex)和边(edge)**组成。顶点—具体事物边—具体事物之间的联系顶点的集合VVV,边的集合EEE,图记为G=(V,E)G = (V,E)G=(V,E)图的存储结构一般分为两种 : 邻接矩阵、邻接表邻接矩阵由一个二维数组实现,比较简单,但是在存储稠密图时比较不划算。G[i][j]G[i][j]G[i][j]表示的是顶点i与顶点j的关系。如果顶点i和顶点j之间有边相连

2020-07-28 21:58:15

树状数组学习笔记

定义树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 —— by baidu实现用一个数组bit[i]bit[i]bit[i]表示从[i−lowbit(x)+1,x][i - lowbit(x) + 1

2020-07-26 22:16:18

数三角 题解

数三角题目描述输入格式输出格式样例样例输入样例输出分析预处理求出连通性判断是否构成三角形完整代码题目描述这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示,有水平的,垂直的或对角的。对角放置的木棍可以交叉。将木棍随意地放在网格上得到的图案可能不含三角形,也可能含一个或多个三角形。如下图所示,(a),(b),©,(d)和(e)分别含有2,5,12,0,0个三角形。你的任务是写一个程序数出一个图案中的三角形个数。。cpp输入格式输入文件count.in包括N+1行:

2020-07-25 21:16:09

分离与合体题解 区间DP + DFS

题目描述经过在机房里数日的切磋,LYD 从杜神牛那里学会了分离与合体,出关前,杜神牛给了他一个测试……杜神牛造了n 个区域,他们紧邻着排成一行,编号 1 ~ n 。在每个区域里都放着一把 OI 界的金钥匙,每一把都有一定的价值,LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走,而是每次只可以拿一把。为了尽快得到所有金钥匙,LYD 自然就用上了刚学的分离与合体特技。一开始 LYD 可以选择 1 … n - 1 中的任何一个区域进入,我们不妨把这个区域记为k 。进入后 LYD

2020-07-19 20:32:10

查看更多

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