精神病科黄主任

分类

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篇）

【每日一题】逆序对来自专栏

考虑从n个位置任取两个，前面位置放1，后面位置放0.所以这是一个组合数n个位置固定了两个位置了，还剩下n-2个位置，每个位置可以放0或者1，是个幂级数所以答案就是进行的除法运算时候，因为模数是个质数，直接用费马小定理即可。当然了，注意特判n=1的情况，因为对于快速幂只能进行非负数，而幂级数的指数部分...

2020-04-15

3 860

牛客算法周周练2

A看到要去前导0，直接字符串模拟了，倒着的时候从第一个不为0的数字开始计算这个数字大小，加上原来数字即可 #include using namespace std; typedef long long ll; int main(){ char s[10]; cin>>s; ...

2020-04-14

4 991

【每日一题】Treepath 来自专栏

题上要求找长度为偶数的路径。根据常识可知偶 = 偶 + 偶 = 奇 + 奇。所以我们可以考虑深度，算出每个节点的深度，深度为偶数的和偶数组合，深度奇数的和奇数组合。因为x到y和y到x属于一条路，不考虑顺序，所以答案是个组合数。也是就其中a、b分别为深度为奇、偶数的节点个数注意结果炸int #inc...

2020-04-14

0 653

【每日一题】Xorto 来自专栏

前缀异或和一边计数即可。枚举i为已经计数的区间右边界，然后以i为左端点，看后面的区间有多少个区间异或和是已经计数的加上即可。对于区间右边界的更新，假设现在已有a、b、c 现在加入一个d，产生的贡献就是[a,d]、[b、d]、[c、d]、[d,d]新增的四个区间根据a^b=c b=a^c 可以用...

2020-04-13

0 825

JOI 2019-Final比赛A、B

。。只会AB签到 A：就是说对于每个字符为J的位置，如果他同一列下方有I，同一行右边有O，答案就加1那么直接对每行维护字符O的后缀和，对每列维护I的后缀和遍历字符集，为J的时候就是两个相乘即可。 #include<bits/stdc++.h> using namespace std;...

2020-04-12

1 663

【每日一题】 Accumulation Degree 来自专栏

思路：一开始的想法就是直接每个点去dfs树形dp后取最大，复杂度n^2看到数据范围后想法直接见祖宗了然后就去学了一下二次扫描和换根法。简单介绍一下。其实第一步就是上面说的dfs树形dp。随便选取一个点为根，假设我们选1，则dp[root]表示以root为根的子树的最大流量。对于root的子节点s...

2020-04-12

0 676

树学【重心性质 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