Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释

C

对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。
由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using LL = long long;void slove()
{int x, y, k; cin >> x >> y >> k;int h = ceil((double)y / k);int l = ceil((double)x / k);int res = max(h, l);res *= 2;if (l > h) res--;cout << res << endl;
} int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1; cin >> t;while (t--) slove();return 0;
}

D

注意到 y 的范围为: [0, 1]，当两点连线垂直 x 轴时，与其余任意点都可以组成直角形。
还有一种组成直角三角形的情况是：一条水平线的点和另一条水平线的两个点组成直角三角形，单独的点的 x 轴坐标位于两点中间，且距离两点长度为 1（由等腰直角三角形的性质可得）

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
using namespace std;
using LL = long long;void slove()
{int n; cin >> n;vector<vector<int>> a(n + 5, vector<int>(2));for (int i = 0; i < n; i++){int x, y; cin >> x >> y;a[x][y]++;}LL res = 0;for (int i = 0; i <= n; i++){res += (LL) a[i][0] * a[i][1] * (n - 2);if (i == 0 || i == n) continue;res += (LL) a[i - 1][0] * a[i][1] * a[i + 1][0];res += (LL) a[i - 1][1] * a[i][0] * a[i + 1][1];}cout << res << endl;
}  int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1; cin >> t;while (t--) slove();return 0;
}

E

注意到数列是一个公差为 1 的等差数列，首项为 k，那么可以根据等差数列的求和公式得到前 i 项的和，i 的范围为: [1, n]
为了使得前缀和后缀差值最小，可以二分 i 的位置，得到最后一个前缀和 小于等于 后缀和的位置；差值需要取该位置的差值和后一个位置的最小值。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
using namespace std;
using LL = long long;
typedef pair<int, int> PII;void slove()
{LL n, k; cin >> n >> k;LL t = (LL) n * (2 * k + n - 1) / 2;int l = 1, r = n + 1;while (l < r){int mid = l + r  + 1 >> 1;LL pre = (LL) mid * (2 * k + mid - 1) / 2;LL suf = t - pre;if (pre <= suf) l = mid;else r = mid - 1;}LL res = 1e18;LL pre = (LL) l * (2 * k + l - 1) / 2;LL suf = t - pre;// cout << abs(pre - suf) << endl;res = min(res, abs(pre - suf));l++;pre = (LL) l * (2 * k + l - 1) / 2;suf = t - pre;res = min(res, abs(pre - suf));// cout << abs(pre - suf) << endl;cout << res << endl;
} int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1; cin >> t;while (t--) slove();return 0;
}

F

数组 b 可以理解为由数组 a 组成的 n x n 的二维矩阵，第 i 行由 ai....an a1...ai-1 组成。
对于每一个询问 l，r；可以将 l，r 映射到由两个 a 数组组成的新的数组中。
对于 l 到 r 的和，可以使用前缀和。首先可以计算出 l 和 r 位于 b 的第几层，假如不是位于同一层，那么中间的层数的和是由 a 的和组成的。然后就是处理 l 到该层末尾的和，r 到层首的和。

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;LL get_pre(vector<LL>& pre, LL cen, LL x)
{int start = x + cen;return pre[start] - pre[cen - 1];
}void slove()
{int n, q; cin >> n >> q;vector<LL> nums(2 * n + 10);vector<LL> pre(2 * n + 10);for (int i = 1; i <= n; i++){cin >> nums[i];nums[i + n] = nums[i];}for (int i = 1; i <= 2 * n; i++){pre[i] = pre[i - 1] + nums[i];}while (q--){LL l, r; cin >> l >> r;LL cen_l = ceil(1.0 * l / n);LL cen_r = ceil(1.0 * r / n);// cout << cen_l << " " << cen_r << endl;int cnt = cen_r - cen_l - 1;LL res = (LL) max(0, cnt) * pre[n];// cout << res << endl;l--, r--;l %= n, r %= n;// cout << l << " " << r << endl;if (cen_l == cen_r){res += get_pre(pre, cen_l, r) - get_pre(pre, cen_l, l - 1);// cout << nums[cen_l + l] <<  endl;}else{res += pre[n] - get_pre(pre, cen_l, l - 1) + get_pre(pre, cen_r, r);}cout << res << endl;}}int main()
{int t; cin >> t;while (t--) slove();return 0;
}

G1

可以将数组的元素 - i，这样对于两个元素如果是连续的子数组的话，那么值就会相同。
证明如下：
对于任意两哥元素 ai aj，另 j - i = k，那么假如 ai 和 aj 满足连续子数组的要求得话，有 aj = ai + k,
ai - i，aj - j = ai + k - j = ai + j - i -j = ai - i。所以当两个元素满足连续子数组的要求，那么减下标将会相等。

对于一个区间需要改变的最小次数等于 len - maxv。（len 表示区间元素个数，maxv 表示区间内满足连续子数组要求的最大元素个数）问题就转变为求区间内最长连续子数组的元素个数。

使用 map 存储每一个元素减下标的个数，使用 multiset 存储个数。对于区间长度 k，可以使用滑动窗口预处理从每一个下标开始，窗口长度为 k 的最大相同元素个数。
先枚举 [1, k)，维护出第一个滑动窗口中相等元素个数。然后依次向后移动，增加进入的元素，减去出去的元素。注意：每枚举一个元素，都会向 multiset 中插入个数，但是在插入之前会将该元素对应的值的个数在 multiset 中减去，否则就重复加了。在这里就需要注意 multiset 的用法：在 erase 之前需要保证 multiset 中有这个值，所以可以在操作之前，先插入 n 个 0，不会影响到答案的获取。

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
using LL = long long;void slove()
{int n, k, q; cin >> n >> k >> q;vector<int> nums(n + 10);vector<int> res (n + 10);for (int i = 1; i <= n; i++) cin >> nums[i];map<int, int> mp;multiset<int> s;for (int i = 1; i <= n; i++) s.insert(0);  // 由于需要先删除，当一个元素没有进入过multiset之前就会为0，那么for (int i = 1; i < k; i++)  // 先处理好第一个窗口{s.erase(s.find(mp[nums[i] - i]));  // 在增加这个个数之前，需要先删除这个个数之前的插入，这样就可以保证不会重复。mp[nums[i] - i]++;s.insert(mp[nums[i] - i]);  // 增加个数到 multiset 中}for (int i = k; i <= n; i++){s.erase(s.find(mp[nums[i] - i]));mp[nums[i] - i]++;s.insert(mp[nums[i] - i]);int p = i - k + 1;res[p] = *s.rbegin();s.erase(s.find(mp[nums[p] - p]));mp[nums[p] - p]--;s.insert(mp[nums[p] - p]);}while (q--){int l, r; cin >> l >> r;cout << k - res[l] << endl;}
}int main()
{int t; cin >> t;while (t--) slove();return 0;
}