[数据结构与算法]Codeforces-1696 C: Fishingprince Plays With Array【构造、贪心】

Codeforces-1696 C: Fishingprince Plays With Array

题目传送门：Codeforces-1696 C

题目

题目截图

样例描述

题目大意

? 给定一个长度为 $n$ 的数组 { a i } \{a_i\} {ai?}，和一个大于 $1$ 的整数 $m$， 可以做两个操作：将数组中 $m$ 倍数的数 $a_i$，换成 $m$ 个 $\frac{a_i}{m}$；或者将数组中连续 $m$ 个相等的 $a_i$ 合并为一个 $m\times a_i$。
? 现在给出数组 { b i } \{b_i\} {bi?}，问 { a i } \{a_i\} {ai?} 能否经过变换变为 $b_i$。

题目解析

? 显然，这两个操作是可逆的，意味着任意两个操作的结果是可比的，而且数组中每个数都拆成最小，就是能得到的最长的数组，任意变化都能从这个“最小元”中操作得到，因此一个简单的做法是将 $a、b$ 两个数组都拆成最长数组，看看它们是否相等。
? 为了让题目更有挑战性（其实就是没想到都变成中间结果），虽然比较麻烦，我将 $a\to t\to b$ 这种方案做了一下。特别注意的是这种方法 $a、b$ 各数组内数的总和可能不同，这种情况下应该输出 NO。

Code

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

#define output {cout << "NO" << endl; fl = true; break;}

int main() {
   int T, n, m, k, x;
   cin >> T;
   while(T--) {
       cin >> n >> m;

       vector<pair<int, long long>> a;
       for (int i = 0; i < n; ++i) {
           cin >> x;
           long long y = 1;
           while (x % m == 0) y *= m, x /= m;
           if(a.empty() || a.back().first != x) a.emplace_back(x, y);
           else a.back().second += y;
       }
       cin >> k;
       vector<int> b(k);
       for (int &i : b) cin >> i;

       bool fl = false; int r = 0;
       for(int i=0; i<k; ++i) {
            if(b[i] != a[r].first) {
                if(a[r].first > b[i] || b[i] % a[r].first != 0) output else {
                    int key = b[i] / a[r].first;
                    if(a[r].second < key) output
                    a[r].second -= key;
                    while(key % m == 0) key /= m;
                    if(key != 1) output
                }
            } else --a[r].second;
            if(a[r].second == 0) ++r;
            if((r >= a.size() && i+1 < k) || (i==k-1 && r < a.size())) output
       }
       if(!fl) cout << "YES" << endl;
   }
   return 0;
}