题意

5702 Count The Repetitions 0x50「动态规划」例题

描述

定义 conn(s,n) 为 n 个字符串 s 首尾相接形成的字符串，例如：

conn("abc",2)="abcabc"

称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。

给定两个字符串 s_1 和 s_2，以及两个整数 n_1 和 n_2，求一个最大的整数 m，满足conn(conn(s_2,n_2 ),m) 能由 conn(s_1,n_1) 生成。

s_1 和 s_2 长度不超过100，n_1 和 n_2 不大于 10^6。

输入格式

本题只有1个测试点，包含多组数据。每组数据由2行组成，第一行是s2,n2，第二行是s1,n1。

输出格式

对于每组数据输出一行表示答案m。

样例输入

ab 2

acb 4

acb 1

acb 1

aa 1

aaa 3

baab 1

baba 11

aaaaa 1

aaa 20

样例输出

来源

https://leetcode.com/problems/count-the-repetitions/deｓｃｒｉｐｔion/

        </article>

分析

发现可以求出最大的m'，满足conn(s2,m')能由conn(s1,n1)生成，那么答案m=m'/n2。

由于m'≤1e8不能直接F[i,j]表示从s1[i]开始要多少字符生成conn(s2,j)，观察到m'可以用二进制拆分，所以利用倍增优化。

设F[i,j]表示从s1[i]开始至少需要多少字符才能生成conn(s2,\(2^j\))。状态转移方程为：

\[F[i,j]=F[i,j-1]+F[(i+F[i,j-1])\bmod |s_1|,j-1]
\]

可以暴力预处理F[i,0]。总时间复杂度\(O(|s_2||s_1|^2+|s_1|\log(|s_1|*n_1/|s_2|))\)

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

typedef long long ll;

using namespace std;

string s1,s2;

int n1,n2;

ll f[100][28];

void Count_the_Repetitions(){

	for(int i=0;i<s1.size();++i){

		int pos=i;

		f[i][0]=0;

		for(int j=0;j<s2.size();++j){

			int cnt=0;

			while(s1[pos]!=s2[j]){

				pos=(pos+1)%s1.size();

				if(++cnt>=s1.size()) return cout<<0<<endl,void();

			}

			pos=(pos+1)%s1.size(),f[i][0]+=cnt+1;

		}

	}

	for(int j=1;j<=27;++j)

		for(int i=0;i<s1.size();++i)

			f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.size()][j-1];

	ll m=0;

	for(int st=0;st<s1.size();++st){

		ll x=st,ans=0;

		for(int k=27;k>=0;--k)

			if(x+f[x%s1.size()][k]<=s1.size()*n1)

				x+=f[x%s1.size()][k],ans+=1<<k;

		m=max(m,ans);

	}

	cout<<m/n2<<endl;

}

int main(){

	ios::sync_with_stdio(0);

	while(cin>>s2>>n2>>s1>>n1) Count_the_Repetitions();

	return 0;

}

巴特西

CH5702 Count The Repetitions

题意

5702 Count The Repetitions 0x50「动态规划」例题

描述

输入格式

输出格式

样例输入

样例输出

来源

分析

代码

最新文章

热门文章