CodeForces 977D - Divide by three, multiply by two

CF第一次Div3的题...
因为当天晚上CF直接炸了十多分钟加上忘了注册...所以鸽了...
事后补题秒A三道...emmm果然还是我太弱了

今早上卡在这道题了....本来打算搜索....
刚好看到官方的题解....发现竟然可以这么做emmmm
CF不愧是脑洞题

来源 Codeforces Round #479 (Div. 3)

1.png
2.png

结论:
对于原序列(未被打乱的答案序列)来说,对每一个数进行整数拆分,可以得到的3的个数应该是递减的,在此基础之上在进行乘2的操作,并不影响当前元素中3的个数

以第一个样例举例
原序列:
9 3 6 12 4 8
整数拆分后3的个数
2 1 1 1 0 0

所以进行排序,将元素反复对3相除,对元素中得到的3的个数进行递减排序,对元素中3的个数相同的元素来说,递增排序

Accept GNU G++17 7.2.0 30ms 3600kB

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-05-08 18:04:10
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

vector<pair<int, long long int> > arr;

int cal3(long long int tmp) {
    int ret = 0;
    while(tmp % 3 == 0) {
        tmp /= 3;
        ret++;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    arr.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i].second;
        arr[i].first = -cal3(arr[i].second);
    }
    sort(arr.begin(), arr.end());
    for(int i = 0; i < n; i++) {
        if(i != 0)
            putchar(' ');
        printf("%lld", arr[i].second);
    }
    putchar('\n');
    return 0;
}

添加新评论

captcha
请输入验证码