精神病科黄主任

题解

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

/ 注册

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

树学【重心性质 or 树形dp换根】

写两种做法吧。第一种是直接重心性质，第二种是树形dp+换根。一、利用重心性质：下面是树的重心的性质：1.树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。3.一棵树添加或者删除一个节点，树的重心...

2020-04-12

0 748

牛客练习赛61

A-打怪因为我先手，我的攻击力如果大于怪物的血量，那么我就能杀无数个，输出-1即可考虑到我先手，所以先把怪物的血扣掉一次，然后就是怪物先手了，计算出我的血量能够让怪物打我几次，以及我需要打几下怪物才能死即可。 #include <bits/stdc++.h> using namespac...

2020-04-10

4 610

Rabbit的工作(1)

思路：dp[i][j][k] 表示对于前i天一共工作了j天现在连续工作了k天的最小花费滚动数组优化掉第一维(不然会MLE)if(s[i]=='0') 为0只能休息dp[j][0]=min(dp[j][0],dp[j][k])if(s[i]=='1')dp[j][0]=min(dp[j][0],d...

2020-04-10

5 956

【每日一题】Running Median 来自专栏

思路经典题，比较简单因为要求中位数，所以拿两个优先队列去维护，一个大顶堆，一个小顶堆大顶堆维护比较小的那一半，堆顶就是中间数了。小顶堆维护比较大的那一半，堆顶自然就是中间数。如果序列是奇数个的时候，不妨把多的一个放在大顶堆内，那么答案就是大顶堆的堆顶了当两个堆都不为空时候，边插入，边比较堆顶大小即...

2020-04-08

0 661

牛客算法周周练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