Marco.C

分类

关于博主(1) 未归档(2) 算法专题(2) 题解(22)

/ 注册

全部文章（共27篇）

[Codeforces 547C] Mike And Foam 莫比乌斯反演

F(i)=sigma(i|d,f(d))=C(g(i),2),g(i)是现在的i的倍数的数量,f(i)=sigma(i|d,miu(d/i)*F(d))所求即为f(1)的值.动态维护g(i)即可. Code： #include <bits/stdc++.h> #define ll ...

2017-06-14

0 502

[Codeforces 235E/236B] Number Challenge 莫比乌斯反演

题目链接：http://codeforces.com/problemset/problem/235/E 题意：d(n)是n的约数个数函数，求值：sigma(i=1..a,j=1..b,k=1...c,d(i*j*k))，a,b,c<=2000. 236B作为一个si...

2017-06-14

0 586

[Codeforces 809E] Surprise me! 莫比乌斯反演+虚树

题目链接： http://codeforces.com/contest/809/problem/E E. Surprise me! Tired of boring dates, Leha and Noora decided t...

2017-06-14

0 469

[Codeforces 674F] Bears and Juice dp+巧妙的meet in the middle优化

题目链接题解：此题是最大值问题，而且又有"最优"这样的字眼，考虑用dp求解，考虑最优策略，无需关注每一次每个选择具体是什么样的，因为是最优，所以每轮游戏中，不同的被ban掉的集合所对应的可能的a值集合应该不存在交集，...

2017-06-11

0 389

[Hackerrank题目选做] 出租车司机问题数据结构+树分治

题目链接题目大意：给一棵树，每条边有两个权值ai和bi，当路径上sigma(ai)和sigma(bi)都不超过限制la,lb时，点对(i,j)可达，求不可达的无序点对(i,j)的数量。数据范围：N&l...

2017-06-08

0 568

[Codeforces 814E] An unavoidable detour for home DP+BFS树+组合数学

题目链接 liu_cheng_ao大爷写的民间题解注意：以下内容打大部分都是对liu_cheng_ao大爷题解的转述(但是可能复杂度并没有那么优秀), 因为博主太菜，并没有什么自己思考的能力(智力-=2) 题解：因为每条边的权值相等，所以考虑bfs的过程， ...

2017-06-08

0 372

[Codeforces 814D] An overnight dance in discotheque 树形dp,贪心

题目链接题解：这道题，首先可以发现，圆与圆关系只有内含与外离，所以可以建立出一个树形结构，每个圆的父亲是与这个圆半径相差最小且包含这个圆的圆，这样，整个一张图形成了一个森林，可以将圆按半径排序后O(n^2)建立出...

2017-06-08

0 389

Matrix-Tree定理(2)----矩阵树定理

那么，现在就可以进入正题了-------->矩阵树定理(Matrix Tree Theorem) 不知道矩阵行列式等线性代数知识的，请左转：点击打开链接 Part 1 Matrix Tree定理引入几个概念：一个图的邻接矩阵G：对于无向图的边(u,v)，G[u][v]++,G[...

2017-06-06

0 778

[Hackerrank题目选做] Random Number Generator 二分+数学+猜结论

题目链接: https://www.hackerrank.com/challenges/random-number-generator-1 题解: 假设1-N产生的概率分别为p[1],....p[N]，则期望得分为sigma(i=1....n,j=i....n,p[i]*p...

2017-06-05

0 692

[Hackerrank题目选做] Mathematical Expectation伪题解

题目链接: https://www.hackerrank.com/challenges/mathematical-expectation 题解: 这个数学期望的题很大的样子，本菜鸡可能有些懵逼啊...... N<=10^9是怎么回事啊？给出的函数怎么那么鬼畜啊？ ...

2017-06-05

0 479