[关闭]
@happyforever 2018-10-30T14:13:19.000000Z 字数 8113 阅读 458

10.25上午解题报告

清北学堂 解题报告

各题情况

期望得分：
实际得分：

T1

写个暴力，又想了个贪心
然后近一个小时想证明而不是换个贪心思路。。。
然后就跪了
日

T2

我TM。。。暴力和特殊性质写挂了
还不如去写暴力（由于的贪心没证明，的std::sort也不会证明，就在暴力和暴力之间艰难抉择了一发。。。然后就TM少了分（我确信能分因为我考完之后又用了就写完了））

T3

没时间了，没写完

考场代码及思路

T1

图片.png

  1. /*
  2.  * 对每一时刻，标记有多少猫会在此时吃完一条鱼
  3.  * 但是空间开不下。。。而且O(x)铁定挂
  4.  *
  5.  * 一只猫能在x的时间内吃完的鱼是x/a[i]条
  6.  * 如果x%a[i]!=0那么吃不完的数量+1
  7.  * 另外考虑有的猫在开始吃一条吃不完的鱼的时候可能剩下的鱼不够了
  8.  * 
  9.  * 把所有猫的吃鱼时间按照从大到小排序
  10.  * 时间越长的越早考虑
  11.  * 对每只猫，考虑其在要求时间内能吃完几条鱼
  12.  *
  13.  * 把所有毛的吃鱼时间按照从小到大排序
  14.  * 对每只猫，考虑在给定时间内能吃完几条鱼，以及是否会有吃到一半的情况
  15.  * 考虑如果后面有猫没得吃并且前面的猫有没吃完的情况，就把这条鱼给后面的猫吃。。
  16.  */
  17. #include <cstdio>
  18. #include <algorithm>
  20. inline int read()
  21. {
  22.     int n=0,w=1;register char c=getchar();
  23.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  24.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  25.     return n*w;
  26. }
  27. const int N=100001;
  28. int n,m,x,a[N],time[N];
  30. inline void work()
  31. {
  32.     int last=n;m-=n;
  33.     for(int i=1;i<=n;++i)
  34.         time[i]=a[i];
  35.     for(int i=1;i<=x;++i)
  36.     {
  37.         for(int j=1;j<=n;++j)
  38.             if(time[j])
  39.             {
  40.                 --time[j];
  41.                 if(!time[j])
  42.                 {
  43.                     --last;
  44.                     if(m)
  45.                         time[j]=a[j],--m,++last;
  46.                 }
  47.             }
  48. //      printf("%d %d\n",m,last);
  49.     }
  50.     printf("%d %d",m,last);
  51. }
  52. inline int ab(int x)
  53. {return x>0?x:0;}
  55. int main()
  56. {
  57.     freopen("fish.in","r",stdin);
  58.     freopen("fish.out","w",stdout);
  60.     m=read(),n=read(),x=read();
  61.     for(int i=1;i<=n;++i)
  62.         a[i]=read();
  63.     if(x<=1000)
  64.         work();
  65.     else
  66.     {
  67.         std::sort(a+1,a+1+n);
  68. /*
  69. //check是否时间充足
  70.         int emp=m;
  71.         for(int i=n;i;--i)
  72.             emp-=x/a[i];
  73.         if(emp<0){printf("0 0");goto E;}*/
  74. //check
  75.         int emp=0,total=0,last=0,tmp=0,left=0;
  76.         for(;a[n]>x;--n)++tmp;
  77.         for(int i=1;i<=n;++i)
  78.         {
  79.             bool flag=false;
  80.             if(emp<m)
  81.             {
  82.                 total+=x/a[i];//这只猫在给定时间内能吃完的数量
  83.                 emp+=x/a[i];
  84.                 flag=true;
  85.             }
  86.             if(x%a[i] && emp<m)
  87.             {
  88.                 ++last;
  89.                 ++emp;
  90.             }
  91.             if(!flag && emp>=m)
  92.                 left+=x/a[i];
  93.         }
  94.         printf("%d %d",ab(m-emp),ab(last-left+tmp));
  95.     }
  97. E:  fclose(stdin),fclose(stdout);
  98.     return 0;
  99. }

T2

