Acwing157周赛题解

A

算法标签: 基础算法, 模拟

将情况分为两类, 因为是两位数, 因此看个位, 如果$<5$, 舍去, 否则进位

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int r = n % 10;

	if (r < 5) cout << n - r << "\n";
	else cout << n - r + 10 << "\n";

	return 0;
}

B

算法标签: 模拟, 贪心

从小数点后第一个$\ge 5$的位置开始向前, 一定是最优进位方式, 如果从后面进位结果一定没有当前进位好

并且每次进位最多一次

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n, m;
	string s;

	cin >> n >> m >> s;
	// 找到小数点位置
	int pt = s.find('.');
	// 找到小数点后第一个大于等于5的位置
	int k = pt + 1;
	while (k < n && s[k] < '5') k++;

	// 小数点后不存在能四舍五入的位置
	if (k == n) {
   
		cout << s << "\n";
		return 0;
	}

	s = s.substr(0, k);
	k--, m--;
	while (k >= 0) {
   
		if (s[k] != '.') {
   
			s[k]++;
			if (s[k] < '5') break;
			if (s[k] <= '9') {
   
				if (!m || k < pt) break;
				s[k] = '0';
				m--;
			}
			else s[k] = '0';
		}
		// 如果当前位置不是小数点继续向前枚举
		k--;
	}

	if (k < 0) s = "1" + s;
	while (s.back() == '0') s.pop_back();
	if (s.back() == '.') s.pop_back();
	cout << s << "\n";

	return 0;
}

最终$k<0$的情况就是计算完后还向前进一位, 因此需要将原字符串前面$+1$

C

算法标签: $DSU$, 线段树

删除某个数后求最大子段和
倒着做相当于每次添加一个数, 因为区间中元素都是正的, 因此区间元素越多越好, 用$DSU$维护区间总和到代表元素上

$DSU$做法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n;
int a[N], b[N];
int fa[N];
LL s[N], ans[N];
bool vis[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= n; ++i) fa[i] = i;

	// 倒着做相当于每次添加一个数
	for (int i = n; i >= 1; --i) {
   
		int k = b[i];
		vis[k] = true, s[k] = a[k];
		if (vis[k + 1]) {
   
			s[find(k + 1)] += s[k];
			fa[k] = find(k + 1);
		}
		// 如果左右都有区间, 全部合并
		if (vis[k - 1]) {
   
			s[find(k)] += s[k - 1];
			fa[k - 1] = find(k);
		}

		// ans[i]存储的是添加完i + 1个元素后的最大子段和, 因此当前计算的是添加完i也就是i - 1处的最大子段和
		ans[i - 1] = max(ans[i], s[find(k)]);
	}

	for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
	return 0;
}

线段树做法

基础线段树之单点修改, 区间查询

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef __int128 LL;
const int N = 1e5 + 10;
const LL INF = 9e18;

int n;
int a[N], b[N];
struct Node {
   
	int l, r;
	LL res, lm, rm, sum;
} tr[N << 4];

ostream &operator<< (ostream &out, LL val) {
   
	if (val == 0) {
   
		out << 0;
		return out;
	}

	vector<int> nums;
	while (val) nums.push_back(val % 10), val /= 10;
	while (!nums.empty()) {
   
		out << nums.back();
		nums.pop_back();
	}

	return out;
}

void push_up(Node &u, Node &ls, Node &rs) {
   
	u.sum = ls.sum + rs.sum;
	u.lm = max(ls.lm, ls.sum + rs.lm);
	u.rm = max(rs.rm, rs.sum + ls.rm);
	u.res = max({
   ls.res, rs.res, ls.rm + rs.lm});
}

void push_up(int u) {
   
	push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
   
	if (l == r) {
   
		int val = a[l];
		tr[u] = {
   l, r, val, val, val, val};
		return;
	}

	tr[u] = {
   l, r};
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void modify(int u, int pos, LL val) {
   
	if (tr[u].l == tr[u].r) {
   
		tr[u] = {
   pos, pos, val, val, val, val};
		return;
	}

	int mid = tr[u].l + tr[u].r >> 1;
	pos <= mid ? modify(u << 1, pos, val) : modify(u << 1 | 1, pos, val);
	push_up(u);
}

Node query(int u, int ql, int qr) {
   
	if (tr[u].l >= ql && tr[u].r <= qr) return tr[u];

	int mid = tr[u].l + tr[u].r >> 1;
	if (qr <= mid) return query(u << 1, ql, qr);
	if (ql > mid) return query(u << 1 | 1, ql, qr);

	Node res;
	Node ls = query(u << 1, ql, qr);
	Node rs = query(u << 1 | 1, ql, qr);
	push_up(res, ls, rs);
	return res;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];

	build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
   
		int k = b[i];
		modify(1, k, -INF);
		Node u = query(1, 1, n);
		cout << max(u.res, (LL) 0) << "\n";
	}

	return 0;
}