ABC398 题解

A题题解

问题陈述

找出满足以下所有条件的长度为 $N$ 的字符串：

• 每个字符都是 - 或 =。
• 它是一个回文字符串。
• 正好包含一个或两个 =。如果包含两个 =，则它们相邻。

这样的字符串是唯一的。

限制因素

• $1\le N\le 100$
• $N$ 是整数。

输入

输入内容由标准输入法提供，格式如下

$N$

输出

打印答案。

思路

由于每个回文串都有一个或两个=所以这两的=是对称的而又因为要相邻所以=一定在最中间!

那么我们只需要把 $N$ 折半输出-在输出一个或两个=最后在把剩下的-输出即可!

$ACCode$

#include <cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    if (n % 2)
    {
        for (int i = 1; i <= n / 2; i++)
            printf("-");
        printf("=");
        for (int i = 1; i <= n / 2; i++)
            printf("-");
        puts("");
    }
    else
    {
        for (int i = 1; i < n / 2; i++)
            printf("-");
        printf("==");
        for (int i = 1; i < n / 2; i++)
            printf("-");
        puts("");
    }
    return 0;
}

B题题解

问题陈述

我们有七张牌。第 $i$ （）张牌 $(i=1,\dots ,7)$ 上写着一个整数 $A_i$ 。
请判断是否有可能从这七张牌中选择五张，使所选的牌组成一个葫芦。

当且仅当满足以下条件时，一组五张牌被称为葫芦：

• 对于不同的整数 $x$ 和 $y$ ，有三张 $x$ 和两张 $y$ 。

限制因素

• $A_i$ 是介于 $1$ 和 $13$ 之间的整数，包括首尾两个整数。

输入

输入内容由标准输入法提供，格式如下

$A_1{A}_2{A}_3{A}_4{A}_5{A}_6{A}_7$

输出

如果选择五张牌可以组成葫芦，则打印 Yes；否则打印 No。

思路

要想求出是否有三带二的情况只需要用一个桶去存每张牌的数字即可!

$cin>>a,t_a++$

