提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【小码匠自习室】鸡汤有毒：ARC154 - B - New Place

New 小码 自习室 有毒 Place
2023-06-13 09:15:31 时间

三句话就下套

今天老码农刷短视频，自然是刷那种毫无新意的但很阳光的，正能量满满的小视频，小视频，小视频...

勤奋是这个世界最朴实的道理，小码匠，你该补题了。。。

努力之后，好事才会款款而来，小码匠，咱们是不是补道题啊。。。

我有选择吗？？？？你的鸡汤让我毫无反驳之力。

题目

  • B - New Place
    • https://atcoder.jp/contests/arc154/tasks/arc154_b

长度为N的小写英文字母组成的字符串S、T。

你可以重复下面的操作（0次也可以）。

删除-S的开头的字符，将相同的字符插入S的任意位置。

请判定S是否能与T一致，如果可能，请求出所需的最小操作次数。

制約

1 \le N \le 2 \times 10^5
  • S、T是由英文小写构成长度N的字符串

入力

N
S
T

出力

S不能与T一致时输出-1。一致的情况下，输出所需的最小操作次数。

入力例 1

4
abab
abba

出力例 1

2

通过执行以下操作，2次使S与T一致。

删除-S开头的字符。然后，在S的末尾插入相同的文字。S变成 baba。

删除-S开头的字符。然后，在S的第2文字和第3文字之间插入相同的文字b。S变成 abba。

因为一次以下的操作不能使S与T一致，所以答案是2。

入力例 2

3
arc
cra

出力例 2

2

小码匠

思路

逆向循环s，正向循环t找s和t的公共子序列，然后用n减去这个子序列长度，即为所求值。

让诸位见笑了，题解写的不好，我会努力的。。。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

void best_coder() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    
    unordered_map <char, int> u;
    unordered_map <char, int> m;
    for (int i = 0; i < n; ++i) {
        ++u[s[i]];
        ++m[t[i]];
    }
    
    for (auto i : s) {
        if (u[i] == m[i]) {
            continue;
        }
        cout << -1;
        return;
    }
    
    int j = n - 1;
    int ans = n;
    for (int i = n - 1; i >= 0; --i) {
        if (t[i] == s[j]) {
            --ans;
            --j;
        }
    }
    
    cout << ans;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

参考代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
const int N = 200200;
const int A = 26;
int cnt[A];
int n;
char s[N], t[N];
 
int main()
{
    startTime = clock();
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
 
    scanf("%d %s %s", &n, s, t);
    for (int i = 0; i < n; i++)
        cnt[(int)(s[i] - 'a')]++;
    for (int i = 0; i < n; i++)
        cnt[(int)(t[i] - 'a')]--;
    for (int i = 0; i < A; i++) if (cnt[i] != 0) {
        printf("-1\n");
        return 0;
    }
    reverse(s, s + n);
    reverse(t, t + n);
    int p = 0;
    for (int i = 0; i < n; i++) {
        while(p < n && s[i] != t[p]) p++;
        if (p == n) {
            printf("%d\n", n - i);
            return 0;
        }
        p++;
    }
    printf("0\n");
    
 
    return 0;
}

相关文章