现在位置: 首页 > 算法 > 文章
2017年04月30日 算法 ⁄ 共 926字 暂无评论
题目大意:给定n,求LCM(1,n)+LCM(2,n)+...+LCM(n,n) 枚举d=GCD(i,n),令F(n)为n以内与n互质的数之和 则ans=Σ[d|n]d*F(d)*n/d=nΣF(d) 现在就是F(n)的问题了 我们发现对于任意n>=3,如果x与n互质,那么n-x一定与n互质 故n以内与n互质的数能两两凑成和为n的数对,一共φ(n)/2对,故F(n)=n*φ(n)/2 注意n<=2时不满足上述条件,但是2满足上面那个式子,1就特判吧。。。 时间复杂度O(T√n) 很疑惑这种复杂度为何在SPOJ能卡过去。...
阅读全文
2017年04月29日 算法 ⁄ 共 5146字 评论关闭
题目大意:给定一棵树,每个节点有一个颜色,多次询问某条路径上颜色数量,强制在线 正解是块状数组,强制在线莫队会TLE到死,想AC这道题的不用看了 如果朴素的跑树上莫队其实并不难- - 但是强制在线 因此我们可以考虑强制在线莫队算法 将树分成O(n^1/3)块,每块大小O(n^2/3) 记录每两块之间的答案、每种颜色的出现次数和哪些点被记录到了答案中 每次查询先找到两端点所在块的端点的答案,然后暴力用莫队转移即可 空间复杂度O(...
阅读全文
2017年04月28日 算法 ⁄ 共 1213字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=3687 抽象了的01背包,不过第一个问题。。。。。。。 //#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> #include <bitset> using namespace std; /************************************************ Code By willinglive ******...
阅读全文
2017年04月28日 算法 ⁄ 共 2347字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=1068 一定要对题意理解透彻,不然就会像我一样一直wa 开始没有考虑一种很特殊的情况,就是开头会有M,wa了3组,70分 后来把DP全改了,但还是有点错误,90分 最后看了遍题,,,才AC、、、、、、 //#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <alg...
阅读全文
2017年04月28日 算法 ⁄ 共 1501字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=1222 好像在哪见过~~~~ //#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ////////...
阅读全文
2017年04月28日 算法 ⁄ 共 1528字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=1037 好难想啊 //#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ////////////////...
阅读全文
2017年04月28日 算法 ⁄ 共 2239字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=1096 最基础的斜率DP 我的推导&草稿: dp[i]:i建设工厂,那么之前所有费用的最小值 朴素方程:dp[i]=min{C[i]+dp[j]+P[j+1]*dis[j+1][i]+P[j+2]*dis[j+2][i]+...+P[i]*dis[i][i]} 求dp[n] 令d[i]=dis[1][i] dp[i]=min{C[i]+dp[j]+P[j+1]*(d[i]-d[j+1])+P[j+2]*(d[i]-d[j+2])+...+P[i]*(d[i]-d[i])} dp[i]=min{C[i]+dp[j]+(P[j+1]+P[j+2]+...+P[i])*d[i]-P[j+1]*d[j+1]...
阅读全文
2017年04月28日 算法 ⁄ 共 1560字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=1597 就是斜率的几何意义 //#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive Blog:http://willinglive.cf ****************************...
阅读全文
2017年04月28日 算法 ⁄ 共 2077字 评论关闭
http://www.lydsy.com/JudgeOnline/problem.php?id=2186 紧跟zky 3月份的步伐~~~~~~~~~~~~~~~~~ 1~n!与m!互质的数的个数(m<=n)  分为两部分:  1.1~m! 2.m!+1~n! Ans=phi[m!]*n!/m!    =m!*((p1-1)/p1*(p2-1)/p2*...*(pk-1)/pk)*n!/m!    =((p1-1)/p1*(p2-1)/p2*...*(pk-1)/pk)*n! 预处理 1.n! 2.((p1-1)/p1*(p2-1)/p2*...*(pk-1)/pk) //#define _TEST _TEST #include <cstdio> #include <cstring> #includ...
阅读全文
2017年04月27日 算法 ⁄ 共 2622字 评论关闭
Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:  左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和...
阅读全文