Znzryb's Blog

2025北京市赛-G. 萤火虫难题（转换状态设计思路，以倍数为核心）

Posted on 2025-06-27 Edited on 2026-04-06

思路讲解

那么首先相邻，状态转移只需要考虑最后一个（前缀dp）。

AC代码

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,lT,C[MAXN],W[MAXN];
/*

*/
ll dp[MAXN];
inline void init(){
	
}
//  minp[i] 存储的是i的最小素因数
vector<ll> minp,primes;
void sieve(ll n){
	minp.assign(n+5,0);
	for(int i=2;i<=n;++i){
		if(minp[i]==0){		// 是素数
			minp[i]=i;
			primes.push_back(i);
		}
		for(auto p:primes){
			if(i*p>n){	// 超范围了
				break;
			}
			minp[i*p]=p;
			// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
			// i * p_next = (p * k) * p_next 最小的应该是p
			if(p==minp[i]){
				break;
			}
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>W[i];
	}
	FOR(i,1,N){
		cin>>C[i];
	}
	ll mxw=*max_element(W+1,W+1+N);
	sieve(mxw);
	// 并按它们在路边的顺序排成一列（这样就不必考虑后效性了）
	//        最大值       次大值
	vector<ll> dp(mxw+5,0),dp2(mxw+5,0),col(mxw+5,0);
	for(int i=1;i<=N;++i){
		vector<ll> prs;
		for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
			ll p=minp[j];
			prs.pb(p);
		}
		sort(all(prs));
		prs.resize(unique(all(prs))-prs.begin());
		// 需要这个max是因为这个转移只关心最后一位
		//	所以应该将素因数状态更新为最大
		ll mx=0;	
		for(auto p:prs){
			if(col[p]!=C[i]){
				mx=max(mx,dp[p]+1);
			}else{
				mx=max(mx,dp2[p]+1);
			}
		}
		for(auto p:prs){
			if(col[p]!=C[i]){
				if(mx>dp[p]){
					dp2[p]=dp[p];
					dp[p]=mx;
					col[p]=C[i];
				}else if(mx>dp2[p]){
					dp2[p]=mx;
				}
			}else{
				if(mx>dp[p]) dp[p]=mx;
			}
		}
	}
	// 不需要考虑1，因为1和任何数都互素
	ll ans=1;
	for(int i=2;i<=mxw;++i){
		ans=max({ans,dp[i],dp2[i]});
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
WA 
https://qoj.ac/submission/1125736

*/

心路历程（WA，TLE，MLE……）

https://qoj.ac/submission/1125736

//        最大值       次大值
vector<ll> dp(mxw+5,0),dp2(mxw+5,0),col(mxw+5,0);
for(int i=1;i<=N;++i){
	vector<ll> prs;
	for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
		ll p=minp[j];
		prs.pb(p);
	}
	sort(all(prs));
	prs.resize(unique(all(prs))-prs.begin());
	for(auto p:prs){
		if(col[p]!=C[i]){
			dp2[p]=dp[p];
			dp[p]+=1;
			col[p]=C[i];
		}else{
			dp2[p]+=1;
		}
	}
}

2025北京市赛-E. 布置 WAP

Posted on 2025-06-26 Edited on 2026-04-06

思路讲解

这种方式更稳定，精度更高（其实就是用这种方式过了）

      // 方案二：使用固定迭代次数（100次）进行三分搜索。
      // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
for(int i=0; i<100; ++i){
	DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
	DB mid2 = r - (r-l)/3.0;
	if(fx(mid1) > fx(mid2)){
		l=mid1;
	}else{
		r=mid2;
	}
}
printf("%.11f\n",fx(l));

AC代码

https://codeforces.com/gym/105851/my#

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
// 采用固定迭代次数的方案，不再需要eps常量
// constexpr double eps=1e-10;

ll N,M,Q,X[MAXN],Y[MAXN],K,lT,A[MAXN];
/*

*/
inline void init(){
	// 根据需要可以清空X和Y数组，但在您的框架中，每次N都会被重置，
    // 旧数据不会被访问，所以这里为空也可以。
}

inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>X[i]>>Y[i];
	}
	ll a,b,c;
	cin>>a>>b>>c;

	auto fx=[&](DB mid)->DB{
		DB x=mid,y=-(DB)a*x/b-(DB)c/b; // 显式转换一下类型，避免整数除法
		DB mx=0;
		FOR(i,1,N){
            // 直接计算距离的平方，最后再开方，可以减少sqrt的调用次数，稍微快一点
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	auto fy=[&](DB mid)->DB{
		DB y=mid,x=-(DB)b*y/a-(DB)c/a; // 显式转换
		DB mx=0;
		FOR(i,1,N){
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	DB l=-2e8,r=2e8; // 搜索范围，根据题目数据范围可能需要调整

    // a, b, c 是 ll, 在除法中最好转成 DB
	if(b!=0){
        // 方案二：使用固定迭代次数（100次）进行三分搜索。
        // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
			DB mid2 = r - (r-l)/3.0;
			if(fx(mid1) > fx(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fx(l));
	}else{
        // 同理，处理直线垂直的情况
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0;
			DB mid2 = r - (r-l)/3.0;
			if(fy(mid1) > fy(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fy(l));
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}

心路历程（WA，TLE，MLE……）

P4391 [BalticOI 2009] Radio Transmission 无线传输

Posted on 2025-06-25 Edited on 2026-04-06

题目内容

题目描述

给你一个字符串 $s_1$ ，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$ ，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

输入输出样例 #1

输入 #1

1 2	8 cabcabca

输出 #1

说明/提示

样例输入输出 1 解释

对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$ ，读入的 $\texttt{cabcabca}$ ，是它的子串。

规模与约定

对于全部的测试点，保证 $1\le L \le 10^6$ 。

思路讲解

给出子串，找出最短循环节。

最大公共前后缀。

结论就是N-pi[N]。~~其实我也不是很懂。~~

不能够使用二分，因为周期并没有单调性。

这道题目 hash 怎么做？

哈希做法思路

核心观察：字符串 $s$ 的最小周期为 $p$ ，当且仅当 $p$ 是满足以下条件的最小正整数：

s_i = s_{i+p} \quad \forall\, 0 \le i < L - p

这等价于： $s$ 去掉前 $p$ 个字符得到的后缀，与去掉后 $p$ 个字符得到的前缀完全相同。即：

s[0 \ldots L-p-1] = s[p \ldots L-1]

用多项式哈希预处理后，每次子串比较 $O(1)$ 。从 $p=1$ 开始枚举，第一个满足条件的 $p$ 就是答案。总复杂度 $O(L)$ 。
参考代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    const long long MOD1 = 1e9 + 7, BASE1 = 131;
    const long long MOD2 = 1e9 + 9, BASE2 = 137;

    vector<long long> h1(n + 1), h2(n + 1), pw1(n + 1), pw2(n + 1);
    h1[0] = h2[0] = 0;
    pw1[0] = pw2[0] = 1;
    for (int i = 0; i < n; i++) {
        h1[i + 1] = (h1[i] * BASE1 + s[i]) % MOD1;
        h2[i + 1] = (h2[i] * BASE2 + s[i]) % MOD2;
        pw1[i + 1] = pw1[i] * BASE1 % MOD1;
        pw2[i + 1] = pw2[i] * BASE2 % MOD2;
    }

    auto qry = [&](int l, int r) -> pair<long long, long long> {
        long long v1 = (h1[r + 1] - h1[l] * pw1[r - l + 1] % MOD1 + MOD1 * 2) % MOD1;
        long long v2 = (h2[r + 1] - h2[l] * pw2[r - l + 1] % MOD2 + MOD2 * 2) % MOD2;
        return {v1, v2};
    };

    for (int p = 1; p <= n; p++) {
        if (qry(0, n - p - 1) == qry(p, n - 1)) {
            cout << p << '\\n';
            return 0;
        }
    }
}

用了双哈希避免冲突。本质上和 KMP 中 $L - \pi_L$ 的经典做法等价，只是换了一种判断周期的手段。

详细解释关键观察

这其实就是把逐字符的条件"打包"成了一个子串相等的条件，是同一件事的两种说法。
逐字符展开：两个长度相同的子串相等，就是对应位置的字符全部相等。把两个子串的对应位置写出来：

前缀中的第 $i$ 个字符	后缀中的第 $i$ 个字符
$s[0]$	$s[p]$
$s[1]$	$s[p+1]$
$\vdots$	$\vdots$
$s[i]$	$s[i+p]$
$\vdots$	$\vdots$
$s[L-p-1]$	$s[L-1]$
前缀的第 $i$ 个字符是 $s[i]$ ，后缀的第 $i$ 个字符是 $s[i+p]$ 。
所以"两个子串相等" $\iff$ 每一行都对应相等 $\iff$ $s_i = s_{i+p}$ 对所有 $0 \le i < L-p$ 成立。
用例子直观感受：取 `cabcabca`， $p = 3$ ：

前缀（去掉后3个）：c a b c a
后缀（去掉前3个）：c a b c a
                    ↕ ↕ ↕ ↕ ↕
原串位置对应：     s[0]=s[3], s[1]=s[4], s[2]=s[5], s[3]=s[6], s[4]=s[7]

每个字符都和它后面第 $p$ 个字符相同，这就是"周期为 $p$ "的含义。把这些逐个比较合在一起看，就是前缀和后缀相等。
两种说法完全等价，只是视角不同：一个是逐字符看，一个是整体看。

把这个列出来以后，我们就知道了周期 p 的成立条件是什么。可以通过枚举 p，非常简单的使用字符串哈希检验答案。

AC代码

https://www.luogu.com.cn/record/221541535

源代码

// Problem: P4391 [BalticOI 2009] Radio Transmission 无线传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}

inline void solve(){
	cin>>N;
	init();
	string s;
	cin>>s;
	// if(N==1) {cout<<1<<"\n";return;}
	s='#'+s;
	vector<ll> pi(N+5);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		while(true){
			if(s[i]==s[len+1]){
				pi[i]=len+1;
				break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<pi[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	// ll ans=0;
	// FOR(i,1,N){
		// ans=max(ans,pi[i]);
	// }
	cout<<N-pi[N]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/221541535
*/

心路历程（WA，TLE，MLE……）

P3375 【模板】KMP（前缀函数）（完全理解 kmp）

Posted on 2025-06-25 Edited on 2026-04-06

思路讲解

https://cp-algorithms.com/string/prefix-function.html

【KMP 学一遍忘一遍？ACM 金牌选手用可视化直击本质，理解了内核后想忘记都难！】【精准空降到 04:05】 https://www.bilibili.com/video/BV1Er421K7kF/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=245

那么我们容易发现，这个

ABC……ABC+D，那么如果前缀字符串后面跟着D，那么就是pi函数=4，但是如果后面不是D，那要怎么办？

不难发现， $S[i+1]=S[\pi[i]+1] \Rightarrow\pi[i+1]=\pi[i]+1$ （注意，这里我采用的是1-based，这更自然）。这不言而喻。（上面的这个图片已经解释了，我们再细化一下）

当然，这个是皆大欢喜的情况，但是如果出现失配了怎么办？

这个 pi_next()，为什么一定是这个 pi_next()。可以使用反证法。

okay，问题就来到了，怎么样使用前缀数组实现这个文本串和模式串的这个匹配？

//                  文本串             模式串
vector<ll> kmp(const string &s1,const string &s2){	// 返回总前缀数组pi
	string S;
	S='#'+s2+'#'+s1;		// 采用1-based 
	N=SZ(S)-1;
	vector<ll> pi(N+1,0);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		// if(S[i]==S[len+1]){
			// pi[i]=len+1;
		// }
		while(true){
			if(S[i]==S[len+1]){
				 pi[i]=len+1;
				 break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
	return pi;
}

特别的，我们认为 i=1 的时候 pi[i]=0。


/*
 * 采用 0-based 设计
 * 模式串(s2)+'#'+文本串(s1) 需要这样子传入，如果想要执行 kmp 的话
 * kmp 模板题 AC https://www.luogu.com.cn/record/269142391
 */
vector<ll> kmp(const string &A) {
    // 返回总前缀数组pi
    // 其定义是【1；i】真前后缀相同的最长长度
    // 特别的，pi【1】=0
    vector<ll> pi(SZ(A));
    for (int i = 1; i < SZ(A); ++i) {
        ll len = pi[i - 1];
        while (len > 0 && A[len] != A[i]) {
            len = pi[len - 1];
        }
        if (A[len] == A[i]) {
            pi[i] = len + 1;
        }
    }
    return pi;
}

void Solve() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<ll> pi = kmp(s2 + "#" + s1);
    for (int i = SZ(s2); i < SZ(pi); ++i) {
        if (pi[i] == SZ(s2)) {
            ll ans = i - SZ(s2) - SZ(s2);
            ++ans;
            cout << ans << "\n";
        }
    }
    for (int i = 0; i < SZ(s2); ++i) {
        cout << pi[i] << " ";
    }
    cout << "\n";
}

AC代码

源代码

// Problem: P3375 【模板】KMP
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3375
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
//                  文本串             模式串
vector<ll> kmp(const string &s1,const string &s2){	// 返回总前缀数组pi
	string S;
	S='#'+s2+'#'+s1;		// 采用1-based 
	N=SZ(S)-1;
	vector<ll> pi(N+1,0);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		while(true){
			if(S[i]==S[len+1]){
				 pi[i]=len+1;
				 break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
	return pi;
}
inline void solve(){
	string s,s1;
	cin>>s>>s1;
	init();
	vector<ll> pi=kmp(s,s1);
#ifdef LOCAL
   FOR(i,1,N){
   		debug(i);
		debug(pi[i]);
	}
#endif
	FOR(i,1,SZ(pi)-1){
		if(pi[i]==SZ(s1)){
			cout<<i-SZ(s1)*2<<"\n";
		}
	}
	FOR(i,1,SZ(s1)){
		cout<<pi[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/221413997
*/

AC
https://www.luogu.com.cn/record/269142391

源代码

/**
 * Problem: P3375 【模板】KMP
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P3375
 * Created: 2026-03-23 13:08:20
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 采用 0-based 设计
 * 模式串(s2)+'#'+文本串(s1) 需要这样子传入，如果想要执行 kmp 的话
 * kmp 模板题 AC https://www.luogu.com.cn/record/269142391
 */
vector<ll> kmp(const string &A) {
    // 返回总前缀数组pi
    // 其定义是【1；i】真前后缀相同的最长长度
    // 特别的，pi【1】=0
    vector<ll> pi(SZ(A));
    for (int i = 1; i < SZ(A); ++i) {
        ll len = pi[i - 1];
        while (len > 0 && A[len] != A[i]) {
            len = pi[len - 1];
        }
        if (A[len] == A[i]) {
            pi[i] = len + 1;
        }
    }
    return pi;
}

void Solve() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<ll> pi = kmp(s2 + "#" + s1);
    for (int i = SZ(s2); i < SZ(pi); ++i) {
        if (pi[i] == SZ(s2)) {
            ll ans = i - SZ(s2) - SZ(s2);
            ++ans;
            cout << ans << "\n";
        }
    }
    for (int i = 0; i < SZ(s2); ++i) {
        cout << pi[i] << " ";
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方（区间操作化简）

Posted on 2025-06-25 Edited on 2026-04-06

思路讲解

那么容易发现，其实这种区间操作的题目一般来说最短的操作是最灵活的，一个长操作也可以化为多个短操作的结果。

比如说这道题目长度为4的操作可以变为对中间两个元素执行一次，再对两侧两个元素分别执行一次。

所以我们不用考虑长度>2的操作。

那么不难注意到，就是说这个开头和结尾往往是这个破局的地方，那么开头那如果不同，必须要操作后面一个，然后不断传递，最后传递到A_[N]，就结束了。

FOR(i,1,N){
	cin>>A[i];
	A_[i]=A[i];
}
FOR(i,1,N){
	cin>>B[i];
}
FOR(i,1,N-1){
	ll diff=B[i]-A_[i];
	A_[i+1]+=diff;
}
if(A_[N]==B[N]){
	cout<<"Yes\n";
}else{
	cout<<"No\n";
}

AC代码

https://www.luogu.com.cn/record/221383853

源代码

// Problem: P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11643
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
ll A_[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
		A_[i]=A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,1,N-1){
		ll diff=B[i]-A_[i];
		A_[i+1]+=diff;
	}
	if(A_[N]==B[N]){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/