[关闭]
@happyforever 2018-11-05T14:26:41.000000Z 字数 7670 阅读 487

11.5清北学堂"18金秋Problem1"解题报告

清北学堂 解题报告

各题状况

期望得分：
实际得分：

T1

概率，好不想做啊。。
算了随便写个方程想想转移。。。
首先考虑不打假赛是最优策略然后写
。。。（十五分钟后）
我转移写出来了？？？？
真的假的
跑跑试试
它对了？
耶
写个挑几场打假赛然后扔上去吧

T2

哇这个数据范围看着都发憷
分的背包还行

每次随机挑选几个物品看能凑成多少？
跑个次。。。
肯定能骗到分的吧qwq

那那个就删掉吧。。。
一场考试写两个随机算法真的是想日神仙吗

T3

这这这这。。。
不就是随便维护吗
（敲完）
稳了稳了

image.png
image.png

改对之后
image.png

这就很难受了啊。。。。

题目及考场代码

T1

image.png

image.png

  1. /*
  2.  * 如果一直赢下去那么答案就是所有可能然后求出期望
  3.  *
  4.  * dp[i][j]表示前i场赢了j场的概率
  5.  * dp[i][j]=dp[i-1][j]*(1-p[i][j])+dp[i-1][j-1]*p[i][j-1];
  6.  * 同时每次j循环开始前单独更新dp[i][0]=dp[i-1][0]*(1-p[i][0]);
  7.  * 假设不打假赛那这样做就是结果
  8.  *
  9.  * 
  10.  * f[i][j][k]表示前i场比赛赢了j场其中k场买外围
  11.  *
  12.  * 但是这个做法过不了啊。。。。
  13.  * 第一维滚动掉之后就开得下空间了，但是O(n^3)的。。。。
  14.  * 就这边这破机子有点悬
  15.  * 吔
  16.  * 
  17.  *
  18.  * mmp
  19.  * rand大法好
  20.  *
  21.  *
  22.  * 算了算了。。
  23.  * 有T2用rand就够了
  24.  * rp耗不起
  25.  */
  26. #include <cstdio>
  27. #include <cstring>
  29. const int N=1001;
  30. int n;
  31. double ans,p[N][N],dp[N][N];
  32. bool vis[N];
  34. int main()
  35. {
  36.     freopen("game.in","r",stdin);
  37.     freopen("game.out","w",stdout);
  39.     scanf("%d",&n);
  40.     for(int i=1;i<=n;++i)
  41.         for(int j=0;j<i;++j)
  42.             scanf("%lf",&p[i][j]);
  43.     if(n<=2)
  44.     {
  45.         double emp=0;
  46.         emp+=p[1][0]*p[2][1]*2;//两局都赢
  47.         emp+=p[1][0]*(1-p[2][1])*1;//第一局赢，第二局输
  48.         emp+=(1-p[1][0])*p[2][0]*1;//第一局输，第二局赢
  50.         ans=emp;
  51.         //第一局打假赛
  52.         emp=p[2][0]*1;
  53.         if(emp>ans)ans=emp;
  54.         //第二局打假赛
  55.         emp=p[1][0]*1;
  56.         if(emp>ans)ans=emp;
  57.         printf("%.2lf",ans);
  58.     }
  59.     else
  60.     {
  61. //      骗分：假设所有比赛都不买外围是最优情况
  62.         dp[0][0]=1;
  63.         for(int i=1;i<=n;++i)
  64.         {
  65.             dp[i][0]=dp[i-1][0]*(1-p[i][0]);
  66.             for(int j=1;j<=i;++j)
  67.                 dp[i][j]=dp[i-1][j]*(1-p[i][j])+dp[i-1][j-1]*p[i][j-1];
  68.         }
  69.         for(int i=1;i<=n;++i)
  70.             ans+=dp[n][i]*i;
  71.         printf("%.2lf",ans);
  72.     }
  74.     fclose(stdin);fclose(stdout);
  75.     return 0;
  76. }

T2

image.png

