2017-C03-team3

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(Screenshot from 2017-08-20 02-20-37.png)]]
= 流水账 =
  今天算是第一个组队赛？虽然Johann学长依然没有来。但是一直在群里看题目，然而reku没有带耳机，所以不能语言交流。搞学长的耳机有问题，所以交流起来非常糟糕。

  开场Johann学长在群里随便喊了两声，就兴奋的交了两发1005，喜获2WA。然后发现思路错了，后来讨论了一会才搞出正确贪心。签到题还算顺利，字符串题因为莫名其妙的原因，卡了一会，过得也很莫名其妙。回文题还算顺利。然后令人绝望的开始搞起了二分图。

  大家稍微商量了一下，就开始随机生成起了解，因为贪心写错了，很快就随机了出来，以为很有希望。后来发现贪心错了，改对之后就再也没有随机出解了。

  最后半个小时才开始进行构造，走上正确方向，可惜一切都太晚，智力也不够，打出GG。

= 总结 =

== reku ==
  我和lzw本场的状态感觉都不是太好，lzw身体有些不适，我则是感觉莫名其妙的疲乏，不想看题。Johann学长在群里说1005的时候，我应该问一下的，不该以为是签到题，放开让学长做。不过感觉也是因为没有在现实中打，也不能语音，就不想打字询问。二分图也是，等到lzw都写的差不多了，我才了解了题意和做法。感觉是因为我的节奏没有把控好，才感觉有点糟糕。以后要多多看学长们的做法靠不靠谱，而且以后到了真正的现场组队的时候，一定要多多交流。而且希望在休息的一天里，lzw学长好好调整身体。
== lzw4896s ==
  一开始签到1003想到Ramsey定理后写完暴力直接就交了，没注意看这题的空间限制比寻常要小一些，开了3000*3000的int结果MLE了，需要吸取教训，看题目不仅要看清题意，还要看时间限制空间限制。看到1001决定不断随机生成二分图，利用最小覆盖等于最大匹配求最小覆盖数，直到卡掉贪心算法。但是写随机的时候不够冷静，中间出了各种错误，尤其是在求二分图覆盖集的时候忘记了怎么做，而我偏偏不久以前还是学过求二分图覆盖集的，结果和队友想了半天浪费了好多时间，说明一些经典的模型和套路掌握还是不够熟练，需要及时复习新学的姿势。另外和队友的配合也出了点问题，因为我一直在回忆之前是怎么求二分图覆盖集的，心里太浮躁，有点听不进去队友提供的做法，以后千万不能因为自己有一点想法就一意孤行。 写题时也不够沉着冷静，如果细心一些，把随机算法一遍敲对，就能早些发现这是条死路，早些转向构造这条路的。最后一个多小时3个人一起想构造也许还能多做出一个题。   之后的比赛一定要注意看清题目条件，多和队友交流，加强团队合作。
== Johann ==

= 教训 =

= 题解 =
 * 1001: 一种是二队和五队的构造方法。 还有一种是icpc camp的题解：构造二分图，左边n个点，然后对于每个i(1<=i<=n),在右边新建[n/i]个点，每个点都选择左边的 i 个点连 1 条边，使得左边每个点最多只被多加了一条边。这样构造完成后可以发现贪心的做法会把右边的所有点当做一个覆盖集，实际上只需左边的 n 个点即可。对于题目的要求可以设 n = 80。
 * 1006: 先考虑给出一个序列怎么求答案。 设dp[i][0...1]表示考虑前i位以0(1)结尾的子序列数。 如果第i位是0, dp[i][0] = dp[i - 1][0] + (dp[i - 1][0] + dp[i - 1][1] + 1 - dp[i - 1][0]) = dp[i - 1][0] + dp[i - 1][1] + 1.  dp[i][1] = dp[i - 1][1]. 第i位是1同理。  考虑如何合并s[l...mid] 和 s[mid + 1...r]的答案。  设k < i, 归纳可知dp[i][0] 和 dp[i][1] 均可以表示成 a * dp[k][0] + b * dp[k][1] + c的形式。 对于线段树上的表示区间[l...r]的节点, 只需要维护 如何用dp[l - 1][0], dp[l - 1][1]来表示dp[r][0], dp[r][1]。  对于交换操作, 考虑对称性做些微调即可。
 * 1009: 首先知道相邻的四个相切的圆，存在(k1+k2+k3+k4)2=2(k1^2^+k2^2^+k3^2^+k4^2^)，k为曲率(+-1/r)，符号和内切外切有关。然后知道了前三个圆就可以推出第四个圆。看上去要解一个二元一次方程，但是用韦达定理可以搞出一个线性递推，相邻的三个圆和外面的两个圆存在线性关系。然后就乱推一下就好了。

