比较弱，只写了金组和银组，铂金组的第一题。
【262144】
http://www.usaco.org/index.php?page=viewproblem2&cpid=648
给一个序列，相邻两个数组相同的可以合并变成数值大一的数，问最大能得到的数。n<262144,val<=40
是金组某道题的升级版。
因为val<40，实际上最大可以取到的不超过60.所以从1-60，看看从i开始是否能合并到当前数值。可以的话记录合并到哪一位。
初始化f[i][val[i]]=i+1,状态转移f[i][j]=f[f[i][j-1][j-1]。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define maxn 300000 using namespace std; int f[62][maxn],num[maxn],ans,n; void input() {freopen("262144.in","r",stdin);freopen("262144.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} void work() { int i,k; memset(f,0,sizeof(f)); for (k=0;k<=60;k++) { for (i=1;i<=n;i++) { if (num[i]==k) f[k][i]=i+1; else { if (!k || !f[k-1][i] || !f[k-1][f[k-1][i]]) f[k][i]=0; else f[k][i]=f[k-1][f[k-1][i]]; } if (f[k][i]) ans=k; } f[k][n+1]=0; } return; } int main() { input(); scanf("%d ",&n); int i; for (i=1;i<=n;i++) scanf("%d",&num[i]); work(); printf("%d ",ans); output(); return 0; }
AU
【Splitting the Field】
http://www.usaco.org/index.php?page=viewproblem2&cpid=645
在平面内给一些点，然后用两个矩形把所有的点围起来，矩形不能有交集和重边，问最小面积。N≤50,000
首先，两个矩形必定会在最左最右最上最下。进一步可以发现，答案一定在左右分割或者上下分割两种情况里面。
然后就排好序，扫一边求以这个点为分界划出的两个区域的面积。
两个答案取最大值。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define LL long long #define maxn 100000 using namespace std; struct node{LL x,y;} point[maxn]; LL nmax[maxn],nmin[maxn]; int n; int cmp1(node p1,node p2){return p1.y<p2.y;} int cmp2(node p1,node p2){return p1.x<p2.x;} void input() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} int main() { input(); scanf("%d",&n); int i; for (i=0;i<n;i++) scanf("%lld %lld",&point[i].x,&point[i].y); LL ans=((LL)(1)<<62),now1,now2,now,big1,big2; //x // printf(" "); sort(point,point+n,cmp1); big1=point[n-1].y-point[0].y; nmax[n-1]=point[n-1].x; nmin[n-1]=point[n-1].x; for (i=n-2;i>=0;i--) { nmax[i]=max(point[i].x,nmax[i+1]); nmin[i]=min(point[i].x,nmin[i+1]); } // for (i=0;i<n;i++) printf("%lld %lld %lld %lld ",point[i].x,point[i].y,nmin[i],nmax[i]); now1=point[0].x; now2=point[0].x; for (i=1;i<n-1;i++) { now1=max(point[i].x,now1); now2=min(point[i].x,now2); if (point[i+1].y!=point[i].y) { now=(point[i].y-point[0].y)*(now1-now2) +(point[n-1].y-point[i+1].y)*(nmax[i+1]-nmin[i+1]); if (now<ans) ans=now; } } // printf("%lld %d ",ans,ans1); //y // printf(" "); sort(point,point+n,cmp2); big2=point[n-1].x-point[0].x; nmax[n-1]=point[n-1].y; nmin[n-1]=point[n-1].y; for (i=n-2;i>=0;i--) { nmax[i]=max(point[i].y,nmax[i+1]); nmin[i]=min(point[i].y,nmin[i+1]); } // for (i=0;i<n;i++) printf("%lld %lld %lld %lld ",point[i].x,point[i].y,nmin[i],nmax[i]); now1=point[0].y; now2=point[0].y; for (i=1;i<n-1;i++) { now1=max(point[i].y,now1); now2=min(point[i].y,now2); if (point[i+1].x!=point[i].x) { now=(point[i].x-point[0].x)*(now1-now2) +(point[n-1].x-point[i+1].x)*(nmax[i+1]-nmin[i+1]); if (now<ans) ans=now; } } // printf("%lld %d ",ans,ans1); printf("%lld ",big1*big2-ans); output(); return 0; }
【Closing the Farm】
http://www.usaco.org/index.php?page=viewproblem2&cpid=646
给一个图，每次去掉一个点，问每次去掉后余下的图是否联通。
倒过来，变成每次加一个点看是否图联通。并查集做就可以。
（并查集加了启发式合并然并卵）
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define maxn 201000 #define maxm 401000 using namespace std; int to[maxm],next[maxm],first[maxn],ans[maxn],fa[maxn],rank[maxn],chose[maxn],num[maxn],n,m,total=0; void input() {freopen("closing.in","r",stdin);freopen("closing.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} void addedge(int j,int k) { next[++total]=first[j]; to[first[j]=total]=k; } int find(int x) { if (fa[x]==x) return x; return fa[x]=find(fa[x]); } int main() { input(); int i,j,k; scanf("%d %d",&n,&m); memset(first,0,sizeof(first)); for (i=1;i<=m;i++) { scanf("%d %d",&j,&k); addedge(j,k); addedge(k,j); } for (i=1;i<=n;i++) scanf("%d",&num[i]); int now=0; for (i=1;i<=n;i++) fa[i]=i; memset(chose,0,sizeof(chose)); memset(ans,0,sizeof(ans)); memset(rank,0,sizeof(rank)); for (i=n;i;i--) { ++now; int x=num[i]; chose[x]=1; rank[x]=1; for (j=first[x];j;j=next[j]) { int too=to[j]; if (chose[too]) { int fy=find(too); int fx=find(x); if (fy!=fx) { --now; if (rank[fx]>rank[fy]) fa[fy]=fx; else { fa[fx]=fy; if (rank[fx]==rank[fy]) rank[fy]++; } } } } if (now==1) ans[i]=1; } for (i=1;i<=n;i++) printf(ans[i]?"YES ":"NO "); output(); return 0; }
【248】
262144的弱化版。n^3dp就可以了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define maxn 300 using namespace std; int f1[maxn][maxn],f2[maxn][maxn],f3[maxn][maxn],num[maxn],ans=0,n; void input() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} void dfs(int ll,int rr) { if (f1[ll][rr]!=-1) return; if (ll==rr) { f1[ll][rr]=num[ll]; f2[ll][rr]=num[ll]; f3[ll][rr]=num[ll]; ans=max(ans,f1[ll][rr]); ans=max(ans,f2[ll][rr]); ans=max(ans,f3[ll][rr]); return; } if (ll+1==rr) { if (num[ll]==num[rr]) { f1[ll][rr]=num[ll]+1; f2[ll][rr]=num[ll]+1; f3[ll][rr]=num[rr]+1; } else { f1[ll][rr]=0; f2[ll][rr]=num[ll]; f3[ll][rr]=num[rr]; } ans=max(ans,f1[ll][rr]); ans=max(ans,f2[ll][rr]); ans=max(ans,f3[ll][rr]); return; } f1[ll][rr]=0; for (int i=ll;i<rr;i++) { dfs(ll,i); dfs(i+1,rr); if (f1[ll][i]==f1[i+1][rr] && f1[ll][i]) f1[ll][rr]=f1[ll][i]+1; if (f2[ll][i]>f2[ll][rr]) f2[ll][rr]=f2[ll][i]; if (f3[i+1][rr]>f3[ll][rr]) f3[ll][rr]=f3[i+1][rr]; if (f3[ll][i]==f2[i+1][rr] && f2[i+1][rr]) ans=max(ans,f2[i+1][rr]+1); ans=max(ans,f1[ll][rr]); ans=max(ans,f2[ll][rr]); ans=max(ans,f3[ll][rr]); } } int main() { input(); scanf("%d",&n); int i,j; for (i=1;i<=n;i++) scanf("%d",&num[i]); for (i=1;i<=n;i++) for (j=i;j<=n;j++) f1[i][j]=-1; dfs(1,n); // for (i=1;i<=n;i++) // for (j=i;j<=n;j++) // printf("%d %d:%d %d %d ",i,j,f1[i][j],f2[i][j],f3[i][j]); printf("%d ",ans); output(); return 0; }
ag
【Field Reduction】
给一些在平面内的点，去掉三个点，问余下的点用矩形圈起来的最小面积。
直接爆搜，每次只可能去最上最下最左最右的点。4^3。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define maxn 600000 using namespace std; struct node{int x,y,num;} point[maxn],po2[maxn]; int ans,n,numx[maxn],numy[maxn],chose[maxn],p[3]; int cmp1(node x,node y){return x.x<y.x;} int cmp2(node x,node y){return x.y<y.y;} void input() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} void dfs(int x) { int l1=-1,l2=n,r1=-1,r2=n; while (!chose[numx[++l1]]); while (!chose[numx[--l2]]); while (!chose[numy[++r1]]); while (!chose[numy[--r2]]); if (x==3) { // for (int i=0;i<3;i++) printf("%d ",p[i]);printf(" "); // printf("%d %d %d %d %d %d %d ",numx[l1],numx[l2],numy[r1],numy[r2], // (po2[numx[l2]].x-po2[numx[l1]].x), // (po2[numy[r2]].y-po2[numy[r1]].y), // (po2[numx[l2]].x-po2[numx[l1]].x)*(po2[numy[r2]].y-po2[numy[r1]].y)); ans=min((po2[numx[l2]].x-po2[numx[l1]].x)*(po2[numy[r2]].y-po2[numy[r1]].y),ans); return; } chose[numx[l1]]=0; p[x]=numx[l1]; dfs(x+1); chose[numx[l1]]=1; chose[numx[l2]]=0; p[x]=numx[l2]; dfs(x+1); chose[numx[l2]]=1; chose[numy[r1]]=0; p[x]=numy[r1]; dfs(x+1); chose[numy[r1]]=1; chose[numy[r2]]=0; p[x]=numy[r2]; dfs(x+1); chose[numy[r2]]=1; } int main() { input(); scanf("%d",&n); int i; for (i=0;i<n;i++) { scanf("%d %d",&point[i].x,&point[i].y); point[i].num=i; po2[i]=point[i]; } sort(point,point+n,cmp1); for (i=0;i<n;i++) numx[i]=point[i].num; sort(point,point+n,cmp2); for (i=0;i<n;i++) numy[i]=point[i].num; // for (i=0;i<n;i++) printf("%d ",numx[i]);printf(" "); // for (i=0;i<n;i++) printf("%d ",numy[i]);printf(" "); ans=(1<<31)-1; for (i=0;i<n;i++) chose[i]=1; dfs(0); printf("%d ",ans); output(); return 0; }
【Diamond Collector】
给一些数，从数中选取出两个集合，要求集合内的数差不超过给定值，问两个集合数字个数和最大？
队列就可以啦，出队为当前点和队头距离大于m。然后每次的答案为之前的最大值和当前队里面数的个数。
#include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> #include<stack> #include<cmath> #include<vector> #include<map> #define LL long long #define maxn 55000 using namespace std; int f[maxn],n,ans,num[maxn],m; void input() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);} void output() {fclose(stdin);fclose(stdout);} int main() { input(); scanf("%d %d",&n,&m); int i; for (i=0;i<n;i++) scanf("%d",&num[i]); sort(num,num+n); int l=0,r=-1,ans=0,now=0; while (++r<n) { while (num[r]-num[l]>m) { if (f[l]>ans) ans=f[l]; l++; } f[r]=r-l+1; // printf("%d %d %d %d %d ",l,r,num[r],f[r],ans); if (now<ans+f[r]) now=ans+f[r]; } // for (i=0;i<n;i++) printf("%d %d %d ",i,num[i],f[i]); printf("%d ",now); output(); return 0; }
【Closing the Farm】同上