AtCoder Beginner Contest 425

atcoder, 题解

A Sigma Cubes

题目描述

输入,计算

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
	int n;
	std::cin >> n;
	int res = 0;
	for(int i = 1; i <= n; i ++) {
		if(i & 1) res -= i * i * i;
		else res += i * i * i;
	}

	std::cout << res << std::endl;
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
}

B Find Permutation 2

题目描述

给出数组 , 判断是否存在一个排列使得满足:

是一个排列。
,

若存在这样的排列，输出 $P$

解题思路

首先记录下中非的其他数的个数记为 ,若则不可能有合法的

将为的依次填入处即可获得排列 .

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a(n + 1, 0), b(n + 1, 0);
	for(int i = 1; i <= n; i ++) {
		std::cin >> b[i];
		if(b[i] != -1) {
			a[b[i]] ++;
		}
	}

	for(int i = 1; i <= n; i ++) {
		if(a[i] > 1) {
			std::cout << "No" << std::endl;
			return;
		}
	}
	std::cout << "Yes" << std::endl;
	std::queue<int> q;
	for(int i = 1; i <= n; i ++) {
		if(!a[i]) {
			q.push(i);
		}
	}
	for(int i = 1; i <= n; i ++) {
		if(b[i] == -1) {
			std::cout << q.front() << ' ';
			q.pop();
		}else {
			std::cout << b[i] << ' ';
		}
	}
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
}

C Rotate and Sum Query

题目描述

给出数组和次查询,每次查询如下:

: 循环次，每次循环都将放在数组末尾.
: 查询区间的总和

数据范围：

解题思路

可以发现数据范围较大，无法使用rotate去模拟，但是可以发现每次循环次数到达后就会回到初始数组，区间总和也只与有关.

我们可以使用变化后的区间和去找变化前的区间 ,可以发现需要预处理前缀和 .

但是变化前的区间可能会出现，这个区间的值则是区间外的总和.

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
	int n, q;
	std::cin >> n >> q;
	std::vector<int> s(n + 1, 0), a(n + 1, 0);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		s[i] = a[i];
		if (i) s[i] = s[i - 1] + a[i];
	}
	int t, x, y, ct = 0;
	while (q--) {
		std::cin >> t >> x;
		if (t == 1) {
			ct += x;
		} else {
			std::cin >> y;
			x = (x - 1 + ct) % n;
			y = (y - 1 + ct) % n;
			if (x > y) {
				std::cout << s[y] + s[n - 1] - (x ? s[x - 1] : 0) << std::endl;
			} else {
				std::cout << s[y] - (x ? s[x - 1] : 0) << std::endl;
			}
		}
	}
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	solve();
}