[关闭]
@LittleRewriter 2017-10-08T02:21:29.000000Z 字数 3668 阅读 891

D3讲题

未分类

T1

从左往右扫过来，遇到一个')'
观察之前有没有左括号
->有则抵消，无则变左(变X次)
一直持续，扫完之后最终一定匹配后剩下'('
将一半的'('变成')'(变Y次)
所以结果为X+Y/2
标程：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char s[100005];
  4. int i,p,o,ans;
  5. int main()
  6. {
  7.     freopen("bracket.in","r",stdin);
  8.     freopen("bracket.out","w",stdout);
  9.     scanf("%s",s); p=strlen(s);
  10.     for (i=0; i<p; i++)
  11.     {
  12.         if (s[i]==')')
  13.         {
  14.                       if (o==0){o++; ans++;} else
  15.                         o--;
  16.         }
  17.         else
  18.           o++;
  19.     }
  20.     cout<<ans+o/2;
  21.   //  system("pause");
  22.     return 0;
  23. }

T2

前置知识：找尽量多的区间互不相交

做法：按照右端点排序，能取就取，取出最多的互不相交的线段
本题是在这个基础上加了权值。下证该做法是适用的。
16xQx.jpg
如图，紫色是直接取走，绿色是选一选。
显然，在同样的路线下，紫色是优于绿色的，因为这样可以留下更多的地方。
这样直接搞就是60分。

再来分析，我们是要维护一个f数组表示i时刻车上有多少只怪兽

  1. 伪代码：
  2. [x,y]加入Z
  3. for(int i=x;i<y;++i) MAX=max(MAX,f[i]);
  4. t=min(Z,M-MAX);
  5. for (int i=X; i<Y; i++) f[i]+=t;
  6. ans+=t;
  7. cout<<ans;

因此维护的就是区间加入一些数和区间查询最大值
可以用线段树或者树状数组。
标程：

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. int tree[65536][4],n,m,c,i,MIN,ans;
  8. struct node
  9. {
  10.     int x;
  11.     int y;
  12.     int z;
  13. };
  14. node A[100005];
  15. int cmp(node i,node j)
  16. {
  17.     return i.y<j.y;
  18. }
  19. void Update(int k)
  20. {
  21.     tree[k*2][2]+=tree[k][3];
  22.     tree[k*2+1][2]+=tree[k][3];
  23.     tree[k*2][3]+=tree[k][3];
  24.     tree[k*2+1][3]+=tree[k][3];
  25.     tree[k][3]=0;
  26. }
  27. void work(int root,int l,int r,int k)
  28. {
  29.     if (l==tree[root][0] && r==tree[root][1])
  30.     {
  31.         tree[root][2]+=k;
  32.         tree[root][3]+=k;
  33.         return;
  34.     }
  35.     Update(root);
  36.     int mid=(tree[root][0]+tree[root][1])/2;
  37.     if (l<=mid) work(root*2,l,min(mid,r),k);
  38.     if (r>mid) work(root*2+1,max(mid+1,l),r,k);
  39.     tree[root][2]=min(tree[root*2][2],tree[root*2+1][2]);
  40. }
  41. int find(int root,int l,int r)
  42. {
  43.     if (l==tree[root][0] && r==tree[root][1]) return tree[root][2];
  44.     Update(root);
  45.     int mid=(tree[root][0]+tree[root][1])/2,p=453266144,q=453266144;
  46.     if (l<=mid) p=find(root*2,l,min(mid,r));
  47.     if (r>mid) q=find(root*2+1,max(mid+1,l),r);
  48.     return min(p,q);
  49. }
  50. int main()
  51. {
  52.     freopen("bus.in","r",stdin);
  53.     freopen("bus.out","w",stdout);
  54.     scanf("%d%d%d",&n,&m,&c);
  55.     for (i=32768; i<=65535; i++) tree[i][0]=tree[i][1]=i;
  56.     for (i=32767; i>=1; i--)
  57.     {
  58.         tree[i][0]=tree[i*2][0];
  59.         tree[i][1]=tree[i*2+1][1];
  60.     }
  61.     work(1,1+32767,m+32767,c);
  62.     for (i=1; i<=n; i++)
  63.     {
  64.         scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z);
  65.         A[i].y--;
  66.     }
  67.     sort(A+1,A+n+1,cmp);
  68.     for (i=1; i<=n; i++)
  69.     {
  70.         MIN=find(1,A[i].x+32767,A[i].y+32767);
  71.         if (MIN>A[i].z)
  72.         {
  73.             work(1,A[i].x+32767,A[i].y+32767,-A[i].z);
  74.             ans+=A[i].z;
  75.         }
  76.         else
  77.         {
  78.             work(1,A[i].x+32767,A[i].y+32767,-MIN);
  79.             ans+=MIN;
  80.         }
  81.     }
  82.     cout<<ans;
  83.     return 0;
  84. }

