西安市住房和城乡建设局官方网站,上海建设门户网站,WordPress免费小说主题,学校网站建设招标方案传送门
题意#xff1a;
思路#xff1a; 转换一下题目就是用若干x,y,zx,y,zx,y,z能凑出来多少个hhh的数。先考虑两个数y,zy,zy,z的情况#xff0c;我们如果能求出来这两个数能凑出来的数设为sumsumsum#xff0c;让后sumkxhsumkxhsumkxh求出来…传送门
题意
思路 转换一下题目就是用若干x,y,zx,y,zx,y,z能凑出来多少个hhh的数。先考虑两个数y,zy,zy,z的情况我们如果能求出来这两个数能凑出来的数设为sumsumsum让后sumkxhsumkxhsumkxh求出来有多少个k即可。然鹅直接求也是不行的因为hhh很大如果hhh很小我们直接bfsbfsbfs跑一遍就好啦。考虑优化sumkxhsumkxhsumkxh这个式子。可以看到我们只需要最大化kkk即可也就是最小化sumsumsum也即是让 summodxsum\bmod xsummodx现在定义dis[i]dis[i]dis[i]为能到达iii所需要走的最小层数(i为在模xxx的意义下的)。算出来dis[i]dis[i]dis[i]之后可以通过ans(h−dis[i])/x1ans(h-dis[i])/x1ans(h−dis[i])/x1算出来答案。
disdisdis没开LLLLLL,直接自闭。
设模数为xxx用dijkstradijkstradijkstra的话可以O(xlogx)O(xlogx)O(xlogx)
//#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;LL x,y,z;
LL h;
LL dis[N];
bool st[N];void bfs()
{memset(dis,63,sizeof(dis));queueintq; q.push(1%x);st[1%x]1; dis[1%x]1;while(q.size()){int uq.front(); q.pop();st[u]false;int t(uy)%x;if(dis[t]dis[u]y){dis[t]dis[u]y;if(!st[t]) st[t]1,q.push(t);}t(uz)%x;if(dis[t]dis[u]z){dis[t]dis[u]z;if(!st[t]) st[t]1,q.push(t);}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinhxyz;bfs();LL ans0;for(int i0;ix;i) if(dis[i]h) ans(h-dis[i])/x1;printf(%lld\n,ans);return 0;
}
/**/
