第二届山西省程序设计竞赛题解.pdfVIP

第二届山西省大学生程序设计大赛 暨第十二届中北大学程序设计大赛 ——————————————— 题解 ——————————————— 2017年5月20 日 ProblemA 2、3、5木头人 ProblemB JackandRose ProblemC 郭姐的数学 ProblemD 魔力手环 ProblemE 回收大佬之气 ProblemF 郭姐相亲 ProblemG 跳跃数 ProblemH 郭姐的老婆 ProblemI 旺大神郭姐 ProblemJ 无聊的一天 ProblemK 玩数字 Problem A 2、3、5木头人 题解：既然求的是第一个大于等于它的数，那么二分的高效性就可以体现了。 把只有2,3,5质因子的数预处理打表排序，大致推一下就知道满足的数不会超 过[log2(1e18)*log3(le18)*log5(1e18)]个，每次询问二分即可。复杂度 T*log2(n)+排序复杂度 标程： #includestdio.h #includestdlib.h #includestring.h #includemath.h #includeiostream #includealgorithm #includestack #includequeue #includevector #includeset #includemap #includestring using namespace std; typedef long long ll; const ll INF 1e18+100; const double eps 1e-9; ll qpow(ll a,ll b) { ll ans 1; while(b) { if(b1)ans (ans*a); b 1;a (a*a); } return ans; } ll vec[1000010]; int cnt; void init() { cnt 0; for(int i 0;qpow(2ll,i) INF;i++) { ll s2 qpow(2ll,i); for(int j 0;qpow(3ll,j) INF/s2;j++) { ll s3 qpow(3ll,j); for(int k 0;qpow(5ll,k) INF/s2/s3;k++) { vec[cnt++] s2*s3*qpow(5ll,k); } } } sort(vec,vec+cnt); } int main() { init();int t;scanf(%d,t); while(t--) { ll n;scanf(%lld,n); if(n 1)printf(2\n); else { ll x lower_bound(vec,vec+cnt,n)-vec; printf(%lld\n,vec[x]); } } return 0; } Problem B Jack and Rose 题解：(1)直接每次跑最小生成树，kruscal复杂度q*m*logm，过于暴力，会超 时，可以想办法优化一下。 （2）一开始没删边的时候直接跑一遍最小生成树， 然后把这些边存入set，以后每次查询，如果删的边不在set里，那么就直接输 出答案，否则，删边重新跑最小生成树。优化之后就能过题了。 （3）当然本题 还有更好的解法，把所有询问的边存起来进行离线处理。首先跑一边最小生成 树，把最小生成树的边和询问中在最小生成树里的边存起来，假设总数为num， 跑出来一个不完全的生成树，然后每次询问的时候只需要在num