今天我挺有状态的，看过的题基本都给了正解(可能是昨晚cf div3打得跟屎一样，人品守恒，不好意思发题解了)，自己也给队伍签了很多水题(不敢让队友写，怕出锅)。
最后6题滚了，有点可惜。还差B和K没做出来。
B我一眼就知道该怎么做了，推了一会发现相当可做，于是给队友嘴巴完队友写挂了 (有些小细节，比如判0什么的，下面的题解会讲)。
K有不同区间的做法一眼秒，没有的话就manacher，队友又写挂了 (弟弟们，怎么回事？
今天的训练我留意到一件事情，我跟队友讲题意的时候他们能听懂，但他们跟我讲题意的时候往往要讲好几遍。只要描述的过程中出现类似“这个”“那个”这样的代词我就完全不能接受，一定会让队友明确指出是什么东西。
以后训练我想刻意地让队友来讲题意，让他们多锻炼一下表达能力。
题目链接：http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=392
A：
图论题。DSU+权值线段树+二分查询+读优才能过。考验码力。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e5 + ;
ll sum[maxn << ], sumn[maxn << ], sume[maxn << ], nei[maxn << ], summan[maxn << ];
int f[maxn], fsz[maxn], n, Q;
ll fed[maxn], sn, sm, tn; inline ll read()
{
ll d = ;
char s = getchar();
while (s < '' || s > '')
s = getchar();
while (s >= '' && s <= '')
{
d = d * + s - '';
s = getchar();
}
return d;
} int findFa(int x)
{
if (f[x] == x) return x;
return f[x] = findFa(f[x]);
} void maintain(int curPos)
{
sum[curPos] = sum[lson] + sum[rson];
sumn[curPos] = sumn[lson] + sumn[rson];
sume[curPos] = sume[lson] + sume[rson];
nei[curPos] = nei[lson] + nei[rson];
summan[curPos] = summan[lson] + summan[rson];
} void build(int curPos, int curL, int curR)
{
if (curL == curR)
{
sumn[curPos] = sum[curPos] = curL == ? n : ;
sume[curPos] = nei[curPos] = summan[curPos] = ;
return;
}
int mid = (curL + curR) >> ;
build(lson, curL, mid); build(rson, mid + , curR);
maintain(curPos);
} void add(int pos, int val, int curPos, int curL, int curR, ll ve)
{
if (curL == curR)
{
sum[curPos] += (ll)curL * val;
sumn[curPos] += val;
sume[curPos] += ve;
nei[curPos] = (ll)curL * (curL - ) / * sumn[curPos] - sume[curPos];
summan[curPos] = (ll)curL * (curL - ) / * sumn[curPos];
return;
}
int mid = (curL + curR) >> ;
if (pos <= mid)
add(pos, val, lson, curL, mid, ve);
else
add(pos, val, rson, mid + , curR, ve);
maintain(curPos);
} void query(int curPos, int l, int r, ll K)
{
if (l == r)
{
int _l = , _r = sumn[curPos], ans = K ? : ;
while (_l <= _r)
{
int mid = (_l + _r) >> ;
ll sp = sn + (ll) l * mid;
ll g = sp * (sp - ) / - sm - (ll) l * (l - ) / * mid;
// cerr << mid << ' ' << g << '\n';
if (g <= K)
{
if (g < K)
ans = max(ans, mid + );
else
ans = max(ans, mid);
_l = mid + ;
}
else
_r = mid - ;
}
tn += ans;
return;
}
int mid = (l + r) >> ;
ll sp = sn + sum[rson];
ll g = sp * (sp - ) / - summan[rson] - sm;
if (g == K)
{
sn += sum[rson];
tn += sumn[rson];
}
if (g < K)
{
sn += sum[rson];
sm += summan[rson];
tn += sumn[rson];
query(lson, l, mid, K);
}
if (g > K)
query(rson, mid + , r, K);
} int main()
{
int t=read();
while (t--)
{
n=read(),Q=read();
rep1(i, , n)
{
f[i] = i, fsz[i] = , fed[i] = ;
}
build(, , n);
int bsz = n;
while (Q--)
{
int op=read();
if (op == )
{
int x=read(), y=read();
int dx = findFa(x), dy = findFa(y);
if (dx == dy)
{
fed[dx]++;
add(fsz[dx], , , , n, );
}
else
{
add(fsz[dx], -, , , n, -fed[dx]);
add(fsz[dy], -, , , n, -fed[dy]);
add(fsz[dx] + fsz[dy], , , , n, fed[dx] + fed[dy] + );
f[dx] = dy;
fsz[dy] += fsz[dx];
fed[dy] += fed[dx] + ;
bsz--;
}
}
else
{
ll K=read();
int mi = max(bsz - K, 1LL), ma;
K -= nei[];
if (K <= )
ma = bsz;
else
{
sn = sm = tn = ;
query(, , n, K);
ma = bsz - tn + ;
}
printf("%d %d\n", mi, ma);
}
}
}
return ;
}
不上读优就是这样的下场（1920ms那次A得莫名其妙）：
B：
定义x,y为原始数组(样例已经给定)的值，x',y'为给定数组计算出来的值。显然可以作x-x',y-y'并提取公因式，计算一下(y-y')/(x-x')==a[i]+a[j]。到这里，解法已经很清晰了：枚举i，求j和a[j]并验证之。
细节有点恶心，要判x-x',y-y'是否为0。仔细点就可以过了。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e5 + ;
ll a[maxn], b[maxn], cnt[maxn];
int t; int main()
{
scanf("%d", &t);
while (t--)
{
ll n, x, y, curX = , curY = ;
scanf("%lld%lld%lld", &n, &x, &y);
rep1(i, , n)
{
scanf("%lld", &a[i]); b[i - ] = a[i];
cnt[i - ] = ;
curX += (i * a[i]); curY += (i * a[i] * a[i]);
}
ll deltaX = x - curX, deltaY = y - curY;
if (!deltaX && deltaY) //除0说明无解
{
puts("");
continue;
}
if (!deltaX && !deltaY) //这情况就很有意思了
{
ll ans = ;
sort(b, b + n);
int m = unique(b, b + n) - b;
rep1(i, , n)
cnt[lower_bound(b, b + m, a[i]) - b]++;
rep0(i, , m)
ans += 1LL * cnt[i] * (cnt[i] - ) / ;
printf("%lld\n", ans);
continue;
}
//不能整除说明无解，不能跟上面的if合在一起，不然会报浮点错误
if (abs(deltaY) % abs(deltaX))
{
puts("");
continue;
}
//有解，枚举i即可
ll rough = deltaY / deltaX, ans = ;
for (ll i = ; i <= n; i++)
{
ll fm = rough - * a[i], fs = deltaX / fm, j = i - fs;
if (!fm) continue;
if (abs(deltaX) % abs(fm)) continue;
if (j <= n && j >= )
if (a[i] + a[j] == rough) ans++;
}
printf("%lld\n", ans / );
}
return ;
}
C：
这个题给队友喂了好多假算法，都被队友hack掉了，有点迷。当时感觉是个姿势非常奇怪的贪心。
晚上写完这个博客之后洗了个澡，突然明白这题是从前往后贪心，线段树维护。(当时看到n<=1e5我就觉得是Onlogn的算法)
然而过了两天之后我发现了更好的做法，发现这个题只要维护得好，On就可以做了。
不得不承认确实是个出得不错的贪心，看完代码甚至觉得这题非常傻……
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e5 + ;
int n, a[maxn], cnt[maxn], cntTwi[maxn], ans[maxn]; //cntTwi[i]==cnt[i]*2
set<pair<int, int>>s; //次数的两倍和数值makepair，set的特性会先按cnt排序，再按数值排序
set<int>all; void init(int n)
{
s.clear(); all.clear();
rep1(i, , n) cnt[i] = cntTwi[i] = ans[i] = ;
} int main()
{
int t; scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
init(n);
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
cnt[a[i]]++;
}
for (int i = ; i <= n; i++)
if (cnt[i])
{
all.insert(i);
s.emplace(cntTwi[i] = * cnt[i], i);
}
int flag = ; //无解标志
for (int i = ; !flag && i <= n; i++)
{
int p = s.rbegin()->second; //先处理cnt最多而且数值较大的那个数字
if (cntTwi[p] > n - i + ) //如果cnt大于剩余位置的一半，必然无解
{
flag = ;
puts("Impossible");
break;
}
else if (cntTwi[p] < n - i + || p == a[i]) //如果要处理的数字正好for到了，不能放下去，那就找个最小的可用的数字替代之
{
auto it = all.begin();
if (*it == a[i]) it++;
p = *it;
}
//更新re
s.erase({cntTwi[a[i]], a[i]});
s.erase({cntTwi[p], p});
if (--cntTwi[a[i]]) s.emplace(cntTwi[a[i]], a[i]);
if (--cntTwi[p]) s.emplace(cntTwi[p], p);
if (--cnt[ans[i] = p] == ) all.erase(p);
}
if (!flag)
for (int i = ; i <= n; i++)
printf("%d%c", ans[i], i < n ? ' ' : '\n');
}
return ;
}
D：
有向图求欧拉路（貌似？我还挺想写的，但是最后的时间都在调B和K，难受。
补题的时候发现这题并没有我想得这么简单，幸好比赛的时候没写，不然更浪费时间了。
原本我还想着什么记忆化之类的事情，dalao直接一发暴力就A了。
Input最后有一句“It's guaranteed that the sum of of all test cases will not exceed 10^6”。当时没看到……
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ struct Graph
{
struct Vertex
{
vector<int>to;
int inDeg, vis; //inDeg:入度
};
vector<Vertex>vertex;
vector<int>eulerPath;
Graph(int n): vertex(n) {} int dfs(int u, int dep)
{
vertex[u].vis = ;
eulerPath.pb(u);
if (!dep) return ;
for (auto to : vertex[u].to)
if (!vertex[to].vis)
{
int flag = ;
vertex[to].inDeg++;
for (auto to : vertex[u].to)
if (!--vertex[to].inDeg && !vertex[to].vis) flag = ;
if (flag && dfs(to, dep - ))
return ;
vertex[to].inDeg--;
for (auto to : vertex[u].to) vertex[to].inDeg++;
}
//如果for一遍都没结果，说明不存在欧拉路
eulerPath.pop_back();
vertex[u].vis = ;
return ;
}
}; int main()
{
int t; scanf("%d", &t);
while (t--)
{
int n; scanf("%d", &n);
Graph g(n + );
for (int i = ; i <= n; i++) //建图
for (auto to :
{
i / , i - , i * , i * +
})
if ( <= to && to <= n)
g.vertex[i].to.pb(to), g.vertex[to].inDeg++;
if (!g.dfs(, n - ))
puts("Impossible");
else
for (int i = ; i < g.eulerPath.size(); i++)
printf("%d%c", g.eulerPath[i], i < g.eulerPath.size() - ? ' ' : '\n');
}
return ;
}
E：
sort一下，倒着判就完事了。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e5 + ;
int n, a[maxn], b[maxn], ans; int main()
{
int t; scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
rep1(i, , n) scanf("%d", &a[i]), b[i] = a[i];
sot(b, n);
ans = n;
for (int i = n; i >= ; i--)
if (a[i] == b[ans]) ans--;
printf("%d\n", ans);
}
return ;
}
F：
没什么意思的细节签到题。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ set<char>ss = { 'a', 'e', 'i', 'y', 'o', 'u' };
const int maxn = ;
char s[maxn];
int t; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%s", s + );
int len = strlen(s + );
printf("%c", s[]);
rep1(i, , len)
if (ss.count(s[i])) continue;
else printf("%c", s[i]);
puts("");
}
return ;
}
G：
温暖人心。
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ int t, n; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = n;; i++)
{
if (i % == && i % != )
{
printf("%d\n", i);
break;
}
}
}
return ;
}
H：
水题，计算出原有极值个数p，答案显然只有p-0,p-1,p-2三种情况（样例太恶臭了。
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std;
const int maxn = ;
int A[maxn];
int fg[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i = ;i <= n;i++){
scanf("%d",&A[i]);
fg[i] = ;
}
if(n <= ){
printf("0\n");
continue;
}
int ans = ;
for(int i = ;i <= n-;i++){
if(A[i-] < A[i] &&A[i] > A[i+]){
ans ++;
fg[i] = ;
}
}
// for(int i = 1;i <= n;i++)
// printf("%d ",A[i]);
// printf("\n");
// for(int i = 1;i <= n;i++)
// printf("%d ",fg[i]);
// printf("\n");
int endflag = ;
for(int i = ;i <= n-;i++){
if(fg[i] == &&fg[i + ] == ){
if(A[i] == A[i + ]){
printf("%d\n",ans-);
endflag = ;
break;
}
}
}
if(endflag) continue;
for(int i = ;i <= n-;i++){
if(fg[i] == ){
if(A[i-] < A[i+]&&A[i+] > A[i+]){
continue;
}else if(A[i-] < A[i-]&&A[i-] > A[i+]) {
continue;
}else{
printf("%d\n",ans-);
endflag = ;
break;
}
}
}
if(endflag) continue;
printf("%d\n",ans);
}
return ;
}
I：
看完题之后队友马上给结论：判读进来的数模3余几即可，虽然我没有听得很懂，不过看队友一脸坚定我还是光速敲了。奇偶性貌似是看能不能被3整除，研究一下就知道了。
/* basic header */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <climits>
#include <float.h>
/* STL */
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <array>
#include <iterator>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define init(a,b) fill(begin(a),end(a),b)
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define repa(i,a) for(auto &i:a)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson curPos<<1
#define rson curPos<<1|1
/* namespace */
using namespace std;
/* header end */ const int maxn = 1e4 + ;
char a[maxn], b[maxn]; int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%s", a + ); scanf("%s", b + );
int len1 = strlen(a + ), len2 = strlen(b + );
int sum1 = , sum2 = , sign1 = , sign2 = ;
rep1(i, , len1) sum1 += a[i] - '';
rep1(i, , len2) sum2 += b[i] - '';
if (sum1 % == ) sign1 = ; if (sum2 % == ) sign2 = ;
printf("%d\n", abs(sign1 - sign2) % );
}
return ;
}
J：
DSU水题，队友居然写挂了要批评，还是我改对的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int pa[maxn]; int find(int x)
{
if (pa[x] == x) return x;
else return pa[x] = find(pa[x]);
}
priority_queue<int, vector<int>, greater<int> > Q;
vector<int> G[maxn];
int vis[maxn], visit[maxn]; int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
{
pa[i] = i;
vis[i] = ;
visit[i] = ;
G[i].clear();
}
for (int i = ; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
if (a > b) swap(a, b);
G[a].push_back(b);
G[b].push_back(a);
int x = find(a);
int y = find(b);
pa[y] = x;
}
int ans = ;
for (int i = ; i <= n; i++)
{
if (find(i) == i) ans ++;
}
printf("%d\n", ans);
while (!Q.empty()) Q.pop();
for (int i = ; i <= n; i++)
{
if (vis[pa[i]] == )
{
Q.push(i);
vis[pa[i]] = ;
visit[i] = ;
}
}
int flag = ;
while (!Q.empty())
{
int x = Q.top();
Q.pop();
if (flag == )
{
printf("%d", x);
flag = ;
}
else printf(" %d", x);
for (int i = ; i < G[x].size(); i++)
{
if (!visit[G[x][i]])
{
visit[G[x][i]] = ;
Q.push(G[x][i]);
}
}
}
printf("\n");
}
return ;
}
K：
和队友讨论了一会口A了。如果存在不相同子串的区间，那么选定一个尽量小的“能包含所有不相同子串区间”的区间，然后往两边扩展即可。
如果不存在不相同子串的区间，直接跑manacher算回文子串个数就完事了。 (赛后队友原来是死在ans没开LL，队友锅++
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm> using namespace std; const int maxn = 2e6+; char ma[maxn * ];
int mp[maxn * ]; long long int manacher (string s) {
auto len = s.length();
int l = ;
ma[l++] = '$';
ma[l++] = '#';
for (int i = ; i < len; i++) {
ma[l++] = s[i];
ma[l++] = '#';
}
ma[l] = ;
int mx = , id = ;
for (int i = ; i < l; i++) {
mp[i] = mx > i ? min(mp[*id-i], mx-i) : ;
while (ma[i + mp[i]] == ma[i-mp[i]]) mp[i]++;
if (i + mp[i] > mx) {
mx = i + mp[i];
id = i;
}
}
long long ans = ;
for (int i = ; i < * len + ; i++) {
ans += mp[i] / ;
}
return ans;
} int main(void) {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
string s, t;
cin >> s >> t;
bool flag = true;
int left = -, right = -;
for (auto i = ; i < s.length(); i++) {
if (s[i] != t[i]) {
if (flag) {
left = i;
flag = false;
}
right = i;
}
}
if (right == -) {
cout << manacher(s) << endl;
} else {
bool possible = true;
for (int i = ; i <= right - left; i++) {
if (s[left + i] != t[right - i]) {
possible = false;
}
}
long long ans = ;
if (possible) {
ans = ;
while (--left >= && ++right < s.length()) {
if (s[left] == s[right] && t[left] == t[right] && s[left] == t[left]) {
ans++;
} else {
break;
}
}
}
// with different bytes
cout << ans << endl;
}
}
return ;
}
L && M：
看到没有人过就溜了。