AtCoder Beginner Contest 481——题解

本次题目均来自：https://atcoder.jp/contests/abc481

A – Digits of A+B

时间限制： 2 秒
内存限制： 1024 MiB
分值： 100 分

题目描述

给定两个整数 $A$ 和 $B$，它们的取值范围均为 $1$ 到 $9$（包含端点）。

求 $A+B$ 的结果有多少位数字。

数据范围

• $A$ 和 $B$ 均为整数。
• $1\le A,B\le 9$。

输入格式

从标准输入读入，格式如下：

A B

输出格式

输出 $A+B$ 的位数。

样例输入 1

4 9

样例输出 1

2

样例解释 1

$4+9=13$，而 $13$ 是一个两位数。

样例输入 2

7 1

样例输出 2

1

样例解释 2

$7+1=8$，而 $8$ 是一个一位数。

解题思路

$A$ 和 $B$ 它们的取值范围均为 $1$ 到 $9$， 他们的加和最大就是$18$，最小是$2$。
因此只要不小于$10$就是结果就是两位数，否则就是一位数。

代码

#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
int ans;

int main()
{
cin >> a >> b;
ans = a + b;
if (ans < 10)
puts("1");
else puts("2");
return 0;
}

B – Polyline

时间限制： 2 秒
内存限制： 1024 MiB
分值： 200 分

题目描述

在 $xy$ 平面上有 $N$ 个点，编号为 $1,2,\dots ,N$。第 $i$ 个点的坐标为 $(i,A_i)$。

对于 $i=1,2,\dots ,N-1$，用线段连接第 $i$ 个点与第 $i+1$ 个点，形成一条折线。

求这条折线上（包括端点）纵坐标为 $K$ 的点的数量。

题目保证满足条件的点的数量是有限的。

数据范围

• $2\le N\le 100$。
• $1\le A_i\le 100$（$1\le i\le N$）。
• $A_i\ne A_{i+1}$（$1\le i<N$）。
• $1\le K\le 100$。
• 所有输入值均为整数。

输入格式

从标准输入读入，格式如下：

N K
A_1 A_2 … A_N

输出格式

输出折线上纵坐标为 $K$ 的点的数量。

样例输入 1

5 3
1 3 1 5 1

样例输出 1

3

样例解释 1

满足条件的点共有 $3$ 个，分别为：

$$(2,3),\left(\frac{7}{2},3\right),\left(\frac{9}{2},3\right)。$$

注意，点 $(2,3)$ 是连接第 $1、2$ 个点的线段与连接第 $2、3$ 个点的线段的公共端点，但只计数一次。

解题思路

本质上就是求$y$ = $k$ 这条直线与折线图之间有几个交点。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 100;

int n, k;
int a[N];
int ans;//在主函数外声明的变量默认是0

int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);

for (int i = 1; i < n; i ++) //情况1
if ((a[i – 1] < k && a[i] > k) || (a[i – 1] > k && a[i] < k))
ans ++;

for (int i = 0; i < n; i ++)//情况2
if (a[i] == k)
ans ++;

printf("%d\\n", ans);
return 0;
}

C – Bank Accounts

时间限制： 2 秒
内存限制： 1024 MiB
分值： 300 分

题目描述

在 Kowasugi 银行的后院里，幽灵们正在种植南瓜。你决定为这些南瓜开设银行账户。

为一个南瓜开设银行账户时，会为该账户分配一个名称和一个 ID。ID 取尚未被使用的最小正整数。

最初，没有任何南瓜的银行账户。接下来会发生 $Q$ 次事件，请按顺序处理：

• 一个南瓜到来，并介绍自己的名字为 $s$。
  • 如果已经存在名称为 $s$ 的账户，则输出该账户的 ID。
  • 如果不存在名称为 $s$ 的账户，则新建一个名称为 $s$ 的账户，并输出其 ID。

数据范围

