2018年6月13日
Sigma Function LightOJ - 1336 （约数和为奇数）
摘要： 题意： 求1-n中约数和为偶数的数的个数 记住一个定理：。。。平方数 及其 平方数的2倍 的约数和为奇数 then。。。。减啦 证明： 。。。。我jiao着人家写的很详细，so 看看人家写的吧！ 转载至：https://blog.csdn.net/Rain722/article/details/64 阅读全文
posted @ 2018-06-13 22:05 WTSRUVF 阅读(250) 评论(0) 推荐(0)
算术基本定理
摘要： （1）一个大于1的正整数N，如果它的标准分解式为： ，那么它的正因数个数为 对于这个式子 如果我们想要奇因子的个数 那么在primes[i] % 2 != 0时再算。。==0时continue就好了 偶因子同理 代码实现： for(i = 0; i < cnt && prime[i] * prime 阅读全文
posted @ 2018-06-13 16:46 WTSRUVF 阅读(372) 评论(0) 推荐(0)
LightOJ - 1341 Aladdin and the Flying Carpet （算术基本定理）
摘要： 题意： 就是。。。。求a的所有大于b的因子有多少对 算术基本定理求 所有因子 阿欧。。。偷张图。 注意范围 就好 。。。。。 解析： 在1 -1012的范围内求大于b的所有a的因子的对数（有几对） 就等于 在1 -1012的范围内求出a的所有因子 除二 减去 在1 - （b-1）的范围内a的所有因子 阅读全文
posted @ 2018-06-13 16:03 WTSRUVF 阅读(198) 评论(0) 推荐(0)
求具体质数和质因子
摘要： //求具体质数void init() { int cnt = 0; mem(vis,0); for(int i=2; i<maxn; i++) if(!vis[i]){ primes[cnt++] = i; for(LL j=(LL)i*i; j<maxn; j+=i) vis[j] = 1; } 阅读全文
posted @ 2018-06-13 10:13 WTSRUVF 阅读(326) 评论(0) 推荐(0)
LightOJ - 1356 Prime Independence (二分图 最大独立集 素数打表)
摘要： 题意： 给你一个集合，让你从这个集合中挑选出几个数，使得这几个数中任意两个数相除后的值不能为素数 即挑选出来的这几个数不能互相冲突 最大独立集 = 所有点数 - 最大匹配数 呵。。呵。。。原先用的二维数组来标记 呵。。呵。。。。呵。。呵。。ER。。。MLE vector 大法好！ orz mmp。。 阅读全文
posted @ 2018-06-13 09:59 WTSRUVF 阅读(332) 评论(0) 推荐(0)
2018年6月12日
Hopcroft-Carp 算法模板 自用
摘要： #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 500, INF = 0xfffffff; int cx[maxn], cy[maxn], dx[maxn], dy[maxn], used[maxn], g[ma... 阅读全文
posted @ 2018-06-12 13:00 WTSRUVF 阅读(319) 评论(0) 推荐(0)
2018年6月10日
（转）二分图匹配匈牙利算法与KM算法
摘要： 匈牙利算法转自于： https://blog.csdn.net/dark_scope/article/details/8880547 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广 阅读全文
posted @ 2018-06-10 20:56 WTSRUVF 阅读(514) 评论(1) 推荐(1)
LightOJ - 1074 Extended Traffic（标记负环）
摘要： 题意：有n个城市，每一个城市有一个拥挤度ai，从一个城市u到另一个城市v的时间为:(au-av)^3，存在负环。问从第一个城市到达第k个城市所话的时间，如果不能到达，或者时间小于3输出？否则输出所花的时间 . 解析：spfa判断负环 然后dfs标记负环 如果某个在环内 || d[e,v] == IN 阅读全文
posted @ 2018-06-10 09:17 WTSRUVF 阅读(163) 评论(0) 推荐(0)
2018年6月9日
最短路类型 （至今做过的）
摘要： 1、普通最短路（单向 双向 去还得回来 。。等等 ） 2、判断环路 （正环 负环）（dfs标记环路） （解法：spfa 。。。在进队后判断if(++ans[e.v] > n ) return 1; 3、层次网络 (解法：因为分层，所以把层抽象为一个点，然后把本层的各点与层连线， 然后层与层之间连线 阅读全文
posted @ 2018-06-09 21:40 WTSRUVF 阅读(342) 评论(0) 推荐(0)
2018年6月8日
POJ - 3159（Candies）差分约束
摘要： 题意： 就是分糖果 然后A觉得B比他优秀 所以分的糖果可以比他多 但最多不能超过c1个， B又觉得A比他优秀。。。。 符合差分约束的条件 设A分了x个 B分了y个 则x-y <= c1 , 根据其它的关系可以找出c2 c3 ···· 如果不懂差分约束的请 点击 所以构成不等式组：x-y <= c1 阅读全文
posted @ 2018-06-08 21:52 WTSRUVF 阅读(155) 评论(0) 推荐(0)