每天一道 CodeForces 构造/思维题 （day1）

每天一道 CodeForces 构造/思维题 （day1）

题目

题目链接 C. Fishingprince Plays With Array

题目大意：

给你一个数组 a,通过两种操作无限次能否得到数组 b

操作1：每次可以选择一个a[i]，如果a[i]能够整除m， t = a[i] / m那么就可以将a[i] 转换为 m 个 t ,也就是[a[i]] => [t, t, t... t]

操作2：选择连续m个相同的值a[i]，将其转换为 m * a[i] ，其实也就是操作1的反操作

思路：

这道题正向思维怎么想都想不出来，需要考虑的因素太多了，因为有无限多操作的可能性，如果思维一直是如何将数组a如何转化为b的话无论怎么写都写不出来。所以我们可以想象逆向思维，操作1和操作2是相反操作，由a操作得到b，那么也可以由b操作得到a,这两种方式互相求也求不出来，那么我们想一想能不能将这两个数组都转化为一个中间数组c,如果它俩的中间数组相同，那么也就可以相互转换，类似于:

A = C

B = C

A = B

那么怎么求中间数组c?

我们可以将两个数组都只使用操作1，将能使用操作1的数组都一直除于m，一直到不能操作为止，这样就能够让A -> C -> B 了

为什么不用操作2？合二为一简单还是一分为二简单？显然是一分为二。聚合一起有太多的可能操作了。

操作完之后，由于得到的两个数组c1,c2长度是不一样的，这里要使用双指针算法来比较两个是否相同

比如，我们得到了这样两个中间数组

1 1 2 2

2 2 2

两个1和一个2对应，所以最后的复杂度是O( (n + k ) * log( max( a[i] ) ) )

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e6 + 10;
PII a[N], b[N]; // 这里定义的数组a,b表示操作后的中间数组
void solve()
{
    int n, m, k;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int t, w;
        cin >> t;
        w = t;
        while (t % m == 0)
        {
            t /= m;
        }
        // t最多可以分解成多少个
        a[i] = {t, w / t};
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        int t, w;
        cin >> t;
        w = t;
        while (t % m == 0)
        {
            t /= m;
        }
        b[i] = {t, w / t};
    }
    int l = 1, r = 1;
    while (l <= n && r <= k)
    {
        if (a[l].x != b[r].x)
        {
            break;
        }
        if (a[l].y > b[r].y)
        {
            a[l].y -= b[r].y;
            r++;
        }
        else if (a[l].y == b[r].y)
        {
            l++;
            r++;
        }
        else
        {
            b[r].y -= a[l].y;
            l++;
        }
    }
    if (l == n + 1 && r == k + 1)
        puts("Yes");
    else
        puts("No");
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}