醉心代码无法自拔

程序员的自我修养(?)

0%

Atcoder Beginner Contest 368 题解

发表于 更新于 分类于
本文字数： 6.6k 阅读时长 ≈ 12 分钟

竞赛结果：Contestant,3378th,Solved ABCD,+5

A.Cut

题目大意

输入一个数组 $ a[1],a[2],…,a[n] $ 和一个数字 $k $ ，输出 $a[k],a[k+1],…,a[n],a[1],a[2],…a[k-1]$。

思路

  1. 直接 for 循环输出即可
  2. 使用 STL deque （？）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() // deque
{
    int n, k, tmp;
    cin >> n >> k;
    deque<int> deq;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        deq.push_back(tmp);
    }
    while (k--)
    {
        deq.push_front(deq.back());
        deq.pop_back();
    }
    while (!deq.empty())
        cout << deq.front() << " ", deq.pop_front();
}
1
2
3
4
5
6
7
8
9
10
11
12
void solve() // for
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = n - k; i < n; i++)
        cout << a[i] << ' ';
    for (int i = 0; i < n - k; i++)
        cout << a[i] << ' ';
}

B.Decrease 2 max elements

题目大意

输入一个数组 $ a[1],a[2],…,a[n] $，重复将数组降序排序，将前两个数字分别 -1，求几次后让整个数组最多只有一个正数

思路

针对此题

范围非常小，直接暴力就行。

范围变大时候的更快解法

首先，每次操作 $\displaystyle\sum _ {i=1} ^ NA _ i$ 都会减少 $2$ ，因此答案小于或等于 $\displaystyle\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor$ 。

接下来，由于每次操作中 $\displaystyle\max _ {1\leq i\leq N}A _ i$ 最多减少 $1$ ，因此 $\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i$ 在 $1$ 操作中减少 $1$ 或 $2$ ，结果小于或等于 $\displaystyle\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i$ 。

所以答案为$\displaystyle\min\Biggl\lbrace\Biggl\lfloor\dfrac12\sum _ {i=1} ^ NA _ i\Biggr\rfloor,\sum _ {i=1} ^ NA _ i-\max _ {1\leq i\leq N}A _ i\Biggr\rbrace$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() // brute
{
	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];
	int cnt = 0;
	sort(all(vec), greater<>());
	do
	{
		vec[0]--, vec[1]--, cnt++;
		sort(all(vec), greater<>());
	} while (vec[0] > 0 && vec[1] > 0);
	cout << cnt << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() // math
{
	int n;
	cin >> n;
	int sum = 0, mx = 0;
	while (n--)
	{
		int a;
		cin >> a;
		sum += a;
		mx = max(a, mx);
	}
	cout << min(sum / 2, sum - mx) << endl;
}

C.Triple Attack

题目大意

输入一个数组 $ a[1],a[2],…,a[n] $，每次对数组第一个数重复以下操作，当第一个数降到0及以下的时候将其移出数组：

  1. 将数字减少1
  2. 将数字减少1
  3. 将数字减少3

问几次操作后能置空整个数组。

思路

本题有坑。移出一个数字以后其操作次数是保留的，如果在移出头部数字的时候已经进行了前两步操作，那么可以直接对下一个数进行第三步操作。（吃了两发）

当第一个敌人的生命值达到 $5$ 或更高时，接下来的 $3$ 操作可以使第一个敌人的生命值减少 $5$ ，无论 $T$ 的当前值是多少。如果第一个敌人的生命值是 $H$ ，这组三个动作将重复 $\lfloor\frac{H}{5}\rfloor$ 组。通过一次性处理这部分并模拟即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using i64 = long long;
void solve()
{
	int n;
	cin >> n;
	i64 cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		cnt += a / 5 * 3;
		a %= 5;
		while (a > 0)
		{
			cnt++;
			if (cnt % 3 == 0)
				a -= 3;
			else
				a--;
		}
	}
	cout << cnt << endl;
}

D.Minimum Steiner Tree

题目大意

给一颗 $n$ 个节点， $n-1$ 条边的树，给出 $k$ 个节点，找到连接这 $k$ 个节点的最小联通块的大小。

思路

带路径染色的DFS。用 vector <bool> 存一下被染色的路径点和需要找到的 $k$ 个节点即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int MAXN = 2e5 + 10;
vector<int> edges[MAXN];
vector<bool> vec(MAXN);
int n, k;
vector<bool> vis(MAXN);
int ans = INT_MAX;
bool dfs(int start)
{
	vis[start] = true;
	for (int edge : edges[start])
	{
		if (!vis[edge] && dfs(edge))
			vec[start] = true;
	}
	vis[start] = false;
	if (vec[start])
		return true;
	else
		return false;
}
void solve()
{
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	int start = -1;
	for (int i = 0; i < k; i++)
	{
		int tmp;
		cin >> tmp;
		if (i == 0)
			start = tmp;
		vec[tmp] = true;
	}
	dfs(start);
	cout << count(all(vec), true) << endl;
}

以下为补题部分

F.Dividing Game

题目大意

输入一个数组 $ a[1],a[2],…,a[n] $，Anna 和 Bruno 轮流选取其中的数字 $a[i]$ ，并且将 $a[i]$ 替换为其任意一个非自己的因数。不能进行此操作的玩家输掉比赛。问谁会赢。

