【做題記錄】csp2025-貪心專題
A. [NOIP2015 普及組] 推銷員
首先考慮一個明顯假的貪心，選擇前 \(X\) 大的疲勞值計算答案。
它假就假在，可以選擇一個（或幾個）疲勞值更小，但更遠的位置，使總貢獻更大。
略經思考后發現，如果要更換，那么一定要滿足距離比當前的所有都遠，而且更換掉的一定是當前最小的疲勞值。
同時，如果更換 \(2\) 個，則新的這 \(2\) 個疲勞值一定會都比當前的小，而距離卻只會按更遠的那個計算，因此一定不如更換一個更優。
故只需從前 \(X\) 大和更換掉一個的兩種答案中取 \(\max\) 即可。具體實現可以用前綴和、前后綴最小值。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,sum[maxn],f[maxn],g[maxn];
struct node{
int a,b;
}p[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(p[i].a);
}
for(int i=1;i<=n;i++){
read(p[i].b);
}
sort(p+1,p+n+1,[](const node &x,const node &y){return x.b>y.b;});
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+p[i].b;
f[i]=max(f[i-1],p[i].a<<1);
}
for(int i=n;i;i--){
g[i]=max(g[i+1],(p[i].a<<1)+p[i].b);
}
for(int i=1;i<=n;i++){
printf("%d\n",max(sum[i]+f[i],sum[i-1]+g[i]));
}
return 0;
}
}
int main(){return asbt::main();}
B. Two Heaps
考慮如果所有數都不一樣，那么答案就為 \(n^2\)。
如果有一個數出現了兩次，那么顯然一個放這邊另一個放那邊更優。
如果出現次數大于 \(2\)，那么剩下的是做不了貢獻的，亂放。
因此步驟為：
\(1.\) 將所有出現次數 \(\ge 2\) 的在兩邊各放一個，剩下的留著。
\(2.\) 將所有出現次數為 \(1\) 的平均分配給兩邊。
\(3.\) 用第 \(1\) 步中剩下的數填滿兩個集合。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=205;
int n,ans[maxn],num[maxn];
struct node{
int zhi,hao;
}a[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n<<1;i++){
read(a[i].zhi);
num[a[i].zhi]++;
a[i].hao=i;
}
sort(a+1,a+(n<<1|1),[](const node &x,const node &y){return x.zhi<y.zhi;});
int cnt1=0,cnt2=0;
for(int i=10;i<=99;i++){
if(num[i]>1){
cnt1++,cnt2++;
}
}
for(int i=10;i<=99;i++){
if(num[i]==1){
if(cnt1<=cnt2){
cnt1++;
}
else{
cnt2++;
}
}
}
printf("%d\n",cnt1*cnt2);
cnt1=cnt2=0;
for(int i=1;i<=n<<1;i++){
if(num[a[i].zhi]>1){
ans[a[i].hao]=1;
ans[a[++i].hao]=2;
cnt1++,cnt2++;
while(a[i+1].zhi==a[i].zhi){
i++;
}
}
}
for(int i=1;i<=n<<1;i++){
if(num[a[i].zhi]==1){
if(cnt1<=cnt2){
cnt1++;
ans[a[i].hao]=1;
}
else{
cnt2++;
ans[a[i].hao]=2;
}
}
}
for(int i=1;i<=n<<1;i++){
if(num[a[i].zhi]>2){
i++;
while(a[i+1].zhi==a[i].zhi){
i++;
if(cnt1<=cnt2){
cnt1++;
ans[a[i].hao]=1;
}
else{
cnt2++;
ans[a[i].hao]=2;
}
}
}
}
// cout<<cnt1<<" "<<cnt2<<"\n";
for(int i=1;i<=n<<1;i++){
printf("%d ",ans[i]);
}
return 0;
}
}
int main(){return asbt::main();}
C. Antichain
首先，題目給出的圖一定是一堆鏈構成的，其中有的點只在一條鏈中，有的同時在兩條鏈中。
首先，一條鏈中一定只能選一個點，即答案最大為鏈的數量。然后考慮這么個事，如果選擇了只在一條鏈中的點，那么會廢掉一條鏈；然而如果選擇了在兩條鏈中的點，那就會廢掉兩條鏈。因此貪心策略為首先選擇只在一條鏈中的點，然后再考慮在兩條鏈中的點。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
int n;
char s[maxn];
bitset<maxn> vis;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
scanf(" %s",s);
n=strlen(s);
int ans=0;
for(int u=0,v;u<n;u++){
if(vis[u]){
continue;
}
if(s[u]==s[(u-1+n)%n]){
// cout<<u<<"\n";
ans++,vis[u]=1,v=u;
while(s[v]==s[u]){
v=(v+1)%n;
vis[v]=1;
}
v=u;
while(s[(v-1+n)%n]==s[u]){
v=(v-1+n)%n;
vis[v]=1;
}
}
}
for(int u=0;u<n;u++){
if(vis[u]){
continue;
}
// cout<<u<<"\n";
ans++;
vis[u]=vis[(u+1)%n]=vis[(u-1+n)%n]=1;
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
D. [AGC057A] Antichain of Integer Strings
記 \(f(x)\) 為最小的大于 \(x\) 的 \(y\)，使得 \(x\) 是 \(y\) 的子串。易得：
\[f(x)=\min(10x,x+10^{|x|})
\]
其中 \(|x|\) 表示 \(x\) 的位數。
可以發現，\(f(x)\) 為一個嚴格單調遞增的函數。
考慮貪心策略，顯然選小的數不如選大的數優，因為小的數更有可能成為別的數的子串。于是，我們要求的其實就是這樣一個集合 \(\mathbb{A}\)，滿足：
\[\mathbb{A}=\{x\in[l,r]\mid f(x)>r\}
\]
因為 \(f(x)\) 是嚴格單增的，因此二分即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int pw10[]={
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000};
il int len(int x){
int res=0;
do{
res++,x/=10;
}while(x);
return res;
}
il int f(int x){
return min(x*10,x+pw10[len(x)]);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
// for(int i=1;i<=33;i++){
// cout<<i<<" "<<f(i)<<"\n";
// }
int T;
read(T);
while(T--){
int l,r,L,R;
read(l)read(r);
L=l,R=r;
while(l<r){
int mid=(l+r)>>1;
if(f(mid)>R){
r=mid;
}
else{
l=mid+1;
}
}
printf("%d\n",R-l+1);
}
return 0;
}
}
signed main(){return asbt::main();}
E. [USACO10MAR] Barn Allocation G
先按左端點升序排序，再按右端點升序排序。然后跑一個線段樹區間減一，區間取 \(\min\)。這樣的做法拿了 \(57 pts\)。然后再反著跑一遍，就過了。
原因是，正解做法為按右端點升序排序然后正著跑，我是按左端點升序排序再反著跑，那肯定是一樣的。。。
正確性證明，因為按右端點升序排序，所以新加的右端點大于后加的。如果有重合，選新的而不選舊的會導致白白給多出來的這一塊減了一個 \(1\)，顯然不如不選優。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,a[maxn];
struct node{
int l,r;
}p[maxn];
struct stree{
int zhi[maxn<<2],tag[maxn<<2];
il void pushup(int id){
zhi[id]=min(zhi[lid],zhi[rid]);
}
il void pushdown(int id){
if(tag[id]){
tag[lid]+=tag[id],tag[rid]+=tag[id];
zhi[lid]+=tag[id],zhi[rid]+=tag[id];
tag[id]=0;
}
}
il void build(int id,int l,int r){
tag[id]=0;
if(l==r){
zhi[id]=a[l];
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
tag[id]+=val,zhi[id]+=val;
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return zhi[id];
}
pushdown(id);
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return min(query(lid,L,mid,l,r),query(rid,mid+1,R,l,r));
}
}SG;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=m;i++){
read(p[i].l)read(p[i].r);
}
sort(p+1,p+m+1,[](const node &x,const node &y){return x.l<y.l||x.l==y.l&&x.r<y.r;});
SG.build(1,1,n);
int ans1=0,ans2=0;
for(int i=1;i<=m;i++){
if(SG.query(1,1,n,p[i].l,p[i].r)){
SG.upd(1,1,n,p[i].l,p[i].r,-1);
ans1++;
// cout<<i<<"\n";
}
}
SG.build(1,1,n);
for(int i=m;i;i--){
if(SG.query(1,1,n,p[i].l,p[i].r)){
SG.upd(1,1,n,p[i].l,p[i].r,-1);
ans2++;
// cout<<i<<"\n";
}
}
printf("%d",max(ans1,ans2));
return 0;
}
}
int main(){return asbt::main();}
F. [USACO09OCT] Allowance G
因為所有面值都可以整除比它大的面值，所以大的面值一定可以用小的湊出來，所以優先用大面值，剩下的用一個小面值來補就行了。
時間復雜度，每個硬幣最多被用一次，這一部分是 \(O(\sum B)\)；死循環中每次的硬幣選擇方式都是不同的，這一部分是 \(O(n2^n)\)，都可以過。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int n,m,ans;
vector<pii> q;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1,a,b;i<=n;i++){
read(a)read(b);
if(a>=m){
ans+=b;
}
else{
q.pb(mp(a,b));
}
}
sort(q.begin(),q.end());
for(;;){
int tmp=m;
for(int i=q.size()-1;~i;i--){
while(tmp>=q[i].fir&&q[i].sec){
tmp-=q[i].fir,q[i].sec--;
}
}
if(tmp>0){
for(int i=0;i<q.size();i++){
if(q[i].fir>=tmp&&q[i].sec){
q[i].sec--,tmp=0;
break;
}
}
}
if(tmp>0){
break;
}
ans++;
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
G. Competition
如果在一個 \(n\) 階樓梯上有 \(\le n\) 位運動員，則一定是合法的。
考慮每個運動員對應著一個區間 \([l,r]\)，表示這個人能到達的臺階。舉個例子：
把臺階的頂端從左往右編號，則 \(1\) 對應 \([1,3]\)，\(2\) 對應 \([2,3]\)，\(3\) 對應 \([4,4]\)，\(4\) 對應 \([3,5]\)。
那么我們只需要選擇一些區間，滿足存在一些點使可以不重復地給每個區間一個包含的點。
這是一個貪心，將所有區間按左端點排序，從左向右掃 \(n\) 個位置，掃到 \(i\) 時加入左端點為 \(i\) 的區間，此時所有的區間都是包含了 \(i\) 的，貪心地選擇右端點最小的，然后再刪去右端點為 \(i\) 的區間。具體實現可以用堆。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m;
struct node{
int id,l,r;
il bool operator<(const node &x)const{
return r>x.r;
}
}p[maxn];
priority_queue<node> q;
vector<int> ans;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1,x,y;i<=m;i++){
read(x)read(y);
p[i]=(node){i,n-y+1,x};
}
sort(p+1,p+m+1,[](const node &x,const node &y){return x.l<y.l;});
for(int i=1,j=1;i<=n;i++){
while(p[j].l==i){
q.push(p[j++]);
}
if(q.size()){
ans.pb(q.top().id);
q.pop();
}
while(q.size()&&q.top().r==i){
q.pop();
}
}
printf("%d\n",ans.size());
for(int x:ans){
printf("%d ",x);
}
return 0;
}
}
int main(){return asbt::main();}
H. Jeff and Permutation
首先將所有 \(a_i\) 都取絕對值，不影響答案。
考慮怎樣會產生逆序對（\(i<j\)）：
- \(a_i<a_j\)，則需要把 \(a_j\) 變成負的，\(a_i\) 變不變無所謂。
- \(a_i>a_j\)，則 \(a_i\) 不能變，\(a_j\) 變不變無所謂。
因此統計 \(a_i\) 前面比它小的、后面比它小的，即將 \(a_i\) 改為負數、不改為負數會增加的逆序對數，二者取 \(\min\) 即可。
在左側不能取小于等于，因為如果 \(a_i\) 的左側比它小的數都已經小于右側了，那么它左邊的一個相同的數肯定也是這樣。換句話說對于同一個數，一定是前面一部分變成負的，后面一部分不變。所以相同的數之間是不會產生貢獻的。
\(a_i\) 變不變號也不會影響其他位置的答案，因為較小的數變或不變號都是不會影響答案的。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e3+5;
int n,a[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
a[i]=abs(a[i]);
}
int ans=0;
for(int i=1,cnt1,cnt2;i<=n;i++){
cnt1=cnt2=0;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
cnt1++;
}
}
for(int j=i+1;j<=n;j++){
if(a[j]<a[i]){
cnt2++;
}
}
ans+=min(cnt1,cnt2);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
I. [HEOI2015] 兔子與櫻花
貪心策略：從下往上，對于每個點不斷選擇代價最小的兒子刪除。
正確性：首先，選擇最小的代價來刪顯然是沒問題的。考慮在節點 \(u\)，若刪除了它的一個兒子，那么可能會導致它的父親本來可以刪它，現在卻刪不了了。這樣先多刪一個再少刪一個，是不會影響答案的。因此此策略正確。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e6+5;
int n,m,a[maxn],ans;
vector<int> e[maxn];
il void dfs(int u){
for(int v:e[u]){
dfs(v);
}
sort(e[u].begin(),e[u].end(),[](const int &x,const int &y){return a[x]<a[y];});
for(int v:e[u]){
if(a[u]+a[v]-1<=m){
a[u]+=a[v]-1;
ans++;
}
else{
break;
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=0;i<n;i++){
read(a[i]);
}
for(int i=0,tot;i<n;i++){
read(tot);
a[i]+=tot;
for(int j=1,x;j<=tot;j++){
read(x);
e[i].pb(x);
}
}
dfs(0);
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
J. 展翅翱翔之時 (はばたきのとき)
從 \(a_i\) 向 \(i\) 連邊，題目給出的就是一個外向基環樹森林。題目的要求是將它變成一個環。考慮將每棵樹分開考慮。
思路是先斷成一條條鏈，然后再連起來。對于每個子樹上的點，只保留代價最大的兒子，其他兒子全部刪去。這樣就變成了一個環，向外伸出一堆鏈的形態。
現在枚舉環上的每個點，設為 \(u\)，則此時 \(a_u\) 是連出了兩條邊的（連向 \(u\) 的和伸出鏈的），一定要刪去一條。記錄刪去所有鏈的代價和將環斷開并保留一條鏈的代價，進行轉移即可。時間復雜度 \(O(n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,a[maxn],deg[maxn];
int cnt,idx[maxn];
ll b[maxn],ans,liu[maxn];
bitset<maxn> vis;
vector<int> e[maxn];
il void dfs1(int u){
vis[u]=1;
idx[++cnt]=u;
for(int v:e[u]){
if(vis[v]){
continue;
}
dfs1(v);
}
}
queue<int> q;
il void dfs2(int u){
ll mx=0,sum=0;
for(int v:e[u]){
if(deg[v]){
continue;
}
sum+=b[v],mx=max(mx,b[v]);
dfs2(v);
}
ans+=sum-mx,liu[u]=mx;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i])read(b[i]);
e[a[i]].pb(i);
deg[a[i]]++;
}
for(int i=1;i<=n;i++){
if(!deg[i]){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
if(--deg[a[u]]==0){
q.push(a[u]);
}
}
for(int x=1,tot;x<=n;x++){
if(vis[x]||!deg[x]){
continue;
}
// cout<<x<<"\n";
tot=cnt+1;
// puts("666");
dfs1(x);
if(cnt-tot+1==n){
for(int i=1;i<=n;i++){
if(!deg[i]){
goto togo;
}
}
puts("0");
return 0;
togo:;
}
for(int i=tot;i<=cnt;i++){
if(deg[idx[i]]){
dfs2(idx[i]);
}
}
// cout<<ans<<"\n";
ll sum=0,res=inf;
for(int i=tot;i<=cnt;i++){
if(deg[idx[i]]){
res=min(min(sum,res)+b[idx[i]],res+liu[a[idx[i]]]);
sum+=liu[a[idx[i]]];
}
}
ans+=res;
}
printf("%lld",ans);
return 0;
}
}
int main(){return asbt::main();}
/*
10
3 12
5 6
1 16
5 3
7 3
10 11
4 20
10 12
7 7
10 3
32
*/
浙公網安備 33010602011771號