25CCPC东北邀请赛vp补题

感觉还好 签到不难F 枚举 暴力枚举范围内每一个合法时间最多6012720个难在计算角度时针分针分别算d e g h 30 ∗ ( h m 60 ) 30 h m 2 deg_h30*(h\frac{m}{60})30h\frac{m}{2}degh​30∗(h60m​)30h2m​有/2可以把所有角度2避免使用doubleintdeg(intx,inty,intx0,inty0){inth2*30*x2*30*y/60,h02*30*x02*30*y0/60;intm2*360*y/60,m02*360*y0/60;// double res(6*min({fabs(y-y0),60-fabs(y-y0)})30*min({fabs(h-h0),12-fabs(h-h0)}));intresmin(abs(h-h0),720-abs(h-h0))min(abs(m-m0),720-abs(m-m0));returnres;}voidsolve(){intx,y,x0,y0,x1,y1;cinxyx0y0x1y1;intansinf;intax,ay;if(x0x1){forr(j,y0,y1){intddeg(x,y,x0,j);if(dans)axx0,ayj,ansd;}}else{forr(i,x0,x1){forr(j,(ix0?y0:0),(ix1?y1:59)){intddeg(x,y,i,j);// couti j dendl;if(dans)axi,ayj,ansd;}}}coutax ayendl;}H 二分 配对参考Hongs_Cai 的题解以下分析来自千问:为什么直接把所有城市的“容纳能力”加起来得s u m c a p a c i t y sum_{capacity}sumcapacity​只要≥ s u m b \geq sum_b≥sumb​就有解这是一个非常深刻的结论基于本题的特殊结构每组人只有一个城市不能去在这个特定的约束下局部的容量限制之和如果大于等于总人数那么一定存在一种分配方案。因为b i b_ibi​可以散开分到不同城市这其实隐含了霍尔婚嫁定理的结论。因为每组人只被一个城市拒绝这种“排斥关系”非常稀疏。霍尔婚嫁定理来自汪湜通俗说法任意k个人他们总共能选择的对象集合大小必须至少是k才能一人一个。反例如果有 3 个人但他们加起来只认识 2 个对象那么这 3 个人不可能每个人都匹配成功必然有人落单。这就是违反了霍尔条件。对这个题来说每组人只有一个城市不能去s u m b sum_bsumb​个人的能选择对象集合大小就是所有城市容纳能力的和s u m c a p a c i t y sum_{capacity}sumcapacity​只要s u m c a p a c i t y ≥ s u m b sum_{capacity}\geq sum_bsumcapacity​≥sumb​就有合理分配方式注如果每组人可以避开多个城市这个贪心求和就不成立了必须用网络流。但本题每组只避开一个使得问题退化为简单的求和判断。voidsolve(){intn;cinn;intsb0;vectorinta(n1),b(n1),c(n1);forr(i,1,n)cina[i];forr(i,1,n){cinb[i];sbb[i];}forr(i,1,n)cinc[i];vectorintmxb(n1,sb);//根据相冲规则 每个城市预期最大的接纳人数forr(i,1,n){mxb[a[i]]-b[i];//犯冲的不不接纳}autocheck[](intx)-bool{vectorintd(n1);forr(i,1,n)d[i](x/c[i]);// 根据x的最大容量ints_cap0;// 总的最大容量forr(i,1,n){s_capmin(d[i],mxb[i]);}if(s_capsb)returnfalse;//小了elsereturntrue;// 大了};intl0,rinf;while(lr){intmid(lr)1;if(check(mid))rmid;elselmid1;}coutrendl;}/* 2 2 1 2 3 4 1 2 5 1 2 3 4 5 5 4 3 2 1 2 1 4 3 5 */L 大模拟之后有空补…