原题B 枚举倍数 模拟 调和级数算时间复杂度一开始以为有某种式子能O(1)算出来但其实a2时每次改变的倍数最多O ( l o g n ) O(logn)O(logn)a1直接全按掉O ( 1 ) O(1)O(1)voidsolve(){intn,m;cinnm;/* 想复杂了 限定n2e5 直接枚举就可以 nlogn */intcntn;vectorintst(n1,0);forr(i,1,m){intans0,a;cina;if(cnt!st[a]){if(a1){// 防止退化为O(n)coutcntendl;cnt0;}else{for(intja;jn;ja){// lognif(st[j])continue;elseans,st[j]1,cnt--;}if(ans)coutansendl;elsecoutthe lights are already on!endl;}}else{coutthe lights are already on!endl;}}}D 思维 贪心一开始没注意到字典序最小贪心来想前面的L越多越好尽量左右横跳整体方向是向右到头再回来voidsolve(){intn;cinn;vectorinta(n2,0);intsm0;forr(i,0,n){cina[i];sma[i];}// 注意还要求字典序最小intpos0;string ans;// 从右推向左vectorintpre(n1,0);// 和前一个位置有多少次交换pre[n]a[n];reforr(i,0,n-1){pre[i]a[i]-pre[i1];if((i0pre[i]0)||(i0pre[i]!0))returncoutImpossibleendl,void();}forr(i,1,n){forr(j,1,pre[i]-1){ansRL;// 左右横跳}ansR;// 向后走}forr(i,1,n){ansL;// 回来}coutansendl;// while (ans.size()sm)// {// // forr(i,0,n)couta[i] ;coutendl;// if(a[pos1]){// ansR;// a[pos]--;// continue;// }else if(pos0a[pos-1]){// ansL;// a[--pos]--;// }else{// return coutImpossibleendl,void();// }// }// // coutposendl;// if(pos!0)return coutImpossibleendl,void();// coutansendl;}L 基环树 树形dpconstintN1e510,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf2e18;vectorintg[N];// 并查集找环intfa[N],vis[N],cnt[N][2];// cnt[][1奶龙/0不是]intfindf(intx){returnfa[x](fa[x]x?x:findf(fa[x]));}intdfs(intnow,intf){// 树形dp找答案vis[now]1;cnt[now][0]0;cnt[now][1]1;for(autox:g[now]){if(xf||vis[x])continue;dfs(x,now);cnt[now][0]max(cnt[x][0],cnt[x][1]);cnt[now][1]cnt[x][0];}vis[now]0;// 回复现场returncnt[now][0];}voidsolve(){/* 自环 自己说自己是奶龙 必然是说假话的其他生物 */intn;cinn;forr(i,1,n)fa[i]i;vectorinta(n1);vectorpiicir;forr(i,1,n){cina[i];g[a[i]].push_back(i);intfxfindf(a[i]),fyfindf(i);if(fx!fy)fa[fy]fx;elsecir.push_back({a[i],i});}intans0;for(auto[u,v]:cir){ansmax(dfs(u,0),dfs(v,0));}coutansendl;}G 贪心(找每次操作的收益比率) 二分查找参考也不算坏天气 的题解贪心 让每个增加都能获得最大收益每次增加前后 商品金额比率p 100 ( t 1 ) l 100 t l 1 l 100 t l 1 x ′ p\frac{100(t1)l}{100tl}1\frac{l}{100tl}1xp100tl100(t1)l​1100tll​1x′发现t越大 p越小t l − 100 x ′ x ′ l t\frac{l-100x}{xl}tx′ll−100x′​向下取整 让p尽量比较大令x 1 x ′ x{1\over {x}}xx′1​t x − 100 l tx-{{100}\over l}tx−l100​intn,k;intL[N],t[N];/* 一开始想用dfs 但是每个点从k中分配 枚举每个城市的t 复杂度爆炸 void dfs(int now,int lst){ } */intcal(doublex){// 计算给定比率 需要的t总和intsm0;forr(i,1,n){t[i]max(0.0,floor(x-100/(L[i]*1.0)));smt[i];}returnsm;}voidsolve(){cinnk;forr(i,1,n)cinL[i];doublel0,r1e6,bestpl;while(r-leps){// coutl rendl;doublemid(lr)/2;if(cal(mid)k)lmid,bestpmid;elsermid;}intusedcal(bestp);/* 用优先队列会损失精度 priority_queuepairdouble,intq; forr(i,1,n){ q.push({(100(t[i]1)*L[i])/(100t[i]*L[i]),i}); } while (usedk) { auto [pn,id]q.top();q.pop(); t[id]; q.push({(100.0(t[id]1)*L[id]*1.0)/(100.0t[id]*L[id]*1.0),id}); used; } */while(usedk){// 线性查找最优比率intid1;doublemx(100.0(t[id]1)*L[id]*1.0)/(100.0t[id]*L[id]*1.0);forr(i,2,n){doublenow(100.0(t[i]1)*L[i]*1.0)/(100.0t[i]*L[i]*1.0);if(nowmx){mxnow,idi;}}t[id];used;}doubleans1;forr(i,1,n)ans*(11.0*(t[i]*1.0*L[i])/100.0);coutfixedsetprecision(8)ansendl;}