思路

Nim 游戏中的 SG 函数。参考资料（OI WIKI），参考资料2（洛谷博客，SG函数精讲）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	int m = INT_MIN;
	for (int i = 0; i < n; i++)
		cin >> a[i], m = max(m, a[i]);
	vector<vector<int>> d(m + 1);
	for (int i = 1; i <= m; i++)
		for (int j = 2 * i; j <= m; j += i)
			d[j].push_back(i); // 因数
	vector<int> sg(m + 1);
	for (int x = 1; x <= m; x++)
	{
		int k = d[x].size();
		vector<int> cnt(k + 1);
		for (auto y : d[x])
			if (sg[y] <= k)
				cnt[sg[y]]++;
		while (cnt[sg[x]] > 0)
			sg[x]++;
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans ^= sg[a[i]];
	cout << (ans > 0 ? "Anna" : "Bruno") << endl;
}

G.Add and Multiply Queries

题目大意

输入两个数组 $ a[1],a[2],…,a[n] 和 b[1],b[2],…,b[n] $，给定 $q$ 组如下格式的询问：

1 i x：将 $a[i]$ 的值改为 $x$。

2 i x：将 $b[i]$ 的值改为 $x$。

3 l r： 设定 $v=0$，对于区间 $[l,r]$ ，将 $v$ 替换为 $v+a[i]$ 或者 $v*b[i]$，求最大的 $v$。

保证操作3的答案最高为$10^{18}$。

思路

因为保证了操作3有答案上限，则数组 $b$ 中超过 $1$ 的个数不会大于 $60$ 个 ($2^{60} > 10^{18}$)。

用树状数组维护 $a$，用 $set$ 维护 $b[i] > 1$ 的 $i$。然后查找区间内有没有大于 $1$ 的数，并且判断两种操作哪种最优即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using i64 = long long;
const int N = 2e5 + 10;
struct Fenwick
{
	int n;
	vector<i64> tr;
	Fenwick(vector<i64> &vec)
	{
		n = vec.size();
		tr.resize(N);
		for (int i = 1; i <= n; i++)
			update_add(i, vec[i]);
	}
	int lowbit(int x)
	{
		return x & -x;
	}

	void update_add(int x, i64 val)
	{
		for (int i = x; i < n; i += lowbit(i))
			tr[i] += val;
	}

	void update_sub(int x, i64 val)
	{
		update_add(x, -val);
	}

	i64 query(int x)
	{
		i64 res = 0;
		for (int i = x; i; i -= lowbit(i))
			res += tr[i];
		return res;
	}
};

void solve()
{
	int n;
	cin >> n;
	vector<i64> a(n + 1), b(n + 1);
	set<int> st;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	Fenwick tree(a);
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
		if (b[i] > 1)
			st.insert(i);
	}
	int q;
	cin >> q;
	while (q--)
	{
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1)
		{
			tree.update_sub(l, a[l]);
			a[l] = r;
			tree.update_add(l, a[l]);
		}
		else if (op == 2)
		{
			if (b[l] > 1)
				st.erase(l);
			b[l] = r;
			if (b[l] > 1)
				st.insert(l);
		}
		else
		{
			i64 v = a[l];
			l = l + 1;
			while (1)
			{
				auto it = st.lower_bound(l);
				if (it == st.end() || *it > r)
				{
					v += tree.query(r) - tree.query(l - 1);
					break;
				}
				v += tree.query(*it - 1) - tree.query(l - 1);
				v = max(v * b[*it], v + a[*it]);
				l = *it + 1;
			}
			cout << v << endl;
		}
	}
}

E.Train Delay

题目大意

$n$ 个城市，$m$ 条火车，第 $i$ 条 从 $a[i]$ 城市在 $s[i]$ 时刻出发，到达 $b[i]$ 城市的时刻为 $t[i]$。

现在第一条线路的火车晚点了 $x[1]$ 分钟，为了让任意一组本来可以换乘的火车仍能换乘，需要对其他的所有火车进行晚点（也可以不晚点）。
找出从第 $2$ 辆到第 $m$ 辆火车，每辆火车最少需要晚点多长时间。

思路

I don't know how to write dp I am dp 低手。

以下代码是 jiangly 的。大概思路还要梳理一下。可以参考一下Atcoder Editorial的思路。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void solve()
{
	int N, M, X0;
	cin >> N >> M >> X0;
	vector<int> A(M), B(M), S(M), T(M);
	for (int i = 0; i < M; i++)
	{
		cin >> A[i] >> B[i] >> S[i] >> T[i];
		A[i]--, B[i]--;
	}

	vector<array<int, 3>> e(2 * M);
	for (int i = 0; i < M; i++)
	{
		e[2 * i] = {S[i], 1, i};
		e[2 * i + 1] = {T[i], 0, i};
	}

	sort(e.begin(), e.end());

	vector<int> X(M);
	vector<int> tm(N);
	X[0] = X0;
	for (auto [t, o, i] : e)
	{
		if (o == 1)
			X[i] = max(X[i], tm[A[i]] - S[i]);
		else
			tm[B[i]] = max(tm[B[i]], T[i] + X[i]);
	}

	for (int i = 1; i < M; i++)
		cout << X[i] << " ";
}