CF1696C Fishingprince Plays With Array 题解

jiangtaizhe001 · 2022-06-28 16:44:15 · 题解

可能更好的阅读体验

题目传送门

题目大意

给定一个长度为 n 的数组 a 、一个长度为 k 的数组 b 和一个数字 m，现在对数组 a 进行以下操作：

• 选择数组 a 中一个 m 的倍数 a_i 替换成 m 个 \dfrac{a_i}{m}
• 选择数组 a 中 m 个相同的数字 a_i,a_{i+1},\dots,a_{i+m-1} 替换成 m\cdot a_i

请问能否把数组 a 变成数组 b。
数据范围：1\le n,k\le 5\times 10^4，2\le m\le 10^9，1\le a_i,b_i\le 10^9，\sum n+k\le 2\times 10^5。

题目解析

发现两个操作是互逆的，所以我们判断是否可以把数组 a 和数组 b 通过这两个操作来转化成同一个数组。
所以我们只需要把两个数组中所有 m 的倍数都拆开，然后判断两个数组是否相同即可。
显然可能会拆出很多项，所以需要开一个结构体来表示数组，里面的两个变量分别代表这个数字和它的重复次数。

int n,m,k,a[maxn],b[maxn],len1,len2; ll sum1,sum2;
struct JTZ{ int s; ll num; }tmpa[maxn],tmpb[maxn];
int solve(int arr[],JTZ res[],int len){
    int nlen=0,tmp,i; ll cnt;
    for(i=1;i<=len;i++){
        cnt=1; tmp=arr[i];
        while(tmp%m==0) tmp/=m,cnt*=m;
        if(nlen==0||res[nlen].s!=tmp) nlen++,res[nlen].num=cnt,res[nlen].s=tmp;
        else res[nlen].num+=cnt;
    } return nlen;
}
void work(){
    n=read(); m=read(); int i;
    for(i=1;i<=n;i++) a[i]=read(); k=read(); for(i=1;i<=k;i++) b[i]=read();
    len1=solve(a,tmpa,n); len2=solve(b,tmpb,k);
    if(len1!=len2){ puts("No"); return; }
    for(i=1;i<=len1;i++) if(tmpa[i].num!=tmpb[i].num||tmpa[i].s!=tmpb[i].s){ puts("No"); return; }
    puts("Yes"); return;
}