暑假集训 Day14 总结

前言：

骗分代码没交上去，痛失 $21$ 分，无缘第二。

D.标记

正解思路：

这道题目就是一道周期问题。首先，我们对长度与步长做 $gcd$，以此求出总共要走多少步，就为 $n\div gcd(n,d)$。而由于 $0$ 这个位置一步到达，第一个组两步到达，所以，步数要减一。求出走完整数组余下的点数：$(k-1)\div (n\div gcd(n,d))$。最后算答案，用步数减一乘每一步的长度加上余下的点数对 $n$ 取余变为正常坐标即为答案。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n, d, k;
int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}
signed main() {
	freopen("D.in", "r", stdin);
	freopen("D.out", "w", stdout);
	cin >> t;

	while (t--) {
		cin >> n >> d >> k;
		int sb = gcd(n, d);//分为了多少组
		int sb2 = (k - 1) / (n / sb);//余了多少，周期问题的余数。
		int sb3 = ((k - 1) * d + sb2) % n; //由于0单独一组，所以要把编号减一，第二组相当于第一组。每一组d个，加上余数，取模变成正常编号。
		cout << sb3 << endl;
	}

	return 0;
}

E.构成回文

正解思路：

首先，我们先分析暴力，显然，用整体减去不用改的是比较好求的。第一层，枚举每一个数，第二三层，枚举每一个数出现的 $l$ 和 $r$，时间复杂度为 $O(n^3)$，超时啊。那么，我们开始优化。首先，假设全部都要修改，那么我们就枚举每一个长度，把所有长度的贡献相加就可以了，公式为 $\sum_{i=1}^n (n-i+1)\times \lfloor\frac{i}{2}\rfloor$。我们接下来要求有多少是可以不用修改的。而由于之前这部分是要用 $O(n^2)$ 算的，一定会超时，那么我们就要找一种优化的方式。我们可以构造一种对称，当位置 $p_i=l+d$，$p_j=r-d$，那么对于某一个 $d$，他们是对称的，$d$ 的取值可以是 $0$ 到 $p_i$，那么正向就有 $p_i$ 个贡献，反向有 $n-p_j+1$ 个贡献，对两个值取较小值就是当前可行的。而我们发现，求 $p_i$ 和 $p_j$ 是可以通过双指针枚举的。当 $p_i$ 小于 $p_j$ 时，$p_i$ 到 $p_j-1$ 之间的值都肯定小于 $p_j$，那么不需要修改的对数就是 $(r-l)\times p_{i,l}$，否则从 $p_j$ 到 $p_i+1$ 这个区间的值都会小于 $p_i$，则贡献为 $(r-l)\times p_{i,r}$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int n, sum, num;
int a[N];
vector<int> b[N];
signed main() {
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += (n - i + 1) * (i / 2);
		b[a[i]].push_back(i);
	}

	for (int i = 1; i <= n; i++) {
		int l = 0, r = b[i].size() - 1;

		while (l < r) {
			if (b[i][l] < n - b[i][r] + 1) {
				num += (r - l) * b[i][l];
				l++;
			} else {
				num += (r - l) * (n - b[i][r] + 1);
				r--;
			}
		}
	}

	cout << sum - num;
	return 0;
}