搜索结果
查询Tags标签: 51nod,共有 13条记录-
51nod 模拟2
A. 直接pow,代码略 B 分子分母分开处理 \(a/b\)转移到\(\frac{\frac{a}{b}+\frac{b}{a}}{2} = \frac{a^2+b^2}{2ab}\) 然后\(a=a^2+b^2, b=2ab\)所以\(a+b=(a+b)^2, a-b = (a-b)^2\) 可以找规律完成递推 %:pragma GCC optimize(3) #include<bits/stdc++.h> using na…
2022/8/13 23:29:11 人评论 次浏览 -
[51nod : 2106] [位运算] 一个奇数次
一个奇数次 51nod 题目 \(Link\) 解析 这里采用的是位运算异或。 让 ans 每次都异或输出的数,因为 a ^ a = 0 的, 所以每次异或时出现偶数次的数就可以消掉(异或符合交换律)。 因为题目中指定只有一个数会出现奇数次,所以易证这个做法的正确性。 Code #include <b…
2022/2/18 23:23:02 人评论 次浏览 -
#原根,BSGS,扩欧#51nod 1038 X^A Mod P
题目 \(T(T\leq 100)\) 组询问在模 \(P\) 意义下给 \(B\) 开 \(A\) 次方根, 求出 \([0,P)\) 的所有解,\(P\) 是一个质数。分析 求出 \(P\) 的原根 \(G\),若 \(G^x\equiv B\pmod{P}\),这个 \(x\) 可以通过 BSGS 求出来。 那么 \(X^A\equiv B\pmod{P}\) 就可以转换成 \(…
2022/2/18 23:22:25 人评论 次浏览 -
队列复原 51Nod - 2151 java题解
题目描述: 小瓜现在让1到n这n个整数排成一列,但是他只告诉你每个整数的后面那个数是什么(最后一个整数的后面那个数是0),请你帮忙复原这个队列。 Input 第一行一个整数n(n<=100000),表示有n个整数。 接下来n行,每行两个数i,j,表示排在整数i后面的那个数是j。…
2022/1/24 14:04:31 人评论 次浏览 -
51Nod 2649 完全背包
题目链接:51Nod 2649 完全背包 题目大意:题解: 完全背包模板题。 #include <iostream> using namespace std;int dp[50010], v[110], c[110], n, V;int main() {cin >> n >> V;for (int i = 1; i <= n; ++i) {cin >> v[i] >> c[i];}f…
2021/7/26 6:08:08 人评论 次浏览 -
51Nod 2649 完全背包
题目链接:51Nod 2649 完全背包 题目大意:题解: 完全背包模板题。 #include <iostream> using namespace std;int dp[50010], v[110], c[110], n, V;int main() {cin >> n >> V;for (int i = 1; i <= n; ++i) {cin >> v[i] >> c[i];}f…
2021/7/26 6:08:08 人评论 次浏览 -
51Nod 1183 编辑距离
题目链接:51Nod 1183 编辑距离 题目大意: 题解: 设\(dp[i][j]\)为字符串\(A\)的前\(i\)个字符变成字符串\(B\)的前\(j\)个字符需要的最小操作数。 若字符串\(A\)的第\(i\)个字符与字符串\(B\)的第\(j\)个字符相等,则问题变成将字符串\(A\)的前\(i-1\)个字符变成字符串…
2021/7/26 6:07:23 人评论 次浏览 -
51Nod 1183 编辑距离
题目链接:51Nod 1183 编辑距离 题目大意: 题解: 设\(dp[i][j]\)为字符串\(A\)的前\(i\)个字符变成字符串\(B\)的前\(j\)个字符需要的最小操作数。 若字符串\(A\)的第\(i\)个字符与字符串\(B\)的第\(j\)个字符相等,则问题变成将字符串\(A\)的前\(i-1\)个字符变成字符串…
2021/7/26 6:07:23 人评论 次浏览 -
51Nod 1006 最长公共子序列Lcs
题目链接:51Nod 1006 最长公共子序列Lcs 题目大意:题解: 最长公共子序列模板题,设\(dp[i][j]\)为字符串\(A[1...i]\)与字符串\(B[1...j]\)的最长公共子序列长度,则状态转移方程为: \[dp[i][j] = max\{dp[i-1][j-1] + (A[i] == B[j]), dp[i-1][j], dp[i][j-1]\} \]用…
2021/7/26 6:07:19 人评论 次浏览 -
51Nod 1006 最长公共子序列Lcs
题目链接:51Nod 1006 最长公共子序列Lcs 题目大意:题解: 最长公共子序列模板题,设\(dp[i][j]\)为字符串\(A[1...i]\)与字符串\(B[1...j]\)的最长公共子序列长度,则状态转移方程为: \[dp[i][j] = max\{dp[i-1][j-1] + (A[i] == B[j]), dp[i-1][j], dp[i][j-1]\} \]用…
2021/7/26 6:07:19 人评论 次浏览 -
51nod 1244 莫比乌斯函数之和(杜教筛)
基准时间限制:3 秒 空间限制:131072 KB 分值: 320 难度:7级算法题收藏关注莫比乌斯函数,由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)(miu(n))作为莫比乌斯函数的记号。具体定义如下: 如果一个数包含平方因子,那么miu(n) = 0。例如:miu(4)…
2021/6/5 10:22:40 人评论 次浏览 -
51nod“省选”模测第二场 B 异或约数和(数论分块)
题意 题目链接 Sol 这题是来搞笑的吧。。 考虑一个数的贡献是\(O(\frac{N}{i})\) 直接数论分块。 #include<bits/stdc++.h> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second #define int long long #def…
2021/6/5 10:22:35 人评论 次浏览 -
51nod“省选”模测第二场 C 小朋友的笑话(线段树 set)
题意 题目链接 Sol 直接拿set维护\(li\)连续段。因为set内的区间互不相交,而且每个线段会被至多加入删除一次,所以复杂度是对的。 #include<bits/stdc++.h> #define Pair pair<int, int> #define MP make_pair #define fi first #define se second using n…
2021/6/5 10:22:35 人评论 次浏览