题目描述

定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件： 

1.序列长度至少为 3。

2. 序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整 数、负整数或 0。 

例如，[1, 2, 3]、[4, 5, 6, 7] 和 [−1, 0, 1] 是符合条件的序列，而 [1, 2]（长度不 足）和 [1, 2, 4]（不连续）不符合要求。

现给定一组包含 N 个正整数的数据 A1, A2, . . . , AN。如果某个 Ai 能够表示 为符合上述条件的连续整数序列中所有元素的和，则称 Ai 是可分解的。 

请你统计这组数据中可分解的正整数的数量。

输入格式

输入的第一行包含一个正整数 N，表示数据的个数。 

第二行包含 N 个正整数 A1, A2, . . . , AN，表示需要判断是否可分解的正整数序列。

输出格式

输出一个整数，表示给定数据中可分解的正整数的数量。

样例输入

3
3 6 15

样例输出

3

提示

【样例说明】 

Ai = 3 是可分解的，因为 [0, 1, 2] 的和为 0 + 1 + 2 = 3。 

Ai = 6 是可分解的，因为 [1, 2, 3] 的和为 1 + 2 + 3 = 6。

Ai = 15 是可分解的，因为 [4, 5, 6] 的和为 4 + 5 + 6 = 15。 

所以可分解的正整数的数量为 3。 

【评测用例规模与约定】 

对于 30% 的评测用例，1 ≤ N ≤ 100，1 ≤ Ai ≤ 100。 

对于 100% 的评测用例，1 ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^9。

要求序列长度至少为3,且序列中的数字是连续递增的整数，可以包括正整数、负整数或 0,则除了1以外的正整数都可以表示为-(n-1)+...+-1+0+1+...+n,如2=-1+0+1+2,而1无法表示(因为序列长度太短),所以只要是1就在总数上减1就好了

#include <bits/stdc++.h>
using namespace std;

int n, a[100010]; 

int main() {
    cin >> n;
    int count = n; 
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) {
            count--;
        }
    }
    cout << count;
    return 0;
}

题目描述

偏远的小镇上，三兄弟共同经营着一家小型矿业公司 “兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 A、B 和 C 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。 

然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时 则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时， 将根据当前的产值 A、B、C，计算新产值： 

1.金矿新产值 

2. 银矿新产值 

3. 铜矿新产值

其中，⌊⌋ 表示向下取整。例如，⌊3.7⌋ = 3，⌊5.2⌋ = 5。 

计算出 A ′、B ′、C ′ 后，同时更新：A 变为 A ′，B 变为 B ′，C 变为 C ′，作为下一年调整的基础。 

三兄弟认为这个方法能平衡产值波动，于是计划连续执行 K 次调整。现在，请你帮他们计算，经过 K 次调整后，金矿、银矿和铜矿的产值分别是多少。

输入格式

输入的第一行包含一个整数 T ，表示测试用例的数量。 

接下来的 T 行，每行包含四个整数 A，B，C，K，分别表示金矿、银矿和铜矿的初始产值，以及需要执行的调整次数。

输出格式

对于每个测试用例，输出一行，包含三个整数，表示经过 K 次调整后金矿、银矿和铜矿的产值，用空格分隔。

样例输入

2
10 20 30 1
5 5 5 3

样例输出

25 20 15
5 5 5

提示

【评测用例规模与约定】 

对于 30% 的评测用例，1 ≤ T ≤ 100，1 ≤ A, B,C, K ≤ 10^5。

对于 100% 的评测用例，1 ≤ T ≤ 10^5，1 ≤ A, B,C, K ≤ 10^9。

这道题只需要按照题意进行计算就行了,但直接按 K 次循环模拟会因 K 可达 10^9 导致超时，因此需利用调整过程的收敛性优化：当某次调整后产值不再变化时，后续调整结果保持不变，可直接终止循环。

#include <bits/stdc++.h>
using namespace std;

int t; // 测试用例数量

int main() {
    cin >> t;
    while (t--) { // 处理每个测试用例
        int a, b, c, k;
        cin >> a >> b >> c >> k; // 读取初始值和调整次数
        int a1, b1, c1; // 存储调整后的新值
        for (int i = 0; i < k; i++) { // 最多执行k次调整
            // 计算新产值（向下取整由整数除法自动实现）
            a1 = (b + c) / 2;
            b1 = (a + c) / 2;
            c1 = (a + b) / 2;
            
            // 若调整后值不变，直接终止循环（后续调整无意义）
            if (a == a1 && b == b1 && c == c1) {
                break;
            }
            
            // 更新为新值，继续下一次调整
            a = a1;
            b = b1;
            c = c1;
        }
        // 输出最终产值
        cout << a << ' ' << b << ' ' << c << endl;
    }
    return 0;
}

题目描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作，其艺术价 值分别为 A1, A2, . . . , AN。他们需要从这 N 幅画中挑选 M 幅，并按照一定顺序 布置在展厅的 M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于 突兀，导致观众的观展体验不够流畅。 

为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使 观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 M 幅 画，应使艺术价值的变化程度通过一个数值 L 来衡量，且该值越小越好。数值 L 的定义为：

                                                             

其中 Bi 表示展厅第 i 个位置上画作的艺术价值。 

现在，他们希望通过精心挑选和排列这 M 幅画作，使 L 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

输入格式

输入共两行。 

第一行包含两个正整数 N 和 M，

分别表示画作的总数和需要挑选的画作数量。 

第二行包含 N 个正整数 A1, A2, . . . , AN，表示每幅画作的艺术价值。

输出格式

输出一个整数，表示 L 的最小值。

样例输入

4 2
1 5 2 4

样例输出

3

提示

【评测用例规模与约定】 

对于 40% 的评测用例，2 ≤ M ≤ N ≤ 10^3，1 ≤ Ai ≤ 10^3。 

对于 100% 的评测用例，2 ≤ M ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^5。

本题的关键在于数学公式的裂项相消推导，将复杂的求和问题转化为简单的差值计算，再结合排序优化找到最优解。

题目中 L 的定义为：L=∑i=1M−1​(Bi+12​−Bi2​)这是一个裂项相消，展开后中间项全部抵消，最终结果为：L=BM^2​−B1^2​其中 B1​ 是所选 M 幅画作艺术价值的最小值，BM​ 是最大值。

因此，求 L 的最小值等价于：从 N 幅画中选 M 幅，使得「最大值的平方 - 最小值的平方」最小。

要最小化 BM^2​−B1^2​，需让所选 M 个数的最大值与最小值尽可能接近。

将所有画作的艺术价值平方后排序（平方后排序不改变数值的相对大小关系）。

在排序后的数组中，连续选取 M 个元素。由于数组有序，连续 M 个元素的最大值减最小值是所有可能组合中最小的（非连续组合的差值必然更大）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m; // n:画作总数，m:选取数量
    long long a;
    long long b[100010]; // 存储每个数的平方
    b[0] = 0; // 初始化，方便后续排序计算

    cin >> n >> m;
    // 输入并计算每个数的平方
    for (long long i = 1; i <= n; i++) {
        cin >> a;
        b[i] = a * a;
    }

    // 对平方数组进行升序排序
    sort(b + 1, b + n + 1);

    long long ans = LLONG_MAX; // 初始化答案为极大值
    // 遍历所有连续M个元素的组合，计算差值的最小值
    for (long long i = 1; i <= n - m + 1; i++) {
        // 排序后，b[i+m-1]是连续M个元素的最大值，b[i]是最小值
        ans = min(ans, b[i + m - 1] - b[i]);
    }

    cout << ans;
    return 0;
}