前言

好久沒(méi)更新這個(gè)系列了，最近閑的無(wú)聊寫(xiě)一下。有兩題搜索懶得寫(xiě)了。

---

P2737 [USACO4.1]麥香牛塊Beef McNuggets

https://www.luogu.com.cn/problem/P2737

解題思路

先只考慮$a_1$，假設(shè)我們拼出了$w$，那么一定能拼出$w+k{a}_1$，換句話我們考慮最大的不能拼出的$k{a}_1+w(0<w<a_1)$。

考慮到$gcd=1$顯然無(wú)解所以$a$中肯定存在$gcd(a_i,a_1)=1$，這樣對(duì)于每個(gè)$k{a}_i\%a_1(k<a_1)$都會(huì)有不同的值，所以根據(jù)鴿籠原理最大不能拼出的$k{a}_1+w\le a_1{a}_i?a_i$，這個(gè)范圍不會(huì)很大，暴力背包就好了。

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int L=256*256; int n,a[11],f[L]; int main() {scanf("%d",&n);int d=0,flag=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);d=__gcd(d,a[i]);flag|=(a[i]==1);}if(d!=1||flag)return puts("0")&0;f[0]=1;for(int i=1;i<L;i++)for(int j=1;j<=n;j++)if(i>=a[j])f[i]|=f[i-a[j]];for(int i=L-1;i>=1;i--)if(!f[i])return printf("%d\n",i)&0;return 0; }

---

P2738 [USACO4.1]籬笆回路Fence Loops

https://www.luogu.com.cn/problem/P2738

解題思路

每個(gè)籬笆開(kāi)兩個(gè)點(diǎn)，每個(gè)籬笆對(duì)之間記錄他們用來(lái)連接的端點(diǎn)然后建圖就變成最小環(huán)問(wèn)題了。

枚舉籬笆斷邊然后兩端跑最短路就好了。

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=210; struct node{int to,next,w;bool ban; }a[N*N]; int n,tot,ls[N],f[N],p[N][N],rev[N],pos[N],ans; bool v[N];queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void SPFA(int s){memset(f,0x3f,sizeof(f));q.push(s);v[s]=1;f[s]=0;while(!q.empty()){int x=q.front();q.pop();v[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(a[i].ban)continue;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y])q.push(y);}}}return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x,l,s1,s2;scanf("%d%d%d%d",&pos[i],&l,&s1,&s2);rev[pos[i]]=i;addl(i*2-1,i*2,l);addl(i*2,i*2-1,l);for(int j=0;j<s1;j++)scanf("%d",&x),p[i][x]=i*2-1;for(int j=0;j<s2;j++)scanf("%d",&x),p[i][x]=i*2;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(p[i][j])addl(p[i][j],p[rev[j]][pos[i]],0);ans=2147483647;for(int i=1;i<=n;i++){int w=i*2;a[w].ban=a[w-1].ban=1;SPFA(w-1);ans=min(ans,a[w].w+f[w]);a[w].ban=a[w-1].ban=0;}printf("%d\n",ans);return 0; }

---

P2740 [USACO4.2]草地排水Drainage Ditches

https://www.luogu.com.cn/problem/P2740

解題思路

最大流模板

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=210; struct node{int to,next,w; }a[N<<1]; int n,m,tot=1,ls[N],dep[N],ans; queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs(){memset(dep,0,sizeof(dep));dep[1]=1;while(!q.empty())q.pop();q.push(1);while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!a[i].w||dep[y])continue;dep[y]=dep[x]+1;if(y==m)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){if(x==m)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(flow==rest)return flow;}if(!rest)dep[x]=0;return rest; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);}while(bfs())ans+=dinic(1,2147483647);printf("%d\n",ans);return 0; }

---

P1894 [USACO4.2]完美的牛欄The Perfect Stall

https://www.luogu.com.cn/problem/P1894

解題思路