不用线段树的做法：

从左往右枚举每一个时刻，扫描一下。一旦满载，赶走最迟下车的怪兽，直到出现不满载。这样相当于我们贪出了最好的选择。
因此这样维护的就是所有怪兽从大到小，用个heap维护就行。复杂度klogM

T3

前置知识：

最大子段和问题

f[i]为以i结尾的最大子段和
f[i]=max(f[i-1]+a[i],a[i])
而ans=max{f[i]}

最大子矩阵问题

枚举一个端点在哪一行，一个端点在另一行()
然后将每一列的和看做点，就是求最大子段和

那么对于本题，由于修改是最小的数，对于
f[i][0]表示以i结尾并且没有数被修改过的最大的和
f[i][1]表示以i结尾并且有数被修改过的最大的和
a[i]为第i列的和
则f[i][0]=max(f[i-1][0]+a[i],a[i])
f[i][1]=max(f[i-1][1]+a[i],f[i-1][0]+a[i]-MIN{i}+P,a[i]-MIN{i}+P)
结果就是MAX{f[i][0/1]}
当然这里还需要特判一下是否会恰好改变一个数
标程：

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <assert.h>//判断输入是否合法
  7. using namespace std;
  8. int n,m,a[305][305],MIN[305],b[305],dp[305][2],i,j,s[305][305],ans,P,k;
  9. int main()
  10. {
  11.     freopen("puzzle.in","r",stdin);
  12.     freopen("puzzle.out","w",stdout);
  13.     while (cin>>n)
  14.     {
  15.         ans=-1000000000;
  16.         scanf("%d%d",&m,&P); assert(1<=n && n<=300 && 1<=m && m<=300 && -1000<=P && P<=1000);
  17.         for (i=1; i<=n; i++)
  18.           for (j=1; j<=m; j++) {scanf("%d",&a[i][j]); assert(-1000<=a[i][j] && a[i][j]<=1000); }
  19.         for (i=1; i<=n; i++)
  20.           for (j=1; j<=m; j++)
  21.             s[i][j]=s[i-1][j]+a[i][j];
  22.         for (i=1; i<=n; i++)
  23.         {
  24.             for (j=1; j<=m; j++) MIN[j]=a[i][j];
  25.             for (j=i; j<=n; j++)
  26.             {
  27.                 for (k=1; k<=m; k++) MIN[k]=min(MIN[k],a[j][k]);
  28.                 for (k=1; k<=m; k++) b[k]=s[j][k]-s[i-1][k]; dp[0][1]=-1000000000;
  29.                 for (k=1; k<=m; k++) dp[k][0]=max(dp[k-1][0]+b[k],b[k]),dp[k][1]=max(max(dp[k-1][1]+b[k],dp[k-1][0]+b[k]-MIN[k]+P),b[k]-MIN[k]+P);
  30.                 for (k=1; k<m; k++) ans=max(ans,max(dp[k][0],dp[k][1]));
  31.                 if (i==1 && j==n)
  32.                 {
  33.                     ans=max(ans,dp[m][1]); int sum=0;
  34.                     for (k=m; k>1; k--) {sum+=b[k]; ans=max(ans,sum);}
  35.                 } else
  36.                   ans=max(ans,max(dp[m][1],dp[m][0]));
  37.             }
  38.         }
  39.         cout<<ans<<endl;
  40.     }
  41.     return 0;
  42. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注