1 Star 1 Fork 0

yinjinrun/code-public-2

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
AGC007F.cpp 2.01 KB
一键复制 编辑 原始数据 按行查看 历史
yinjinrun 提交于 2022-08-01 09:44 +08:00 . AGC 007 B & F
#include <bits/stdc++.h>
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
using namespace std;
using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;
template < typename T > T read() {
T x = 0; bool f = 0; char ch = getchar();
while(!isdigit(ch)) f |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }
const int N = 1e6 + 10;
int n, segpos[N];
char s[N], t[N];
vec pot[30], ps;
int main() {
#ifdef YJR_2333_TEST
freopen("1.in", "r", stdin);
#endif
n = in; scanf("%s", s + 1), scanf("%s", t + 1);
bool fl = 1;
rep(i, 1, n) fl &= s[i] == t[i];
if(fl) return cout << 0 << endl, 0;
if(s[1] != t[1]) return cout << -1 << endl, 0;
rep(i, 1, n) pot[s[i] - 'a'].eb(i);
rep(i, 1, n)
if(t[i] == t[i - 1]) segpos[i] = segpos[i - 1];
else ps.eb(i), segpos[i] = segpos[i - 1] + 1;
int ans = 0, ret = n + 1;
veg tpot;
per(j, (int)ps.size() - 1, 0) {
chkmin(ret, ps[j]); int p = ps[j];
while(pot[t[p] - 'a'].size() && pot[t[p] - 'a'].back() > ret) pot[t[p] - 'a'].pop_back();
if(!pot[t[p] - 'a'].size()) return puts("-1"), 0;
//chkmax(ans, j + 1 - segpos[pot[t[p] - 'a'].back()]);
//chkmax(ans, pot[t[p] - 'a'].back());
tpot.eb(p, pot[t[p] - 'a'].back());
chkmin(ret, pot[t[p] - 'a'].back());
pot[t[p] - 'a'].pop_back();
} reverse(tpot.begin(), tpot.end());
rep(i, 0, tpot.size() - 1) {
auto v = tpot[i];
if(v.fi == v.se) continue;
int l = 0, r = i - 1;
while(l <= r) {
int mid = l + r >> 1;
int ret = tpot[mid].fi + (i - mid);
if(ret <= v.se) l = mid + 1;
else r = mid - 1;
} chkmax(ans, i - l + 1);
}
cout << ans + 1 << endl;
return 0;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/yinjinrun/code-public-2.git
git@gitee.com:yinjinrun/code-public-2.git
yinjinrun
code-public-2
code-public-2
f656cb76c71c3e1cb209ff663c44f418931e72d4

搜索帮助