精神病科黄主任

分类

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篇文章 1987人学习

4篇文章 1059人学习

全部文章（共204篇）

小A买彩票来自专栏

线性DPdp[i][j]表示前i张彩票中奖j元的方案数那么易得转移方程dp[i][j] += dp[i-1][j-k] 其中1≤k≤4 k≤j边界为dp[0][0]买n张彩票，每张彩票有四种情况，总的方案数就是sum=4^n所以计算出来ans=sum(dp[n][k]) 其中k>=3n答案就...

2020-06-23

10 1204

签到题

B-签到题题意n个数，生成一个长度为n的排列，并且有n-1种数，问有多少种方案。思路：n个数，选择n-1种，也就是有1个数字不选，那么有n种方案。对于每种方案，要从n-1个数里面，选择一个重复的数字，有n-1种方案。此时对于每种方案，长度都是为n的序列，考虑多重集合的全排列方案数。因为只有一个数是...

2020-06-22

1 726

ar采蘑菇

D-ar采蘑菇题意：起点在(0,0),目标在(n,m),指定k种行走方案。问走到终点最多能使用多少种方案。思路：范围很小，可以搜索也可以状压dp。只用了状压的做法。dp[i][j][k] 表示走到i，j，可以用q种行走方式走到(k是这q种行走方式的二进制串)枚举每一点的每一种状态，考虑从前面哪个状...

2020-06-22

2 756

Forsaken喜欢数论来自专栏

题意：求1~n中每个数的最小质因数的和。思路：素数筛即可，把每个数的第一个质因数加到答案当中。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int a[30000005]; int main() ...

2020-06-22

0 956

Three States 来自专栏

题意有一个n*m的地图，地图上有三个国家和一些道路(路没修就不能走)，还有一些障碍，每个国家都是一个联通块，现在可以在道路上进行修路，让路可以走，现在问让三个国家联通最小需要修多少条路。思路对于每个国家都进行bfs，算出每个国家到每个点的最短距离。三个国家联通，枚举联通的一点即可。所以枚举所有不是...

2020-06-22

0 728

Supermarket 来自专栏

考虑以过期时间升序排序。维护一个价值的小根堆。每次都将商品丢入到堆里面，判断当前堆中的个数是不是大于过期时间，是的话，弹出堆顶(价值最小的)。这样最后堆中剩余的就是规定天数内能获得的最大收益 #include<bits/stdc++.h> using namespace std; typ...

2020-06-17

0 646

字符串来自专栏

双指针(尺取法) 双指针(快慢指针)即可。右指针先走，一直到满足条件后，维护一下长度的最小值，然后左指针开始右移，直到不满足子串含有所有小写字母，右指针继续右移动。总的复杂度来说，右指针右移动n次，左指针右移也是n次。复杂度是On #include<bits/stdc++.h> usi...

2020-06-15

0 788

扑克牌来自专栏

有n种牌，和一种万能牌，每一套牌由n种牌各一张组成，在一套牌中万能牌只能代替其中任意一种牌，最多只能用一次。问最多能由多少套牌。考虑二分。如果二分的答案x，可以凑到x套，那么可能能凑到更多，如果凑不到x，那么只能凑的少一点，满足单调性。对于二分check来说，对于牌的个数大于等于x的，那么每套都...

2020-06-10

7 970

小A与小B 来自专栏

分别对两个人进行bfs 计算出到达每个点的最短时间然后枚举两个人都能达到的点，最晚到的那个人的时间就是在这个点的相遇时间。因为要求时间最小，所以总体维护一个最小值即可对于判断点两个人是不是能同时达到，应该判断这个点两个人是不是能在有限时间内到，而不是这个点是不是障碍比如1 3C#D答案显然是NO 不...

2020-06-07

1 913

Contest 来自专栏

树状数组+排序 A比B的一场排名高，并且B也有一场的排名比A高那么对第一场排序后，就保证了后面的排名比前面的排名高，这样只需要统计有多少个数对(a[i],a[j]) 满足 i<j && a[i]>a[j] 这不就是求逆序数对吗。所以我们对任意两场求逆序数对即可。以第一场...

2020-06-07

0 779