[关闭]
@LittleRewriter 2017-10-08T02:23:04.000000Z 字数 4735 阅读 956

D4讲题

题解 爆零

T1

数据太弱暴力AC.jpg
比如向右看 5 6 7 这样单调递增
而维护这个东西就是只有一段插入，没有删除->单调栈
而查询最近的由于要删掉小的所以就是top减一这个位置。
从右向左：

  1. for(int i=n;i>=1;--i){
  2.     while(r&&s[r]<=h[i]) r--
  3.     b[q[r]]+=a[i];//b[i]为第i个人收到的玫瑰数
  4.     s[++r]=h[i];
  5.     q[r]=i;//整个栈中第r个是i
  6. }

从左向右反过来就行。
复杂度O(n)

标程

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. int n,s[50002],d[50002],ans[50002],ANS,a[50002],b[50002],r,i;
  8. int main()
  9. {
  10.     freopen("treasure.in","r",stdin);
  11.     freopen("treasure.out","w",stdout);
  12.     cin>>n;
  13.     for (i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]);
  14.     s[1]=a[1]; d[1]=1; r=1;
  15.     for (i=2; i<=n; i++)
  16.     {
  17.         while (r!=0 && a[i]>s[r]) { ans[i]+=b[d[r]]; r--; }
  18.         r++;
  19.         s[r]=a[i];
  20.         d[r]=i;
  21.     }
  22.     s[1]=a[n]; d[1]=n; r=1;
  23.     for (i=n-1; i>=1; i--)
  24.     {
  25.         while (r!=0 && a[i]>s[r]) { ans[i]+=b[d[r]]; r--; }
  26.         r++;
  27.         s[r]=a[i];
  28.         d[r]=i;
  29.     }
  30.     for (i=1; i<=n; i++) ANS=max(ANS,ans[i]);
  31.     cout<<ANS;
  32.     return 0;
  33. }

T2

30%

暴搜点

50%

如果是长方形，那么一定是和糖果贴紧的
对于正方形，先离散化，然后枚举上边、下边、左边再枚举右边
最后将长方形变成正方形。

离散化

  1. struct node {int x,y;} t[10005];
  2. int cmp(node i,ndoe j) {i.y<j.y;}
  4. for (i=1; i<=n; i++) cin>>a[i];
  5. for (i=1; i<=n; i++) t[i].x=i,t[i].y=a[i];
  6. sort(t+1,t+n+1,cmp);
  7. for (i=1; i<=n; i++)
  8. {
  9.   if (t[i].y!=t[i-1].y) now++;
  10.   p[now]=a[t[i].x]; a[t[i].x]=now;
  11. }

离散化之后为n*n，直接枚举即可

80%

枚举上边、下边，判断左边是1的情况下右边是什么
由于是个正方形，随着左边的向右移动，右边一定向右移动，直接枚举即可。

100%

假如x可行，那么x+1能覆盖C个糖果，x-1不行。
所以答案是连续的，那么我们可以二分答案。
问题就是check()函数。
枚举上边，下边位置是固定的。那么就能确定哪些糖果被夹在区间中，而左边的移动带来右边的移动，如果用前缀和维护就可以O(n)判断

标程

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. struct node {int x,y;} a[1005];
  8. int C,n,L,R,mid,b[1005],o,i;
  9. int cmp(node i,node j) {return i.x<j.x;}
  10. int CMP(int i,int j) {return i<j;}
  11. bool WORK(int l,int r)
  12. {
  13.      if (r-l+1<C) return false; o=0;
  14.      for (int i=l; i<=r; i++) b[++o]=a[i].y;
  15.      sort(b+1,b+o+1,CMP);
  16.      for (int i=C; i<=o; i++)
  17.        if (b[i]-b[i-C+1]<=mid) return true;
  18.       return false;
  19. }
  20. bool OK(int x)
  21. {
  22.     int l=1;
  23.     for (int i=1; i<=n; i++)
  24.     {
  25.         if (a[i].x-a[l].x>x)
  26.         {
  27.             if (WORK(l,i-1)) return true;
  28.             while (a[i].x-a[l].x>x) l++;
  29.         }
  30.     }
  31.     if (WORK(l,n)) return true;
  32.     return false;
  33. }
  34. int main()
  35. {
  36.     freopen("square.in","r",stdin);
  37.     freopen("square.out","w",stdout);
  38.     scanf("%d%d",&C,&n);
  39.     for (i=1; i<=n; i++)
  40.         scanf("%d%d",&a[i].x,&a[i].y);
  41.     sort(a+1,a+n+1,cmp);
  42.     L=0; R=10000; mid=(L+R)/2;
  43.     while (L<=R)
  44.     {
  45.           if (OK(mid)) {R=mid-1; mid=(L+R)/2;} else
  46.           {
  47.                        L=mid+1;
  48.                        mid=(L+R)/2;
  49.           }
  50.     }
  51.     cout<<L+1;
  52.     return 0;
  53. }

T3

计算几何

40分

手算即可

60分

做出来s-t图。
答案就是最大值减去最小值
2017-10-4 13-37-7.JPG
也就是绿色的东西
观察可知绿色在交点处似乎可以取到最值。怎么证明？我们使用反证法：
假设在某一个不是交点的位置取到了最值，那么我们一定能找到其它点更小。
所以自然而然的，求出所有交点，求出每只豹子的位置，更新答案。

80分

蛤？

100分

后来时刻只有进行追逐的才有意义，否则出发晚并且速度慢的就没意义。
因此只有这些追逐的交点才是有意义的。也就是求图像上界与下界。
2017-10-4 13-36-39.JPG

