USACO 2018 December Contest, Silver
Problem 1.Convention
思路:二分最小時間,如果此時人數超過限制或兩頭奶牛相差時間小於最小時間,則增加車輛。
通過對比車輛數與要求的關係繼續二分。
程式碼:
#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> static const int MAXN=100050; using namespace std; int n,m,c,l,r,a[MAXN]; inline int read() { int x=0;bool sign=false; char alpha=0; while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar(); while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar(); return sign?-x:x; } inline bool check(int x) { int cnt=0,num=1,last=a[1]; for(int i=1;i<=n;i++) { if(++cnt>c) num++,cnt=1,last=a[i]; if(a[i]-last>x) num++,cnt=1,last=a[i]; } return num<=m; } int main() { n=read();m=read();c=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); r=a[n]-a[1]; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",l); return 0; }
Problem 2.Convention II
思路:先按時間從小到大排序,後使用優先佇列,先處理吃草的牛,後入隊上一頭牛吃草時到達的牛,選擇閱歷大的先吃。如果沒有牛到達,即無牛等待,那麼直接入隊,到目前的時間更改即可。
程式碼:
#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> static const int MAXN=100050; using namespace std; struct grass { int x,y,t; bool operator < (const grass &a)const { return t>a.t; } }; struct node { int t1,t2,cnt; }a[MAXN]; priority_queue<grass> q; int n,last,nowt,Max; inline int read() { int x=0;bool sign=false; char alpha=0; while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar(); while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar(); return sign?-x:x; } inline bool cmp(node a,node b) { if(a.t1==b.t1) return a.cnt<b.cnt; return a.t1<b.t1; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].t1=read(),a[i].t2=read(),a[i].cnt=i; sort(a+1,a+n+1,cmp); last=1; while(last<=n) { while(!q.empty()) { grass now=q.top(); q.pop(); Max=max(Max,nowt-now.x); nowt+=now.y; while(last<=n) { if(a[last].t1<=nowt) q.push((grass){a[last].t1,a[last].t2,a[last].cnt}),last++; else break; } } q.push((grass){a[last].t1,a[last].t2,a[last].cnt}); if(last<n) last++; nowt=q.top().x; } printf("%d\n",Max); return 0; }
Problem 3.Mooyo Mooyo
思路:大模擬。卻因為廣搜寫錯調了許久。。最後還是使用深搜,先處理出聯通塊,後模擬清除即可。
程式碼:
#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <set> static const int MAXN=150; static const int dirx[5]={0,1,-1,0}; static const int diry[5]={1,0,0,-1}; using namespace std; struct node { int x,y; char c; }q[MAXN*MAXN]; struct search { int x,y; bool operator < (const search &a) const { return x<a.x||(x==a.x&&y<a.y); } }; set<search> s; int n,k,head,tail,cnt; char a[MAXN][15]; bool vis[MAXN][MAXN],flag; inline bool check(int x,int y){return x<1||y<1||x>n||y>10?true:false;} int dfs(int x,int y,char c) { vis[x][y]=true; s.insert({x,y}); int ans=1; for(int i=0;i<4;i++) { int dx=x+dirx[i],dy=y+diry[i]; if(vis[dx][dy]||check(dx,dy)||a[dx][dy]!=c) continue; vis[dx][dy]=true; ans+=dfs(dx,dy,a[dx][dy]); } return ans; } inline void fall() { for(int i=n-1;i>=1;i--) { for(int j=1;j<=10;j++) { if(a[i][j]!='0') { int x=i,y=j; while(a[x+1][y]=='0') swap(a[x][y],a[x+1][y]),x++; } } } } int main() { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); while(1) { memset(vis,false,sizeof(vis)); bool flag=false; for(int i=1;i<=n;i++) { for(int j=1;j<=10;j++) { if(a[i][j]=='0'||vis[i][j]) continue; else { cnt=dfs(i,j,a[i][j]); if(cnt>=k) { for(set<search>::iterator it=s.begin();it!=s.end();it++) a[(*it).x][(*it).y]='0'; flag=true; } s.clear(); } } } fall(); if(!flag) break; } for(int i=1;i<=n;i++) { for(int j=1;j<=10;j++) printf("%c",a[i][j]); printf("\n"); } return 0; }