精神病科黄主任

题解

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

/ 注册

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

【每日一题】糖糖别胡说来自专栏

对于这一位置的糖糖能存活，当且仅当他编号后面的另一个组的糖糖的最大值≤它对于发功，发功的作用会对1~i产生影响，也就是提高前面的能力值，我们大可以直接处理出来发功次数用完后的能力值。为什么可以这样？因为如果前面的糖糖会被提前干掉，发功产生的影响其实是对前面的都进行增加的，是不影响前面会被打掉的人，只...

2020-04-20

2 775

聚会

考虑二分答案。二分出来mid，那么对于绝对值≤mid的，我们不需要管他，因为他可以直接走到原点，在mid时间内一定可以到。那么对于剩下的呢？我们对于剩下的去找最大值max和最小值min，如果max - min <= 2 * mid,说明mid这个是满足答案的，那么就需要下降二分上界，至于一个门...

2020-04-17

4 655

【每日一题】二分图染色来自专栏

考虑只有一种颜色，对于选取i个节点每边有f[n]= 种那么两边的话就有ans=f[n]*f[n].这样是有重复的，考虑容斥结果就是但是这样复杂度需要n^2 这样就是on递推了 #include <bits/stdc++.h> using namespace std;...

2020-04-17

0 912

【每日一题】华华给月月准备礼物来自专栏

经典题。二分答案。二分木棍的值mid，遍历一次数组看得到的个数是不是≥所要求的k个，是的话，考虑提高二分下界，即l=mid否则说明mid过大，考虑下调二分上界，即r=mid #include<bits/stdc++.h> using namespace std; typedef long...

2020-04-16

0 554

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

考虑从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