核心内容摘要
17C—5C起草口：数字时代的智慧之选，未来生活的无限可能
hetao1733837 的刷题笔记LGP3045 [USACO12FEB] Cow Coupons G原题链接[USACO12FEB] Cow Coupons G分析其实吧这个可以拿背包做但是M ≤ 10 14 M\le 10^{14}M≤1014显然不行充分理解了fqh所说的dp实现复杂度不行的论断。
思考一下模一下样例……哦注意是价格降为C i C_iCi。
思考一下……难道说……那么简单吗按照什么贪心思考一下……NOIP2025 T1算反悔吗要是算的话……那紫也不能和黄比呀难道说我先按照差去贪一遍然后再按照……反一下神秘……unk……看到了一个并行的东西……就是因为C i ≤ P i C_i\le P_iCi≤Pi所以我们在一些情况下是尽可能把优惠券用完的所以很微妙啊……怎么贪呢开两个priority_queue再开一个vis差不多就这看看题解……这么纯粹直接算贡献就是先贪使用优惠卷然后每个物品再反悔一次没了……就这正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN50005;intn,k,m,p[N],c[N];priority_queuepairint,int,vectorpairint,int,greaterpairint,intpr,cr;priority_queueint,vectorint,greaterintd;boolvis[N];signedmain(){ios::sync_with_stdio(
;cin.tie(
;cout.tie(
;cinnkm;for(inti1;in;i){cinp[i]c[i];pr.push({p[i],i});cr.push({c[i],i});}for(inti1;ik;i){d.push(
;}intans0;while(!pr.empty()){autotmp1pr.top(),tmp2cr.top();if(vis[tmp
second]){pr.pop();continue;}if(vis[tmp
second]){cr.pop();continue;}if(d.top()tmp
first-tmp
first){m-tmp
first;pr.pop();vis[tmp
second]true;}else{m-tmp
firstd.top();d.pop();cr.pop();vis[tmp
second]true;d.push(p[tmp
second]-c[tmp
second]);}if(m
ans;elsebreak;}coutans;}一些小细节还是自己想一下为好吧……LGP9749 [CSP-J 2023] 公路原题链接[CSP-J 2023] 公路分析切不了橙……理论上……为啥我想到了单调栈思考一下……好的那么既然你每次找后面小的为啥不在前面经过的找最大的这不就结了正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN100005;intn,d,v[N],a[N];signedmain(){// freopen(road.in, r, stdin);// freopen(road.out, w, stdout);ios::sync_with_stdio(
;cin.tie(
;cout.tie(
;cinnd;for(inti1;in;i){cinv[i];}for(inti1;in;i){cina[i];}intans0,mn0x3f3f3f3f;intdis0;for(inti1;in;i){disv[i];mnmin(mn,a[i]);if(dis
{inttmp(disd-
/d;anstmp*mn;dis-tmp*d;}}coutans;}LGP3093 [USACO13DEC] Milk Scheduling S原题链接[USACO13DEC] Milk Scheduling S分析真的吗按照时间贪一下那反悔在哪对于一个时间点我似乎只能贪一个吧……就这那我辛苦写的优先队列WA了算什么/ll正解#includebits/stdc.husingnamespacestd;constintN10005;intn;structnode{intd,g;}a[N];boolcmp(node x,node y){returnx.gy.g;}boolvis[N];signedmain(){ios::sync_with_stdio(
;cin.tie(
;cout.tie(
;cinn;for(inti1;in;i){cina[i].ga[i].d;}sort(a1,an1,cmp);longlongans0;for(inti1;in;i){for(intja[i].d;j1;j--){if(!vis[j]){vis[j]true;ansa[i].g;break;}}}coutans;}LGP1163 银行贷款原题链接银行贷款分析没啥可说的我以前汤包了。
得出公式a n s w m w 0 m − 1 − 1 ans\sqrt[m-1]{\frac{wm}{w_0}}-1ansm−1w0wm−1然后那个… m − 1 \sqrt[m-1]{\dots}m−1…可以直接pow(···,
0/(m-
1.
)打一下。
算了老老实实写实数二分吧。
正解#includebits/stdc.husingnamespacestd;constdoubleeps1e-5;doublew0,w,m;boolcheck(doublex){if(pow(
0/(
0x),m)1-w0/w*x)returntrue;returnfalse;}signedmain(){cinw0wm;doublel
0,r
0;while(r-leps){doublemid(lr)/
0;if(check(mid))rmid;elselmid;}coutfixedsetprecision(
l*
1
0;}浦东启动吧……没错似乎有半周了我还没有走出原生动物……所以竞赛门槛哪有什么高低之分都是时间、努力、天分、运气的积淀。
lz不让我用他的充电线给台灯充电是害怕我把台灯当成充电宝给别的东西充电吗我似乎也没啥了……早知道上午充了……嘻嘻岁岁大好入借到了……誓死追随岁岁LGP3537 [POI 2012] SZA-Cloakroom原题链接[POI 2012] SZA-Cloakroom分析这不是个线段覆盖问题吗n ≤ 1000 n\le1000n≤1000很微妙啊……似乎可以做类似d p i , j dp_{i,j}dpi,j表示[ i , j ] [i,j][i,j]这段时间的最大价值。
q ≤ 10 6 q\le10^6q≤106就差不多要O ( 1 ) O(
O(
了。
好像是对的……就是要求中间没人而且这个可以达到他的要求。
我是这么理解的。
思考一下……怎么做这个转移如果说中间有点那炸了我们可以整一个− ∞ -\infty−∞对于那些单点和没有起始节点或者结束节点的段……思考一下怎么更新……而且要控制到O ( n 2 ) O(n^
O(n
思考一下……咋还要求恰好为k i k_iki……难道说再记录一维那铁定炸啊……理论上确实是预处理之后O ( 1 ) O(
O(
回答啊还是看题解吧……还是背包可以做离线我是……我们设f i f_ifi表示取价值为i ii的物品截止时间的最小值的最大值……可以理解为一个瓶颈吧……总之就是这个东西。
代码比较清新。
正解#includebits/stdc.husingnamespacestd;constintN1005,M100005,K1000005;structnode1{intc,a,b;}inp[N];boolcmp1(node1 x,node1 y){returnx.ay.a;}structnode2{intm,k,s,id;}que[K];boolcmp2(node2 x,node2 y){returnx.my.m;}intf[M];boolans[K];intn,p;intmain(){ios::sync_with_stdio(