如图，对于这两条线，在后面的时候斜率大的占领靠上的。
那么按照斜率排序，每插入一条线就会将上界的一段后缀覆盖掉。也就是插入并赋值这个操作是O(1)的。
下界同理，由于我们可以维护出交点和对应的解析式，这个时候搞一个双指针：上追到下就让下移动，下追到上就让上移动。这样就可以O(n)跑完。
用栈维护一开始保证跑的慢的豹子一定先跑，跑的快的一定后跑
也就是：
上凸壳：对于两只豹子，一只跑得慢(v小)且后来才跑(t大)，一只跑得快(v大)且一开始就跑(t小)，我们保留后面那只。
下凸壳：对于两只豹子，一只跑得慢且后来才跑，一只跑得快且一开始就跑，我们保留前面那只。
这样预处理一下。

非常精妙的神奇方法

找见上凸壳与下凸壳，那么要求的东西一定是先变小后变大（上凸壳斜率增加，下凸壳减小）
也就是近似抛物线的一个东西
那么就可以二分
check()函数：
上凸壳斜率小于下面则往右，否则往左
斜率可以定义法求导或者直接维护一下得到。

也可以用神奇的三分做法

标程

  1. //ZHW:这个标程写的很sabi
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<iostream>
  7. #include<algorithm>
  9. using namespace std;
  10. const long double INF=(long double)1000000000*10;
  11. long double L,R,mid,ans,hh[100005];
  12. int r,rr,i,n,MAX,X,Y,cnt,vv[100005],vv2[100005];
  13. struct node2 {int t; long double l;} s[200005],S[200005];
  14. struct node {int t,v;} t[100005];
  15. int cmp(node i,node j) {return i.v<j.v || i.v==j.v && i.t>j.t;}
  16. struct Node {long double x;int y,z;} p[200005];
  17. int CMP(Node i,Node j) {return i.x<j.x;}
  18. long double work(int x,long double y) {return (long double)t[x].v*y-hh[x];}
  19. int main()
  20. {
  21.     freopen("chase.in","r",stdin);
  22.     freopen("chase.out","w",stdout);
  23.     while (1)
  24.     {
  25.         scanf("%d",&n);
  26.        // if (n==0) return 0;
  27.         MAX=0;
  28.         for (i=1; i<=n; i++)
  29.         {
  30.             scanf("%d%d",&t[i].t,&t[i].v);
  31.             MAX=max(MAX,t[i].t);
  32.         }
  33.         sort(t+1,t+n+1,cmp); int MIN=t[n].t;
  34.         for (i=n-1; i>=2; i--)
  35.         {
  36.             if (t[i].t>MIN) vv[i]=1; else
  37.             MIN=t[i].t,vv[i]=0;
  38.         }
  39.         for (i=1; i<=n; i++) hh[i]=(long double)t[i].t*t[i].v;
  40.         r=1; s[1].l=MAX; s[1].t=1; s[2].l=INF; vv[n]=0;
  41.         for (i=2; i<=n; i++)
  42.         if (!vv[i])
  43.         {
  44.             while (r && work(i,s[r].l)>=work(s[r].t,s[r].l)) r--;
  45.             if (!r) {r=1; s[1].l=MAX; s[1].t=i; continue;}
  46.             L=s[r].l; R=s[r+1].l; mid=(L+R)/2.0;
  47.             for (int I=1; I<=80; I++)
  48.             {
  49.                 if (work(i,mid)>=work(s[r].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;}
  50.             }
  51.             s[++r].l=mid; s[r].t=i; s[r+1].l=INF;
  52.         }
  53.         rr=1; S[1].l=MAX; S[2].l=INF; S[1].t=n;
  54.         MIN=t[1].t;
  55.         for (i=2; i<n; i++)
  56.           if (t[i].t<MIN) vv2[i]=1; else
  57.             MIN=t[i].t,vv2[i]=0;
  58.         for (i=n-1; i>=1; i--)
  59.         if (!vv2[i])
  60.         {
  61.             while (rr && work(i,S[rr].l)<=work(S[rr].t,S[rr].l)) rr--;
  62.             if (!rr) {rr=1; S[1].l=MAX; S[1].t=i; continue;}
  63.             L=S[rr].l; R=S[rr+1].l; mid=(L+R)/2.0;
  64.             for (int I=1; I<=80; I++)
  65.             {
  66.                 if (work(i,mid)<=work(S[rr].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;}
  67.             }
  68.             S[++rr].l=mid; S[rr].t=i; S[rr+1].l=INF;
  69.         }
  70.         cnt=0;
  71.         for (i=1; i<=r; i++) {p[++cnt].x=s[i].l; p[cnt].y=1; p[cnt].z=s[i].t;}
  72.         for (i=1; i<=rr; i++) {p[++cnt].x=S[i].l; p[cnt].y=0; p[cnt].z=S[i].t;}
  73.         sort(p+1,p+cnt+1,CMP); X=Y=0; ans=INF;
  74.         for (i=1; i<=cnt; i++)//X为上凸壳指针，y为下凸壳指针
  75.         {
  76.             if (p[i].y==1) X=p[i].z; else Y=p[i].z;
  77.           //  printf("%.5f\n",(double)p[i].x);
  78.             if (X && Y) ans=min(ans,work(X,p[i].x)-work(Y,p[i].x));
  79.         }
  80.         printf("%.2f\n",fabs((double)ans));
  81.         return 0;
  82.     }
  83. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注