【2021CCPC女生赛】E. 被遗忘的计划
2022/1/23 23:06:31
本文主要是介绍【2021CCPC女生赛】E. 被遗忘的计划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Gym-103389E
注意这题价值和价格不要搞混,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. 被遗忘的计划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!