Codeforces Round 971 (Div. 4)

A - Minimize!

inline void solve(){
	int a, b;
	cin >> a >> b;

	cout << b - a << '\n';
}

B - osu!mania

inline void solve(){
	int n;
	cin >> n;

	vector<string> a(n);
	for (auto& x : a) {
		cin >> x;
	}

	for (int i = n - 1; i >= 0; --i) {
		int p = a[i].find('#');
		cout << p + 1 << " \n"[i == 0];
	}
}

C. The Legend of Freya the Frog

题意：给定x和y，k，每次可以移动0~k步数，每次移动后面向另一个方向，初始时面向x（只能移动面向的方向），问最少移动次数(0, 0->x, y)

思路：因为可以移动0步，所以就看最后一步是在x是在y。

总结：假如最少移动步数为1，如何考虑？先算出x或者y方向哪个需要移动的步数多，然后看这个步数在另一个方向上是否能够满足移动不超过终点，至于构造问题，就是先求出每次移动的基础步数，然后再取余，在前面或者后面的步数上分散这些余数即可

inline void solve(){
	int x, y, k;
	cin >> x >> y >> k;

	if ((x + k - 1) / k > (y + k - 1) / k) {
		cout << (x + k - 1) / k * 2 - 1<< '\n';
	}
	else {
		cout << (max(x, y) + k - 1) / k * 2 << '\n';
	}
}

D. Satyam and Counting

题意：给定n对点，y不超过1，问有多少种方式可以组成直角三角形。

总结：y不超过1，就直接暴力写就行。 一开始想的是对点排序，但是不如这样直接把点记录到坐标上方便。

inline void solve(){
	int n;
	cin >> n;

	vector<array<int, 2>> a(n + 233, {0, 0});
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		a[x][y] ++;
	}

	long long ans = 0;
	for (int i = 0; i <= n; ++i) {
		if (a[i][0] && a[i][1]) {
			ans += n - 2;
		}
		if ((i && a[i][0] && a[i - 1][1] && a[i + 1][1])) {
			ans ++;
		}
		if ((i && a[i][1] && a[i - 1][0] && a[i + 1][0])) {
			ans++;
		}

	}

	cout << ans << '\n';
}

E. Klee's SUPER DUPER LARGE Array!!!

题意:给定长度为n，数值连续（从k开始）的数组，求满足条件的最大值。

思路：一眼就是前缀和然后暴力找点就行，但是n太大不允许暴力，于是问题转化为寻找差值最小的前后缀问题。因为前缀和递增，所以直接在n上二分，找到左区间<=右区间的第一个端点，然后再跟>右区间的第一个端点来比较，取最优的即可。

总结：下次看清数据范围，调试了才发现n数量级不对，第i个数的值写错了，应该是k + i - 1

inline void solve(){
	long long n, k;
	cin >> n >> k;


	long long sum = ((k + n - 1 + k) * n / 2);

	long long ans = sum;
	int l = 1, r = n - 1;
// 2 3 4 5 6 7 8
	auto valid = [&](int i) {
		long long left = (k + i - 1 + k) * i / 2;
		long long right = sum - left;
		return left <= right;
	};

	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (valid(mid)) {
			l = mid;
		}
		else {
			r = mid - 1;
		}
	}

	auto cal = [&](int i)->long long {
		if (i == 0) {
			return INF_LL;
		}
		long long left = (k + i - 1 + k) * i / 2;
		long long right = left - sum;
		return abs(left + right);
	};

	ans = min({ans, cal(l), cal(l + 1)});

	cout << ans << "\n";
}

F. Firefly's Queries

题意：长度为n的数组循环n次，每次循环从第i个下标开始。q个查询给定区间端点[l, r]，求[l, r]的和。

思路：前缀和差分一步到位，对于当前端点x，先求出前面数组完整循环了多少次，然后求出本次循环开始的下标以及循环的长度，如果这个长度在pref[n]之前结束，可以直接算，否则要先把后面这部分加上来，再去加前面一部分。

总结：很久没接触这个类型了，一时没想到根据下标如何快速的计算出一个sum值出来。题型跟e有点像，e是循环要被填充，这个是直接循环，不过都要指定一个新的起点出来，计算贡献。

inline void solve(){
	int n, q;
	cin >> n >> q;

	vector<long long> pref(n + 1);
	for (int i = 0; i < n; ++i) {
		int t;
		cin >> t;
		pref[i + 1] = pref[i] + t;
	}

	auto cal = [&](long long x) {
		int q = x / n;
		long long res = pref[n] * q;
		long long rem = x % n;
		if (rem + q <= n) {
			res += pref[rem + q] - pref[q];
		}
		else {
			res += pref[n] - pref[q] + pref[rem + q - n];
		}
		return res;
	};

	while (q --) {
		long long l, r;
		cin >> l >> r;

		cout << (cal(r) - cal(l - 1)) << '\n';
	}
}

unrated 是真无语啊