精神病科黄主任

题解

cf(33) dfs(3) dp（动态规划）(4) poj(1) 二分(7) 位运算(1) 双端队列(1) 娱乐(1) 并查集(3) 快速幂(1) 思维(1) 拓扑排序(1) 数学(11) 数论(2) 暴力(8) 最短路(1) 未归档(3) 栈(1) 预处理优化(3)

/ 注册

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

【每日一题】Shortest Path 来自专栏

思路：题中给定的是一棵树，要求把分成n/2对让权值最小看一下范围在加上是一棵树所以做法应该是dfs 复杂度为on直接去考虑贡献设当前父节点为x 如果x的子树(包括x自己)的大小是个奇数意味着什么呢因为要两两配对，那么意味着这奇数个数中，一定有一个数要有外界配对那么他就一定会经过x到x的父节...

2020-04-02

1 922

【每日一题】合并回文子串来自专栏

有一说一这题对我来说难度还是挺大的，看了大佬的题解才懂得，确实还是个dp小白思路：用dp[i][k][j][l]表示第一个串从i到k位置和第二个串从j到l位置是不是可以组成回文串是的话值为1，否则为0 那么考虑转移有2*2种 (两个头两个尾) a[i]==a[k] dp[i][k][j][...

2020-04-01

0 646

【每日一题】月月查华华的手机来自专栏

思路：m次询问看字符串是不是给定字符串的子序列暴力的做法就是直接两个循环去匹配复杂度m * strlen(a) * Σ(strlen(b)) 这复杂度显然是不可接受的那么考虑一下预处理cnt[i][j] 表示当前位置为i下一个字符为j的位置倒着遍历字符串即可预处理一遍之后，每次循环跑的次数就...

2020-04-01

3 832

【每日一题】Rinne Loves Edges 来自专栏

思路：注意题中的M M=N-1 并且图联通说明这是一棵树然后题意就是说让重要点s 到不了其他度为1的点度为1的点那不就是叶子节点嘛所以我们只要从点s开始dfs，计算出到叶子节点的路上的最短的边权加起来即可复杂度O(n)用dp[x]表示节点x到每个叶子节点的最小边权值那么dp[x]+=mi...

2020-03-31

1 973

【每日一题】tokitsukaze and Soldier 来自专栏

思路：这题对于每个士兵多了一个si的限制，也就是对要选择的人数有了限制，如果没有这个限制的话，我们肯定是直接按照武力值从大到小去选取，有了这个限制就不行了考虑把si从大到小排序这样的话对于si就是不升序的排列，那么我们能选取的个数就是取决于已经选择的人的si限制了所以对于每个vi我们先加进去到要选...

2020-03-31

1 693

【每日一题】滑动窗口来自专栏

思路:最暴力的做法就是模拟过程，枚举每一个长度为k的区间，然后遍历一遍找最值，复杂度为n^2这题n的范围到了1e6 n^2 在规定时间内是跑不完的所以这题要用数据结构优化什么样的数据结构呢对于当前区间为l到r那么往后移动了之后区间变为了 l+1 到 r+1也就是a[l]被弹出 a[r...

2020-03-30

1 728

牛客练习赛60 (前四题)

A让求一个和式的值，按照和式内容模拟要两个for，n^2复杂度会TLE，所以显然是不可取的那么因为是位运算& 所以我们考虑去按位算贡献，对于每一位，我们会进行k*(k-1)次计算也就是排列数A(k,2) 那么该位对答案的贡献就是就是(1<<i) * k * (k-1) 其中...

2020-03-27

1 721

数学考试来自专栏

链接：https://ac.nowcoder.com/acm/problem/15553来源：牛客网题目描述今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续...

2020-03-26

70 1934