打卡信奥刷题（3531）用C++实现信奥题 P10976 统计重复个数

P10976 统计重复个数

题目描述

定义 $str=[s,n]$ 表示 $str$ 由 $n$ 个字符串 $s$ 连接构成。

例如，$str==[\text{abc},3]==\text{abcabcabc}$。
如果可以从 $s_2$ 中删除某些字符使其变为 $s_1$，则称字符串 $s_1$ 可以从字符串 $s_2$ 获得。

例如，根据定义，$s1=\mathtt{abc}$ 可以从 $s2=\mathtt{ab}\mathtt{dbe}\mathtt{c}$ 获得，仅需要删除红色标识的字符。

现在给你两个字符串 $s_1$ 和 $s_2$ 和两个整数 $n_1$ 和 $n_2$。由此构造得到两个字符串，其中 $st{r}_1=[s_1,n_1]$、$st{r}_2=[s_2,n_2]$。

请你找出一个最大整数 $m$，以满足 $str=[st{r}_2,m]$ 可以从 $st{r}_1$ 获得。

输入格式

本题有多组测试数据。测试数据不超过 $100$ 组。

对于每组测试数据，分为两行：

• 第一行输入字符串 $s_2$ 和整数 $n_2$；
• 第二行输入字符串 $s_1$ 和整数 $n_1$；

输出格式

对于每组测试数据，输出整数 $m$ 表示答案。

输入输出样例 #1

输入 #1

ab 2
acb 4
acb 1
acb 1

输出 #1

2
1

说明/提示

数据保证，$s_1,s_2$ 全为小写字母构成，且 $1\le |s_1|,|s_2|\le 100$，$0\le n_1,n_2\le 10^6,n_2\ne 0$，每个测试点的测试数据不超过 $100$ 组。

C++实现

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
int main(){
cin.tie(0)->sync_with_stdio(0);
string s1,s2;
int n1,n2;
while(cin>>s2>>n2>>s1>>n1){
int l1=s1.size(),l2=s2.size();
vi bt(26);
for(auto c:s1)bt[c–'a']=1;
bool sf=true;
for(auto c:s2)if(bt[c–'a']==0){sf=false;break;}
if(!sf){cout<<0<<endl;continue;}
vector<tp>a(l1);
int p=l1–1,t1=0,t2=0,sc_p=–1;
while(1){
sc_p=p,t2++;
for(int i=0;i<l2;i++){
if(p+1==l1)p=0,t1++;else p++;
while(s1[p]!=s2[i]){
if(p+1==l1)p=0,t1++;else p++;
}
}
if(a[p]==tp{0,0})a[p]={t1,t2};
else break;
}
tie(t1,t2)=a[sc_p];
p=sc_p+1;
while(t2—){
for(int i=l2–1;i>=0;i—){
if(p–1==–1)p=l1–1,t1—;else p—;
while(s1[p]!=s2[i]){
if(p–1==–1)p=l1–1,t1—;else p—;
}
}
}
tie(t1,t2)=a[sc_p];
bool y=(sc_p<p);
ll M=(ll)(n1–y)/(t1–y)*t2,sx1=(n1–y)%(t1–y)+y,sx2=0;
for(auto [t1,t2]:a){
if(t1!=0&&t1<=sx1&&t2>sx2)sx2=t2;
}
M+=sx2;
cout<<M/n2<<endl;
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容