AtCoder题解｜ABC 109B Shiritori

题目信息 📚

【题目描述】

Takahashi is practicing shiritori alone again today.

Shiritori is a game as follows:

In the first turn, a player announces any one word.
In the subsequent turns, a player announces a word that satisfies the following conditions:
- That word is not announced before.
- The first character of that word is the same as the last character of the last word announced.

In this game, he is practicing to announce as many words as possible in ten seconds.

You are given the number of words Takahashi announced, $N$, and the $i$-th word he announced, $W_i$, for each $i$.

Determine if the rules of shiritori were observed, that is, every word announced by him satisfied the conditions.

【输入】

The input is given from Standard Input in the following format:

$N$

$W_1$

$W_2$

$\vdots$

$W_N$

【输出】

If every word announced by Takahashi satisfied the conditions, print Yes; otherwise, print No.

【数据范围】

$N$ is an integer satisfying $2 \leq N \leq 100$.
$W_i$ is a string of length between $1$ and $10$ (inclusive) consisting of lowercase English letters.

【输入样例1】

4
hoge
english
hoge
enigma

【输出样例1】

No

As hoge is announced multiple times, the rules of shiritori was not observed.

【输入样例2】

9
basic
c
cpp
php
python
nadesico
ocaml
lua
assembly

【输出样例2】

Yes

【输入样例3】

8
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaa
aaaaaaa

【输出样例3】

No

【输入样例4】

3
abc
arc
agc

【输出样例4】

No

【题目来源】

https://atcoder.jp/contests/abc109/tasks/abc109_b

题目解析 🍉

【题目分析】

利用 map<string, int> 存储当前单词数组，然后进行查询即可。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;

int main() {
    cin >> n;

    string w;
    char pre;
    map<string, int> mp;  // map存储单词序列
    for (int i = 1; i <= n; i++) {
        cin >> w;
        mp[w]++;
        if (mp[w] > 1 || (pre != w[0] && i != 1)) {
            cout << "No" << endl;
            return 0;
        }
        pre = w.back();  // pre记住上个单词的结尾
    }
    cout << "Yes" << endl;

    return 0;
}