image.png

  1. /*
  2.  * 40分的01背包
  3.  * 100分。。。可能是状压？
  4.  * 鬼知道。
  5.  *
  6.  * 我大概可以。。。维护一个大小的数组？
  7.  * dfs枚举所有可能的组合？
  8.  * 2^40次方。。
  9.  * 。。。
  10.  * 想屁吃。。。
  11.  *
  12.  *
  13.  * emmmm
  14.  * 如果dfs可以剪枝掉非常多的情况，就dfs
  15.  * 否则跑5e5次rand，rand出选择的物品
  16.  * 所有rand出的情况取最优
  17.  */
  18. #include <cstdio>
  19. #include <cstdlib>
  20. #include <cstring>
  21. //#include <vector>
  22. #include <algorithm>
  24. const int N=41,M=1e4+1;
  25. int n,x,v[N],dp[M],ans;
  26. bool vis[N];
  27. //std::vector<int> qwq;
  29. void dfs(int now,int w)
  30. {
  31.     if(now>n)
  32.     {
  33.         if(w==x){printf("0");exit(0);}
  34.         if(w>ans)
  35.             ans=w;
  36.         return ;
  37.     }
  38. //  先把所有都选上应该是个不错的选择。。
  39. //  printf("%d %d\n",now,w);
  40.     if(w+v[now]<=x)
  41.         dfs(now+1,w+v[now]);
  42.     dfs(now+1,w);
  43. }
  45. void work()
  46. {
  47.     memset(vis,false,sizeof vis);
  48.     int emp=0;
  49.     for(int s,i=1;i<=n;++i)
  50.     {
  51.         s=rand()%(n+1);
  52.         vis[s]=true;
  53.     }
  54.     for(int i=1;i<=n;++i)
  55.         if(vis[i])
  56.         {
  57.             if(emp+v[i]>x)
  58.                 continue ;
  59.             emp+=v[i];
  60.         }
  61.     if(emp>ans)ans=emp;
  62. }
  63. inline int max(int x,int y)
  64. {return x>y?x:y;}
  66. int main()
  67. {
  68.     freopen("cake.in","r",stdin);
  69.     freopen("cake.out","w",stdout);
  71.     scanf("%d%d",&n,&x);
  72.     for(int i=1;i<=n;++i)
  73.         scanf("%d",&v[i]);
  74. /*
  75.     for(int i=1;i<=100000;++i)
  76.         work();
  77.     printf("%d",x-ans);
  78. */
  79.     if(n<=20)
  80.     {
  81.         for(int i=1;i<=n;++i)
  82.             for(int j=x;j>=v[i];--j)
  83.                 dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
  84.         printf("%d",x-dp[x]);
  85.     }
  86.     else
  87.     {
  88. //      srand(time(0));
  89. //      srand(19260817);
  90.         srand(20010929);
  91.         bool flag=false;
  92.         for(int i=1;i<=n;++i)
  93.         {
  94.             if(ans+v[i]<=x)
  95.                 ans+=v[i];
  96.             else    flag=true;
  97.         }
  98.         if(flag)
  99.         {
  100.             std::sort(v+1,v+1+n);//排序对随机影响不大，但是需要在排序的基础上进行dfs剪枝效果的判断
  101.             if(v[(n>>1)+1]>(x>>1))
  102.                 dfs(1,0);
  103.             else
  104.                 for(int i=1;i<=500000;++i)//极限数据0.7s
  105.                 {
  106.                     if(ans==x){printf("0");goto E;}
  107.                     work();
  108.                 }
  109.         }
  110.         printf("%d",x-ans);
  111.     }
  113. E:  fclose(stdin);fclose(stdout);
  114.     return 0;
  115. }

T3

image.png

