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]=d...
51nod 1237 最大公约数之和 V3（杜教筛）
【题目链接】https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1237【题目大意】求[1,n][1,n]最大公约数之和【题解】枚举最大公约数k，得到答案为2*∑(k*phi_sum(n/k))-n*(n+1)/2phi_su...
51nod 最近刷题 简要题解
51nod1564由于数据是随机的，可以证明，对于每一个数，向左或右找比它小的数，长度是logn级别的考虑枚举最大值注意，对于每一个最大值，如果直接用2个循环枚举左右端点的话，理论是lognlogn级别的，但是还是很容易被卡的，换成贪心，用2个指针指着左右端点，每一次移动我们往数大的那个方向移动代码...
【51nod】1238 最小公倍数之和 V3 杜教筛
【题意】给定n，求Σi=1~nΣj=1~nlcm(i,j)，n<=10^10。【算法】杜教筛【题解】就因为写了这个非常规写法，我折腾了3天……$$ans=\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)$$令$$g(n)=n*\sum_{i=1}^{n}\frac{i}...
51nod 1244 莫比乌斯函数之和（杜教筛）
【题目链接】http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1244【题目大意】计算莫比乌斯函数的区段和【题解】利用杜教筛：求F(n)=∑(f(i))存在g=f*I，定义G(n)=∑(g(i))就可以得到F(n)=G(n)-...
51nod 1292 字符串中的最大值V2（后缀自动机）
题意：有一个字符串T。字符串S的F函数值可以如下计算：F(S)=L*S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。题解：求T的后缀自动机，然后所有每个后缀自动机的结点u求出endpos[u]*maxlen[u]中的最大值即可#include<iostrea...
51Nod 1070：Bash游戏 V4（斐波那契博弈）
1070 Bash游戏 V4 基准时间限制：1 秒空间限制：131072 KB分值: 40 难度：4级算法题 收藏 关注有一堆石子共有N个。AB两个人轮流拿，A先拿。每次拿的数量最少1个，最多不超过对手上一次拿的数量的2倍（A第1次拿时要求不能全拿走）。拿到最后1颗石子的人获胜。假设AB都非常聪明，...
51nod 平均数(马拉松14)
平均数alpq654321 (命题人) 基准时间限制：4 秒空间限制：131072 KB分值: 80LYK有一个长度为n的序列a。他最近在研究平均数。他甚至想知道所有区间的平均数，但是区间数目实在太多了。为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。Input...
51Nod 1069：Nim游戏（尼姆博弈）
1069 Nim游戏 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注有N堆石子。AB两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设AB都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最...
51nod 1080 两个数的平方和
没心情写数学题啦啊 好难啊#include<bits/stdc++.h>usingnamespacestd;set<int>s;set<int>::iteratorit;intmain(){s.clear();for(inti=;i*i<=1e9;i++)s...
51nod 1376 最长递增子序列的数量(线段树)
51nod1376最长递增子序列的数量数组A包含N个整数（可能包含相同的值）。设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。如果S的长度是所有递增子序列中最长的，则称S为A的最长递增子序列（LIS）。A的LIS可能有很多个。例如A为：{13204}，134，124均为A的LIS。给出数...
51nod 1050 循环数组最大子段和【环形DP/最大子段和/正难则反】
1050 循环数组最大子段和基准时间限制：1 秒空间限制：131072 KB分值: 10 难度：2级算法题 收藏 关注N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[...
51nod贪心算法入门-----活动安排问题2
题目大意就是给几个活动，问要几个教室能够弄完。这个题目的想法就是把活动的开始——结束的时间看做是数轴上的一段线段，教室的个数就是在某点的时间厚度，求最大的时间厚度就是所需要的教室个数。#include<stdio.h>#include<iostream>#include<...
51Nod 1737 配对（树的重心）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737题意：思路：树的重心。树的重心就是其所以子树的最大的子树结点数最少，删除这个点后最大连通块的结点数最小，也就说各个连通块尽量平衡。这道题的话就是先求一个重心，然后求各个...
51nod 1770 数数字 找规律，注意进位，时间复杂度O（n）
题目：这题很简单，找规律即可。考虑两次进位：1.a*b时的进位。2.aa*b时加法时进位。代码:#include<bits\stdc++.h>usingnamespacestd;intnum[];intmain(){inta,b,d,n,t;cin>>t;while(t--)...
51nod 1443 路径和树（最短路树）
题目链接：路径和树题意：给定无向带权连通图，求从u开始边权和最小的最短路树，输出最小边权和。题解：构造出最短路树，把存留下来的边权全部加起来。（跑dijkstra的时候松弛加上$<$变成$<=$，因为之后跑到该顶点说明是传递下来的，该情况边权和最小。）以样例作说明：第一次从顶点3跑到顶点...
51nod比赛
http://www.cnblogs.com/wzj-is-a-juruo/p/5619901.html51nod比赛的更多相关文章他们在军训，我在搞OI（三）昨天忘记写了,因为急着去看51nod比赛,然而思考了许久还是一道都不会,好菜啊T_T...补一下Day3的情况.Day3上午还是常规地做vj...
51Nod 算法马拉松21(迎新年)
这次打算法马拉松是在星期五的晚上，发挥还算正常(废话，剩下的题都不会==)。讲讲比赛经过吧。8:00准时发题，拿到之后第一时间开始读。A配对，看上去像是二分图最大权匹配，一看范围吓傻了，先跳过读后面的题。B完全二叉树的方差，大概看了一遍，好神的样子，跳过。C多项式？好吧没学过FFT和NTT的我肯定不...
51nod 1672 贪心/队列
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=16721672区间交基准时间限制：1秒空间限制：131072KB分值:40难度：4级算法题收藏关注小A有一个含有n个非负整数的数列与m个区间，每个区间可以表示为li,ri。它...
51nod 循环数组最大子段和（动态规划）
循环数组最大子段和输入第1行：整数序列的长度N（2<=N<=50000)第2-N+1行：N个整数(-10^9<=S[i]<=10^9)输出 输出循环数组的最大子段和。 输入示例6-211-413-5-2输出示例20请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范...