Marco.C

题解

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

/ 注册

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

[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

[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

[Hackerrank题目选做] Jim And Challenges

题目链接: https://www.hackerrank.com/challenges/jim-and-the-challenge 题目大意: 给定d维空间的n个点，每个点有权值h[i]，求sigma(i=1...n,j=i+1...n,h[i]*h[j]*dis(i,j))的值，其中dis(i...

2017-06-05

0 504

[Hackerrank题目选做] Tree Pruning

题目链接:https://www.hackerrank.com/challenges/tree-pruning 题解: 先吐槽一下数据，非常无脑的O(nk^2)的代码加了一点小优化就0.12s闪过，惊讶.jpg 先上O(nk^2)的AC代码: #include <...

2017-06-02

0 497

[Hackerrank题目选做] Kundu and Tree 组合数学

题目链接: https://www.hackerrank.com/challenges/kundu-and-tree 题目大意: 给一棵n个点的树，每条边被染成黑色或红色，求三元组(x,y,z)的对数，使得(x,y),(y,z),(x,z)最短路径中都至少有...

2017-06-01

0 516