• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AcWing 3727. 乘方相乘(进位制)

开发技术 开发技术 12小时前 3次浏览

参考:https://www.acwing.com/problem/content/video/3730/

题目

给定一个长度为 n 的数组 v1,v2,…,vn。
初始时,数组中的所有元素都为 0。
接下来,可以对该数组进行若干次如下操作——对于第 i 次操作(i 从 0 开始),你可以:
要么选择其中一个元素 vpos,将其增加 k^i。
要么不选择任何元素,直接跳过此次操作。
你可以随时停止操作(不进行任何操作也可以)。
现在,给定 k 的值以及一个目标数组 a1,a2,…,an。
请问,能否通过上述操作,将数组 v 转化为数组 a。

输入输出

输入:
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,k。
第二行包含 n 个整数 a1,a2,…,an。
输出:
每组数据输出一行结果,能将数组 v 转化为数组 a,则输出 YES,否则输出 NO。

思路

可以将数组a的每个元素转化成k进制,进行第i次操作,只能使某个数的k进制第i位上+1。因此,只要判断所有数的k进制第i位上之和是否位1,等于1或0说明可以转化,大于1说明不能转化。
将思路转化为代码是一种编程思维
用一个数组s[i],记录第i位上的数之和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100;  //ai的k进制不会超过100位
int s[N];

int main()
{
    int T;
    cin >> T;
    while (T--){
        int n,k;
        cin >> n >> k;
        memset(s, 0 ,sizeof s); //每个样例s[i]都要清零
        while (n -- ){
            LL x;
            cin >> x;
            for(int i=0;x; i++,x/=k){   //枚举k进制每一位
                s[i] += x % k;   //记录k进制第j位
            }
        }
        int flag = 0;
        for (int i = 0; i < N; i ++ ){
            if(s[i] > 1){
                flag = 1;
                break;
            }
        }
        if(flag) cout << "NO" << endl;
        else cout << "YES" <<endl;
    }
}

程序员灯塔
转载请注明原文链接:AcWing 3727. 乘方相乘(进位制)
喜欢 (0)