专栏文章

AtCoder Beginner Contest 373 A~D

IIronMen
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir1ufks
此快照首次捕获于
2025/12/04 14:22
3 个月前
此快照最后确认于
2025/12/04 14:22
3 个月前
查看原文

A - September

洛谷链接
AtCoder链接

题目

有 1212 个由小写英文字母组成的字符串 S1,S2,…,S12S_1,S_2, \ldots ,S_{12}。
求有多少个整数 i(1≤i≤12)i(1 \le i \le 12) 满足 SiS_i 的长度为 ii 的整数。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

string s;
int cnt;

int main()
{
	for (int i = 0; i < 12; i ++ )
	{
		cin >> s;
		if (s.length() == i + 1)
			cnt ++;
	}
	cout << cnt << '\n';
	return 0;
}

B - 1D Keyboard

洛谷链接
AtCoder链接

题目

有一个键盘，上面的 2626 键排列在一条数轴上。
键盘的排列用字符串 SS 表示，它是由 ABCDEFGHIJKLMNOPQRSTUVWXYZ 组成的排列。字符 SxS_x 对应的按键位于坐标 x(1≤x≤26)x(1 \le x \le 26) 处。(1≤x≤26)(1 \le x \le 26)。这里的 SxS_x 表示 SS 的第 xx 个字符。
您将使用此键盘按此顺序输入 ABCDEFGHIJKLMNOPQRSTUVWXYZ，准确输入每个字母一次。要输入一个字符，您需要将手指移到与该字符对应的按键坐标处并按下该键。
起初，您的手指位于字母 A 对应键的坐标处。请找出从按下 A 键到按下 Z 键之间手指可能移动的最小总距离。在这里，按键并不影响距离。

思路

先找到 A 的位置，标记为 now，然后按顺序依次找到对应按键的位置，标记为 sit，更新距离，将 now 赋值为 sit。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

string s;
int now, cnt, sit;

int main ()
{
	cin >> s;
	for (int i = 0; i < 26; i ++ )
	{
		if (s[i] == 'A')
			now = i + 1;
	}
	for (int i = 1; i < 26; i ++ )
	{
		for (int j = 0; j < 26; j ++ )
		{
			if (s[j] == 65 + i)
			{
				sit = j + 1;
				break;
			}
		}
		cnt += abs(sit - now);
		now = sit;
	}
	cout << cnt << '\n';
	return 0 ;
}

C - Max Ai+Bj

洛谷链接
AtCoder链接

题目

给你两个整数序列 AA 和 BB，每个长度为 NN。请选择整数 i,j(1≤i,j≤N)i,j(1 \le i,j \le N) 使 Ai+BjA_i+B_j 的值最大。

思路

很明显，要得到 max⁡Ai+Bj\max_{A_i+B_j} 只需要分别取两个序列的最大值相加。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int n, a[500010], b[500010];

int main ()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i ++ )
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i ++ )
		scanf("%d", &b[i]);
	sort(a, a + n);
	sort(b, b + n);
	cout << a[n - 1] + b[n - 1] << '\n';
	return 0 ;
}

D - Hidden Weights

洛谷链接
AtCoder链接

题目

给你一个有向图，图中有 NN 个顶点和 MM 条边。第 jj 条有向边从顶点 uju_j 到顶点 vjv_j，权值为 wjw_j。
请找出一种方法，在每个顶点写入一个介于 −1018-10^{18} 和 101810^{18} 之间的整数，从而满足下面的条件。
  • 假设 xix_i 是写在顶点 ii 上的值。对于所有的边 j=1,2,…,Mj=1,2, \ldots ,M，xvj−xuj=wjx_{v_j}-x_{u_j}=w_j 成立。
可以保证在给定的输入中至少存在一个这样的赋值。

思路

如果确定了一个顶点的值，相邻顶点的值确定。由于该图的连通性，只要任意一点上的值确定，所有的值都会根据该点得知而确定。
因此，可以给初始的顶点赋值为 00，BFS 确定其连通的值。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

struct node
{
	long long v, w;
};

queue<long long> q;
vector<node> vc[200010];
bool vis[200010];
long long n, m, u, v, w, ans[200010];

int main()
{
	scanf("%lld %lld", &n, &m);
	while (m -- )
	{
		scanf("%lld %lld %lld", &u, &v, &w);
		vc[u].push_back({v, w});
		vc[v].push_back({u, -w});
	}
	for (long long i = 1; i <= n; i ++ )
	{
		if (vis[i])
			continue;
		q.push(i);
		vis[i] = 1;
		while (!q.empty())
		{
			u = q.front();
			for (auto i : vc[u])
			{
				if (!vis[i.v])
				{
					vis[i.v] = 1;
					ans[i.v] = ans[u] + i.w;
					q.push(i.v);
				}
			}
			q.pop();
		}
	}
	for (long long i = 1; i <= n; i ++ )
		cout << ans[i] << ' ';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...