2025 北京市大学生程序设计竞赛暨“小米杯”全国邀请赛

E 计算几何 坐标系转换 二分答案题意在一条线上找一个点到所给点的最大距离最短最大的最小考虑对最大距离进行二分答案check(dis)判断dis能不能≥\geq≥线上某个点到每个点的距离坐标变换后设线上合理的某个点是(xc,0)(x_c,0)(xc​,0)(x−xc)2y2≤dis2(x-x_c)^2y^2\leq dis^2(x−xc​)2y2≤dis2xcx_cxc​的范围是[xc−y2−dis2,xcy2−dis2][x_c-\sqrt{y^2-dis^2},x_c\sqrt{y^2-dis^2}][xc​−y2−dis2​,xc​y2−dis2​]交集不是空集即合理constdoublePIacos(-1);constlonglongmod998244353,inf1e9;doublea,b,c;// double dis(pdd p){// return abs(a*p.xxb*p.yyc)/sqrt(a*ab*b);// }voidsolve(){intn;cinn;vectorpddpos(n1);forr(i,1,n)cinpos[i].xxpos[i].yy;cinabc;doublemagsqrt(a*ab*b);doublethetaacos(abs(b/mag));if(-a*b0)theta-theta;// coutthetaendl;//转换坐标系forr(i,1,n){doublenxpos[i].xx*cos(theta)pos[i].yy*sin(theta);doublenypos[i].yy*cos(theta)-pos[i].xx*sin(theta)(b0?-c/a:c*cos(theta)/b);// double nypos[i].yy*cos(theta)-pos[i].xx*sin(theta);pos[i].xxnx,pos[i].yyny;// coutnx nyendl;}// 二分答案 枚举最后的距离答案autocheck[](doubledis)-bool{doublelmx-1e18,rmn1e18;forr(i,1,n){if(dis-abs(pos[i].yy)-1e-8)returnfalse;doubledsqrt(dis*dis-pos[i].yy*pos[i].yy);lmxmax(lmx,pos[i].xx-d),rmnmin(rmn,pos[i].xxd);if(rmn-lmx-1e-8)returnfalse;}returntrue;};doublel0,r1e7;while(r-l1e-8){doublemid(lr)/2;if(check(mid)){rmid;}elselmid;}// coutans;coutfixedsetprecision(8)rendl;}G dp一看这个题就感觉是dp本次选哪一个之前的路径会影响到未来但是受限于水平不会实现…动态规划成立的前提一旦当前阶段的状态确定未来的演变与过去无关当前状态已包含所有对未来决策有用的信息每次更新的是以当前萤火虫作为末尾的状态每次从上一个记录的w的质因数p和颜色cw的质因数p和颜色cw的质因数p和颜色c转移过来dp[p][c]dp[p][c]dp[p][c]但是和本次颜色不同的颜色有很多一一判断会超时为了让最后答案链最长需要关注前面最长的链但是最长链的末尾颜色和本次颜色相同的话这个链就断了末尾颜色与最长链不同的次长链也会是最优解的一个选择本次更新后不是选之前的最长链就是次长链。设计color[p][0最长/1次长],dp[p][0最长/1次长]color[p][0最长/1次长],dp[p][0最长/1次长]color[p][0最长/1次长],dp[p][0最长/1次长]或者直接合二为一dp[p][0最长/1次长][0记录的颜色/1链的长度]]dp[p][0最长/1次长][0记录的颜色/1链的长度]]dp[p][0最长/1次长][0记录的颜色/1链的长度]]constintN5e5,M1e91;constdoublePIacos(-1);constlonglongmod998244353,inf1e9;vectorintprime;intminp[N10];// 每个数的最小质因数voidfind_p(){minp[1]1;forr(i,2,N){if(!minp[i]){minp[i]i;prime.push_back(i);}for(autop:prime){if(i*pN)break;minp[i*p]p;if(pminp[i])break;}}}arrayarrayint,2,2f[N10];voidsolve(){find_p();intn;cinn;vectorintw(n1),c(n1);forr(i,1,n)cinw[i];forr(i,1,n)cinc[i];f[1][0][0]c[1],f[1][0][1]1;f[1][1][0]c[1],f[1][1][1]1;forr(i,1,n){//分解质因数vectorintfactor;while(w[i]1){intxminp[w[i]];while(w[i]%x0)w[i]/x;factor.push_back(x);}// 找本次最优intres1;for(autop:factor){if(c[i]!f[p][0][0])resmax(res,f[p][0][1]1);if(c[i]!f[p][1][0])resmax(res,f[p][1][1]1);}//记录最优值for(autop:factor){/* 这里正解代码写的是 if (c[i] ! f[x][0][0]) { if (res f[x][0][1]) { f[x][1] f[x][0]; f[x][0] {c[i], res}; } else if (res f[x][1][1]) { f[x][1] {c[i], res}; } } else { if (res f[x][0][1]) { f[x][0] {c[i], res}; } } assert(f[x][0][0] ! f[x][1][0]); *//* 之前的错误解法 if(resf[p][0][1]){ f[p][1]{c[i],res}; f[p][0]{c[i],res};//最大次大都成一个颜色了 }else if(resf[p][1][1]){ f[p][1]{c[i],res}; } 会wa在 7 2 5 4 3 6 3 5 6 9 7 7 7 2 8 *///需要保证最大次大的颜色不同if(c[i]!f[p][0][0]){//颜色不同if(resf[p][0][1]){//放到最大的位置f[p][1]f[p][0];f[p][0]{c[i],res};}elseif(resf[p][1][1]){//放到次大的位置f[p][1]{c[i],res};}}else{//颜色相同if(resf[p][0][1]){f[p][0][1]res;//直接刷新}}}}intans1;for(autop:prime){ansmax(ans,f[p][0][1]);}coutansendl;}