图片.png

  1. /*
  2.  */
  3. #include <cstdio>
  4. #include <algorithm>
  6. inline int read()
  7. {
  8.     int n=0,w=1;register char c=getchar();
  9.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  10.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  11.     return n*w;
  12. }
  13. const int N=1001,M=5001;
  14. int n,m,dp[M];
  15. struct Node{
  16.     int p,q,v;
  17.     bool operator<(const Node &gg)const
  18.     {return q-p<gg.q-gg.p;}
  19. }things[N];
  20. bool vis[N];
  22. void dfs(int now,int left,int V)
  23. {
  24.     if(now>n)
  25.     {
  26.         if(V>dp[m])dp[m]=V;
  27.         return ;
  28.     }
  29.     for(int i=1;i<=n;++i)
  30.         if(!vis[i])
  31.         {
  32.             vis[i]=true;
  33.             if(left>=things[i].q)
  34.                 dfs(now+1,left-things[i].p,V+things[i].v);
  35.             dfs(now+1,left,V);
  36.             vis[i]=false;
  37.         }
  38. }
  39. /*
  40. void dfs(int now,int left,int V)
  41. {
  42.     if(now>n)
  43.     {
  44.         if(V>dp[m])dp[m]=V;
  45.         return ;
  46.     }
  47.     if(left>=things[now].q)
  48.         dfs(now+1,left-things[now].p,V+things[now].v);
  49.     dfs(now+1,left,V);
  50. }
  51. */
  52. inline int max(int x,int y)
  53. {return x>y?x:y;}
  54. int main()
  55. {
  56.     freopen("bag.in","r",stdin);
  57.     freopen("bag.out","w",stdout);
  59.     n=read(),m=read();
  60.     bool flag1=false,flag2=false;
  61.     for(int i=1;i<=n;++i)
  62.     {
  63.         things[i]=(Node){read(),read(),read()};
  64. //      printf("%d %d %d\n",p[i],q[i],v[i]);
  65.         if(things[i].p!=things[i].q)flag1=true;
  66.         if(things[i].v!=1)flag2=true;
  67.     }
  68.     std::sort(things+1,things+1+n);
  69.     if(n<=12)
  70.         dfs(1,m,0);
  71.     else
  72.     {
  73.         if(!flag1)
  74.             for(int i=1;i<=n;++i)
  75.                 for(int j=m;j>=things[i].q;--j)
  76.                     dp[j]=max(dp[j],dp[j-things[i].p]+things[i].v);
  77.         else
  78.             if(!flag2)
  79.             {
  80.                 ;//不会。。。
  81.             }
  82.             else
  83.                 for(int i=1;i<=n;++i)
  84.                     for(int j=m;j>=max(things[i].p,things[i].q);--j)
  85.                         dp[j]=max(dp[j],dp[j-things[i].p]+things[i].v);
  86.     }
  88. //  dfs(1,m,0);
  89.     printf("%d",dp[m]);
  91.     fclose(stdin),fclose(stdout);
  92.     return 0;
  93. }

T3

图片.png

  1. /*
  2.  * 考虑对走过的边染色。。。
  3.  * 然后从左上角、右下角、右上角、左下角分别开始洪水法dfs
  4.  * 最后删掉被淹的就是答案???
  5.  *
  6.  * 考虑对所有点求。。。求矩阵面积？
  7.  */
  8. #include <cstdio>
  9. #include <algorithm>
  11. inline int read()
  12. {
  13.     int n=0,w=1;register char c=getchar();
  14.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  15.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  16.     return n*w;
  17. }
  19. const int N=5001;
  20. int k,map[N][N];
  21. struct Node{
  22.     int x,y;
  23.     bool operator<(const Node &gg)const
  24.     {return x==gg.x?y<gg.y:x<gg.x;}
  25. }point[N];
  27. int main()
  28. {
  29.     freopen("beng.in","r",stdin);
  30.     freopen("beng.out","w",stdout);
  31. /*
  32.     k=read();char c;int tot=0,loc,x=2001,y=2001;
  33.     while(k--)
  34.     {
  35.         while(c!='R' && c!='D' && c!='U' && c!='L')
  36.             c=getchar();
  37.         loc=read();
  38. //      switch(c)
  39. //      {
  40. //          case 'R':while(loc--)map[x][++y]=1;break;
  41. //          case 'L':while(loc--)map[x][--y]=1;break;
  42. //          case 'U':while(loc--)map[--x][y]=1;break;
  43. //          case 'D':while(loc--)map[++x][y]=1;
  44. //      }
  45.         switch(c)
  46.         {
  47.             case 'R':y+=loc;;break;
  48.             case 'L':y-=loc;break;
  49.             case 'U':x-=loc;break;
  50.             case 'D':x+=loc;
  51.         }
  52.         point[++tot]=(Node){x,y};
  53.     }
  54.     std::(point+1,point+1+tot);
  55.     tot-=4;
  56.     for(int i=1;i<=tot;++i)
  57.         ans+=(point[i].x-point[i+1].x)*(point[i].y-poing[i+1].y);
  58. */
  59.     printf("2195569");
  61.     fclose(stdin),fclose(stdout);
  62.     return 0;
  63. }

