昵称很长很长真是太好了

题解

bfs(5) codeforces(19) kmp(1) python(7) 前缀和(1) 图论(2) 数据结构(18) 未归档(14) 每日一题(14) 牛客(3) 线段树(4) 记忆优化搜索(1) 逆元(1)

/ 注册

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

月月查华华的手机来自专栏

语言：c++14 c++11会超时，但是c++14最多就100多ms，差了十倍多。题解：我们用a[i][j]代表在第i个位置上时，第j个字母（一共26个字母，从0-25编号），距离此位置最近的位置时什么。这样我们就免去了挨着遍历的复杂度，可以直接跳着来进行查找，如果在第i个位置之后的某个字母找不到...

2020-06-27

0 600

Rinne Loves Edges 来自专栏

题解：我们可以从这个s结点出发开始遍历，遍历到根节点，把根节点标为正无穷大，回溯的时候dp[x]代表x出发去掉x到往所有叶子的最小值（删除边的最小值）比如说这样一棵树。1.我们可以删除1-2，1-5这两条边。2.也可以删除2-3，2-4，1-5这三条边。所以我们通过回溯的方法来找出到底是哪种方法更好...

2020-06-27

0 555

数学考试来自专栏

这个题目有比较刁钻的数据，所以0xc0c0c00c这个极小值在用的时候会出错，所以尽量把极小值开的再小一点为好。题解：我们可以对前缀和进行一个小小的变式。原来的前缀和：假如我们要求l-r这个区间，那么就是sum[r]-sum[l-1]为这个区间的和，但是现在看题目来说，这个区间的长度已经定住不会再变...

2020-06-27

0 625

滑动窗口

首先，单调队列具有两个性质1.队列中的元素其对应在原来的列表中的顺序必须是单调递增的。2.队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)这个题是单调队列的模板题，因为范围最大时1e6，所以这里直接用数组来模拟队列即可。1.维护队首（就是如果你已经是当前的m个之前那你就可以被删了,hea...

2020-06-27

0 528

取数游戏2 来自专栏

这个题做的时候发生了一个很搞笑的事情，就是如果你把代码里面的 int a[1011],b[1011]; int dp[1011][1011];调换一下位置，哈，你就会惊喜的发现，段错误。仅限c++11题解：dp[i][j]代表着左边取i个数右边取j个数能获得的最大值。当i+j==n的时候，就可以获得...

2020-06-26

6 926

tokitsukaze and Soldier 来自专栏

题解：贪心大多的贪心都会与排序有关系，这个题给了两个值，估计也会是跟排序有关系。那么我们可以这样排序：先按照每个人容纳人数的值从大到小进行排序。（下面说为什么）接下来就是关键了，我们建立一个优先队列，按照每个人的价格由小到大排序，我们每次往有限队列塞进去一个数，因为我们是按照每个人容纳人数的值从大到...

2020-06-26

0 597

NC23413 小A买彩票来自专栏

题解：这个题既然我们要求他不亏本的概率，那么我们就需要找出所有的情况和不亏本的情况。然后用不亏本的情况，也就是说总钱数要大于等于3*n的情况数来除以总的情况数。接下来就可以用dp的方法做题了。dp[i][j]代表前i个彩票中奖的钱数为j的方案数。然后就相当于是一个递推式。 dp[i][j]+=dp[...

2020-06-24

0 521

哈尔滨理工大学软件与微电子学院程序设计竞赛B-Min Value 来自专栏

题解：这个题他要求数组内相加差值最小的数，我的思路是排序+双指针。但是这个双指针的内部操作有几点是要注意的。1.排序：如何排序？我们先按照元素大小进行排序，再按照其下表进行排序，为什么第二点要按照下标进行排序，后面我会说一下。2.双指针：首先我们用l指针指向排好序的第一个元素，再用r指针指向排好序的...

2020-06-16

0 509

哈尔滨理工大学软件与微电子学院程序设计竞赛H-Maze 来自专栏

题解：一看到3000的范围，如果每次都进行暴力深搜的话，会不会超时？（应该会）我们可以发现假设我们能从点（x1，y1）走到点（x2，y2）那么我们必然可以从（x2，y2）走到点（x1，y1）那么假设我们走过这一片区域的面积是5，那么这五点，你从哪个点进入这个地图，最多能走出的面积也只能是5.那就好办...

2020-06-16

0 730

[NC18386]字符串来自专栏

题解：尺取法，因为这个题目让你找包含26个字母且长度最小的连续区间，所以我们考虑双指针这种算法，从左边往右边移动，每次判断一下确定的区间是否符合标准1.如果符合标准的话，那么我们让左指针往右边移动，同时对应的删除左指针移动走的拿个字符。2.如果不符合标注，那么我们需要让区间继续扩大，也就是让右指针往...

2020-06-15

1 908