[原创]2015年百度之星程序设计大赛 - 初赛(1) 【解题报告】【未完待续】
2017-03-29 20:35:11 Tabris_ 阅读数:1086
博客爬取于2020-06-14 22:41:02
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/68083224
总结一波 : 还是读题不清,中文题关键部分读错,导致最终GG, 计算几何薄弱,模板匮乏。
超级赛亚ACMer 虽然题目说打完一次k–,但是没有限定顺序 所以这个限制可以忽略不计
然后说正常怎么来, 先从小到大排序一遍,然后每一次遇到与其相等的就升级战斗力. 为了确保我下一次还能升级战斗力,我就变成比当前战斗力+k小的最大的那个战斗力就行了, 然后扫一遍即可,
(当时以为遇到相等的不能赢.wa一发…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 # include <bits/stdc++.h> using namespace std; typedef long long int LL; # define lowbit(x) (x&-x) # define abs(x) ((x)>0?(x):-(x)) const int N = 10000+7; LL n,m,k,mx; LL a[N]; LL mylb(LL x){ LL l=1,r=n,mid,ans=0; while(l<=r){ mid = (l+r)>>1; if(a[mid]<=x) l = mid + 1,ans = mid; else r = mid - 1; } return ans ; } int main(){ int _,kcase = 0; scanf("%d",&_); while(_--){ a[0]=0;mx = 0; scanf("%I64d%I64d%I64d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%I64d",&a[i]); if(a[i]<=m){ mx = (mx>a[i])?mx:a[i]; } } m = mx; sort(a+1,a+n+1); // for(int i=1;i<=n;i++) printf("%I64d%c",a[i],(i==n)?'\n':' ' ); int sum = 0; for(int i=1;i<=n;i++){ if(m>=a[i]) sum++; else break; if(a[i]==m&&k) m=a[mylb(m+k)],k--; // printf("%I64d%c",m,(i==n)?'\n':' ' ); } // printf("%d\n",sum); printf("Case #%d:\n",++kcase); if(sum==n) puts("why am I so diao?"); else puts("madan!"); } return 0; }
找连续数 这个题还是很简单的 我们要找一个长度为k的区间使得其中元素升序后连续, 那么也就说明了这个区间是没有重复元素的, 那么确保了区间内没有相同元素的后 其实也就是找这个区间的最大值和最小值的差是不是等于k-1 ,
确定区间有没有相同元素,可以预处理出每个位置的数出现过的在前面的最近位置,
然后计算的时候我们可以枚举右界, 根据预处理相同元素的位置,能够维护左界, 因为元素没有变化,所以最大最小值可以用ST表预处理出来 一次O(n)就能统计了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 # include <bits/stdc++.h> using namespace std; typedef long long int LL; # define lowbit(x) (x&-x) # define abs(x) ((x)>0?(x):-(x)) const int N = 100000+7; LL a[N]; LL mx[N][20],mi[N][20];int mm[N]; int n,m,x; void initrmq(){ mm[0]=-1; for(int i=1;i<=n;i++){ mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; mi[i][0]=mx[i][0]=a[i]; } for(int j=1;j<=mm[n];j++) for(int i=1;i+(1<<j)-1<=n;i++){ mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); } } LL rmqmi(int x,int y){ int k=mm[y-x+1]; return min(mi[x][k],mi[y-(1<<k)+1][k]); } LL rmqmx(int x,int y){ int k=mm[y-x+1]; return max(mx[x][k],mx[y-(1<<k)+1][k]); } map<LL,int>mmp; int pre[N]; int main(){ mmp.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ pre[i]=0; scanf("%I64d",&a[i]); pre[i]=mmp[a[i]]; mmp[a[i]]=i; } initrmq(); puts("Case #1:"); while(m--){ scanf("%d",&x); int sum = 0,l = 0; for(int i=1;i<=n;i++){ l=max(l,pre[i]); if(i-l>=x){ if(rmqmx(i-x+1,i)-rmqmi(i-x+1,i)+1==1ll*x) sum++; } } printf("%d\n",sum); } return 0; }
序列变换 这个题也很水,
如果直接进行求解 很困难,那么反过来想想,如果知道了一个数 来判断可不可行是不是非常好做了呢, 显然是的 , 左边的尽量让他小就行了,
我们考虑如果花费为$x\时能满足题意 , 那么 时能满足题意,那么 时能满足题意 , 那么 \big[x,+\infty\big)\ $都是满足的
所以我们可以二分来做就好了
(最开始把所求看成了c o s t ( A , B ) = ∑ i = 1 n m a x ( ∣ A i − B i ∣ ) 。 cost(A,B)=\sum_{i=1}^nmax(|Ai−Bi|)。 cos t ( A , B ) = ∑ i = 1 n ma x ( ∣ A i − B i ∣ ) 。 mabi
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 # include <bits/stdc++.h> using namespace std; typedef long long int LL; # define lowbit(x) (x&-x) # define abs(x) ((x)>0?(x):-(x)) const int N = 100000+7; int a[N],b[N],n; bool check(int x){ for(int i=1;i<=n;i++) b[i]=a[i]; b[1]-=x; for(int i=2;i<=n;i++){ if(b[i-1]+1<=b[i]+x) b[i]=max(b[i-1]+1,b[i]-x); else return false; } for(int i=2;i<=n;i++) if(b[i-1]>=b[i]) return false; // for(int i=1;i<=n;i++) printf("%d ",b[i]); puts(""); return true; } int main(){ int _,kcase = 0; scanf("%d",&_); while(_--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=0,r=10000000,mid,ans; while(l<=r){ mid = (r+l)>>1; // printf("%d <--\n",mid); if(check(mid)) ans=mid,r=mid-1; else l = mid+1; } printf("Case #%d:\n",++kcase); printf("%d\n",ans); } return 0; }
KPI 这题就是一个模拟,我这里是离线+二分+树状数组 做的时间复杂度是O ( n log 2 2 n ) O(n\log_2^2{n}) O ( n log 2 2 n )
首先离线出来每个数,按照题意的顺序操作,但是每次都是插入到树状数组中,这样我就能用O ( log 2 2 n ) O(\log_2^2{n}) O ( log 2 2 n ) 的复杂度来处理查询操作了,对于其他操作,我先拿一个数组来存每次的操作元素是谁,那么也可以O ( log 2 n ) O(\log_2{n}) O ( log 2 n ) 处理了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 # include <bits/stdc++.h> using namespace std; typedef long long int LL; # define lowbit(x) (x&-x) # define abs(x) ((x)>0?(x):-(x)) const int N = 100000+7; int op[N]; int b[N],c[N],m; int x,n,k; char a[20]; int sum[N]; void update(int i,int v){ for(;i<=m;i+=lowbit(i)) sum[i]+=v; } int getSum(int i){ int ans=0; for(;i;i-=lowbit(i)) ans+=sum[i]; return ans ; } int mylb(int x){ int l=1,r=m,mid,ans; while(l<=r){ mid = (r+l)>>1; if(getSum(mid)>=x) ans=mid,r=mid-1; else l=mid+1; } return ans ; } int mybs(int x){ int l=1,r=m,mid,ans; while(l<=r){ mid = (r+l)>>1; if(b[mid]>=x) ans = mid,r=mid-1; else l=mid+1; } return ans ; } void init(){ memset(sum,0,sizeof(sum)); m=0,k=0; } int main(){ int kcase = 0; while(~scanf("%d",&n)){ init(); for(int i=1;i<=n;i++){ scanf("%s",a); if(a[0]=='i'){ op[i]=1; scanf("%d",&x); b[++m]=x; } else if(a[0]=='q'){ op[i]=2; } else if(a[0]=='o'){ op[i]=(++k)*10+3; } } printf("Case #%d:\n",++kcase); // for(int i=1;i<=n;i++){ // printf("%d <--\n",op[i]); // } for(int i=1;i<=m;i++) c[i]=b[i]; sort(b+1,b+m+1); // m = unique(b+1,b+m+1)-(b+1); int sum = 0,num = 0; for(int i=1;i<=n;i++){ if(op[i]==1){ sum++;num++; update(mybs(c[num]),1); continue; } else if(op[i]==2){ printf("%d\n",b[mylb(sum/2+1)]); continue; } op[i]/=10; update(mybs(c[op[i]]),-1);sum--; } } return 0; }
三阶魔方 不会玩魔方啊 不会做…(这两点可能惯性并不是很大,)
矩形面积 这题很明显的是要对所有的矩形求凸包,然后求最小面积的矩形覆盖,旋转卡壳可过,
旋转卡壳应用很详细的介绍
贴上模板就行了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 # include <map> # include <set> # include <vector> # include <math.h> # include <string> # include <stdio.h> # include <stdlib.h> # include <string.h> # include <iostream> # include <algorithm> # include <functional> using namespace std; const int MAXN=1005; const double eps=1e-10; int dcmp(double x){ if(fabs(x)<eps)return 0; if(x>0)return 1; return -1; } //弄精度 struct Point { double x,y; }p[MAXN]; //搞点 double dot(Point a,Point b,Point c){ double s1=b.x-a.x; double t1=b.y-a.y; double s2=c.x-a.x; double t2=c.y-a.y; return s1*s2+t1*t2; } //点积 int n,res[MAXN],top; bool cmp(Point a,Point b){ if(a.y==b.y)return a.x<b.x; return a.y<b.y; } bool mult(Point sp,Point ep,Point op){ return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y); } void Graham(){ int len; top=1; sort(p,p+n,cmp); if(n==0)return;res[0]=0; if(n==1)return;res[1]=1; if(n==2)return;res[2]=2; for(int i=2;i<n;i++){ while(top&&mult(p[i],p[res[top]],p[res[top-1]]))top--; res[++top]=i; } len=top; res[++top]=n-2; for(int i=n-3;i>=0;i--){ while(top!=len&&mult(p[i],p[res[top]],p[res[top-1]]))top--; res[++top]=i; } } //求凸包 double dist(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double Cross(Point a,Point b,Point c){ return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y); } double ComGeo(){ int R=1,U=1,L; double ans=99999999999999; for(int i=0;i<top;i++){ while(dcmp(fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[(U+1)%top]]))-fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[U]])))>=0) U=(U+1)%top;//最上面一点 while(dcmp(dot(p[res[i]],p[res[(i+1)%top]],p[res[(R+1)%top]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[R]]))>0) R=(R+1)%top;//最右一点 if(i==0)L=R; while(dcmp(dot(p[res[i]],p[res[(i+1)%top]],p[res[(L+1)%top]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[L]]))<=0) L=((L+1)%top)%top;//最左一点 //旋转卡壳精髓所在 double d=dist(p[res[i]],p[res[(i+1)%top]])*dist(p[res[i]],p[res[(i+1)%top]]); double area=fabs(Cross(p[res[i]],p[res[(i+1)%top]],p[res[U]]))*//求面积 fabs(dot(p[res[i]],p[res[(i+1)%top]],p[res[R]])-dot(p[res[i]],p[res[(i+1)%top]],p[res[L]]))/d; if(area<ans) ans = area; } return ans; } //旋转卡壳 int main() { int t; scanf("%d",&t); int k=1; while(t--){ int m; scanf("%d",&m); n=0; double x; for(int i=0;i<m;i++){ for(int j=1;j<=8;j++){ scanf("%lf",&x); if(j&1)p[n].x=x; else p[n++].y=x; } } Graham(); double ans; if(top<3)ans=0; else ans=ComGeo(); long long sum=ans+0.5; //进1法 因为要覆盖上 所以不能四舍五入 printf("Case #%d:\n%I64d\n",k++,sum); } return 0; }