链接：

https://codeforces.com/contest/1185/problem/B

题意：

Methodius received an email from his friend Polycarp. However, Polycarp's keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word "hello", the following words could be printed: "hello", "hhhhello", "hheeeellllooo", but the following could not be printed: "hell", "helo", "hhllllooo".

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp's keyboard.

思路：

将每个字符串对应的字母和相连次数存下来，比较一下即可。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 3e5 + 10;

const int MOD = 1e9 + 7;

int n, m, k, t;

vector<pair<char, int> > inp;

vector<pair<char, int> > out;

string a, b;

bool Solve()

{

    if (inp.size() != out.size())

        return false;

    for (int i = 0;i < inp.size();i++)

    {

        if (inp[i].first != out[i].first)

            return false;

        if (inp[i].second > out[i].second)

            return false;

    }

    return true;

}

int main()

{

    cin >> t;

    while (t--)

    {

        inp.clear(), out.clear();

        cin >> a >> b;

        int tmp = 0;

        for (int i = 0;i <= a.length();i++)

        {

            if (i == a.length() || (i > 0 && a[i] != a[i-1]))

                inp.emplace_back(a[i-1], tmp), tmp = 0;

            tmp++;

        }

        tmp = 0;

        for (int i = 0;i <= b.length();i++)

        {

            if (i == b.length() || (i > 0 && b[i] != b[i-1]))

                out.emplace_back(b[i-1], tmp), tmp = 0;

            tmp++;

        }

//        for (auto pa:inp)

//            cout << pa.first << ' ' << pa.second << endl;

        if (Solve())

            cout << "YES" << endl;

        else

            cout << "NO" << endl;

    }

    return 0;

}

巴特西

Codeforces Round #568 (Div. 2) B. Email from Polycarp

链接：

题意：

思路：

代码：

最新文章

热门文章