• $1\le Q\le 2\times 10^5$，且 $Q$ 为整数。
• 每次事件中的 $s$ 都是长度为 $1$ 到 $10$（包含端点）的字符串，仅由小写英文字母组成。

输入格式

从标准输入读入，格式如下：

Q
query_1
query_2
…
query_Q

其中，$quer{y}_i$ 表示第 $i$ 次事件，格式如下：

s

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 次事件中需要输出的账户 ID。

样例输入 1

8
pumpkin
hobak
ponpoen
hobak
pumpkin
boga
boga
hobak

样例输出 1

1
2
3
2
1
4
4
2

样例解释 1

事件按以下顺序发生：

• 第 $1$ 次事件：新建名称为 pumpkin 的账户，ID 为 $1$。
• 第 $2$ 次事件：新建名称为 hobak 的账户，ID 为 $2$。
• 第 $3$ 次事件：新建名称为 ponpoen 的账户，ID 为 $3$。
• 第 $4$ 次事件：名称为 hobak 的账户已经存在，其 ID 为 $2$。
• 第 $5$ 次事件：名称为 pumpkin 的账户已经存在，其 ID 为 $1$。
• 第 $6$ 次事件：新建名称为 boga 的账户，ID 为 $4$。
• 第 $7$ 次事件：名称为 boga 的账户已经存在，其 ID 为 $4$。
• 第 $8$ 次事件：名称为 hobak 的账户已经存在，其 ID 为 $2$。

解题思路

对于新建的账户（之前没有存在过的账户），从1开始往后分配，可以维护一个num来记录当前分配到哪个数了。
对于已经存在的账户，直接输出他的ID。
可以用一个哈希表来存储建立的账户，如果哈希表里面没有，就把num分配给新的账户，然后存在哈希表里，num++。
如果哈希表里有，直接输出字符串对应的数字。

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 2e5 + 100;

int n;
int num = 1;
unordered_map<string, int> ma;

int main()
{
scanf("%d", &n);

for (int i = 0; i < n; i ++)
{
string s;
cin >> s;

if (ma.count(s)) //哈希表中s的数目，存在返回1，不存在返回0
printf("%d\\n", ma[s]);
else
{
ma[s] = num ++;
printf("%d\\n", ma[s]);
}
}

return 0;
}

D – Autopilot

时间限制： 2 秒
内存限制： 1024 MiB
分值： 400 分

题目描述

有 $N$ 个星球和 $M$ 条航线。星球的编号为 $1$ 到 $N$，航线的编号为 $1$ 到 $M$。

第 $i$ 条航线从星球 $A_i$ 通往星球 $B_i$。所有航线均为单向航线。

一艘宇宙飞船可以进行以下两种操作：

• 在从当前星球沿一条航线可以直接到达的所有星球中，移动到编号最小的星球，不消耗燃料。
• 任意选择一个从当前星球沿一条航线可以直接到达的星球，移动到该星球，消耗 $1$ 单位燃料。

求飞船从星球 $S$ 出发，到达星球 $T$ 所需消耗的最少燃料。

如果无法到达星球 $T$，则输出 $-1$。

数据范围

• $2\le N\le 2\times 10^5$。
• $1\le M\le 2\times 10^5$。
• $1\le S,T\le N$。
• $S\ne T$。
• $1\le A_i,B_i\le N$。
• $A_i\ne B_i$。
• 所有输入值均为整数。

输入格式

从标准输入读入，格式如下：

N M S T
A_1 B_1
A_2 B_2
…
A_M B_M

输出格式

输出从星球 $S$ 到达星球 $T$ 所需消耗的最少燃料。如果无法到达，则输出 $-1$。

样例输入 1

7 10 2 1
2 5
2 4
4 2
4 3
3 1
3 5
3 6
5 6
6 1
6 7

样例输出 1

1

样例解释 1

按照以下顺序移动，飞船可以从星球 $2$ 到达星球 $1$，总共消耗 $1$ 单位燃料：

解题思路

