ray52033

分类

学习笔记(4) 比赛题解(7) 题解(13)

/ 注册

全部文章（共24篇）

CQOI2014危桥

调了半天TLE，发现初始化的位置有问题。（自闭）题意: 给你一个无向图，其中有一些岛屿间有桥，有一些没有，然后桥又有一些是危桥，只能走两次。（危桥难道不应该只能走一次吗）然后和两个拆桥大队队员来了，希望在和两个岛屿之间往返次，希望在和两个岛屿之间往返次，问两个人的希望能不能成功。 ...

2020-02-27

2 641

【小岛】洛谷P2683

最短路模板题，如果对最短路不是很熟悉的同学请移步：传送门进入正题此题与其他题不同的是，每新增条边，就必须存储，然后等1操作到达时跑最短路，于是我们有dijkstra和SPFA两种跑最短路的方法：其次，如何处理无法到达呢。只需要if(dis[]==inf)就行了。因为我们dis一开始初始化为i...

2020-02-26

1 734

【Einstein学画画】

CSP马上到了,赶紧复习图论，顺便写下题解题目要使画的次数最小，那么我们就可以知道最小的次数为1 于是这道题就是一笔画（欧拉路）板题，甚至还不需要求路径。先来说一下什么是欧拉路吧：七桥问题欧拉说：是否可从某个地方出发，经过每座桥一次,回到原来出发的地方？然后七桥问题就能转化成如下的一个无...

2020-02-26

1 749

[SDOI2013]费用流

这道题标题写着费用流，可好像实际上跟费用流没有甚关系（这不是废话吗，不然nodgd给你放在最大流里干嘛雾）题意：给出一个图，然后在图上（很臭不要脸的）先跑一个最大流，只要每个节点流入量=流出量就是一个合法的“最大流”，然后选一些边加费用，所有边的加的最费用=P。总费用每条边的实际流量...

2020-02-26

1 641

CQOI2008. 传感器网络

这道题肯定用网络流，不然给你放在网络流考试里干嘛题意：给了一个有向无环图，给（除了根节点）每个节点选一条出边构成一棵树，让儿子个数最多的节点的儿子个数最少。（根节点不算）依次输出每个节点的父亲，要求字典序最小。先不考虑字典序，考虑计算最小的负载级别。很显然想到负载级别可以用二分答案来求。 ...

2020-02-24

2 646

2020.02.21.小测验

A.Nicole的生物期末考试问题描述少壮不努力，长大写程序。当年Nicole就是因为努力不够，现在正坐在期末考试的考场里做生物试卷。某生态系统的物种之间发生了，这些物种分成了两派。“正派”有n1个物种，这些物种编号依次是1,2,…,n1；“反派”有n2个物种，这些物种编号依次是n1+...

2020-02-22

1 579

练习赛题解

A-赫式几何问题描述 19世纪的德国数学家赫尔曼●明科夫斯基发现了一种非欧几里德几何空间，称作“出租车几何空间或者曼哈顿距离”。在这种神奇的空间中，定点T1(X1,Y1)与T2(X2,Y2)的距离表示为： D(T1,T2)=|X1-X2|+|Y1-Y2| 其他的定义都同欧几里德几何相同，包括圆的定...

2020-01-04

3 1006

二叉苹果树

今天讲了树形dp，正好看到这道题，仔细一看，这不是板题吗（滑稽）。咳咳，强行切入正题首先，我们根据样例画出一张无比丑陋的图：现在我们减去1的右枝就得到了下面这张图：如果减去1的左枝：如果保留1的左右枝，左子树保留条，右子树保留条，使得由此可以推出：对于任意子树，若要保留其条枝，均可按减掉...

2020-01-04

6 937

Moovie Mooving

题面翻译：奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最...

2020-01-04

1 785

【NOIP】排座椅

此题是一道十分考察细节的一道题。此题就是让我们求的矩阵里，分割出条横线和条竖线，要求两两相邻的点，尽可能多的不再相邻。题目已经告诉你了，这是一道贪心！！！为什么是贪心呢？？？要使答案最优，肯定要让条横线和条竖线要穿过尽可能多的会讲话的两个人！如图：如果只有一条横线和竖线上图中的最优解，很...

2020-01-04

23 1559