Dear㉿You

题解

未归档(1)

/ 注册

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

Present 来自专栏

前言刚开始什么思路都没有，但是突然想到了一道题——换教室，似乎也是二分，然后运用到这一道题，似乎就明了了分析这道题的话，通过二分最小的w，是每一盆花的a[i]>=w，并且浇的天数小于等于m。这就是主要思路。实现题目中给出了一个w(刚开始我也不知所措啊QwQ)，然而我们想一想...

2020-09-20

3 609

Telephone Lines 来自专栏

题意求1到n的所有路中的最小的第k+1长的路。分析题目中说，可指定免费修k条路，而最终的费用就取决于边权值第k+1大的边。所以可以二分其值，每次二分出一个mid，跑spfa，求出到n最少要免费牵多少根线。如果小于等于k条，说明这条边还可以更小。代码 #include<ios...

2020-09-11

6 771

道路与航线来自专栏

解法一看数据范围，以及一点分析，能够确定这是单源最短路，可选DJ与SPFA，但是图中存有负权边，只能SPFA了。 However so，这里要用一个江湖人称“SLF”的优化，即当前节点到起点距离小于队首的时候，将此点插入队首，否则，正常插入队尾。感觉这种优化可能被用到的机会很少，但很可能正...

2020-09-10

3 1123

网格图来自专栏

题目分析我的第一个想法是bfs(QwQ),不用说，肯定凉凉。思考，对于一个点( i , j )，如果和小B的切比雪夫距离大于D，那么肯定可以转移到 ( i , j )的四个方向，也可以停留原地。但是如果小于等于D时，肯定只能单方向转移或是停留原地这样我们就可以写出dp方程了设f[ t...

2020-09-09

2 828

Working Out 来自专栏

翻译(口胡) 有一个n*m大小的健身房，每走到一个点(i,j)，都会消耗a[i][j]大小的卡路里，小西从(1,1)出发走到(n,m)，只能向右走或向下走，小瓜从(n,1)出发走到(1,m),只能向右走或向上走,他们两人决定在某一个点会面且只进行一次会面，那个点的卡路里不计入总卡路里。求出小西...

2020-09-09

3 695

牛客挑战赛42 A-小睿睿的序列来自专栏

前言初，遇题甚恐，不知何以解之。一暴以试，得AC，作此篇分析别学数据结构学傻了我们对于每一个点，可以向左扩展最长能满足条件的区间，然后再向右扩展。但是如果不作些许操作，万一这个序列是10000个1，这样跑就是n^2，直接飞起(但是数据不太强，也可以过)。于是可以记录一个lm[i],r...

2020-09-09

3 630

牛客小白月赛27 B-乐***对来自专栏

前言初见此题，便一贪为敬，不曾想，数据过强，需dp，作此篇，解此题QwQ 分析可以发现，如果这个人要加入团队，一定是和[1,i],[2,i]...[i-a[i],i]这些人组队，并且当前的a[i]要小于等于i，那这里就可以记下一笔 dp[i]=max(dp[1~(i-a[i])])+...

2020-09-08

8 649

Tree 来自专栏

翻译(qwq,看了好久的题) 输入n组数据,p,x,y,将其处理为x^=las,y^=las,las是上一次输出的答案，初始为1 1. 1 x y 将一个权值为y的新节点加到x节点的后面 2. 2 x y 求从点x到根节点的路径上求出最长的不下降子序列，且满足它的和不大于y...

2020-09-05

3 649

牛客IOI周赛18-普及组来自专栏

A 数字计数分析较为基础，因为要最大最小，次大次小，可以先想到排序，但是不要忘了，数值中有重复的，所以还要去重。去重的方法有两种，一种是直接调用unique函数，另一种是遍历一遍将出现一次的计入数组 int main() { scanf("%d",&n); ...

2020-09-05

6 721

Abracadabra 来自专栏

前言看到这道题，如果范围稍小一点，可以尝试将两串构造出来，然后连在一起，运用后缀排序求出hei数组进行求解，但很可惜的是，l和r太大了。思考我们先手造一下串1 a2 aba3 abacaba4 abacabadabacaba...会发现中点左右的串是一样的，比如[1,7...

2020-09-03

4 774