本题显然是一个图论问题。求从$S$ 到 $T$ 所需消耗的最少燃料，可以转化为从$S$ 到 $T$ 的最短路径。
每个都是单向航道，因此是有向图。

代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 100;

int n, m, s, t;
int h[N], e[N], ne[N], mi[N], idx;
int dist[N];
bool st[N];

void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
mi[a] = min(mi[a], b); //记录该点连接的最小的编号点
}

//堆优化版
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;

priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({dist[s], s});

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second;
if (st[ver]) continue;
st[ver] = true;

for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
int w = 1;
if (j == mi[ver]) //是连接的最小编号点，边权就是0， 否则是1
w = 0;
if (dist[j] > dist[ver] + w)
{
dist[j] = dist[ver] + w;
heap.push({dist[j], j});
}
}
}

if (dist[t] >= 0x3f3f3f3f / 2) return -1;
else return dist[t];
}

int main()
{
memset(h, -1, sizeof(h));
memset(mi, 0x3f, sizeof(mi));
scanf("%d %d %d %d", &n, &m, &s, &t);
for (int i = 0; i < m; i ++)
{
int a, b;
scanf("%d %d", &a, &b);
add(a, b);
}

printf("%d\\n", dijkstra());
return 0;
}

E – Most Brilliant Starry Sky

时间限制： 2 秒
内存限制： 1024 MiB
分值： 450 分

题目描述

在 $xy$ 平面上有 $N$ 颗星星，第 $i$ 颗星星用坐标为 $(X_i,Y_i)$ 的点表示。

画一条经过原点且不经过任何星星的直线，并从这条直线将平面划分出的两个区域中选择一个。

求所选区域内最多可以包含多少颗星星。

给定 $T$ 组测试数据，请分别求解。

数据范围

• $1\le T\le 2\times 10^5$。
• $1\le N\le 2\times 10^5$。
• 所有测试数据的 $N$ 之和不超过 $2\times 10^5$。
• $-10^9\le X_i,Y_i\le 10^9$。
• $(X_i,Y_i)\ne (0,0)$。
• 当 $i\ne j$ 时，$(X_i,Y_i)\ne (X_j,Y_j)$。
• 任意两颗不同的星星都不与原点共线。
• 所有输入值均为整数。

输入格式

从标准输入读入，格式如下：

T
case_1
case_2
…
case_T

每组测试数据的格式如下：

N
X_1 Y_1
X_2 Y_2
…
X_N Y_N

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 组测试数据的答案。

样例输入 1

3
4
2 1
2 -1
-1 2
-2 -3
3
1 0
2 1
3 -2
20
351656128 486980400
43833334 189818465
244758360 416609525
82300518 959687980
37964139 458230904
-27725133 788196612
392638907 -544184247
-305242856 -60014958
-928747557 460755669
-415881318 638281062
307080966 -865172261
588339611 459847409
42654321 -744472144
-286500328 34461456
-874976232 -245368444
462187336 588372286
-229275227 749709882
-180126519 740406850
877877433 -211582842
256315745 -928285685

样例输出 1

3
3
15

样例解释 1

对于第 $1$ 组测试数据，如果画出直线 $y=-x$，并选择包含第 $1$ 颗星星的区域，那么该区域包含第 $1、2、3$ 颗星星。由于无法让所选区域包含全部 $4$ 颗星星，因此答案为 $3$。

对于第 $2$ 组测试数据，如果画出直线 $x=0$，并选择其右侧的区域，那么该区域包含全部星星。

解题思路

可以先进行极角排序，以$X$轴正方向为基准，然后绕着原点逆时针旋转360°这个方向来进行排序。

先把方向分成两部分：在$X$轴上方还是下方

int half(Point a)
{
if (a.y > 0 || (a.y == 0 && a.x > 0))
return 0;
return 1;
}