image.png

  1. /*
  2.  * 10分输出m^(h*w)
  3.  * 20分手玩
  4.  * 
  5.  *
  6.  * 对于没有被限定的区域，其总方案数是m^(格子数)
  7.  * 考虑每次询问实际是给一块矩形限制了上界，以及在最后时刻这个矩形内必须至少有一个是给定值
  8.  * 考虑有一块矩形的上界都是v
  9.  * 那么该矩形内的方案数为v^(格子数)-(v-1)^(格子数)
  10.  * 把重叠的位置扣去，对每组询问记录其格子数
  11.  *
  12.  *
  13.  * 突然发现调出来之后如果不删输出调试的注释，代码好丑陋啊。
  14.  */
  15. #include <cstdio>
  16. #include <algorithm>
  18. inline int read()
  19. {
  20.     int n=0,w=1;register char c=getchar();
  21.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  22.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  23.     return n*w;
  24. }
  26. const int N=1e4+1,mod=1e9+7;
  27. int h,w,m,n,map[N][N];
  28. struct Node{
  29.     int a,b,x,y,v,sum;
  30.     bool operator<(const Node &gg)const
  31.     {return v<gg.v;}
  32. }q[11];
  34. inline int ksm(long long x,int b)
  35. {
  36.     long long res=1;
  37.     for(;b;b>>=1,x=x*x%mod)
  38.         if(b&1)
  39.             res=res*x%mod;
  40.     return res;
  41. }
  43. int main()
  44. {
  45.     freopen("grid.in","r",stdin);
  46.     freopen("grid.out","w",stdout);
  48.     h=read(),w=read(),m=read(),n=read();
  49.     int sum=h*w;
  50.     for(int i=1;i<=h;++i)
  51.         for(int j=1;j<=w;++j)
  52.             map[i][j]=m+1;
  54.     for(int i=1;i<=n;++i)
  55.     {
  56.         q[i]=(Node){read(),read(),read(),read(),read(),0};
  57.         q[i].sum=(q[i].b-q[i].a+1)*(q[i].y-q[i].x+1);
  58.         //数据保证x>a,y>b
  59.     }
  60. //  puts("GG");
  61. //  离线处理
  62.     std::sort(q+1,q+1+n);
  63.     for(int v,k=1;k<=n;++k)
  64.     {
  65.         v=q[k].v;
  66.         for(int i=q[k].a;i<=q[k].x;++i)
  67.         {
  68.             for(int j=q[k].b;j<=q[k].y;++j)
  69.             {
  70. //              printf("%d ",map[i][j]);
  71.                 if(map[i][j]>v)
  72.                     map[i][j]=v,--sum;
  73.                 else    --q[k].sum;
  74.             }
  75. //          puts("");
  76.         }
  77.     }
  78. //  printf("%d",sum);
  79.     int ans=ksm(m,sum);//没有被限制的区域的方案数
  80.     for(int emp,i=1;i<=n;++i)
  81.     {
  82. //      printf("%d %d %d\n",emp,q[i].v,q[i].sum);
  83.         emp=(ksm(q[i].v,q[i].sum)-ksm(q[i].v-1,q[i].sum)+mod)%mod;
  84.         ans=ans*emp%mod;
  85.     }
  86.     printf("%d",ans);
  88.     fclose(stdin);fclose(stdout);
  89.     return 0;
  90. }

正解及代码

T1

最优策略就是不卖外围不打假赛，每一场都认认真真打
然后就期望最大了。。。
它范围和时限开那么大是误导人用的。。
太毒瘤了这人。

证明：最优策略就是认真打比赛
假设有这样一个状态
image.png
已经赢了场
在状态获胜的概率为状态获胜概率为状态获胜概率为
如果这场比赛获胜了那么会转移到，否则会转移到
考虑如果这场比赛打假赛那么最后期望会增加
如果这场比赛认真打那么会有几种情况：状态赢状态赢，状态赢状态输，状态输状态赢，状态输状态输
分别对应的期望是
不妨假设
那么这场比赛打假赛会增加的期望，这场比赛认真打会增加的期望
化简出来是


证毕

表示前场赢了场的概率

当然需要单独转移：
最后

  1. #include <cstdio>
  2. #include <cstring>
  4. const int N=1001;
  5. int n;
  6. double ans,p[N][N],dp[N][N];
  7. bool vis[N];
  9. int main()
  10. {
  11.     freopen("game.in","r",stdin);
  12.     freopen("game.out","w",stdout);
  14.     scanf("%d",&n);
  15.     for(int i=1;i<=n;++i)
  16.         for(int j=0;j<i;++j)
  17.             scanf("%lf",&p[i][j]);
  18.     dp[0][0]=1;
  19.     for(int i=1;i<=n;++i)
  20.     {
  21.         dp[i][0]=dp[i-1][0]*(1-p[i][0]);
  22.         for(int j=1;j<=i;++j)
  23.             dp[i][j]=dp[i-1][j]*(1-p[i][j])+dp[i-1][j-1]*p
  25. [i][j-1];
  26.     }
  27.     for(int i=1;i<=n;++i)
  28.         ans+=dp[n][i]*i;
  29.     printf("%.2lf",ans);
  31.     fclose(stdin);fclose(stdout);
  32.     return 0;
  33. }

T2