流水账

今天算是第一个组队赛？虽然Johann学长依然没有来。但是一直在群里看题目，然而reku没有带耳机，所以不能语言交流。搞学长的耳机有问题，所以交流起来非常糟糕。

开场Johann学长在群里随便喊了两声，就兴奋的交了两发1005，喜获2WA。然后发现思路错了，后来讨论了一会才搞出正确贪心。签到题还算顺利，字符串题因为莫名其妙的原因，卡了一会，过得也很莫名其妙。回文题还算顺利。然后令人绝望的开始搞起了二分图。

大家稍微商量了一下，就开始随机生成起了解，因为贪心写错了，很快就随机了出来，以为很有希望。后来发现贪心错了，改对之后就再也没有随机出解了。

最后半个小时才开始进行构造，走上正确方向，可惜一切都太晚，智力也不够，打出GG。

总结

reku

我和lzw本场的状态感觉都不是太好，lzw身体有些不适，我则是感觉莫名其妙的疲乏，不想看题。Johann学长在群里说1005的时候，我应该问一下的，不该以为是签到题，放开让学长做。不过感觉也是因为没有在现实中打，也不能语音，就不想打字询问。二分图也是，等到lzw都写的差不多了，我才了解了题意和做法。感觉是因为我的节奏没有把控好，才感觉有点糟糕。以后要多多看学长们的做法靠不靠谱，而且以后到了真正的现场组队的时候，一定要多多交流。而且希望在休息的一天里，lzw学长好好调整身体。

lzw4896s

一开始签到1003想到Ramsey定理后写完暴力直接就交了，没注意看这题的空间限制比寻常要小一些，开了3000*3000的int结果MLE了，需要吸取教训，看题目不仅要看清题意，还要看时间限制空间限制。看到1001决定不断随机生成二分图，利用最小覆盖等于最大匹配求最小覆盖数，直到卡掉贪心算法。但是写随机的时候不够冷静，中间出了各种错误，尤其是在求二分图覆盖集的时候忘记了怎么做，而我偏偏不久以前还是学过求二分图覆盖集的，结果和队友想了半天浪费了好多时间，说明一些经典的模型和套路掌握还是不够熟练，需要及时复习新学的姿势。另外和队友的配合也出了点问题，因为我一直在回忆之前是怎么求二分图覆盖集的，心里太浮躁，有点听不进去队友提供的做法，以后千万不能因为自己有一点想法就一意孤行。 写题时也不够沉着冷静，如果细心一些，把随机算法一遍敲对，就能早些发现这是条死路，早些转向构造这条路的。最后一个多小时3个人一起想构造也许还能多做出一个题。 之后的比赛一定要注意看清题目条件，多和队友交流，加强团队合作。

Johann

教训

题解

  • 1001: 一种是二队和五队的构造方法。 还有一种是icpc camp的题解：构造二分图，左边n个点，然后对于每个i(1<=i<=n),在右边新建[n/i]个点，每个点都选择左边的 i 个点连 1 条边，使得左边每个点最多只被多加了一条边。这样构造完成后可以发现贪心的做法会把右边的所有点当做一个覆盖集，实际上只需左边的 n 个点即可。对于题目的要求可以设 n = 80。
  • 1006: 先考虑给出一个序列怎么求答案。 设dp[i][0...1]表示考虑前i位以0(1)结尾的子序列数。 如果第i位是0, dp[i][0] = dp[i - 1][0] + (dp[i - 1][0] + dp[i - 1][1] + 1 - dp[i - 1][0]) = dp[i - 1][0] + dp[i - 1][1] + 1. dp[i][1] = dp[i - 1][1]. 第i位是1同理。 考虑如何合并s[l...mid] 和 s[mid + 1...r]的答案。 设k < i, 归纳可知dp[i][0] 和 dp[i][1] 均可以表示成 a * dp[k][0] + b * dp[k][1] + c的形式。 对于线段树上的表示区间[l...r]的节点, 只需要维护 如何用dp[l - 1][0], dp[l - 1][1]来表示dp[r][0], dp[r][1]。 对于交换操作, 考虑对称性做些微调即可。
  • 1009: 首先知道相邻的四个相切的圆，存在(k1+k2+k3+k4)2=2(k12+k22+k32+k42)，k为曲率(+-1/r)，符号和内切外切有关。然后知道了前三个圆就可以推出第四个圆。看上去要解一个二元一次方程，但是用韦达定理可以搞出一个线性递推，相邻的三个圆和外面的两个圆存在线性关系。然后就乱推一下就好了。
附加文件