最大匹配，把上面那個(gè)最大流改一下就好了。

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=410; struct node{int to,next,w; }a[N*N]; int n,m,s,t,tot=1,ls[N],dep[N],ans; queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs(){memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty())q.pop();q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!a[i].w||dep[y])continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){if(x==t)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(flow==rest)return flow;}if(!rest)dep[x]=0;return rest; } int main() {scanf("%d%d",&n,&m);s=n+m+1;t=s+1;for(int i=1;i<=n;i++){int k,x;scanf("%d",&k);for(int j=0;j<k;j++)scanf("%d",&x),addl(i,x+n,1);}for(int i=1;i<=n;i++)addl(s,i,1);for(int i=1;i<=m;i++)addl(i+n,t,1);while(bfs())ans+=dinic(s,2147483647);printf("%d\n",ans);return 0; }

---

P2751 [USACO4.2]工序安排Job Processing

https://www.luogu.com.cn/problem/P2751

解題思路

考慮貪心，第一個(gè)正著做，開(kāi)一個(gè)單調(diào)隊(duì)列然后每次取最早做完的。

第二個(gè)和第一個(gè)一樣反著做，然后兩道工序時(shí)間長(zhǎng)的配時(shí)間短的就好了。

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1100; int n,A,B,t[N],s[N],a[N],ans; priority_queue<pair<int,int> > q; int main() {scanf("%d%d%d",&n,&A,&B);for(int i=1;i<=A;i++)scanf("%d",&a[i]),q.push(mp(-a[i],i));for(int i=1;i<=n;i++){pair<int,int> k=q.top();t[i]=-k.first;q.pop();q.push(mp(k.first-a[k.second],k.second));}printf("%d ",t[n]);while(!q.empty())q.pop();for(int i=1;i<=B;i++)scanf("%d",&a[i]),q.push(mp(-a[i],i));for(int i=1;i<=n;i++){pair<int,int> k=q.top();s[i]=-k.first;q.pop();q.push(mp(k.first-a[k.second],k.second));}for(int i=1;i<=n;i++)ans=max(ans,s[i]+t[n-i+1]);printf("%d\n",ans);return 0; }

---

P2687 [USACO4.3]逢低吸納Buy Low, Buy Lower

https://www.luogu.com.cn/problem/P2687

解題思路

最長(zhǎng)下降子序列，但是因?yàn)槭枪蓛r(jià)序列不同，所以方案數(shù)轉(zhuǎn)移的時(shí)候枚舉到上一個(gè)與它相等的就要停止。

要開(kāi)$longdouble$或者高精度

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define ll long double using namespace std; const int N=5100; long long n,a[N]; ll f[N],g[N]; signed main() {scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);a[++n]=0;a[0]=1e18;f[0]=g[0]=1;for(int i=1;i<=n;i++){for(int j=0;j<i;j++)if(a[j]>a[i])f[i]=max(f[i],f[j]+1);for(int j=i-1;j>=0;j--)if(a[j]==a[i])break;else if(a[j]>a[i]&&f[j]+1==f[i])g[i]+=g[j];}printf("%.0Lf %.0Lf\n",f[n]-2,g[n]);return 0; }

---

P2752 [USACO4.3]街道賽跑Street Race

https://www.luogu.com.cn/problem/P2752

解題思路

先跑一遍$Flody$，然后枚舉點(diǎn)，每次重新跑$Flody$判必經(jīng)點(diǎn)。

然后如果是必經(jīng)點(diǎn)用第一次的$Flody$判中間點(diǎn)。

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=51; int n;bool a[N][N],f[N][N],g[N][N]; vector<int>ans1,ans2; int main() {while(1){int x;scanf("%d",&x);if(x==-1)break;while(x!=-2){a[n][x]=g[n][x]=1;scanf("%d",&x);}n++;}for(int i=0;i<n;i++)a[i][i]=g[i][i]=1;for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]|=g[i][k]&g[k][j];for(int p=1;p<n-1;p++){memset(f,0,sizeof(f));for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=p&&j!=p)f[i][j]=a[i][j];for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)f[i][j]|=f[i][k]&f[k][j];if(!f[0][n-1]){ans1.push_back(p);bool flag=1;for(int i=0;i<n;i++){if(i==p)continue;if(f[0][i])flag&=(g[i][p]&&!g[p][i]);if(f[i][n-1])flag&=g[p][i];}if(flag)ans2.push_back(p);}}printf("%d",ans1.size());for(int i=0;i<ans1.size();i++)printf(" %d",ans1[i]);putchar('\n');printf("%d",ans2.size());for(int i=0;i<ans2.size();i++)printf(" %d",ans2[i]);putchar('\n');return 0; }

