zjnu_tjq

分类

未归档(3) 板子(2) 题解(104)

/ 注册

全部文章（共109篇）

小x的奇遇-adventure

小x的奇遇-adventure 题意：给定函数f(n),g(n),求 G k ( n ) G_k(n) Gk(n) f ( n ) = { 1 , n = 1 ∑ i = 1 n − 1 [ g c d ( i , n − i ) = = 1 ] , n > 1 f(n)=\begi...

2021-08-14

0 396

P3172 [CQOI2015]选数（莫比乌斯反演+杜教筛）

P3172 [CQOI2015]选数题意给定区间[L,H]，区间内n个数的最大公约数为k的方案书有多少个。即求 ∑ a 1 = L H ∑ a 2 = L H . . . ∑ a n = L H [ g c d ( a 1 , a 2 , . . . , a n ) = k ] \sum_...

2021-08-14

0 368

简单题（莫比乌斯反演+公式）

简单题题意：求： ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) φ ( i j ) μ ( i j ) \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\varphi(ij)\mu(ij) i=1∑nj=1∑mgcd(i,j)φ(ij)μ(ij...

2021-08-14

0 436

P3327 [SDOI2015]约数个数和 (莫比乌斯反演+公式)

P3327 [SDOI2015]约数个数和题意：设d(x)为x的约数个数，给定 n , m n,m n,m，求 ∑ i = 1 n ∑ j = 1 m d ( i j ) \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) i=1∑nj=1∑md(ij) Soluti...

2021-08-14

0 472

phi and phi（莫比乌斯反演+公式）

phi and phi 题意：求 a n s ( n ) = ∑ i = 1 n ∑ j = 1 n φ ( i j ) φ ( g c d ( i , j ) ) ans(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(ij)\varphi(gcd(i,j)) ...

2021-08-14

0 402

A Very Easy Math Problem（莫比乌斯反演）

A Very Easy Math Problem 题意：给定 n , x , k n,x,k n,x,k，求解： ∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g c d ( a 1 , a 2 , . ....

2021-08-14

0 321

最小圆覆盖（板子）

当点的顺序被打乱：时间复杂度： O ( N ) O(N) O(N) 空间复杂度： O ( N ) O(N) O(N) 否则，时间复杂度可能为 O ( N 3 ) O(N^3) O(N3) #include<bits/stdc++.h> using namespace std; con...

2021-08-14

0 580

补题清单

Contest - 2021-03-10 个人排位赛1 A-Marathon III B-Piggy Back C-Cow Jog III D-Learning by Example E-Crosswords F-Marathon I G-Marathon II H-Cow Jog I I-Gua...

2021-08-14

0 422

Sjekira（逆向思维+带权并查集）

Sjekira 题意：给了你n个点权，n-1条边（题目保证这个图是棵树），问你将这n-1条边都砍掉的花费和最小是多少。砍掉一条边的花费是这条边所连的两个联通块最大的点权之和。 Solution：因为要使最后砍完n-1条边之后的花费最小，可以贪心的知道，每次都是先将点权最大的点所连的边先...

2021-08-14

0 430

Needle(FFT)

Needle 题意：有三条栅栏，相邻之间的栅栏距离为1 unit，每条栅栏上都有若干个点（点的横坐标已知），问有多少中穿过栅栏的方案。 Solution：记第一个栅栏上的点为a[i],第二个为b[j]，第三个为c[k] 根据几何的性质（相似性质）可知，若一个针能穿过三个栅栏，那么a[i]...

2021-08-14

0 544