sums专题

【SPOJ】Triple Sums【FFT】

传送门：【SPOJ】Triple Sums 题目分析：首先我们不考虑 i<j<k i<j<k这个条件，构造多项式： Y=∑xai \qquad\qquad\qquad Y = \sum x^{a_i} 那么 ai+aj+ak=S ai+aj+ak=S的个数即 xai+aj+ak=S x^{a_i+a_j+a_k=S}的个数，等价于 Y3中xS Y^3中x^S的系数。然后我们考虑容斥

codeforces 289 C Sums of Digits

贪心，做了两个半小时没做出来！主要在于求有k位且恰比某个数大的最小值，从左到右检查可以加1的位，若后面的位满足条件，再根据solve中的方法满足条件的最小值。 #include<iostream>#include<string>#include<cstring>#include<cstdio>#include<cmath>#include<iomanip>#include<map

UVA11997K Smallest Sums(优先队列+二路归并）

题目：UVA11997K Smallest Sums(优先队列+二路归并）题目大意：求K个最小和。给出K行，每行有K个数，在每行中取一个元素相加，求这些和中最小的k的值。解题思路：每一行排列一下，那么对于两张表a1< a2 < a3 < a4... ，可以将a1 + b1（最小的）, a1+ b2, a1 + b3...a1 + bk存到优先队列中，然后最小的出队，就尝试将剩余

【规律题】Backward Digit Sums

【POJ3187】【洛谷1118】Backward Digit Sums Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other) Problem Description FJ and his cows enjoy playing a mental game. They write do

122 Triangular Sums

Triangular Sums 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 The nth Triangular number, T(n) = 1 + … + n, is the sum of the first n integers. It is the number of points in a triangula

uva 11997 - K Smallest Sums(优先队列)

题目链接：uva 11997 - K Smallest Sums 题目大意：有k个整数数组，包含k个元素，在每个数组中取一个元素加起来可以得到k

ICPC 6929 Sums

思路：如果一个数n是2的阶乘，那么是无解的。然后，如果N是奇数，那么肯定能由中间的两个数相加得到。如果N是偶数，就要分成两种情况，一种是取 n-1 n n+1等等，n的左右两边可以取I个值，可以发现n-2和n+2相加和n-1加n+1相加相等。。另一种情况就是中间情况是 n-1 n n+1,n-1和n的值等于n-2和n+1的值。。贴上JYJJ阿姨的代码

373. Find K Pairs with Smallest Sums

题意：输入两个整形升序数组，整数k，要求分别从2个数组中取出2个数组成对，输出和最小的k个对。思路：1 参考leetcode discuss； 2 PriorityQueue实现最小堆，具体步骤如下：初始化为array1中的前k个元素（注意，如果array1中的长度小于k，则为array1.length）和array2中的首个元素组成的pair；每次从堆中剔除首个元素p（即目

[LeetCode算法笔记]Find K Pairs with Smallest Sums与优先队列

LeetCode第373题 Find K Pairs with Smallest Sums是一道中等难度的题题面挺简单的：给定两组升序排列的整形（int）数组，从中分别挑选k对和最小的数对（pair）意思就是从两个数组中分别挑选一个数，组成一个数队，使两个数的和最小例子：输入：nums1:[1,6,7,11]，nums2:[1,2,6,9]，k=4

P1466 集合 Subset Sums（计数类dp)

题目描述对于从1到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，每个子集合的所有数字和是相等的： {3} 和 {1,2} 这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法

【每日一题】CF988 C. Equal Sums | 排序 | 简单

题目内容原题链接给定 k k k 个数组，第 i i i 个数组的长度为 n i n_i ni 。问是否可以选择两个数组，编号分别为 a a a 和 b b b ，从 a a a 和 b b b 中各删除一个数，使得两者的数组和相同。如果可以，输出三行第一行输出 YES第二行输出选择的数组 a a a 的编号以及数组 a a a 中删除的数组元素的下标

Spoj 8372 Triple Sums

传送门：http://www.spoj.com/problems/TSUM/ 思路：先不管i<j<k这个条件构造一个多项式A(x)=sigma x^a[i] 那么S=a[i]+a[j]+a[k]的个数就是x^(a[i]+a[j]+a[k]=S)的个数为了让指数相加，我们把A(x)进行立方那么个数就是A(x)^3中S次项的系数然后进行容斥,为了方便，以下省去指数a[i]

5. Equal Tree Sums

题目链接：Equal Tree Sums 这是昨晚比赛中没有做出来的一道题。让你给一棵树的所有节点赋值，使其删去任意一个节点后产生的连通块权值和均相等。当时手画了几种简单的情况，发现可以对树二染色后交替赋正值和负值，但没能构造出赋值的方案。其实很简单，染色后每条边的两端颜色必然不同，可以让每条边的总贡献均为零，即每个点的权值的绝对值都是其度数，这样删去一个点就相当于将这个点的权值平均流到

Codeforces348C - Subset Sums

Portal Description 给出长度为\(n(n\leq10^5)\)的序列\(\{a_n\}\)以及\(m(m\leq10^5)\)个下标集合\(\{S_m\}(\sum|S_i|\leq10^5)\)，进行\(q(q\leq10^5)\)次操作：询问下标属于集合\(S_k\)的所有数之和。将下标属于集合\(S_k\)的所有数加\(x\)。 Solution 记\(N_0=\sqr

LeetCode 01 Two Sums

LeetCode的学习笔记：001 题目描述： 1.第一个解决办法就是两层循环求和，时间复杂度达到了O（n^2）,按题目所给范例运行时间是68ms。 leetcode所给的代码模板和OJ不同。LeetCode所给的是一个Solution类，需要在这个类下写出问题解决的函数。 C++模板给出的函数是 vector<int> twoSum(vector<int>& nums, int

（UVa 11997）K Smallest Sums --多路归并问题，优先队列

题目链接： http://acm.hust.edu.cn/vjudge/problem/18702 题意：有k个数组，每个数组k个元素。在每个数组中取一个元素加起来，有k^k个和。求这些和中最小的k个（重复的值算多次）？分析：我们先来求两个元素个数为n的且有序的数组A,B的前n个最小值。组合情况有n*n种，但是我们可以我这些和组织成如下有序表：表1：A1+B1<=A1+B2<=

集合 Subset Sums

题目描述对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的： {3} and {1,2} 这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的

hdu 4193 - Non-negative Partial Sums(滚动数列)

题意：给定一个由n个整数组成的整数序列，可以滚动，滚动的意思就是前面k个数放到序列末尾去。问有几种滚动方法使得前面任意个数的和>=0. 思路：先根据原来的数列求sum数组，找到最低点，然后再以最低点为始点，求解题目答案，（每求解一始点i，符合要求的条件为：sum[i]>=minx,[minx是i<x<=n中的最小值],之所以不用考虑前面的，就是因为我们的预处理是的所有的x<i的sum[

Leetcode 2915. Length of the Longest Subsequence That Sums to Target

Leetcode 2915. Length of the Longest Subsequence That Sums to Target 1. 解题思路2. 代码实现题目链接：2915. Length of the Longest Subsequence That Sums to Target 1. 解题思路这一题其实就是一个动态规划的题目，本身没啥难的，只不过最开始用cache来偷懒的

[python 刷题] 974 Subarray Sums Divisible by K

[python 刷题] 974 Subarray Sums Divisible by K 题目如下： Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous