sunrise__sunrise

分类

未归档(12) 读书笔记(1) 题解(372)

/ 注册

TA的专栏 306篇文章 2人订阅

147篇文章 1181人学习

牛客算法竞赛入门课

92篇文章 1264人学习

牛客编程巅峰赛S1

6篇文章 795人学习

2020牛客暑期多校训练营

10篇文章 877人学习

7篇文章 1221人学习

2021牛客寒假算法基础集训营

6篇文章 804人学习

2篇文章 695人学习

2021牛客暑期多校训练营

36篇文章 1383人学习

全部文章（共385篇）

题解 | #The Fair Nut and Strings# 01trie 来自专栏

中文题意你要选择个长度是的字符串，这些字符串要满足字典序大于小于，在输入的第二行和第三行给出，求本质不同的前缀一共有几个。 Solution 如果我们把看作的话，我们就可以构建一颗满二叉树。那么其实我们对应的在满二叉树中有自己的对应编号。其实就是问你给你两个这样的端点前面你可以选择的节点数一...

2021-04-29

4 846

网络流来自专栏

参考学习的题解 P3376 【模板】网络最大流因为只是一道模板题，不涉及建图这里就不展开介绍。实现最大流，不会的可以参考这篇文章用上了弧优化以及优化。 #include <bits/stdc++.h> using namespace std; #define js ios::sync...

2021-04-25

1 629

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

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

最大子段和来自专栏

简介首先我们介绍一下，什么叫做序列的最大连续子段和。给你一个序列，序列中有正有负，问你只选其中连续的一段子串求合可以拿到的最大值是多少？那么对于这样的一个问题，首先我们分两种情况。 1、静态查询所谓静态查询，也就是对序列中原本的数不进行修改，每次只会查询一个固定的区间。那么对于这种静态的问题，我...

2021-04-11

1 1221

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

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

2021-04-01

2 810

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

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

2021-03-25

1 940