正解及思路

T1

枚举每一条鱼，找最小时刻的猫
开一个小根堆，第一个元素是吃完这条鱼的时间，第二个元素记录吃这条鱼的猫吃一条鱼用的时间
总复杂度

  1. /*
  2.  */
  3. #include <cstdio>
  4. #include <queue>
  6. inline int read()
  7. {
  8.     int n=0,w=1;register char c=getchar();
  9.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  10.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  11.     return n*w;
  12. }
  13. #define mp std::make_pair
  14. #define pr std::pair<int,int>
  15. const int N=100001;
  16. int n,m,x;
  17. std::priority_queue<pr,std::vector<pr>,std::greater<pr> > q;
  18. pr emp;
  20. int main()
  21. {
  22.     freopen("fish.in","r",stdin);
  23.     freopen("fish.out","w",stdout);
  25.     m=read(),n=read(),x=read();
  26.     m-=n;
  27.     for(int qwq,i=1;i<=n;++i)
  28.     {
  29.         qwq=read();
  30.         q.push(mp(qwq,qwq));
  31.     }
  32.     for(int i=1;i<x && m;++i)
  33.         while(!q.empty())
  34.         {
  35.             emp=q.top();
  36.             if(emp.first > i)
  37.             {
  38.                 i=emp.first-1;
  39.                 break;
  40.             }
  41.             q.pop();
  42.             q.push(mp(emp.second+i,emp.second));
  43.             --m;
  44.             if(!m)break;
  45.         }
  46.     int ans=0;
  47.     while(!q.empty())
  48.     {
  49.         if(q.top().first>x)
  50.             ++ans;
  51.         q.pop();
  52.     }
  53.     printf("%d %d",m,ans);
  55.     fclose(stdin),fclose(stdout);
  56.     return 0;
  57. }

T2

可以观察到这题与背包的区别只是多了个限制，购买一件物品时如果手中的钱数少于那么不能购买这件物品
考虑到普通背包问题取物品是从前往后决策，而本题某件物品可能编号靠后、最优方案选择它和它前面的某物但是先选了前面的物品则无论如何选不上这个物品

对于第一个数据：可以先求全排列，再枚举选不选。
对于第二个数据：枚举购买顺序。
对于第三个数据：枚举每个物品买或不买，判断这种方案是否可行，贪心判断。也可以写状压 。。
对于第四个数据：裸的背包。
对于第五个数据：装箱
对于的数据：
事实上。。。
先按从小到大排序
然后跑背包就好了。。。
证明的话。。。类比“国王游戏”邻项扰动

证明：
由于越大，越放到后面考虑时可选取的可能性越低，所以越大的理应越靠前
由于越小，越放到前面考虑时可选取的可能性越高，所以越小的理应越靠前
所以显然物品的排列顺序是需要与这两者有关的
（考场上遇到这种情况可以直接为关键字排序都试一遍，或者在代码里面都跑一遍取最优值）

如果最优的答案的取的顺序是
那dp时的顺序一定是。所以接下来是任务就是确定某个排序，使答案最大。
此时是只和与有关的。
由特殊到一般，先假设有个，就是.所以要做的就是找最优的顺序，使一开始的钱越少越好。


设

