2026-10-03~04 hetao1733837 的刷题记录

LGP2865 [USACO06NOV] Roadblocks G原题链接[USACO06NOV] Roadblocks G分析我感觉可以动态维护次大值……做完了……不是哥们你别乱写Dijkstra啊正解#includebits/stdc.husingnamespacestd;constintN5005;intn,r;vectorpairint,inte[N];intd[N],dd[N];priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;voiddijkstra(intS){memset(d,0x3f,sizeof(d));memset(dd,0x3f,sizeof(dd));d[S]0;q.push({0,S});while(!q.empty()){autotmp1q.top();q.pop();intdutmp1.first;intutmp1.second;if(dudd[u])continue;for(autotmp2:e[u]){intvtmp2.first;intwtmp2.second;intndduw;if(ndd[v]){dd[v]d[v];d[v]nd;q.push({d[v],v});if(dd[v]0x3f3f3f3f)q.push({dd[v],v});}elseif(ndd[v]nddd[v]){dd[v]nd;q.push({dd[v],v});}}}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnr;for(inti1,a,b,d;ir;i){cinabd;e[a].push_back({b,d});e[b].push_back({a,d});}dijkstra(1);coutdd[n];}LGP2868 [USACO07DEC] Sightseeing Cows G原题链接[USACO07DEC] Sightseeing Cows G分析别急这个就是给我写O ( n 2 ) O(n^2)O(n2)的那不就是你开一个超级源点Dijkstra的时候算路径的最小时间和最大点权然后枚举找一个最大值就行了竟然是最大比率环那我不会了。别急我居然看过这集吗我好像暑假真的学过……那不就是二分吗哦妙哉妙哉那么开写吧……正解#includebits/stdc.husingnamespacestd;constintN1005,M5005;constdoubleeps1e-6;intl,p,f[N];structedge{intto,nxt,w;}e[M];inthead[N],tot;boolvis[N];intcnt[N];doubled[N];voidadd(intu,intv,intw){e[tot].nxthead[u];e[tot].tov;e[tot].ww;head[u]tot;}boolcheck(doublex){queueintq;for(inti1;il;i){q.push(i);d[i]0;vis[i]true;cnt[i]1;}while(!q.empty()){intuq.front();q.pop();vis[u]false;for(intihead[u];i;ie[i].nxt){intve[i].to;doublevale[i].w;if(d[v]d[u]x*val-f[u]){d[v]d[u]x*val-f[u];if(!vis[v]){q.push(v);vis[v]true;if(cnt[v]l)returntrue;}}}}returnfalse;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinlp;for(inti1;il;i){cinf[i];}for(inti1,l1,l2,t;ip;i){cinl1l2t;add(l1,l2,t);}doubleL0,R1000000;while(R-Leps){doublemid(LR)/2.0;if(check(mid))Lmid;elseRmid;}coutfixedsetprecision(2)L;}AT_abc478_f [ABC478F] Min-First Search原题链接[ABC478F] Min-First Search分析这为啥是绿啊道心破碎了l r h lrhlrh咋这么牛[拜谢]确实你会发现这个东西类似于dfn同时又加上了每次选取最小值这一条件。这么一看这道题不是特别困难……但是也并不简单……为啥我场上没有想这道题啊不可以吗别急那不就是先后出现的问题吗那不是随便做吗哦那不就是前面的都有可能成为它的父亲然后乘一下做完了说得有点笼统。那不就是如果前面出现了比这个数更大的数那么他肯定在这个数之前是这个位置的祖先同样在这一段上升之中还是有可能作为这个位置的祖先那么个数乘起来不就行了正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN200005;intn,q[N];intpre[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti0;in;i){cinq[i];q[i]--;}intans1;for(inti1;in;i){intposi-1;while(pos0q[pos]q[i]){pospre[pos];}pre[i]pos;ansans*(i-pos)%mod;}coutans;}