网站推广制作,帮齐家网做的网站,品牌整合推广,商务网站推广目标有哪些传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
有nnn个时间#xff0c;每个时间给你两个操作#xff0c;第一个是kkxkkxkkx#xff0c;第二个是kk∗xkk*xkk∗x#xff0c;且可以执行[0,y][0,y][0,y]次#xff0c;kkk初始状态为000#xff0c;求[1,m…传送门
文章目录题意思路题意
有nnn个时间每个时间给你两个操作第一个是kkxkkxkkx第二个是kk∗xkk*xkk∗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]现在x4,y4x4,y4x4,y4那么你对于每个数更新的时候遍历到的集合就是[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)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
struct Node
{LL t,x,y;
}a[N];
vectorboolv(N1,0);
int ans[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in;i){scanf(%lld%lld%lld,a[i].t,a[i].x,a[i].y);if(a[i].t1){LL now(a[i].x100000-1)/100000;a[i].xnow;}}v[0]1;for(int i1;in;i){auto nvv;if(a[i].t1){for(int k0;km;k){if(!v[k]) continue;for(int j1;ja[i].y;j){LL now1ll*j*a[i].x;if(nowm) break;if(nowkm!v[nowk]) nv[nowk]true,ans[nowk]i;else break;}}}else if(a[i].t2){for(int k0;km;k){if(!v[k]) continue;LL nowk;for(int j1;ja[i].y;j){now(now*a[i].x100000-1)/100000;if(nowm) break;if(nowm!v[now]) nv[now]true,ans[now]i;else break;}}}vnv;}for(int i1;im;i) if(ans[i]0) printf(-1 ); else printf(%d ,ans[i]);return 0;
}