$ACCode$

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int a[15] = {0};
    for (int i = 1; i <= 7; i++)
    {
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    sort(a + 1, a + 14);
    reverse(a + 1, a + 14);
    if (a[1] >= 3 && a[2] >= 2)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

C题题解

问题陈述

有 $N$ 人，他们的标签从 $1$ 到 $N$ 。人 $i$ 有一个整数 $A_i$ 。

在满足 "其他 $N-1$ 人中没有一个人的整数与自己相同 "条件的人中，找出整数最大的那个人，并打印这个人的标签。

如果没有人满足条件，则报告这一事实。

限制因素

• $1\le N\le 3\times 10^5$
• $1\le A_i\le 10^9$
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

$N$

$A_1{A}_2\dots A_N$

输出

如果没有人满足 "其他 $N-1$ 人中没有人的整数与自己相同 "的条件，则打印 -1。

否则，在满足条件的人中，打印整数最大的人的标签。

思路

我们只需要用一个map来标记每个数出现的次数，为什么这里不用桶呢？

$N\le 10^9$ 空间太大了所以不行！

$ACCode$

#include <cstdio>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int a[500005];               // 记录a[i]
    unordered_map<int, int> cnt; // 记录a[i]的出现次数
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }
    int mx = -1, ans = -1;
    for (int i = 0; i < n; i++)
    {
        if (cnt[a[i]] == 1 && a[i] > mx)
        {
            mx = a[i];
            ans = i + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D题

问题陈述

有一个无限大的二维网格，在坐标 $(0,0)$ 处有一堆篝火。
在时间 $t=0$ 时，只有单元格 $(0,0)$ 存在烟雾。

给你一个长度为 $N$ 的字符串 $S$ ，由 “N”、“W”、“S”、"E "组成。在 $t=1,2,\dots ,N$ 时刻，会依次发生以下情况：

• 风吹起，当时存在的所有烟雾按如下方式移动：
  • 如果 $S$ 的 $t_{th}$ 字符是 “N”， $(r,c)$ 单元格中的烟雾会移动到 $(r-1,c)$ 单元格。
  • 如果是 “W”， $(r,c)$ 单元格中的烟雾会移动到 $(r,c-1)$ 单元格。
  • 如果是 “S”， $(r,c)$ 单元格中的烟雾会移动到 $(r+1,c)$ 单元格。
  • 如果是 “E”， $(r,c)$ 单元格中的烟雾会移动到 $(r,c+1)$ 单元格。
• 如果单元格 $(0,0)$ 中没有烟雾，则会在单元格 $(0,0)$ 中产生新的烟雾。

高桥站在 $(R,C)$ 单元格。
对于每个整数 $1\le t\le N$ ，判断在时间 $t+0.5$ 时，单元格 $(R,C)$ 是否有烟雾存在，并按照要求的格式打印答案。

限制因素

• $N$ 是介于 $1$ 和 $200000$ 之间的整数，包括首尾两个整数。
• $S$ 是长度为 $N$ 的字符串，由 “N”、“W”、“S”、"E "组成。
• $R$ 和 $C$ 是介于 $-N$ 和 $N$ (含)之间的整数。
• $(R,C)\ne (0,0)$

输入

输入内容由标准输入法提供，格式如下

$NRC$

$S$

输出

打印一个由 0 和 1 组成的 $N$ / 字符串。
$t$ -th 字符( $1\le t\le N$ )应该是：

• 如果在时间 $t+0.5$ 时，单元格 $(R,C)$ 中存在烟雾，则字符串为 1，否则为 0。
• 否则为0。

思路

本题我本来是挂了的但是赛后我想出来了!

1:模拟

首先用一个set<pair<int, int>> st来存储每个烟雾的坐标，在n次循环中每次把st中的每个值更行一下

复杂度:

• 时间复杂度： $O(N^2)$ 你猜能不能过
• 空间复杂度： $O(2N)$ 没问题

所以模拟会超时！

2:换种思路

既然模拟不行那就换种思路!

学过物理的朋友们都知道:
$$运动是相对的$$
所以所有烟雾向北飘一个对于篝火来说就是向北移，但队于所有烟雾来说就是篝火在向南移！

什么你不懂!来看图!

风一吹变成了这样如果只盯着篝火看就是烟雾向北飘

但不要往了篝火产生的烟雾

有了思路让我们来算一下复杂度:

• 时间复杂度:
  • 对于每次循环: 处理篝火的x, y坐标，即：$O(1)$
  • 对于整个程序: $N$ 次循环, 即: $O(N)\times O(1)=O(N)$
• 空间复杂度:
  • 只需存储一个集合， 即：$O(N)$

那么我们怎么判断 $(R,C)$ 是否有烟雾呢？

很简单：因为 $(R,C)$ 只是一个相对位置**我们只需要判断st中是否有 $(x_{篝}+R,y_{篝}+C)$ 即可!

有了思路那么直接上代码！

$ACCode$

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, R, C;
    int x = 0, y = 0;
    string s;
    cin >> n >> R >> C >> s;
    string res = "";
    set<pair<int, int>> st;
    for (int i = 0; i < s.size(); i++)
    {
        char op = s[i];
        int dx = 0, dy = 0;
        switch (op)
        {
        case 'N':
            dx = -1;
            break;
        case 'W':
            dy = -1;
            break;
        case 'S':
            dx = 1;
            break;
        case 'E':
            dy = 1;
            break;
        }
        st.insert({x, y});				//在当前位置生成一个烟雾
        x -= dx, y -= dy;    			//相对移动
        int cpx = x + R, cpy = y + C;   //相对位置
        if (st.count({cpx, cpy}))
            res += '1';
        else
            res += '0';
    }
    cout << res << endl;
    return 0;
}

$Thanksforreading!$