Given 1 integers n, you are supposed to output the value of 1+(1+2)+(1+2+3)+... ...+(1+2+...+n).

题目要求我们计算1到n的所有数字中1的个数，而这道题目要求我们计算1+(1+2)+(1+2+3)+...+(1+2+...+n)的值。我们可以通过数学方法来解决这个问题。我们可以将每个括号内的数字相加，得到1、3、6、10、15……这个数列，可以发现这个数列是一个等差数列，公差为1，首项为1，可以使用等差数列求和公式来计算这个数列的和。即：(首项+末项)×项数÷2。其中，项数为n，末项为n×(n+1)÷2，首项为1。因此，这个数列的和为n×(n+1)×(n+2)÷6。

相关问题

请用C语言实现Once upon a time in the mystical land of Draconis, there existed two powerful arrays: M and N . These arrays were filled with positive integers, each carrying its own magical essence. The inhabitants of the land were intrigued by the concept of similarity between arrays. They discovered that two arrays, M and N , could be considered similar if it was possible to transform a subarray of N into M by adding or subtracting a constant value to each element. You are now summoned to solve a puzzle. Given two arrays, M and N , your task is to determine the number of subarrays of N that are similar to M . Will you be able to unravel this mystical connection? Input The input consists of multiple lines. The first line contains two integers M and N (1≤M≤N≤106) , representing the lengths of arrays M and N respectively. The second line contains M space-separated positive integers m1,m2,…,mM (1≤mi≤109) , representing the magical elements of array M . The third line contains N space-separated positive integers n1,n2,…,nN (1≤ni≤109) , representing the mystical elements of array N . Output Output a single integer, the number of subarrays of N that are similar to M .

为了解决这个问题，我们可以先对两个数组进行排序，然后用双指针法来找到所有相似的子数组。具体实现如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000

int M[MAX_N], N[MAX_N];
int m, n;

int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int count_similar() {
    int i = 0, j = 0;
    int count = 0;
    while (i < m && j < n) {
        if (M[i] == N[j]) {  // 找到相同的元素
            int k = j;
            while (k < n && N[k] == N[j]) {
                k++;
            }
            count += k - j;  // 加上与N[j]相同的元素的个数
            i++;
            j = k;
        } else if (M[i] < N[j]) {  // M[i]较小，需要增加N中的元素
            i++;
        } else {  // M[i]较大，需要减少N中的元素
            j++;
        }
    }
    return count;
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%d", &M[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &N[i]);
    }
    qsort(M, m, sizeof(int), compare);
    qsort(N, n, sizeof(int), compare);
    printf("%d\n", count_similar());
    return 0;
}

首先读入两个数组的长度和元素，然后对它们进行排序。然后用双指针法找到所有相似的子数组，具体方法如下：

1. 初始化两个指针i和j，分别指向M和N的开头；
2. 如果M[i]等于N[j]，说明找到了一个相似的子数组，接着向右移动j，直到N[j]不等于N[j+1]；
3. 如果M[i]小于N[j]，说明N[j]需要增加，所以向右移动i；
4. 如果M[i]大于N[j]，说明N[j]需要减少，所以向右移动j；
5. 重复2~4步，直到i到达M的末尾或j到达N的末尾。

遍历过程中，我们用一个计数器count来累计相似的子数组的个数，每当找到一个相似的子数组时，我们就把与N[j]相同的元素的个数加到count中。最后返回count即可。

时间复杂度为O(MlogM + NlogN)，空间复杂度为O(M + N)。

请给出下题的c++参考代码For an array of integers [a1,a2,…,an], let's call the value |a1−a2|+|a2−a3|+⋯+|an−1−an| the contrast of the array. Note that the contrast of an array of size 1 is equal to 0 . You are given an array of integers a . Your task is to build an array of b in such a way that all the following conditions are met: b is not empty, i.e there is at least one element; b is a subsequence of a, i.e b can be produced by deleting some elements from a (maybe zero); the contrast of b is equal to the contrast of a . What is the minimum possible size of the array b ? Input The first line contains a single integer t (1≤t≤104 ) — the number of test cases. The first line of each test case contains a single integer n (1≤n≤3⋅105) — the size of the array a . The second line contains n integers a1,a2,⋅,an (0≤ai≤109 ) — elements of the array itself. The sum of n over all test cases doesn't exceed 3⋅105 . Output For each test case, print a single integer — the minimum possible size of the array b .

以下是参考代码，时间复杂度为O(n)：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i > 0) {
                sum += abs(a[i] - a[i - 1]);
            }
        }
        long long max_diff = 0;
        for (int i = 1; i < n - 1; i++) {
            max_diff = max(max_diff, abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]));
        }
        cout << sum - max_diff << endl;
    }
    return 0;
}

思路：

题目要求找到一个非空子序列，其 contrast 值等于原序列的 contrast 值，且该子序列长度最小。对于一个长度大于等于2的子序列，其 contrast 值可以拆分成相邻元素之差的绝对值之和，即

|a[i]-a[i-1]| + |a[i+1]-a[i]|

利用绝对值的性质，可以将其拆分为

(a[i]-a[i-1]) + (a[i+1]-a[i]), a[i]>a[i-1] and a[i+1]>a[i]

(a[i-1]-a[i]) + (a[i]-a[i+1]), a[i]<a[i-1] and a[i+1]<a[i]

(a[i]-a[i-1]) + (a[i]-a[i+1]), a[i]>a[i-1] and a[i+1]<a[i]

(a[i-1]-a[i]) + (a[i+1]-a[i]), a[i]<a[i-1] and a[i+1]>a[i]

其中第三种情况需要特殊处理，即对于一个数列 a，找到一个位置 i，使得 a[i-1]<a[i]>a[i+1]，将 a[i] 从子序列中删除，即可得到一个新的子序列，其 contrast 值等于原序列的 contrast 值。

因此，我们可以遍历整个序列，计算出原序列的 contrast 值。然后再遍历一遍序列，找到最大的相邻元素之差，计算出其对应的拆分方式，即可得到最小的子序列长度。