AtCoder Beginner Contest 374 A~D

IronMen · 2024-11-25 22:30:56 · 题解

A - Takahashi san 2

洛谷链接

AtCoder链接

题目

给你一个由小写英文字母组成的字符串 S。

如果 S 以 san 结尾，则输出 Yes；否则输出 No。

代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;
    if (s[s.length() - 1] == 'n' && s[s.length() - 2] == 'a' && s[s.length() - 3] == 's')
        puts("Yes");
    else
        puts("No");
    return 0;
}

B - Unvarnished Report

洛谷链接

AtCoder链接

题目

有两个字符串 S 和 T，它们都由小写英文字母组成。

如果 S 和 T 相等，则输出 0；否则，输出它们不同的第一个字符的位置。

在这里，如果 S 和 T 中只有一个存在第 i 个字符，则认为第 i 个字符是不同的。

更确切地说，如果 S 和 T 不相等，输出满足以下条件之一的最小整数 i：

这里，|S| 和 |T| 分别表示 S 和 T 的长度，S_i 和 T_i 分别表示 S 和 T 的第 i 个字符。

代码

#include <bits/stdc++.h>

using namespace std;

string s, t;

int main()
{
    cin >> s >> t;
    for (int i = 0; i < (int)max(s.length(), t.length()); i ++ )
    {
        if (s[i] != t[i])
        {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    puts("0");
    return 0;
}

C - Separated Lunch

洛谷链接

AtCoder链接

题目

KEYENCE 总部有 N 个部门，第 i(1 \le i \le N) 个部门的人数为 K_i。

将每个部门分配到 A 组或 B 组，让每个组在同一时间午休，并确保 A 组和 B 组的午休时间不重叠，求同一时间午休的最大人数的最小值。

换句话说，求分配给 A 组的部门总人数和分配给 B 组的部门总人数中较大者的最小值。

思路

由于 N \le 20，数据很小，所以直接暴力。

代码

#include <bits/stdc++.h>

using namespace std;

int n, p[30], ans = 0x3f3f3f3f, a, b;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &p[i]);
    for (int i = 0; i < (1 << n); i ++ )
    {
        a = b = 0;
        for (int j = 0; j < n; j ++ )
        {
            if (i & (1 << j))
                a += p[j];
            else
                b += p[j];
        }
        ans = min(ans, max(a, b));
    }
    cout << ans << '\n';
    return 0;
}

D - Laser Marking

洛谷链接

AtCoder链接

题目

有一台印刷机可以通过发射激光在 xy 平面上打印线段。

打印开始时，激光位置位于坐标 (0,0)。
在打印线段时，应遵循以下步骤。
- 首先，将激光位置移动到线段的一个端点。
- 可以从任一端点开始绘制。
- 然后，在发射激光的同时，将激光位置从当前端点直线移动到另一个端点。
- 不允许在线段中间停止打印。
不发射激光时，激光位置可以以每秒 S 个单位的速度向任意方向移动。
发射激光时，激光位置可以以每秒 T 个单位的速度沿打印线段移动。
激光位置移动以外的操作所需的时间可以忽略。

高桥希望使用这台印刷机印刷 N 条线段。

第 i 条线段连接坐标 (A_i,B_i)和 (C_i,D_i)。

有些线段可能会重叠，在这种情况下，他需要分别打印每个线段的重叠部分。

当他以最佳方式操作印刷机时，完成所有线段的印刷至少需要多少秒？

思路

按照题意，先算出位置到线段的一段所需的时间；再算出画线段所需的时间。

输出后发现与答案不一样，没关系，只要小数后六位是对的就行了。

记得要分情况，看先移动的线段的那一头。

代码

#include <bits/stdc++.h>

using namespace std;

double ans = 0x3f3f3f3f;
bool v[110];
int n, s, t, a[10010], b[10010], c[10010], d[10010];

void dfs(int x, int y, int z, double ss)
{
    double q1, q2;
    if (z == n)
    {
        ans = min(ans, ss);
        return;
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (!v[i])
        {
            v[i] = 1;
            q1 = sqrt(double(a[i] - x) * double(a[i] - x) + double(b[i] - y) * double(b[i] - y));
            q2 = sqrt(double(a[i] - c[i]) * double(a[i] - c[i]) + double(b[i] - d[i]) * double(b[i] - d[i]));
            dfs(c[i], d[i], z + 1, ss + q1 / s + q2 / t);
            q1 = sqrt(double(c[i] - x) * double(c[i] - x) + double(d[i] - y) * double(d[i] - y));
            dfs(a[i], b[i], z + 1, ss + q1 / s + q2 / t);
            v[i] = 0;
        }
    }
}

int main()
{
    scanf("%d %d %d", &n, &s, &t);
    for (int i = 1; i <= n; i ++ )
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    dfs(0, 0, 0, 0);
    printf("%.20lf", ans);
    return 0;
}