AtCoder Beginner Contest 359

作者：在线问答5 | 2024-07-24 23:41:53

踩

atcoder beginner contest 359

@[TOC](AtCoder Beginner Contest 359)
1

AtCoder Beginner Contest 359

这场我赛时打的非常不好，只做出了 $2$ 题。

A - Count Takahashi

签到

// Problem: A - Count Takahashi
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")

template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

signed main ()
{
	int n = rd (int); 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		string s; cin >> s; 
		if (s == "Takahashi") ans ++ ; 
	}
	printf ("%d\n", ans); 
    return 0;
}
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

B - Couples

签到

// Problem: B - Couples
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 105; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
vector <int> vec[N]; 
signed main ()
{
	n = rd (int); 
	for (int i = 1; i <= 2 * n; i ++ )
	{
		int x = rd (int); 
		vec[x].push_back (i); 
	}
	int ans = 0; 
	for (int i = 1; i <= n; i ++ ) ans += (vec[i][1] - vec[i][0] == 2); 
	printf ("%d\n", ans); 
    return 0;
}
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

C - Tile Distance 2

首先，如果起点坐标或终点坐标在一个砖块的右侧时，把他变为在这个砖块的左侧不影响最终答案。
计算横坐标和纵坐标需要移动的格子数，分别记为 $a$ ， $b$ 。
画图模拟可知：进行纵向运动时，可以免费向左或者向右移动一格。所以优先向上运动。
如果向上运动后，横坐标依旧没有达到目标值，那么就需要进行横向运动。可以发现，每花 $1$ 块钱，可以横向移动 $2$ 格，所以横向运动的花费为 $\frac{\operatorname{max}(0,a-b)}{2}$

// Problem: C - Tile Distance 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")

template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int sx, sy, ex, ey; 
signed main ()
{
	sx = rd (int), sy = rd (int), ex = rd (int), ey = rd (int); 
	if ((sx + sy) % 2 == 1) sx -- ; 
	if ((ex + ey) % 2 == 1) ex -- ; 
	int a = abs (sx - ex), b = abs (sy - ey); 
	printf ("%lld\n", b + max (0ll, a - b) / 2); 
    return 0;
}
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

D - Avoid K Palindrome

把题目中的 A，B 转化为 $0$ ， $1$ 。
$dp_{i,s}$ 表示前 $i$ 个字符中，最后 $k$ 个字符为 $s$ ，保证没有长度为 $k$ 的方案数
转移显然

// Problem: D - Avoid K Palindrome
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 1005, M = (1 << 10) + 5, mod = 998244353; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n, k; 
string S; 
int dp[N][M]; 
bool checkpalin (int state)
{
	for (int i = 0; i < k / 2; i ++ )
	{
		if (((state >> i) ^ (state >> k - i - 1)) & 1)
			return 0;
	}
	return 1;
}
signed main ()
{
	cin >> n >> k >> S; 
	dp[0][0] = 1; 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		for (int s = 0; s < (1 << k); s ++ )
		{
			if (i >= k && checkpalin (s)) continue;
			if ((S[i - 1] == 'A' || S[i - 1] == '?') && s % 2 == 0)
				dp[i][s] = (dp[i][s] + (dp[i - 1][(s >> 1) + (1 << (k - 1))] + 
										dp[i - 1][s >> 1])) % mod;
			if ((S[i - 1] == 'B' || S[i - 1] == '?') && s % 2 == 1)
				dp[i][s] = (dp[i][s] + (dp[i - 1][(s >> 1) + (1 << (k - 1))] + 
										dp[i - 1][s >> 1])) % mod;
			if (i == n) ans = (ans + dp[i][s]) % mod;
		}
	}
	printf ("%d\n", ans); 
	return 0; 
}
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

E - Water Tank

题目意思感觉有点抽象
对于每个挡板 $i$ ，找到在他前面第一个比他高的挡板 $pos_i$ （用单调栈），那么答案 $ans_i$ 就可以从这个挡板继承过来。
$ans_i=ans_{pos_i}+(i-pos_i)\times a_i$

// Problem: E - Water Tank
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 200005; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
int a[N], pos[N]; 
int ans[N]; 
signed main ()
{
	n = rd (int); 
	stack <pii> stk; 
	for (int i = 1; i <= n; i ++ )
	{
		a[i] = rd (int); 
		while (!stk.empty () && stk.top ().fi < a[i]) stk.pop (); 
		if (!stk.empty ()) pos[i] = stk.top().se; 
		stk.push ({a[i], i});
	}
	for (int i = 1; i <= n; i ++ )
	{
		ans[i] = ans[pos[i]] + (i - pos[i]) * a[i]; 
		printf ("%lld ", ans[i] + 1); 
	}
	return 0; 
}
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

F - Tree Degree Optimization

首先，因为这是一棵树，所以每个点的度数至少为 $1$
总度数为 $2\times n - 2$
我们可以进行贪心。在每个节点的度数都是 $1$ 的基础上，考虑去动态安排度数，使得最终答案最小
对 $i$ 号点考虑，如果度数从 $d_i$ 变为 $d_i+1$ ：
原本贡献 $d_i^2 \times a_i$ ；
新的贡献： $(d_i+1)^2\times a_i=(d_i^2+2\times d_i+1)\times a_i$
如果给 $i$ 号点增加一个度数，造成的增量为 $(2\times d_i+1)\times a_i$
每次选取最小的增量，加入答案。这一步可以使用 priority_queue 来实现

// Problem: F - Tree Degree Optimization
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 200005; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
int a[N]; 
struct node
{
	int x, y;
	bool operator < (const node &t) const
	{
		return (2 * x + 1) * y > (2 * t.x + 1) * t.y;
	}
}; 
signed main ()
{
	n = rd (int); 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		a[i] = rd (int); 
		ans += a[i]; 
	}
	priority_queue <node> q; 
	for (int i = 1; i <= n; i ++ ) q.push ({1, a[i]});
	for (int i = 1; i < n - 1; i ++ )
	{
		node u = q.top (); q.pop (); 
		ans += (u.x * 2 + 1) * u.y;
		if (u.x < n - 1) q.push ({u.x + 1, u.y});
	}
	printf ("%lld\n", ans); 
	return 0;
}
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

G - Sum of Tree Distance

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】