目錄

• [USACO 2007 Jan S]保護花朵【經(jīng)典貪心】
• [NOIP2005]校門外的樹【區(qū)間合并】
• [NOIP2006]明明的隨機數(shù)【簽到】
• [HNOI2003]激光炸彈【二維前綴和】
• 鋪地毯【枚舉】
• [NOIP2007]紀念品分組【模擬】
• [NOIP2016]回文日期【日期模擬】
• [NOIP1998]拼數(shù)【經(jīng)典貪心題】
• 毒瘤xor【貪心】
• 字符串【雙指針】
• 數(shù)學(xué)考試【貪心 前綴和】
• 「土」秘法地震【二維前綴和】
• 丟手絹【取尺法 雙指針】
• [NOIP2008]排座椅【貪心】
• [NOIP2012]國王的游戲【貪心 高精度】

[USACO 2007 Jan S]保護花朵【經(jīng)典貪心】

https://ac.nowcoder.com/acm/problem/25043
題解: 很經(jīng)典的一個貪心問題，你會發(fā)現(xiàn)一組牛中相鄰的兩個牛順序的改變不會改變其前面的牛的消費，也不會影響后面牛的花費

設(shè)A(t1,d1),B(t2,d2)。前面等的總的時間為s 如果先A再B則總的花費為 s*d1+(s+t1*2)*d2 如果先B再A則總的花費為 s*d2+(s+t2*2)*d1如果A先回去比B先回去更優(yōu)則: s*d1+(s+t1*2)*d2<s*d2+(s+t2*2)*d1 s*d1+s*d2+t1*2*d2<s*d2+s*d1+t2*2*d1 最終化簡可得: t1*d2<+t2*d1 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; typedef pair<int,int> PII; vector<PII>ve; int n,a,b; bool cmp(PII a,PII b) {return a.first*b.second<a.second*b.first;} int main(void) {cin>>n;for(int i=0;i<n;i++)cin>>a>>b,ve.push_back({a,b});sort(ve.begin(),ve.end(),cmp);LL s=0,ans=0;for(int i=0;i<ve.size();i++){ans+=s*ve[i].second;s+=ve[i].first*2;}cout<<ans;return 0; }

[NOIP2005]校門外的樹【區(qū)間合并】