---

P2753 [USACO4.3]字母游戲Letter Game

解題思路

先看懂題，然后發(fā)現(xiàn)雖然字符串很多，但是合法的字符串個(gè)數(shù)不會(huì)超過(guò)$2^7$所以只跑合法的不會(huì)超過(guò)$O(n^2)$

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int w[26]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7}; struct node{char s[7];int l,c; }a[410000]; int n,ans,c[30],v[30]; char t[7]; vector<pair<int,int> >pr; //bool operator==(node x,node y){ // for(int i=0;i<7;i++) // if(x.s[i]!=y.s[i])return 0; // return 1; //} //bool operator<(node x,node y){ // for(int i=0;i<7;i++) // if(x.s[i]!=y.s[i])return x.s[i]<y.s[i]; // return 0; //} bool check(node x,node y){for(int i=0;i<26;i++)v[i]=c[i];for(int i=0;i<x.l;i++)if(v[x.s[i]-'a'])v[x.s[i]-'a']--;else return 0;for(int i=0;i<y.l;i++)if(v[y.s[i]-'a'])v[y.s[i]-'a']--;else return 0;return 1; } int main() {scanf("%s",t);int m=strlen(t);for(int i=0;i<m;i++)c[t[i]-'a']++;while(1){++n;scanf("%s",a[n].s);if(a[n].s[0]=='.'){n--;break;}a[n].l=strlen(a[n].s);if(!check(a[n],a[0])){n--;continue;}for(int i=0;i<a[n].l;i++)a[n].c+=w[a[n].s[i]-'a'];}ans=0;for(int i=1;i<=n;i++){if(a[i].c>ans)ans=a[i].c,pr.clear();if(a[i].c==ans)pr.push_back(make_pair(i,0));for(int j=i;j<=n;j++){if(check(a[i],a[j])){if(a[i].c+a[j].c>ans)ans=a[i].c+a[j].c,pr.clear();if(a[i].c+a[j].c==ans)pr.push_back(make_pair(i,j));}}}printf("%d\n",ans);for(int i=0;i<pr.size();i++)printf("%s %s\n",a[pr[i].first].s,a[pr[i].second].s);return 0; }

---

P1344 [USACO4.4]追查壞牛奶Pollutant Control

https://www.luogu.com.cn/problem/P1344

解題思路

以前寫(xiě)的了，費(fèi)用流模板，那個(gè)費(fèi)用變成第一關(guān)鍵值乘上一個(gè)很大的值加上第二個(gè)關(guān)鍵值就好了。

code

// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ll long long using namespace std; const ll N=320,M=10010,inf=1e18,cs=2333; struct node{ll to,next,w; }a[M*2]; ll tot=1,n,s,t,m,ans; ll dep[N],ls[N]; queue<int> q; void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs() {memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(!dep[y]&&a[i].w){dep[y]=dep[x]+1;if(y==t) return true;q.push(y);}}}return false; } ll dinic(ll x,ll flow) {ll rest=0,k;if(x==t) return flow;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow) return flow;}}if(!rest) dep[x]=0;return rest; } void netflow() {while(bfs())ans+=dinic(s,inf); } int main() {scanf("%lld%lld",&n,&m);s=1;t=n;for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);w=w*cs+1;addl(x,y,w);}netflow(); printf("%lld %lld",ans/cs,ans%cs); }

---

后面兩道搜索懶得寫(xiě)了

總結(jié)

以上是生活随笔為你收集整理的USACO Section 4的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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