Atcoder beginner contest 378

atcoder, 题解

A.Pairing

题目描述

{% tabs A %}

There are four balls, and the color of the -th ball is .
Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

{% endtabs %}

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
	std::map<int, int> mp;
	for(int i = 0; i < 4; i++) {
		int x;
		std::cin >> x;
		mp[x]++;
	}

	int s = 0;
	for(auto [x, y] : mp) {
		s += y / 2;
	}
	std::cout << s << endl;
}

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

B.Garbage Collection

Garbage Collection

题目描述

{% tabs B %}

In AtCoder City, types of garbage are collected regularly. The -th type of garbage is collected on days when the date modulo equals .
Answer queries. In the -th query , given that the -th type of garbage is put out on day , answer the next day on which it will be collected.
Here, if the -th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

{% endtabs %}

解题思路

模拟

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
	int n;
	std::cin >> n;
	std::vector<pii > a(n);
	for(int i = 0; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		a[i] = {u, v};
	}

	int q;
	std::cin >> q;
	while (q--) {
		int t, d;
		std::cin >> t >> d;
		t--;
		auto [x, y] = a[t];
		int w = d / x * x + y;
		if (w < d) w += x;
		std::cout << w << endl;
	}
}

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

C.Repeating

Repeating

题目描述

{% tabs C %}

You are given a sequence of positive numbers, . Find the sequence of length defined as follows.

For , define as follows: - Let be the most recent position before where an element equal to appeared. If such a position does not exist, let .
More precisely, if there exists a positive integer such that and $j < i$ , let be the largest such . If no such exists, let .

给你一个由个正数组成的数列。求长度为的序列的定义如下。

对于，定义如下：- 设是在之前出现过与相同元素的最近位置。如果不存在这样的位置，则设为。
更确切地说，如果存在一个正整数，使得和 $j < i$ ，那么就让成为最大的。如果不存在这样的 , 则设 . {% endtabs %}

解题思路

标记之前出现过的数的位置

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a(n + 2), b(n + 2);
	std::map<int, int> mp;
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	b[1] = -1;
	mp[a[1]] = 1;
	for(int i = 2; i <= n; i++) {
		if (mp.find(a[i]) != mp.end()) {
			b[i] = mp[a[i]];
		}else {
			b[i] = -1;
		}
		mp[a[i]] = i;
	}

	for(int i = 1; i <= n; i++) std::cout << b[i] << " \n"[i == n];
}

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

D.Count Simple Paths

Count Simple Paths

题目描述

{% tabs D %}

There is a grid of cells. Let denote the cell at the -th row from the top and the -th column from the left.
Cell is empty if is ., and blocked if it is #.
Count the number of ways to start from an empty cell and make moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.
Specifically, count the number of sequences of length , , satisfying the following.

, , and is ., for each .
for each .
for each $0 \leq k < l \leq K$ .

有一个由个单元格组成的网格。让表示从上往下第行，从左往上第列的单元格。
如果是 .，则单元格为空；如果是 # ，则单元格阻塞。
计算从一个空单元格开始，向相邻单元格（向上、向下、向左或向右）进行移动，而不经过被阻塞的方格，并且不多次访问同一单元格的方法的数目。
具体地说，计算满足以下条件的长度为 , 的序列的个数。

、和为 .，每个为 .。
为每个。
每个 $0 \leq k < l \leq K$ 的。 {% endtabs %}

解题思路

dfs暴搜

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void solve() {
	int n, m, k;
	std::cin >> n >> m >> k;
	std::vector<std::string> s(n);
	for(int i = 0; i < n; i++) std::cin >> s[i];

	auto check = [&](int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < m;
	};

	int res = 0;

	std::vector vis(n, std::vector<bool>(m, false));
	std::function<void(int, int, int)> dfs = ([&](int x, int y, int val) {
		vis[x][y] = true;
		if (val == k) {
			res++;
			return;
		}
		for(int i = 0; i < 4; i++) {
			int u = x + dx[i], v = y + dy[i];
			if (check(u, v) && !vis[u][v] && s[u][v] == '.') {
				dfs(u, v, val + 1);
				vis[u][v] = false;
			}
		}
	});

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if (s[i][j] == '.')
				dfs(i, j, 0), vis[i][j] = false;
		}
	}
	std::cout << res << endl;
}

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