2017-Sp66-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：XVIII Opencup Grand Prix of Gomel
 * Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7380/standings/
== 流水账 ==
开场各自看题，yzc看了A，和sub讲了讲，得到了一个naive的结论，上机'''A1y7'''。看到fdu和sjtu先过了B，就一起看B，上机打表，没看到有什么规律，无奈之下花了一些时间分析，造了个二分的算法，最后'''B1y88'''。接下来sub和yzc研究了一下G，yzc上机开始写斜率优化，cjb和sub开始研究F。之后sub给出了一个F的构造，上机'''F1y138'''。yzc之后写好了G，提交获得wa。yzc打印检查，cjb上机敲K的板子部分，sub之后补全，最后'''K1y200'''。yzc上机对拍G，之后wa了一发后终于'''G3y243'''。期间cjb和sub研究D和E，都没得到很好的做法，最后三个人试图做D失败，5题到了最后。thu有一个9题一个6题，pku 6题，fdu和sjtu也是5题，罚时优于我们排在前面。
== 总结 ==
=== chenjb ===
今天一切正常....出不动第6个题啊.....菜菜菜，就练练练啊！
[[BR]][[BR]]楼下yzcsb!
=== oipotato ===
cjbsb!
=== subconscious  ===
我tm射爆。
== 题解 ==
 * C：
   * 题意：构造n个点的三点不共线的简单多边形，使得有恰好k条对角线完全落在多边形内，n<=100。
   * 题解：先构造出甜筒型的最小值n-3，通过把t个点翻出可得到t*(t-3)/2条对角线，最后一个点选取恰当的值不劝剩余的部分即可，注意边界。
 * D：
   * 题意：具体见题面。
   * 题解：存在i支配时，该i支配唯一。f(n,i)代表n个猴子存在i支配的概率，有f(n,i)=f(n-1,i)*p^k^+f(n-1,i-1)*(1-p)^n-k^,又f(n,i)=f(n-1,i)*(1-p)^i^+f(n-1,i-1)*p^n-i^，联立可得f(n,k)->f(n,k+1)的递推式。特别地，a/b=1/2时，可得f(n,i)=C(n,i)*1/2^i*(n-i)^。
 [[BR]] [[BR]]* [https://wiki-nightfall.icpc-camp.org/Day5 Solution by Nightfall]
== 补题 ==
 * ~~C~~ by sub
 * ~~D~~ by yzc
 * E
 * H
 * I
 * J

  • 题目来源：XVIII Opencup Grand Prix of Gomel
  • Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7380/standings/

流水账

开场各自看题，yzc看了A，和sub讲了讲，得到了一个naive的结论，上机A1y7。看到fdu和sjtu先过了B，就一起看B，上机打表，没看到有什么规律，无奈之下花了一些时间分析，造了个二分的算法，最后B1y88。接下来sub和yzc研究了一下G，yzc上机开始写斜率优化，cjb和sub开始研究F。之后sub给出了一个F的构造，上机F1y138。yzc之后写好了G，提交获得wa。yzc打印检查，cjb上机敲K的板子部分，sub之后补全，最后K1y200。yzc上机对拍G，之后wa了一发后终于G3y243。期间cjb和sub研究D和E，都没得到很好的做法，最后三个人试图做D失败，5题到了最后。thu有一个9题一个6题，pku 6题，fdu和sjtu也是5题，罚时优于我们排在前面。

总结

chenjb

今天一切正常....出不动第6个题啊.....菜菜菜，就练练练啊！



楼下yzcsb!

oipotato

cjbsb!

subconscious

我tm射爆。

题解

  • C：
    • 题意：构造n个点的三点不共线的简单多边形，使得有恰好k条对角线完全落在多边形内，n<=100。
    • 题解：先构造出甜筒型的最小值n-3，通过把t个点翻出可得到t*(t-3)/2条对角线，最后一个点选取恰当的值不劝剩余的部分即可，注意边界。
  • D：
    • 题意：具体见题面。
    • 题解：存在i支配时，该i支配唯一。f(n,i)代表n个猴子存在i支配的概率，有f(n,i)=f(n-1,i)*pk+f(n-1,i-1)*(1-p)n-k,又f(n,i)=f(n-1,i)*(1-p)i+f(n-1,i-1)*pn-i，联立可得f(n,k)->f(n,k+1)的递推式。特别地，a/b=1/2时，可得f(n,i)=C(n,i)*1/2i*(n-i)。



* Solution by Nightfall

补题

  • C by sub
  • D by yzc
  • E
  • H
  • I
  • J
附加文件