【转载】线段树

区间的修改或者统计,来实现快速对[L,R]的修改或者统计。   由此看出,用线段树统计的东西,必须符合区间加法,否则,不可能通过分成的子区间来得到[L,R]的统计结果。   符合区间加法的例子: 数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和 最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD ); 最大值——总最大值=max(左区间最大值,右区间最大值) ...

费波拉契数列的算法分析

  费波拉契数列 什么叫费波拉契数列呢? 数学家费波拉契在自己的著作中用兔子繁殖模型引入了这样一个数列:1,1,2,3,5,8,13… 这个数列的第1项和第2项都为1,以后的项都是前面两项之和。 写成递推公式如下: f(n) = 1                                  n=1,2 f(n) = f(n-1)+f(n-2)              ...

(LeetCode篇)1. 两数之和

  题目描述: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]   完整...

两数之和

import java.util.HashMap; public class twoSum { public static int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> m = new HashMap(); int res[] = new int[2]; for (int i = 0;i<nums.length;i++...

【DP】最大子矩阵之和

题目给出一个N [2<=N<=100],并给出一个N*N的矩阵,矩阵中的数为[-127,127]之间。求出矩阵中一块子矩阵的最大和。输入样例40 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2输出样例15解题思路每读入一个数,就求出它那列的前缀和,最后直接利用前缀和进行计算子矩阵和(其实就是最大连续数列的和),时间复杂度是O(n^3)。代码#include...

J - Just Too Lucky-数位DP

念,例如,有时门票被认为是幸运的,如果是上半年的总和 数字等于下半部的和,有时使用乘积而不是求和,有时 允许数字的排列等。 在圣安德鲁堡,整数从1到N用作票号。比尔认为幸运票 如果它的个数是由它的数字之和整除的。帮助比尔找到幸运票的数量。 思路: 枚举每一种各个位数的和最大为108,枚举108种情况即可。 #include<bits/stdc++.h>using namespace std;#de...

国庆个人赛——NO.5

少对的‘R’‘L'、’U‘’D',把能形成整数对 ‘R’‘L'、’U‘’D' 的个数去掉(在原个数的基础上减去能形成整数对的个数),剩下的就是需要改配对的, 也就是需要改变的某几个数 剩下的数之和除 2——就是需要改变的个数 CODE: #include <iostream>#include <cstdio>#include <cstring>#include <cmath>#incl...

J - Invitation Cards (spfa从源点(1)到其他点来回的最短路之和

21 2 132 1 334 61 2 102 1 601 3 203 4 102 4 54 1 50 Sample Output 46210 题意:计算从源点到其他点来回的最短路之和 思路:数据较大,spfa正反各跑一次,累计源点到其他点之间的最短路 #include <iostream>#include <algorithm>#include <cstdio>#inclu...

51nod 1405 树的距离之和

1405 树的距离之和基准时间限制:1 秒 空间限制:131072 KB给定一棵无根树,假设它有n个节点,节点编号从1到n, 求任意两点之间的距离(最短路径)之和。Input第一行包含一个正整数n (n <= 100000),表示节点个数。后面(n - 1)行,每行两个整数表示树的边。Output每行一个整数,第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。Input示...

leetcode129. 求根到叶子节点数字之和

描述  给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。 例如,从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。   示例   思路 递归。   代码 /** * Definition for a binary tree node. * struct TreeNode ...
关于我们 联系我们 友情链接 LMLPHP后院 
本站由 LMLPHP 强力驱动 ©2014-2020 LMLPHP 耗时0.076275(s)
2020-02-26 23:24:40 1582730680