51Nod 1293 球与切换器 DP分类
基准时间限制：1 秒 空间限制：131072 KB有N行M列的正方形盒子。每个盒子有三种状态0, -1, +1。球从盒子上边或左边进入盒子，从下边或右边离开盒子。规则：如果盒子的模式是-1，则进入它的球从下面出去。（方向变为向下）如果盒子的模式是+1，则进入它的球从右面出去。 （反向变为向右）如果盒...
51nod 1366 贫富差距（flody）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1366题意：思路：如果不是一个连通块的话，肯定是无穷大的。用floyd求出两两之间的最短路，然后在这些最短路中选最长的*d即可。 #include<iostream&g...
51Nod 1256 乘法逆元 扩展欧几里得
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。Input输入2个数M, N中间用空格分隔（1 <= ...
51nod 1202 子序列个数
1202 子序列个数 题目来源： 福州大学 OJ基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1&...
51Nod 1753 相似子串
题目大意:两个字符串相似定义为：1.两个字符串长度相等2.两个字符串对应位置上有且仅有至多一个位置所对应的字符不相同给定一个字符串，每次询问两个子串在给定的规则下是否相似。给定的规则指每次给出一些等价关系，如‘a'=’b'，‘b'=’c'等，注意这里的等价关系具有传递性，即若‘a'=’b'，‘b'=...
51nod 1237 最大公约数之和 V3【欧拉函数||莫比乌斯反演+杜教筛】
用mu写lcm那道卡常卡成狗(然而最后也没卡过去，于是写一下gcd冷静一下首先推一下式子\[\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\]\[\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{n}[gcd(i,j)==d]d\]\[\sum...
51nod 1227 平均最小公倍数【欧拉函数+杜教筛】
以后这种题能用phi的就不要用mu…mu往往会带着个ln然后被卡常致死把题目要求转换为前缀和相减的形式，写出来大概是要求这样一个式子：\[\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{j}{gcd(i,d)}\]注意j的限制是i\[\sum_{d=1}^{n}\sum_{i=1...
【学术篇】51nod 1238 最小公倍数之和
这是一道杜教筛的入(du)门(liu)题目...题目大意求\[\sum_{i=1}^n\sum_{j=1}^nlcm(i,j)\]一看就是辣鸡反演一类的题目, 那就化式子呗..\[\sum_{i=1}^n\sum_{j=1}^nlcm(i,j) \\=\sum_{i=1}^n\sum_{j=1}^n...
51Nod 1238 最小公倍数之和V3
题目传送门分析：现在我们需要求：\(~~~~\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)\)\(=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{i ~\cdot ~j}{gcd(i,j)}\)\(=\sum_{d=1}^{n}d\sum_{i=1}^...
51nod 1244 莫比乌斯函数之和 【杜教筛】
51nod 1244 莫比乌斯函数之和莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下：如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。如果...
51Nod 1007 正整数分组 | DP （01背包）
Input示例512345Output示例1分析：2组的差最小，那么每一组都要接近sum/2,这样就转化成了普通的0 - 1背包了#include <bits/stdc++.h>using namespace std;typedef long long LL;#define rep(i,...
51Nod 1007 正整数分组（01背包）
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。Input第1行：一个数N，N为正整数的数量。第2 - N+1行，N个正整数。(N <= 100, 所有正整数的和 <= 10000)Outp...
51Nod 1007 正整数分组 -简单DP
题意：将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。N<=100 sum<=10000想了个N*sum的lowDP网上还有背包做法，很神奇最简单的我觉还是扫一遍，set作为答案暴力更新 #...
[51nod] 1007 正整数分组 dp
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。Input第1行：一个数N，N为正整数的数量。第2 - N+1行，N个正整数。(N <= 100, 所有正整数的和 <= 10000)Outp...
51nod 1007 正整数分组
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。Input第1行：一个数N，N为正整数的数量。第2 - N+1行，N个正整数。(N <= 100, 所有正整数的和 <= 10000)Outp...
（DP）51NOD 1007正整数分组
将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。输入第1行：一个数N，N为正整数的数量。第2 - N+1行，N个正整数。(N <= 100, 所有正整数的和 <= 10000)输出输出这个最...
[51nod 1847]奇怪的数学题
【 51nod 1847 】奇怪的数学题题目 点这里看题目。分析 是挺奇怪的...... 以下定义质数集合为\(P\)，\(p_i\)为第\(i\)个质数。 定义\(mp(x)\)为\(x\)的最小质因子，则可以得到：\[sgcd(a,b)=\frac{\gcd(a,b)}{mp(\gcd(...
51NOD 1222 最小公倍数计数 [莫比乌斯反演 杜教筛]
1222 最小公倍数计数题意：求有多少数对\((a,b):a<b\)满足\(lcm(a,b) \in [1, n]\)\(n \le 10^{11}\)卡内存！枚举\(gcd, \frac{a}{gcd}, \frac{b}{gcd}\)，然后\(\mu\)代入，就是\[\sum_{d=1}^...
【51nod】1222 最小公倍数计数 莫比乌斯反演+组合计数
【题意】给定a和b，求满足a<=lcm(x,y)<=b && x<y的数对(x,y)个数。a,b<=10^11。【算法】莫比乌斯反演+组合计数【题解】★具体推导过程参考：51nod1222 最小公倍数计数过程运用到的技巧：1.将所有i和j的已知因子提取出来压缩...
51nod 1965 奇怪的式子 —— min_25筛
题目：http://www.51nod.com/Challenge/Problem.html#!#problemId=1965推式子就同这里：https://www.cnblogs.com/yoyoball/p/9196092.html一开始想设 \( g(n,j) = \sum\limits_{i...