【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）题面51NOD\[\sum_{i=1}^n\sum_{j=1}^nsgcd(i,j)^k\]其中\(sgcd\)表示次大公约数。题解明摆着\(sgcd\)就是在\(gcd\)的基础上除掉\(gcd\)的最小因...
【51nod】1239 欧拉函数之和 杜教筛
【题意】给定n，求Σφ(i)，n<=10^10。【算法】杜教筛【题解】定义$s(n)=\sum_{i=1}^{n}\varphi(i)$杜教筛$\sum_{i=1}^{n}(\varphi *I)(i)=\sum_{i=1}^{n}\sum_{d|i}\varphi(d)=\sum_{i=1}...
51NOD 1185 威佐夫游戏 V2(威佐夫博弈)
1185 威佐夫游戏 V2 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出...
51nod 1163贪心
用优先队列来贪心，是一个很好地想法。优先队列在很多时候可以维护最值，同时可以考虑到一些其他情况。http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1163#include<queue>#include<sta...
51nod 1073 约瑟夫环
题目链接先说一下什么是约瑟夫环，转自：传送门关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的...
51nod 1444 破坏道路（bfs+枚举）
1444 破坏道路 题目来源： CodeForces基准时间限制：1.5 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 收藏 关注在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家...
51nod 1092 回文字符串 (dp)
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1092这个题是poj-3280的简化版，这里只可以增加字符，设 dp[i][j] 为把以i开头j结尾的子串变为回文串的最少次数，if(s[i]==s[j]) dp[i][j...
51Nod 2006 飞行员配对（二分图最大匹配）
链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=2006思路：二分匹配 注意n m的关系代码： #include <iostream> #include <string.h> using nam...
【51Nod 1674】【算法马拉松 19A】区间的价值 V2
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1674对区间分治，统计\([l,r]\)中经过mid的区间的答案。我的做法是从mid向右扫到r，统计出所有\([mid,i],mid\leq i \leq r\)的and和o...
51nod 1376 最长递增子序列的数量(线段树)
51nod 1376 最长递增子序列的数量数组A包含N个整数（可能包含相同的值）。设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。如果S的长度是所有递增子序列中最长的，则称S为A的最长递增子序列（LIS）。A的LIS可能有很多个。例如A为：{1 3 2 0 4}，1 3 4，1 2 4均...
51nod 1080 两个数的平方和
没心情写数学题啦啊 好难啊#include<bits/stdc++.h>using namespace std;set<int> s;set<int>::iterator it;int main (){ s.clear(); for(int i=;...
51nod 1201 整数划分 基础DP
1201 整数划分 基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 收藏 关注将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。Inp...
51Nod 1201 整数划分 (经典dp)
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201题意不多说了。dp[i][j]表示i这个数划分成j个数的情况数。dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]前者表示将...
51nod 1201 整数划分 dp
1201 整数划分基准时间限制：1 秒 空间限制：131072 KB 收藏 关注将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。Input输入1个数N(1 <=...
51nod 1349 最大值（单调栈）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1349题意：求区间内最大值大于等于k的区间个数。思路：利用求出对于以a[i]为最大值的区间范围，pre[i]表示左端范围，aft[i]表示右端范围，则区间个数为$(i-pre...
计算幂 51Nod 1046 A^B Mod C
给出3个正整数A B C，求A^B Mod C。 例如，3 5 8，3^5 Mod 8 = 3。Input3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)Output输出计算结果Input示例3 5 8Output示例3 #include <iostr...
51nod 1069 Nim游戏 + BZOJ 1022: [SHOI2008]小约翰的游戏John（Nim游戏和Anti-Nim游戏）
首先，51nod的那道题就是最简单的尼姆博弈问题。尼姆博弈主要就是判断奇异局势，现在我们就假设有三个石子堆，最简单的（0,n,n）就是一个奇异局势，因为无论先手怎么拿，后手总是可以在另一堆里拿走相同的石子数。再看另外一个奇异局势（1,2,3）：①如果先手拿第一个石子堆，那么后手可以形成（0,2,2）...
51NOD 1069 Nim游戏
1069 Nim游戏 有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。例如：3堆石子，每堆1颗。A拿1颗，B拿1颗，此时还剩1堆，所以...
51Nod 1067 Bash游戏 V2
1067 Bash游戏 V2 基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都...
51nod 1067 Bash游戏 V2
#include <bits/stdc++.h>using namespace std;int main(){int t,n,k;cin>>t;while(t--){scanf("%d",&n);if(n%7==0||n%7==2) printf("B\n");els