是最优的。
所以，应按从大到小排序。
证毕

  1. /*
  2.  */
  3. #include <cstdio>
  4. #include <algorithm>
  6. inline int read()
  7. {
  8.     int n=0,w=1;register char c=getchar();
  9.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  10.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  11.     return n*w;
  12. }
  13. const int N=1001,M=5001;
  14. int n,m,dp[M];
  15. struct Node{
  16.     int p,q,v;
  17.     bool operator<(const Node &gg)const
  18.     {return q-p<gg.q-gg.p;}
  19. }things[N];
  20. inline int max(int x,int y)
  21. {return x>y?x:y;}
  22. int main()
  23. {
  24.     freopen("bag.in","r",stdin);
  25.     freopen("bag.out","w",stdout);
  27.     n=read(),m=read();
  28.     for(int i=1;i<=n;++i)
  29.         things[i]=(Node){read(),read(),read()};
  30.     std::sort(things+1,things+1+n);
  31.     for(int i=1;i<=n;++i)
  32.         for(int j=m;j>=max(things[i].p,things[i].q);--j)
  33.             dp[j]=max(dp[j],dp[j-things[i].p]+things[i].v);
  35. //  dfs(1,m,0);
  36.     printf("%d",dp[m]);
  38.     fclose(stdin),fclose(stdout);
  39.     return 0;
  40. }

T3

考虑有这样一张图
图片.png
把走过的路径染色
从左上角、右下角、左下角、右上角分别进行灌水，遇到染过色的就停止
有分是给灌水的
有分是给灌水的
而满分。。。
二维离散化灌水

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  5. inline int read()
  6. {
  7.     int n=0,w=1;register char c=getchar();
  8.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  9.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  10.     return n*w;
  11. }
  12. const int N=3001;
  13. int n,px[N],py[N],x[N],y[N],Tx,Ty;
  14. char a[N][N];
  15. int nowx,nowy,sx[10000005],sy[10000005],L,R;
  16. const int F1[4]={0,0,1,-1};
  17. const int F2[4]={1,-1,0,0};
  19. inline bool judge(int x,int y)
  20. {return x>=1 && x<=Tx && y>=1 && y<=Ty;}
  22. void bfs(int x,int y)
  23. {
  24.     if(!(1<=x&&x<=Tx&&1<=y&&y<=Ty))return;
  25.     a[x][y]=1; sx[1]=x; sy[1]=y; L=1; R=1;
  26.     while(L<=R)
  27.     {
  28.         nowx=sx[L]; nowy=sy[L]; ++L;
  29.         for(int xx,yy,i=0;i<4;++i)
  30.         {
  31.             xx=nowx+F1[i],yy=nowy+F2[i];
  32.             if(!a[xx][yy] && judge(xx,yy))
  33.             {
  34.                 ++R;
  35.                 a[xx][yy]=1;
  36.                 sx[R]=xx;sy[R]=yy;
  37.             }
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     freopen("beng.in","r",stdin);
  44.     freopen("beng.out","w",stdout);
  46.     n=read();char c;
  47.     for(int cx=0,cy=0,i=0;i<=n;++i)
  48.     {
  49.         for(int j=-1;j<2;++j)
  50.             x[++Tx]=cx+j,y[++Ty]=cy+j;
  51.         px[i]=cx,py[i]=cy;
  52.         if(i==n)break;
  53.         while(c!='R' && c!='L' && c!='U' && c!='D')
  54.             c=getchar();
  55.         int l=read();
  56.         switch(c)
  57.         {
  58.             case 'R':cy+=l;break;
  59.             case 'L':cy-=l;break;
  60.             case 'U':cx-=l;break;
  61.             case 'D':cx+=l;
  62.         }
  63.     }
  65.     std::sort(x+1,x+1+Tx);Tx=std::unique(x+1,x+1+Tx)-x-1;
  66.     std::sort(y+1,y+1+Ty);Ty=std::unique(y+1,y+1+Ty)-y-1;
  67.     for(int i=0;i<=n;++i)
  68.         px[i]=std::lower_bound(x+1,x+1+Tx,px[i])-x,
  69.         py[i]=std::lower_bound(y+1,y+1+Ty,py[i])-y;
  70.     for(int i=1;i<=n;++i)
  71.     {
  72.         int sx=px[i-1],tx=px[i],sy=py[i-1],ty=py[i];
  73.         if(sx>tx)std::swap(sx,tx);
  74.         if(sy>ty)std::swap(sy,ty);
  75.         for(int j=sx;j<=tx;++j)
  76.             for(int k=sy;k<=ty;++k)
  77.                 a[j][k]=2;
  78.     }
  80.     bfs(1,1);
  81.     long long ans=0;
  82.     for(int i=2;i<=Tx;++i)
  83.         for(int j=2;j<=Ty;++j)
  84.             if(a[i][j]!=1)
  85.                 ans+=1ll*(x[i]-x[i-1])*(y[j]-y[j-1]);
  86.     printf("%d",ans);
  88.     fclose(stdin);fclose(stdout);
  89.     return 0;
  90. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注