c2c网站的主要功能,石家庄智能网站建设,东莞常平房价,商城网站优化方案D. Bananas in a Microwave
题意#xff1a;
u1s1#xff0c;题意真难懂 有n个时间#xff0c;每个时间给你两个操作#xff0c;第一个是kkx#xff0c;第二个是kk∗x#xff0c;且可以执行[0,y]次#xff0c;#xff08;在第i个时间点#xff0c;必须应用第i个操作…D. Bananas in a Microwave
题意
u1s1题意真难懂 有n个时间每个时间给你两个操作第一个是kkx第二个是kk∗x且可以执行[0,y]次在第i个时间点必须应用第i个操作 k 初始状态为0 现在让你依次输出从1到m到达每个数最少的操作次数
题解
满脑子都是暴力。。但是暴力肯定不行 有点背包问题的感觉但是第二种操作怎么都不能有效实现 看来终究还是暴力 根据题意可以知道最后的步数范围也就是[1,n] 最直接暴力是O(n*m^2),遍历[1,n]尝试[0,y]次相应操作y的范围是[0,m] 比如原本能到的数是[3,11]现在x 4y 4对于每个数更新的时候遍历到的集合就是[3,7,11,15,19]和[11,15,19,23,27]11的位置重复出现所以当我们加数的时候如果当前数已经存在就直接break
总结 先将所有位置初始化为inf第0位是0 每次从m到0循环看哪个数已经被确定了第一次因为只有位置0还未确定所以会从0开始然后就在那个数的基础上继续扩展出现已经确定的就break 复杂度是n * m * 2
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i x;i n;i)
#define forr(i,x,n) for(int i n;i x;--i)const int N 1e67,INF 1e9;
int ans[N];int main()
{int n,m;scanf(%d%d,n,m);for(int i1;im;i) ans[i] INF;for(int cur1;curn;cur){ll t,x,y;scanf(%lld%lld%lld,t,x,y);for(int im;i0;i--){if(ans[i] INF) continue;ll z i;for(int j1;jy;j){if(t 1) z z (x 100000 - 1) / 100000;else z (z * x 100000 - 1) / 100000;if(z m) break;if(ans[z] INF) break;ans[z] cur;}}}forn(i,1,m) printf(%d ,ans[i] INF ? -1 : ans[i]);puts();return 0;
}