half = 0 表示度数范围在[0°，180°），也就是$X$轴上方的区域
half = 1 表示度数范围在[180°，360°），也就是$X$轴下方的区域

对于两个向量 (a,b)：
$$\mathrm{cross}(a,b)=a_x{b}_y-a_y{b}_x$$

在同一个半平面内：

• cross(a, b) > 0：a 的角度更小，排在前面。
• cross(a, b) < 0：b 的角度更小，排在前面。

则排序函数：

bool mul(PII w1, PII w2)
{
LL tmp1 = (LL)w1.first * w2.second;
LL tmp2 = (LL)w2.first * w1.second;
return tmp1 – tmp2 > 0;
}

bool cmp(PII w1, PII w2)
{
if (half(w1) != half(w2))
return half(w1) < half(w2);
else
return mul(w1, w2);
}

这样就排序完成了。接下来可以通过依次遍历每个点，然后找到有多少个点在该点所在的半平面中（180°）。
由于已经排序好，每个点与该点的角度是逐渐变大的，具有单调性，因此可以采用二分来优化复杂度。
通过二分来找到第一个不满足条件的位置。

值得一提的是：
在程序设计时，需要把数组需要存储两边这些点的信息。如果只有1 – n 时，如果遍历到k, 那么只能检查到k – n中有多少与k在同一半面的点，但是点1,2，…也可能与k是同一平面的。
因此需要存两遍：1 – n – 2n。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <utility>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 100;

int t, n;
PII a[2 * N];

// 将方向分成上下两个半平面，方便极角排序
int half(PII w)
{
if (w.second > 0 || (w.second == 0 && w.first > 0))
return 0;
else return 1;
}

// 叉积为正：从 w1 逆时针转到 w2 的角度在 (0°, 180°) 内
bool mul(PII w1, PII w2)
{
LL tmp1 = (LL)w1.first * w2.second;
LL tmp2 = (LL)w2.first * w1.second;
return tmp1 – tmp2 > 0;
}

// 先按半平面排序，同一半平面内用叉积比较方向
bool cmp(PII w1, PII w2)
{
if (half(w1) != half(w2))
return half(w1) < half(w2);
else
return mul(w1, w2);
}

int main()
{
scanf("%d", &t);

while (t –)
{
int ans = 0;
scanf("%d", &n);

for (int i = 0; i < n; i ++)
scanf("%d %d", &a[i].first, &a[i].second);

sort(a, a + n, cmp);

// 复制一遍，让跨过 360° 的区间也能连续访问
for (int i = 0; i < n; i ++)
a[i + n] = a[i];

for (int i = 0; i < n; i ++)
{
// 固定起点 i，二分第一个角度差不小于 180° 的位置
int l = i + 1, r = n + i;

while (l < r)
{
int mid = (l + r) / 2;

if (!mul(a[i], a[mid]))
r = mid;
else l = mid + 1;
}

// [i, r) 内的点可以放在同一侧
int cnt = r – i;
ans = max(ans, max(cnt, n – cnt));
}

printf("%d\\n", ans);
}

return 0;
}

F – Evil Shortest Path

时间限制： 2 秒
内存限制： 1024 MiB
分值： 525 分

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1,2,\dots ,N$。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$，边上写有一个 $1$ 到 $9$ 之间的数字 $C_i$。

沿着边的方向移动时，将经过的边上的数字按经过顺序拼接起来，得到的整数称为这次移动的得分。例如，如果依次经过的边上的数字为 $3,1,4$，则得分为 $314$。同一个顶点或同一条边可以经过多次。

对于每个 $v=2,3,\dots ,N$，求从顶点 $1$ 移动到顶点 $v$ 的最小得分，并输出该最小得分对 $998244353$ 取模的结果。

题目保证，从顶点 $1$ 出发，沿有向边可以到达其他所有顶点。

数据范围

• $2\le N\le 2\times 10^5$。
• $N-1\le M\le 2\times 10^5$。
• $1\le A_i,B_i\le N$。
• $1\le C_i\le 9$。
• 所有输入值均为整数。
• 从顶点 $1$ 出发，沿有向边可以到达其他所有顶点。

输入格式

从标准输入读入，格式如下：

N M
A_1 B_1 C_1
A_2 B_2 C_2
…
A_M B_M C_M

输出格式

输出 $N-1$ 行。

对于每个 $v=2,3,\dots ,N$，第 $v-1$ 行输出从顶点 $1$ 到顶点 $v$ 的最小得分对 $998244353$ 取模的结果。

样例输入 1

4 4
1 2 1
1 3 1
2 4 9
3 4 2

样例输出 1

1
1
12

样例解释 1

• 对于顶点 $2$，沿 $1\stackrel{1}{}2$ 移动，得分为 $1$。
• 对于顶点 $3$，沿 $1\stackrel{1}{}3$ 移动，得分为 $1$。
• 对于顶点 $4$，沿 $1\stackrel{1}{}2\stackrel{9}{}4$ 移动，得分为 $19$；沿 $1\stackrel{1}{}3\stackrel{2}{}4$ 移动，得分为 $12$。因此，最小得分为 $12$。

所以依次输出 $1,1,12$，每个数占一行。

样例输入 2

3 5
1 2 9
1 2 2
2 2 1
1 3 9
2 3 1

样例输出 2

2
9

样例解释 2

• 对于顶点 $2$，沿 $1\stackrel{9}{}2$ 移动，得分为 $9$；沿 $1\stackrel{2}{}2$ 移动，得分为 $2$。因此，最小得分为 $2$。
• 对于顶点 $3$，沿 $1\stackrel{9}{}3$ 移动，得分为 $9$；沿 $1\stackrel{2}{}2\stackrel{1}{}3$ 移动，得分为 $21$。因此，最小得分为 $9$。

注意，给定的图可能包含重边和自环。

解题思路

根据题目的特点：

由于需要比较一下字典序，这就不同于普通的BFS。

举个例子：
假设到节点 a、b 的最优路径数字都是 12：
a → x，边上是 9，得到 129
b → x，边上是 1，得到 121

如果先处理 a，就会先访问 x，记录 129，但真正最优的是 121。

因此，所有路径数字同为 12 的节点，必须一起处理出边。把它们的出边统一按 1～9 分组，才能保证先发现 121，再发现 129。

综上，可以让队列里存“一组节点”，而不是一个节点。

代码

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

using namespace std;

typedef long long LL;

const int N = 2e5 + 100, MOD = 998244353;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int ans[N];
bool st[N];

// 链式前向星存储有向边
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}

void bfs()
{
// 同一组节点的最优路径数字完全相同
queue<vector<int>> q;
q.push(vector<int>{1});

st[1] = true;
ans[1] = 0;

while (q.size())
{
vector<int> group = q.front();
q.pop();

// 同组答案相同，取一个作为公共前缀的模值
int val = ans[group[0]];

vector<int> tmp[10];

// 收集整组的出边，按边上的数字分桶，此时不标记访问
for (int t : group)
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];

if (!st[j])
tmp[w[i]].push_back(j);
}

// 优先扩展较小的数字，保证首次访问时得到最优答案
for (int c = 1; c <= 9; c ++)
{
vector<int> res;

for (int j : tmp[c])
{
// 跳过已在更早的桶中访问或重复出现的节点
if (st[j])
continue;

st[j] = true;

// 在公共前缀末尾添加数字 c
ans[j] = ((LL)val * 10 + c) % MOD;
res.push_back(j);
}

// 同一前缀添加相同数字，形成一个新组
if (res.size())
q.push(res);
}
}
}

int main()
{
memset(h, -1, sizeof(h));

scanf("%d %d", &n, &m);

for (int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
}

bfs();

for (int i = 2; i <= n; i ++)
printf("%d\\n", ans[i]);

return 0;
}

G – Half-Baked

正在学习中…
有机会一定补上。