Codeforces Round 578 (Div. 2) - E. Compress Words

Solost

2023 年 04 月 14 日

215 次浏览

暂无评论

905字数

题目题解

## 题目链接

[题目链接](https://codeforces.com/contest/1200/problem/E)

## 题目大意

题目的意思是把字符串删去连续的两个字母，问剩下的字符串拼起来有多少种？

## 题解

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007, P = 13331;
const int N = 2e5 + 10;

ull h[N], p[N];

ull get_hash(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    s = ' ' + s;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    unordered_set<ull> q;
    for (int i = 1; i <= n; i++) {
        if (i == 1)
            q.insert(get_hash(i + 2, n));
        else if (i == n)
            q.insert(get_hash(1, n - 2));
        else
            q.insert(get_hash(i + 2, n) + get_hash(1, i - 1) * p[n - i - 1]);
    }
    cout << q.size() << endl;
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 14 日