C/C++教程

【2021CCPC女生赛】E. 被遗忘的计划

本文主要是介绍【2021CCPC女生赛】E. 被遗忘的计划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Gym-103389E
image

注意这题价值和价格不要搞混，vp的时候还以为是价值模n...

  • k个都取价值最大的物品maxv，和就是f中的最大值maxf，k的唯一可能取值maxf/maxv
  • 得出的k不在[1,1e9]或快速幂求出 v 数组的循环卷积的 k 次幂后不等于f数组说明无解

循环卷积：这个其实就是多项式乘法，这道题目以v数组的k次幂来表示取k个物品的可能取值（生成函数求方案）。f数组下标是价格之和对n的余数，v的价格就是下标，所以多项式相乘时将下标(i+j)%n。

代码参考

点击查看代码 
typedef vector<ll> vl;

vl operator *(vl a, vl b){

    vl ve(a.size(), -LNF);
    for(int i = 0; i < a.size(); ++ i){
        for(int j = 0; j < b.size(); ++ j){
            ve[(i + j) % a.size()] = max (ve[(i + j) % a.size()], a[i] + b[j]);
        }
    }
    return ve;
}

vl qmi(vl m, ll k){
    vl res (m.size(), -LNF);
    res[0] = 0; // 答案至少是0
    while (k){
        if(k&1) res = res * m;
        m = m * m;
        k >>= 1;
    }
    return res;
}

int main(){
    int n; cin >> n;
    vl v(n), f(n);
    for(int i = 1; i <= n ; ++ i) cin >> v[i%n];
    for(int i = 0; i < n ; ++ i) cin >> f[i];
    ll maxv=*max_element(v.begin(), v.end());
    ll maxf=*max_element(f.begin(), f.end());
    ll k=maxf / maxv;
    if(k>1e9||k<1) cout<<-1;
    else{
        v = qmi(v, k);
        cout << (v == f ? k : -1) << endl;
    }
    return 0;
}
这篇关于【2021CCPC女生赛】E. 被遗忘的计划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航