正经题解|序列合拆
2024-09-02 11:40:09
发布于:浙江
23阅读
0回复
0点赞
题目大意
给定两个序列,进行两种操作
- 选定连续子序列,满足条件a_l = a_{l+1} \dost = a_r,长度为,使其合并为
- 选定数字,满足条件 ,拆分为个。
求解是否可以使序列相同。
思路解析
进行反向思考,从答案出发,若序列能够变为相同,那么相同的两个序列若一直执行拆分的操作,最后得到的序列也必然会相同,反之不能。
因此可以得出对应的模拟思路,不停的执行拆分操作,直到不可以在拆分的时候,根据两个序列的拆解序列是否相同输出YES 或 NO即可。
共有两种模拟方式
- 采用字符串,从前往后依次拆分,累加到字符串当中进行判断
- 采用pair, 将拆分的序列分段,最后判断两个pair数组是否相等
标程采用pair的方式进行判断。
时间复杂度
代码演示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
void solve(){
vector<pair<ll,ll> > ve1,ve2;
ll n,m,k,a,b;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a;
ll temp = a;
while(temp % m == 0){
temp /= m;
}
if(!ve1.empty() && ve1.back().first == temp)
{
ve1.back().second += a/temp;
}
else ve1.push_back({temp,a/temp});
}
cin >> k;
for(int i = 1 ; i <= k ; i ++ )
{
cin >> b;
ll temp = b;
while(temp % m == 0)
temp /= m;
if(!ve2.empty() && ve2.back().first == temp)
{
ve2.back().second += b/temp;
}
else ve2.push_back({temp,b/temp});
}
if(ve1 == ve2){
cout << "Yes" << endl;
}else cout << "No" << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
这里空空如也
有帮助,赞一个