传送门

文章目录

题意：

有nnn个时间，每个时间给你两个操作，第一个是k=k+xk=k+xk=k+x，第二个是k=k∗xk=k*xk=k∗x，且可以执行[0,y][0,y][0,y]次，kkk初始状态为000，求[1,m][1,m][1,m]中kkk能到达的数的最短时间。

思路：

首先比较容易的能想到一个nm2nm^2nm2的暴力方法，就是遍历[1,n][1,n][1,n]，让后对于每个已经出现过的数，尝试进行[0,y][0,y][0,y]次相应的操作，yyy的范围[0,m][0,m][0,m]。

我们可以发现这样更新的话，会有很多重复更新的数。

比如原本能到的数有[3,11][3,11][3,11]，现在x=4,y=4x=4,y=4x=4,y=4，那么你对于每个数更新的时候遍历到的集合就是[3,7,11,15,19][3,7,11,15,19][3,7,11,15,19]和[11,15,19,23,27][11,15,19,23,27][11,15,19,23,27]，我们可以发现当333加到111111后，之后的数都会在111111的位置再次加一遍，由此可见，我们当加数的时候，如果当前数已经存在了，那么我们直接breakbreakbreak就好啦，因为之后遍历到这个数的时候也会再次加一遍，这样是无效的工作。

由于我们[0,m][0,m][0,m]的数最多遍历两次，是常数级别的，所以复杂度为O(NM)O(NM)O(NM)。

还有就是上取整的时候最好别用浮点数的ceilceilceil，容易错。

//#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#include<vector>#include<set>#include<queue>#include<algorithm>#include<sstream>#include<ctime>#include<cstdlib>#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define pb push_back#define mk make_pair#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define random(a,b) ((a)+rand()%((b)-(a)+1))#define db puts("---")using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL;typedef unsigned long long ULL;typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;struct Node{LL t,x,y;}a[N];vector<bool>v(N+1,0);int ans[N];int main(){//ios::sync_with_stdio(false);//cin.tie(0);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&a[i].t,&a[i].x,&a[i].y);if(a[i].t==1){LL now=(a[i].x+100000-1)/100000;a[i].x=now;}}v[0]=1;for(int i=1;i<=n;i++){auto nv=v;if(a[i].t==1){for(int k=0;k<=m;k++){if(!v[k]) continue;for(int j=1;j<=a[i].y;j++){LL now=1ll*j*a[i].x;if(now>m) break;if(now+k<=m&&!v[now+k]) nv[now+k]=true,ans[now+k]=i;else break;}}}else if(a[i].t==2){for(int k=0;k<=m;k++){if(!v[k]) continue;LL now=k;for(int j=1;j<=a[i].y;j++){now=(now*a[i].x+100000-1)/100000;if(now>m) break;if(now<=m&&!v[now]) nv[now]=true,ans[now]=i;else break;}}}v=nv;}for(int i=1;i<=m;i++) if(ans[i]==0) printf("-1 "); else printf("%d ",ans[i]);return 0;}