精神病科黄主任

分类

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

/ 注册

TA的专栏 60篇文章 0人订阅

56篇文章 1934人学习

4篇文章 1057人学习

全部文章（共204篇）

牛客算法周周练1

A注意题上说了，ai序列是不降序列，那么对于Σai * i来说，大的数自然是在后面更好啦。所以说至少移动k个位置，那么我们就只让他动k个位置，这样保证减少的数尽可能小，保证结果尽可能大。那么我们首先求出最开始的ans=Σai * i 然后对k+1后的枚举一个数字往前移动k位，对结果的影响就是：i-1...

2020-04-07

1 580

【每日一题】黑白树来自专栏

思路：看到树的题，第一想法往往就是先考虑dfs这题我们可以知道，叶子节点是一定要染色的，因为他染色是一个从叶子节点往父亲节点更新的过程。那么我们应该考虑dfs应该要维护什么？首先我们肯定是贪心的策略去做，就是我选了叶子节点开始染色，那么染过色的地方就尽量不要去选，这应该是最优策略。但其实这样是有错误...

2020-04-07

8 1017

【每日一题】城市网络来自专栏

思路：暴力的话复杂度很高，所以考虑倍增去找往上跳f[i][j]表示i节点往上跳能买的第1<<j个节点的位置跑一遍dfs处理出来所有点往上跳的可以购买的第j个位置在哪然后每次询问复杂度只要logn即可倍增应该先往大的跳，比如从1到5，应该从128，64，32，16，8，4，2，1 这样...

2020-04-07

0 582

【每日一题】树来自专栏

思路：我们知道树是联通的，即任意两点之间一定是可以到达的，那么题意等价能将这棵树分成多少个联通块，并且最多只能分解k个联通块那么其实这棵树的结构是怎么样的我们并不在乎只需要考虑当前节点和上一个节点是不是要在同一个连通块即可所以考虑dpdp[i][j]表示前i个节点分成j个联通块的方案数转移方程易得d...

2020-04-06

1 604

牛客OI周赛15-普及组

A题意其实有点迷(其实是自己读题没认真)就是只要问字符串是不是由若干个"mq"组成所以长度奇数的肯定就是No(不过数据貌似没有mqmqm这种？试了下竟然ac了)否则就去看奇数位置是不是m 偶数位置是不是q 都是的话就Yes 不然就No #include<bits/stdc++.h> u...

2020-04-04

3 615

【每日一题】数码来自专栏

思路：求l到r的个数转换为求1到r的个数减去 1到l-1的个数可以看到 l和r的长度长达1e9 如果暴力算每个的话光是枚举x就要1e9可能会想到枚举约数，但是这样也还不够，复杂度还是高的批爆枚举约数是肯定没错的，问题是考虑如何去优化可以考虑去枚举以x为最高位的区间的约数的个数比如求最高数码x...

2020-04-03

15 1338

【每日一题】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