精神病科黄主任

题解

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

/ 注册

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

SQL18 小破站哪一类视频观看人数最多

比较基础，首先根据video_id字段连接两张表，然后根据video_type进行分组，之后就是统计出去重后的用户数量，然后根据去重数量逆序排列取第一个即可 SELECT b.video_type, COUNT(DISTINCT(user_id)) FROM user_view_tb AS a IN...

Mysql

2021-10-20

0 635

[HAOI2006]旅行COMF 来自专栏

题意：给了一个无向图，给了S和T两个点，问从S走到T的路径中，最大值比最小值的最小是多少思路：点只有500个，边只有5000个，所以支持O(m^2)判断S到T的话，我们可以用并查集维护联通性。类似最小生成树，对边权从小到大排序。枚举第一条边，然后对边一条条加进去，直到S能走到T时即可，这时候判断...

2021-01-14

1 809

E 解方程

移项后是个分数，分离常数项出来得到容易知道x一定大于b，所以就是看ab有多少个因子个数直接sqrt计算会TLE所以预处理出来1e6以内的素数即可 #include<bits/stdc++.h> using namespace std; typedef long long ll; cons...

2021-01-10

8 907

牛客挑战赛47(A、B、C)

A 那么对于最小得k就是(g-a1%g)%g 注意要排序 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+50; ll a[N]; int main(){ int...

2021-01-09

13 820

小M和天平来自专栏

题意：给一些石子，多次询问，问能不能测出所给重量思路：①考虑把重量放在单独一边，石子放在单独一边。这样就是一个01背包。②实际上重量那边也可以放石子，那么其实就是从①中的01背包中可以达到的状态，减去放在另一边的石子堆所以这里也是一个类似01背包的过程，枚举石子，然后枚举重量，要注意第二维循环按照从...

2021-01-08

1 890

2020牛客暑期多校训练营（第九场） Groundhog Chasing Death 来自专栏

题意：给出a、b、c、d、x、y，让求下列式子。思路：对于gcd(x,y)我们知道gcd(x,y)=p1 ^(min(n1,n2)) * p2 ^(min(n1,n2))....pk ^(min(n1,n2))p1、p2....pk是x和y的质因子，n1代表x中该质因子的个数，n2代表y中该质因子...

2020-09-10

0 782

2020牛客暑期多校训练营 (第二场) FakeMaxpooling(单调队列) 来自专栏

题意：给一个n * m的矩阵，其中a[i][j]=lcm(i,j) (lcm指最小公倍数)。再给一个k，求n * m的矩阵中，所有k阶矩阵中最大值之和。思路：二维滑动窗口。我们用ma[i][j]来表示第i行中，从第j-k+1个数到第j个数的最大值。即一个区间长度为k的最大值。先处理好每一行中的...

2020-09-10

1 772

第四场H-Harder Gcd Problem 来自专栏

题意：给出1-n的数字，让选择m对数字，让gcd(a_i,b_i)>1，让m尽可能大，并且输出这m对对应的数字。思路：整体的思路就是筛法+贪心。不过我代码写的比较复杂，比较low。。首先就是筛法，把n个数的质因子种类数，和最小质因数维护出来。cnt[i]表示i的质因子有多少种，mi[i]表示...

2020-07-20

6 965

多校第二场 B-Boundary 来自专栏

题意：给了n个点，让你自己随便定义圆心(圆心不要求是n个点的其中一个)和半径，要求这n个点有尽可能多的点在圆上，并且该圆经过坐标原点(0,0)。求满足的圆上的点最多有多少个。思路：n是2e3，复杂度应该要小于n^3。我们知道最少三点可以确定一个圆。因为圆要求经过原点(0,0)，所以考虑n^2枚举两...

2020-07-14

26 1060

珂朵莉的数列来自专栏

题意：求所有子区间的逆序数对的个数。思路：考虑贡献。假设存在逆序数对(a[i],a[j] (i<j)那么含有a[i]的区间的左边界L<=i,含有a[j]的区间的右边界R>=j。也就是逆序数对贡献的个数为i*(n-j+1)。我们可以枚举j，统计在j前面，有多少个数比a[j]大，计算他...

2020-07-02

0 969