https://ac.nowcoder.com/acm/problem/16649
經(jīng)典的區(qū)間合并，在處理的時候順便處理計算刪除的數(shù)量即可。

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; vector<PII>ve; int n,m,l,r; int main(void) {cin>>n>>m;while(m--) cin>>l>>r,ve.push_back({l,r});sort(ve.begin(),ve.end());int l=ve[0].first,r=ve[0].second;for(int i=1;i<ve.size();i++){if(ve[i].first<=r) r=max(r,ve[i].second);else{n-=r-l+1;l=ve[i].first,r=ve[i].second;}}n-=r-l+1;cout<<n+1<<endl;//+1是因為從0開始return 0; }

差分做法: 對于刪除的區(qū)間統(tǒng)一加1，最后統(tǒng)計0的個數(shù)即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int s[N],n,m,l,r; int main(void) {cin>>n>>m;while(m--){cin>>l>>r;l++,r++;//從將其 [0,n] 變成 [1,n+1]s[l]+=1,s[r+1]-=1;}int ans=0;for(int i=1;i<=n+1;i++) {s[i]=s[i]+s[i-1];if(!s[i]) ans++;//當(dāng)前的數(shù)為0,說明該樹還在}cout<<ans;return 0; }

[NOIP2006]明明的隨機數(shù)【簽到】

https://ac.nowcoder.com/acm/problem/16669

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,x,cnt; int main(void) {cin>>n;for(int i=0;i<n;i++) {cin>>x;if(!a[x]) cnt++;a[x]++;}cout<<cnt<<endl; for(int i=0;i<N;i++) if(a[i]) cout<<i<<" ";return 0; }

[HNOI2003]激光炸彈【二維前綴和】

https://ac.nowcoder.com/acm/problem/20032

#include<bits/stdc++.h> using namespace std; const int N=5010; int s[N][N],n,m; int main(void) {cin>>n>>m; m=min(m,N);while(n--){int x,y,c; cin>>x>>y>>c;x++,y++;s[x][y]+=c;}for(int i=1;i<N;i++)for(int j=1;j<N;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];int res=0;for(int i=1;i<N-m;i++)for(int j=1;j<N-m;j++){int x=i,y=j;int xx=i+m-1,yy=j+m-1;int temp=s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];res=max(res,temp); }cout<<res<<endl;return 0; }

鋪地毯【枚舉】

https://ac.nowcoder.com/acm/problem/16593
題解: 先存一下所有的地毯，然后枚舉所有的地毯可不可以覆蓋主該點即可。

#include<bits/stdc++.h> using namespace std; struct node{int x,y,g,k;}temp; vector<node>ve; int n,x,y; int main(void) {cin>>n;while(n--) {cin>>temp.x>>temp.y>>temp.g>>temp.k;ve.push_back(temp);}cin>>x>>y;int ans=-1;for(int i=0;i<ve.size();i++){int l1=ve[i].x,r1=l1+ve[i].g-1;int l2=ve[i].y,r2=l2+ve[i].k-1;if(x>=l1&&x<=r1&&y>=l2&&y<=r2) ans=i+1;}cout<<ans; }

[NOIP2007]紀念品分組【模擬】

https://ac.nowcoder.com/acm/problem/16640
就用雙端隊列模擬即可，每次取一個最大的和一個最小的看可不可以配對，盡可能多的配對。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int m,n,a[N]; deque<int>q; int main(void) {cin>>m>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);for(int i=0;i<n;i++) q.push_back(a[i]);int cnt=0;while(q.size()){if(q.size()>=2){auto l=q.front(); q.pop_front();auto r=q.back(); q.pop_back();if(l+r>m) q.push_front(l);}else q.pop_back();cnt++;}cout<<cnt<<endl;return 0; }

[NOIP2016]回文日期【日期模擬】

https://ac.nowcoder.com/acm/problem/16438

#include<bits/stdc++.h> using namespace std; int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; bool judge(int x) {if(x%400==0||(x%4==0&&x%100!=0)) return true;return false; } bool check(int a,int b,int c) {string s1=to_string(a);while(s1.size()<4) s1="0"+s1;string s2=to_string(c);while(s2.size()<2) s2="0"+s2;s2=to_string(b) +s2;while(s2.size()<4) s2="0"+s2;string s=s1+s2;for(int i=0;i<8/2;i++) if(s[i]!=s[8-1-i]) return false;return true; } int main(void) {int year1,year2,month1,month2,day1,day2;string a,b; cin>>a>>b;year1=stoi(a.substr(0,4)),month1=stoi(a.substr(4,2)),day1=stoi(a.substr(6,2));year2=stoi(b.substr(0,4)),month2=stoi(b.substr(4,2)),day2=stoi(b.substr(6,2));int cnt=0;if(check(year1,month1,day1)) cnt++;while( (year1!=year2) || (month1!=month2) || (day1!=day2) ){day1++;if(judge(year1)) month[2]=29;if(day1>month[month1]) day1=1,month1++;if(month1>12) month1=1,year1++;if(check(year1,month1,day1)) cnt++;month[2]=28;}cout<<cnt;return 0; }

[NOIP1998]拼數(shù)【經(jīng)典貪心題】

https://ac.nowcoder.com/acm/problem/16783

#include<bits/stdc++.h> using namespace std; string s; vector<string>ve; bool cmp(string a,string b) {return a+b>b+a;} int main(void) {int n; cin>>n;while(n--) cin>>s,ve.push_back(s);sort(ve.begin(),ve.end(),cmp);for(int i=0;i<ve.size();i++) cout<<ve[i]; }

毒瘤xor【貪心】

https://ac.nowcoder.com/acm/problem/18979

以第一個例子為例 0000,0000,0000,0000,0000,0000,0100 1110 0000,0000,0000,0000,0000,0000,0000,1100 0000,0000,0000,0000,0000,0000,0000,0001 0000,0000,0000,0000,0000,0000,0000,0011 我們對于每一位看是0優(yōu)還是1優(yōu)既可以了，這里的優(yōu)主要看該位的哪個數(shù)更少。 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int s[N][32]; int n,m,x; int main(void) {cin>>n;for(int i=1;i<=n;i++){cin>>x;for(int j=0;j<31;j++)if((x>>j)&1) s[i][j]++;}for(int i=1;i<=n;i++)//前綴和for(int j=0;j<31;j++) s[i][j]+=s[i-1][j];cin>>m;while(m--){int l,r; cin>>l>>r;int ans=0;int temp[32]={0};for(int i=0;i<31;i++) temp[i]=s[r][i]-s[l-1][i];//區(qū)間for(int i=0;i<31;i++){int cnt0=r-l+1-temp[i];//該位0的個數(shù)int cnt1=temp[i];//該位1的個數(shù)if(cnt0>cnt1) ans+=pow(2,i);//貪心}cout<<ans<<endl;}return 0; }

字符串【雙指針】

https://ac.nowcoder.com/acm/problem/18386

#include<bits/stdc++.h> using namespace std; int cnt[29]; int main(void) {string s; cin>>s;int ans=1e9,n=0;for(int i=0,j=0;i<s.size();i++){if(!cnt[s[i]-'a']) n++;cnt[s[i]-'a']++;while(n==26&&cnt[s[j]-'a']>1) cnt[s[j]-'a']--,j++;if(n==26) ans=min(ans,i-j+1);}cout<<ans;return 0; }

數(shù)學(xué)考試【貪心 前綴和】

https://ac.nowcoder.com/acm/problem/15553
枚舉第二個區(qū)間，在枚舉第二個區(qū)間的時候，維護前面的那個區(qū)間的值最大。

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+10; typedef long long int LL; LL s[N],t,n,k; int main(void) {cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];LL l=-1e18,ans=-1e18;for(int i=k;i+k<=n;i++){l=max(l,s[i]-s[i-k]);ans=max(ans,l+s[i+k]-s[i]); }cout<<ans<<endl;}return 0; }

「土」秘法地震【二維前綴和】

https://ac.nowcoder.com/acm/problem/53676
簡單的二維前綴和+枚舉

#include<bits/stdc++.h> using namespace std; const int N=1010; int s[N][N],n,m,k; string a[N]; int main(void) {cin>>n>>m>>k;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++)s[i+1][j+1]=a[i][j]-'0';for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];int cnt=0; for(int i=k;i<=n;i++)for(int j=k;j<=m;j++){int x=i-k+1,y=j-k+1;int xx=i,yy=j;int temp=s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];if(temp) cnt++;}cout<<cnt;return 0; }

丟手絹【取尺法 雙指針】

https://ac.nowcoder.com/acm/problem/207040
就是取尺法，用雙指針來維護。我們可以知道的是正解一定是趨于總路程對半分的狀態(tài)，只要維護這個即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,s,a[N]; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i],s+=a[i];int ans=0,temp=0;for(int i=0,j=0;i<n;i++) {while(temp<s/2){temp+=a[j];j=(j+1)%n;}int val=min(temp,s-temp);ans=max(ans,val);temp-=a[i];}cout<<ans<<endl;return 0; }

