首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
51nod专题
【51nod】算法马拉松4 F 移数字 【快速求N!%P】【FFT】
传送门:【51nod】算法马拉松4 F 移数字 涉及知识点:多项式求逆,多项式除法,多点插值,阶乘取模。 对于N!%P,复杂度为 O(N−−√log2N−−√) O(\sqrt N \log^2\sqrt N)。 但常数巨大,和暴力算实际复杂度只相差常数= = 这个是可以扩展到组合数取模的~ my code: my~~code: #include <stdio.h>#includ
阅读更多...
独木舟(51Nod-1432)
题目 n个人,已知每个人体重。独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟? 输入 第一行包含两个正整数n (0<n<=10000)和m (0<m<=2000000000),表示人数和独木舟的承重。 接下来n行,每行一个正整数,表示每个人的体重。体重不超过1000000000,并且每个人的体
阅读更多...
51nod 1847 奇怪的数学题
Description 给出 N,K ,请计算下面这个式子: ∑Ni=1∑Nj=1sgcd(i,j)k 其中,sgcd(i, j)表示(i, j)的所有公约数中第二大的,特殊地,如果gcd(i, j) = 1, 那么sgcd(i, j) = 0。 考虑到答案太大,请输出答案对2^32取模的结果. 1≤N≤109,1≤K≤50 样例解释: 因为gcd(i, j)=1时sgcd(i,j)
阅读更多...
51nod-1050 循环最大字段和
N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。 例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。 Input 第1行:整数序列的长
阅读更多...
51Nod 1163 最高的奖励(贪心+优先队列 并差集)
题目链接:最高的奖励 题目大意 有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。 Input 第1行:一个数N,表示任务的数量(2 <= N <= 50000) 第2 - N + 1行,每行2个数
阅读更多...
51Nod 1376 最长递增子序列的数量(dp+树状数组)
题目链接 最长递增子序列的题做过不少,让求数量的还是第一次,O(n^2)的代码很好写,但数据范围50000,故无情超时,想了很久,总算有所得。 时间: O(nlog(n)) 空间: O(2*n) 思路 O(n^2)的思路中,每次求以第i个数结尾的最大长度和记录总数都要对前i-1个数进行遍历比较,如果能把这个比较过程转化为对前i项对求和,就可以用树状数组或线段数进行求和优化了。 重
阅读更多...
51Nod 1022 石子归并 V2 (划分型dp四边形不等式优化)
石子归并以前做过好几次,是经典划分型dp题之一,一直用的O(n3)的正常dp方法,也从未想过该怎么去优化它。 直到昨天做这道题,n的范围由往常的100改为了1000,老方法 一直超时,苦不堪言,搜到有个四边形不等式的优化方法,看帖子,画式子,拉着学长帮忙推导,总算是大概弄明白了一点。 dp(i,j) = min(dp(i,k)+dp(k+1,j)) + w(i,j);(i < j
阅读更多...
51nod 1264 线段相交(几何)
1264 线段相交 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 给出平面上两条线段的两个端点,判断这两条线段是否相交(有一个公共点或有部分重合认为相交)。 如果相交,输出"Yes",否则输出"No"。 Input 第1行:一个数T,表示输入的测试数量(1 <= T <= 1000)第2
阅读更多...
51nod 1174 区间中最大的数(RMQ)
1174 区间中最大的数 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 给出一个有N个数的序列,编号0 - N - 1。进行Q次查询,查询编号i至j的所有数中,最大的数是多少。 例如: 1 7 6 3 1。i = 1, j = 3,对应的数为7 6 3,最大的数为7。(该问题也被称为RMQ问题)
阅读更多...
51nod 1134 最长递增子序列(动态规划)
1134 最长递增子序列 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的) 例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。 Input 第1行:1个数N,N为序列的长度(
阅读更多...
51nod 1073 约瑟夫环 (数学递推)
1073 约瑟夫环 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 N个人坐成一个圆环(编号为1 - N),从第1个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。 例如:N = 3,K = 2。2号先出列,然后是1号,最后剩下的是3号。 Input 2个数N和
阅读更多...
51nod 1049最大子段和(dp)
1049 最大子段和 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 N个整数组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。 例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,
阅读更多...
51nod 1066 Bash游戏 (博弈)
1066 Bash游戏 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 有一堆石子共有N个。A B两个人轮流拿,A先拿。每次最少拿1颗,最多拿K颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N和K,问最后谁能赢得比赛。 例如N = 3,K = 2。无论A如何拿,B都
阅读更多...
51Nod-1082 与7无关的数【进制+打表】
1082 与7无关的数 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7,则称其为与7相关的数。求所有小于等于N的与7无关的正整数的平方和。 例如:N = 8,<= 8与7无关的数包括:1 2 3 4 5 6 8,平方和为:155。 Input 第1行:一个数T,表
阅读更多...
51Nod-1136 欧拉函数【数论】
1136 欧拉函数 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。例如:φ(8) = 4(Phi(8) = 4),因为1,3,5,7均和8互质。 Input 输入一个数N。(
阅读更多...
51Nod-1008 N的阶乘 mod P【模除】
1008 N的阶乘 mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 输入N和P(P为质数),求N! Mod P = ? (Mod 就是求模 %) 例如:n = 10, P = 11,10! = 3628800 3628800 % 11 = 10 Input 两个数N,P,中间用空格隔开。(N < 10000, P <
阅读更多...
51Nod-1046 A^B Mod C【快速模幂】
1046 A^B Mod C 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 给出3个正整数A B C,求A^B Mod C。 例如,3 5 8,3^5 Mod 8 = 3。 Input 3个正整数A B C,中间用空格分隔。(1 <= A,B,C <= 10^9) Output 输出计算结果 Input示例 3 5 8 Output示
阅读更多...
51nod 1005: 大数加法(含符号)
1005 大数加法 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 给出2个大整数A,B,计算A+B的结果。 Input 第1行:大数A第2行:大数B(A,B的长度 <= 10000 需注意:A B有可能为负数) Output 输出A + B Input示例 6893214758
阅读更多...
51Nod 1005 有负数的高精度加法
51Nod是个好地方啊 题意 51Nod基础题第二题,高精度加法,可能有负数。 解题 如果按照一般的高精度,我们发现要分情况讨论,还要写高精度加法和减法,代码实现有点烦。而初中数学里说,省略加号的和。也就是说,只有加法,没有减法。那么我们又没有办法在做高精度的时候也统一加减法?当然有咯,不然我写这博客干啥 那么到底怎么办呢? 我们还是以加法作为基准,统一加减法。我们知道,减去某个数,就是加上它的
阅读更多...
51nod 和为k的连续区间(map/暴力)
1094 和为k的连续区间 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 一整数数列a1, a2, ... , an(有正有负),以及另一个整数k,求一个区间[i, j],(1 <= i <= j <= n),使得a[i] + ... + a[j] = k。 Input 第1行:2个数
阅读更多...
51nod 1432 (贪心)
1432 独木舟 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 n个人,已知每个人体重。独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟? Input 第一行包含两个正整数n (0<n
阅读更多...
51nod 1092 回文字符串(LCS)
1092 回文字符串 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符,使之变为回文字符串。 例如:abbc 添加2个字符可以变为 acbbca,也可以添加3个变为 abbcbba。方案1
阅读更多...
51nod 1007 正整数分组(背包/dp)
1007 正整数分组 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 将一堆正整数分为2组,要求2组的和相差最小。 例如:1 2 3 4 5,将1 2 4分为1组,3 5分为1组,两组和相差1,是所有方案中相差最少的。 Input 第1行:一个数N,N为正整数的数量。第2 -
阅读更多...
51nod 1102单调栈
1102 面积最大的矩形 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注 有一个正整数的数组,化为直方图,求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3,对应的直方图如下: 面积最大的矩形为5,6组成的宽度为2的矩形,面积为10。 Input 第1
阅读更多...
51nod 5172(单调栈/思维)
1272 最大距离 题目来源: Codility 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注 给出一个长度为N的整数数组A,对于每一个数组元素,如果他后面存在大于等于该元素的数,则这两个数可以组成一对。每个元素和自己也可以组成一对。例如:{5, 3, 6, 3, 4, 2},可以组成11对,如
阅读更多...
51nod 1090 三个数和为0的问题
给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合,输出No Solution。如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则按照第二小的数排序。 Input 第1行,1个数N,N为数组的长度(0 <= N <= 1000)第2 - N + 1行:A[i](-10^9 <=
阅读更多...