第24次csp认证考试第二题满分做法

满分做法"/>

第24次csp认证考试第二题满分做法

第24次csp认证考试第二题满分做法

第二题和第一题几乎逻辑一样，考虑到n比较小，N比较大，那么复杂度尽量控制在 θ ( n ) \theta(n) θ(n)以内，借鉴第一题的思路，我们不用 f o r for for循环来计算一段数的乘积，给定的 n n n个数字将 0 → N 0 \rightarrow N 0→N整个区间划分成了n个区间，我们只需要分别计算每个单独的区间即可。

那么怎么计算每个区间的值呢？

考虑到 g ( i ) g(i) g(i)这个函数是单调递增的，而对于每一个区间， f ( i ) f(i) f(i)的值是固定的，那么我们可以想到二分，对于每个区间，我们二分 g ( i ) g(i) g(i)中大于 f ( i ) f(i) f(i)的最小数，这样子就可以将绝对值符号去掉了，并且每个区间的贡献可以 θ ( 1 ) \theta(1) θ(1)的时间求解出来，实际的实现过程中还有很多的细节，比如我们要很方便的求出如下式子: ∑ ⌊ x / r ⌋ a < = x < = b \displaystyle \sum \lfloor x/r \rfloor a<=x<=b ∑⌊x/r⌋a<=x<=b

经过分析发现，这个式子可以分类讨论求得，具体代码实现如下：

#include <bits/stdc++.h>using namespace std;
int cal(int a, int b, int r)
{// 计算[a,b]这个区间/r的总和if (a / r == b / r)return (b - a + 1) * (b / r);int ans = 0;int ra = a % r;int rb = b % r;int L = a + r - ra;int R = b - rb - 1;ans += (a / r) * (r - ra);ans += (b / r) * (rb + 1);if (L > R)return ans;int x = L / r, y = R / r;ans += ((x + y) * (y - x + 1) / 2) * r;return ans;
}
int main()
{int n, N;scanf("%d%d", &n, &N);vector<int> a(n + 1, 0);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);long long ans = 0;int r = N / (n + 1);vector<pair<int, int>> res;for (int i = 1; i <= n; i++){res.push_back({a[i - 1], a[i] - 1});}res.push_back({a[n], N - 1});for (int i = 0; i < res.size(); i++){int x = res[i].first, y = res[i].second;if (x / r >= i){ans += cal(x, y, r) - (y - x + 1) * i;}else if (y / r <= i){ans += (y - x + 1) * i - cal(x, y, r);}else{int L = x, R = y;while (L < R){int mid = L + R + 1 >> 1;if (mid / r <= i)L = mid;elseR = mid - 1;}ans += (L - x + 1) * i - cal(x, L, r);ans += cal(L + 1, y, r) - (y - L) * i;}}cout << ans << endl;return 0;
}