[NOIP2008]排座椅【貪心】

https://ac.nowcoder.com/acm/problem/16618
你會發(fā)現(xiàn)的一點就是行列的分法并無聯(lián)系。故分開考慮即可。
對于每一對的關(guān)系，我們就在該行/列記錄一下數(shù)字即可。最后排序，挨個取最大的即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef pair<int,int> PII; PII cntx[N],cnty[N]; int n,m,k,l,d; int main(void) {cin>>n>>m>>k>>l>>d;for(int i=1;i<=m;i++) cntx[i].second=i;//初始化編號for(int i=1;i<=n;i++) cnty[i].second=i;//初始化編號for(int i=0;i<d;i++){int x,y,xx,yy; cin>>y>>x>>yy>>xx;if(abs(x-xx)==1) cntx[min(x,xx)].first++;//該邊上的關(guān)系數(shù)加1else cnty[min(y,yy)].first++;}sort(cntx+1,cntx+1+m);sort(cnty+1,cnty+1+n); vector<int>a,b;for(int i=n,j=1;j<=k;i--,j++) a.push_back(cnty[i].second);for(int i=m,j=1;j<=l;i--,j++) b.push_back(cntx[i].second);sort(a.begin(),a.end());sort(b.begin(),b.end());for(int i=0;i<a.size();i++) cout<<a[i]<<" ";cout<<endl;for(int j=0;j<b.size();j++) cout<<b[j]<<" ";return 0; }

[NOIP2012]國王的游戲【貪心 高精度】

https://ac.nowcoder.com/acm/problem/16561
洛谷題解的推導(dǎo):

#include<bits/stdc++.h> using namespace std; struct node{long long int x,y;}temp; vector<node>ve; bool cmp(node a,node b){return a.x*a.y<b.x*b.y;} int n; vector<int>s,ans; vector<int> div(vector<int> A,int b) {vector<int>C;int t=0;for(int i=A.size()-1;i>=0;i--){t=t*10+A[i];C.push_back(t/b);t=t%b;}reverse(C.begin(),C.end());while(C.size()>1&&C.back()==0) C.pop_back();return C; } vector<int> mul(vector<int> A,int b) {vector<int>C;long long int t=0;for(int i=0;i<A.size()||t;i++){if(i<A.size()) t+=A[i]*b;C.push_back(t%10);t/=10;}while(C.size()>1&&C.back()==0) C.pop_back();return C; } vector<int> maxv(vector<int> A,vector<int> B) {if(A.size()>B.size()) return A;if(A.size()<B.size()) return B;for(int i=A.size()-1;i>=0;i--){if(A[i]>B[i]) return A;if(A[i]<B[i]) return B;}return A; } int main(void) {cin>>n; for(int i=0;i<=n;i++) cin>>temp.x>>temp.y,ve.push_back(temp);sort(ve.begin()+1,ve.end(),cmp);s.push_back(1),ans.push_back(0);for(int i=1;i<=n;i++){s=mul(s,ve[i-1].x);auto temp=div(s,ve[i].y);ans=maxv(ans,temp);}for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021算法竞赛入门班第一节课【枚举、贪心】习题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。