折半搜索
虽然无法接受，但是还是比较稳的
把所有物品分成两堆，第一堆有个，第二堆是剩下的那些
那么对这两堆物品分别求出能够组合出的价值和
考虑Meet in the middle
排序后用两个指针从两侧向中间夹逼找到最接近的和，或者在右边的一堆有一个，在左边的一堆里面找出小于等于的最大值

  1. #include <cstdio>
  2. #include <algorithm>
  4. const int N=1<<20|1,M=1e4+1;
  5. int x,n,up,a[N],v[41],ans;
  7. void dfs1(int now,int w)
  8. {
  9.     if(now>up)
  10.     {
  11.         a[++a[0]]=-w;
  12. //      printf("%d\n",w);
  13.         return ;
  14.     }
  15.     if(w+v[now]<=x)
  16.         dfs1(now+1,w+v[now]);
  17.     dfs1(now+1,w);
  18. }
  20. int emp,tmp;
  21. void dfs2(int now,int w)
  22. {
  23.     if(now>n)
  24.     {
  25. //      printf("%d\n",w);
  26.         emp=w-x;
  27.         if(emp<=a[a[0]])
  28.             w-=a[std::lower_bound(a+1,a+1+a[0],emp)-a];
  29.         if(w>ans)ans=w;
  30.         return ;
  31.     }
  32.     if(w+v[now]<=x)
  33.         dfs2(now+1,w+v[now]);
  34.     dfs2(now+1,w);
  35. }
  37. int main()
  38. {
  39.     freopen("cake.in","r",stdin);
  40.     freopen("cake.out","w",stdout);
  42.     scanf("%d%d",&n,&x);
  43.     up=n>>1;
  44.     for(int i=1;i<=n;++i)
  45.         scanf("%d",&v[i]);
  46.     dfs1(1,0);
  47.     std::sort(a+1,a+1+a[0]);
  48.     dfs2(up+1,0);
  49.     printf("%d",x-ans);
  51.     fclose(stdin);fclose(stdout);
  52.     return 0;
  53. }

T3

对当前的图考虑有个矩形将其覆盖
对于没有被任何矩形覆盖的位置，假设其个数为,那么这部分没有被任何矩形覆盖的位置对答案的贡献为
而对于被矩形覆盖过的位置，其实质是将这些位置的值域限制在了“最大值”
那么离线之后每个位置的值域就会变成所有覆盖到这个位置的矩形的的最小值
考虑每个矩形对答案的贡献：假设矩形大小等于，那么对于这个矩形，假设忽略其“矩形内至少有一个值等于”的限制，那么总共有种构造方法，再减掉其中不合法的（没有任何一个位置的值等于）方案数
另外由于有的矩形会重合，所以需要对某些矩形扣掉一部分
这里给出一种离线方法：
注意到每个位置最后保留的都是覆盖过该位置的最小的矩阵的
首先把所有的操作都读入，读入时记录该操作覆盖的格子数；将所有操作按照从小到大排序，每次操作暴力枚举每个位置进行覆盖；如果枚举到了某个之前有值的位置，那么说明这个位置需要从当前矩阵中扣出，也就是当前矩阵的

考虑无解的情况：某两个矩形是包含关系且被包含的矩形的要大于外面包含它的矩形的
另外这题需要二维离散化。。。。。

下面给出没有二维离散化过的代码（会个点，因为复杂度是的）

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline int read()
  5. {
  6.     int n=0,w=1;register char c=getchar();
  7.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n*w;
  10. }
  12. const int N=1e4+1,mod=1e9+7;
  13. int h,w,m,n,map[N][N];
  14. struct Node{
  15.     int a,b,x,y,v,sum;
  16.     bool operator<(const Node &gg)const
  17.     {return v==gg.v?sum<gg.sum:v<gg.v;}
  18. }q[11];
  20. inline int ksm(long long x,int b)
  21. {
  22.     long long res=1;
  23.     for(;b;b>>=1,x=x*x%mod)
  24.         if(b&1)
  25.             res=res*x%mod;
  26.     return res;
  27. }
  29. int main()
  30. {
  31.     freopen("grid.in","r",stdin);
  32.     freopen("grid.out","w",stdout);
  34.     h=read(),w=read(),m=read(),n=read();
  35.     int sum=h*w;
  37.     for(int i=1;i<=n;++i)
  38.     {
  39.         q[i]=(Node){read(),read(),read(),read(),read(),0};
  40.         q[i].sum=(q[i].x-q[i].a+1)*(q[i].y-q[i].b+1);
  41.     }
  42.     std::sort(q+1,q+1+n);
  43.     for(int v,k=1;k<=n;++k)
  44.     {
  45.         v=q[k].v;
  46.         for(int i=q[k].a;i<=q[k].x;++i)
  47.         {
  48.             for(int j=q[k].b;j<=q[k].y;++j)
  49.             {
  50.                 if(map[i][j]>v || map[i][j]==0)
  51.                     map[i][j]=v,--sum;
  52.                 else    --q[k].sum;
  53.             }
  54.         }
  55.     }
  56.     long long emp,ans=ksm(m,sum);
  57.     for(int i=1;i<=n;++i)
  58.     {
  59.         if(!q[i].sum)continue;
  60.         emp=(ksm(q[i].v,q[i].sum)-ksm(q[i].v-1,q[i].sum)+mod)%mod;
  61.         ans=ans*emp%mod;
  62.     }
  63.     printf("%d",ans);
  65.     fclose(stdin);fclose(stdout);
  66.     return 0;
  67. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注