sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

题解 | #环路运输# 单调队列来自专栏

Solution 首先观察题目中的定义可以得知，在不区分前后关系的时候判断很复杂。我们对于这种环形的办法一般都是断环成链，复制一份。那么这样处理之后，就可以永远保证按照这种的方式求解不会漏掉情况，并且每次我们每次往前选择的。接下来就是维护转换方程了。我们要求解的答案是定长区间的最值问题，使...

2021-04-21

0 757

题解 | #逛公园# 最短路，记忆化搜索来自专栏

题目大意组输入，每次有个点条边的有向图。首先如果从起点不能到达终点，那么输出一个，如果可以到达求解出最短路的距离记录为。那么我在保证最多另外让你走个距离的情况下，问你从起点到终点的方式有几种？并且方案数要对取模。因为我们存在边权为的边，所以如果有一个环它的权值和都是，那么直接输出。 Solutio...

2021-04-15

2 849

题解 | #[JSOI2015]地铁线路# 来自专栏

Solution 交汇地铁类型的图，一般都考虑分层建图或者借助额外的点建图。我们把起始的站点用表保留编号，上下地铁的位置建立额外的编号，这样就可以保证我们每次上下地铁计算到正确的票价。所以我们再把地铁路线上的点拆分成向左向右两边的点，那么很明显边权存在两个(票价，时间)，那么从起始站点上地铁我们开...

2021-04-14

2 842

题解 | #Max Flow# 树上差分来自专栏

中文题意给你个节点的一棵树，并且存在次操作，每次操作把节点之间路径上全部的点权值加一。问操作次操作后整棵树最大的权值是多少？ Solution 读懂题的话，就是树上差分模板题，我实现的办法是树链剖分，会了之后就觉得比倍增快乐多了。给个OIWiki的差分链接树上点差分就是： #include &...

2021-04-13

3 1071

【每日一题】4月13日[HAOI2012]音量调节动态规划 bitset+滚动数组优化来自专栏

Solution 转移方程比较简单，这里就直接给出了。代表第首歌结束的时候是的音量，并且可以满足前面首歌都不低于0和不大于的条件。初始条件就是。转移方程就是下面给出的，注意不要越界了。状态总数，转移时间复杂度，空间复杂度。解决之后考虑如何做下优化吧，第一步首先知道对于第个物品可以更新的状态...

2021-04-13

4 789

【每日一题】3月30日Modern Art 二维差分来自专栏

中文题意第一行给出一个整数。接下来给出一个的矩阵，你有种颜料，每次你可以选择一个矩阵中的格点填涂一个小正方形，你选择的格点将会成为这个正方形的左上点，并且每个格点做为左上方点只能选择一次，下一次填涂颜料会把上次的颜色覆盖，初始化矩阵都是没涂过颜色的你可以当作涂了颜色，你需要选择中的全部点，填涂次...

2021-04-01

2 810

【每日一题】3月26日[HAOI2015]树上操作树链剖分来自专栏

Solution 这是一题树链剖分的模板题，接着这个题目我仔仔细细重新在OI Wiki学了一下之前一直不是很懂的树链剖分总算是搞定了，以前只会把一棵树控制的全部子树转化到线性的可执行区间，然后再去树状数组操作之类的，并没有把重子节点这些名次好好理解，现在看了之后还是有了比较深刻的理解，过几个简单变形...

2021-03-25

1 940

【每日一题】3月24日 Landscaping P 带后悔的贪心来自专栏

中文题意现在你一共有个花坛，每个花坛有一定量的起始泥土，现在你要把每个花坛泥土数量变成。你有三种操作分别是：花费直接给这个花坛填入一单位泥土，花费直接给这个花坛移除一单位泥土，如果你想把第个花坛的泥土移动到第个花坛，那么花费就是，现在询问你使得全部花坛数量都变成指定的的最小花费是多少...

2021-03-23

4 857

【每日一题】3月23日[SCOI2010]幸运数字容斥来自专栏

Solution 第一眼以为是数位，但是发现如果是倍数也成立的话那就不知道怎么写每位的状态了。首先我们可以很容易找到从全部的幸运数字，通过一次即可，可以知道最多的初始幸运数字是个，那么我们如何通过这些幸运数字找到答案。这类倍数题目，考虑容斥处理。首先我们加上中的倍数的个数，这个答案等于，同理我们...

2021-03-22

1 776

牛客小白月赛32

写在前沿：这场小白赛难度不大，但是模拟题太多太多了，码量巨大，并不是很喜欢。因为模拟太多赛后进行代码改良许多参考了码量很少的hx073269的代码。 A、拼三角组给出个数，询问能不能构成两个三角形。三种做法都是暴力，不可以通过去比较更小的三个和更大的三个，这里给出出题人的例子。 3 8 12 ...

2021-03-22

18 1129