三句话就下套
今天老码农刷短视频，自然是刷那种毫无新意的但很阳光的，正能量满满的小视频，小视频，小视频...
勤奋是这个世界最朴实的道理，小码匠，你该补题了。。。
努力之后，好事才会款款而来，小码匠，咱们是不是补道题啊。。。
我有选择吗？？？？你的鸡汤让我毫无反驳之力。
题目
- B - New Place
- https://atcoder.jp/contests/arc154/tasks/arc154_b
长度为N的小写英文字母组成的字符串S、T。
你可以重复下面的操作（0次也可以）。
删除-S的开头的字符，将相同的字符插入S的任意位置。
请判定S是否能与T一致，如果可能，请求出所需的最小操作次数。
制約
- S、T是由英文小写构成长度N的字符串
入力
代码语言：javascript复制N
S
T
出力
S不能与T一致时输出-1。一致的情况下，输出所需的最小操作次数。
入力例 1
代码语言：javascript复制4
abab
abba
出力例 1
代码语言：javascript复制2
通过执行以下操作，2次使S与T一致。
删除-S开头的字符。然后，在S的末尾插入相同的文字。S变成 baba。
删除-S开头的字符。然后，在S的第2文字和第3文字之间插入相同的文字b。S变成 abba。
因为一次以下的操作不能使S与T一致，所以答案是2。
入力例 2
代码语言：javascript复制3
arc
cra
出力例 2
代码语言：javascript复制2
小码匠
思路
逆向循环s，正向循环t找s和t的公共子序列，然后用n减去这个子序列长度，即为所求值。
让诸位见笑了，题解写的不好，我会努力的。。。
代码
代码语言：javascript复制#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;
}
参考代码
代码语言：javascript复制#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("-1n");
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("%dn", n - i);
return 0;
}
p ;
}
printf("0n");
return 0;
}
