2026-01-27 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，差不多就这？看看题解……
这么纯粹？直接算贡献？就是先贪使用优惠卷，然后每个物品再反悔一次，没了……就这？！
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=50005;intn,k,m,p[N],c[N];priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pr,cr;priority_queue<int,vector<int>,greater<int>>d;boolvis[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k>>m;for(inti=1;i<=n;i++){cin>>p[i]>>c[i];pr.push({p[i],i});cr.push({c[i],i});}for(inti=1;i<=k;i++){d.push(0);}intans=0;while(!pr.empty()){autotmp1=pr.top(),tmp2=cr.top();if(vis[tmp1.second]){pr.pop();continue;}if(vis[tmp2.second]){cr.pop();continue;}if(d.top()>tmp1.first-tmp2.first){m-=tmp1.first;pr.pop();vis[tmp1.second]=true;}else{m-=tmp2.first+d.top();d.pop();cr.pop();vis[tmp2.second]=true;d.push(p[tmp2.second]-c[tmp2.second]);}if(m>=0)ans++;elsebreak;}cout<<ans;}一些小细节还是自己想一下为好吧……
LGP9749 [CSP-J 2023] 公路
原题链接：[CSP-J 2023] 公路
分析
切不了橙……理论上……为啥我想到了单调栈？思考一下……好的，那么，既然你每次找后面小的，为啥不在前面经过的找最大的？这不就结了？
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=100005;intn,d,v[N],a[N];signedmain(){// freopen("road.in", "r", stdin);// freopen("road.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>d;for(inti=1;i<n;i++){cin>>v[i];}for(inti=1;i<=n;i++){cin>>a[i];}intans=0,mn=0x3f3f3f3f;intdis=0;for(inti=1;i<n;i++){dis+=v[i];mn=min(mn,a[i]);if(dis>0){inttmp=(dis+d-1)/d;ans+=tmp*mn;dis-=tmp*d;}}cout<<ans;}LGP3093 [USACO13DEC] Milk Scheduling S
原题链接：[USACO13DEC] Milk Scheduling S
分析
真的吗？🤔按照时间贪一下？那反悔在哪？对于一个时间点，我似乎只能贪一个吧……
就这？那我辛苦写的优先队列WA了算什么/ll
正解
#include<bits/stdc++.h>usingnamespacestd;constintN=10005;intn;structnode{intd,g;}a[N];boolcmp(node x,node y){returnx.g>y.g;}boolvis[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>a[i].g>>a[i].d;}sort(a+1,a+n+1,cmp);longlongans=0;for(inti=1;i<=n;i++){for(intj=a[i].d;j>=1;j--){if(!vis[j]){vis[j]=true;ans+=a[i].g;break;}}}cout<<ans;}LGP1163 银行贷款
原题链接：银行贷款
分析
没啥可说的，我以前汤包了。得出公式
a n s = w m w 0 m − 1 − 1 ans=\sqrt[m-1]{\frac{wm}{w_0}}-1ans=m−1w0wm−1
然后那个… m − 1 \sqrt[m-1]{\dots}m−1…可以直接pow(···,1.0/(m-1.0))，打一下。
算了，老老实实写实数二分吧。
正解
#include<bits/stdc++.h>usingnamespacestd;constdoubleeps=1e-5;doublew0,w,m;boolcheck(doublex){if(pow(1.0/(1.0+x),m)>=1-w0/w*x)returntrue;returnfalse;}signedmain(){cin>>w0>>w>>m;doublel=0.0,r=5.0;while(r-l>=eps){doublemid=(l+r)/2.0;if(check(mid))r=mid;elsel=mid;}cout<<fixed<<setprecision(1)<<l*100.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(1)O(1)了。好像是对的……就是要求中间没人而且这个可以达到他的要求。我是这么理解的。思考一下……怎么做这个转移？如果说中间有点，那炸了，我们可以整一个− ∞ -\infty−∞，对于那些单点和没有起始节点或者结束节点的段……思考一下怎么更新……而且要控制到O ( n 2 ) O(n^2)O(n2)，思考一下……咋还要求恰好为k i k_iki……难道说再记录一维？那铁定炸啊……理论上确实是预处理之后O ( 1 ) O(1)O(1)回答啊？还是看题解吧……还是背包！可以做离线，我是🍬……我们设f i f_ifi表示取价值为i ii的物品截止时间的最小值的最大值……可以理解为一个瓶颈吧……总之就是这个东西。代码比较清新。
正解
#include<bits/stdc++.h>usingnamespacestd;constintN=1005,M=100005,K=1000005;structnode1{intc,a,b;}inp[N];boolcmp1(node1 x,node1 y){returnx.a<y.a;}structnode2{intm,k,s,id;}que[K];boolcmp2(node2 x,node2 y){returnx.m<y.m;}intf[M];boolans[K];intn,p;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>inp[i].c>>inp[i].a>>inp[i].b;}sort(inp+1,inp+n+1,cmp1);cin>>p;for(inti=1;i<=p;i++){cin>>que[i].m>>que[i].k>>que[i].s;que[i].id=i;}sort(que+1,que+p+1,cmp2);f[0]=0x7f7f7f7f;intj=1;for(inti=1;i<=p;i++){while(j<=n&&inp[j].a<=que[i].m){for(intk=M-1;k>=inp[j].c;k--){f[k]=max(f[k],min(f[k-inp[j].c],inp[j].b));}j++;}if(f[que[i].k]>que[i].m+que[i].s){ans[que[i].id]=true;}}for(inti=1;i<=p;i++){if(ans[i])cout<<"TAK"<<'\n';elsecout<<"NIE"<<'\n';}}洛谷评测机有点坑啊，很多RE都给报的WA……
aoao提醒我该练代码能力了，启动！
)
)
