2020-team2-030

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: 9/13

 rank: 10

= 流水账 =

队长不在，pb去看病了，前期cxt单打，后来pb找了个网吧云参赛，'''但是我们在力所能及的范围内保证了只有一台机子写代码'''。

比赛前期，cxt单人18min签到A，M，然后在签到B的时候，看到表达式求值，一个激动想用python的eval函数，结果惨遭'''宇宙射线攻击'''——本地和评测机python解释器行为不同。

一番debug无果，只好重新用c++再写一遍。'''B2(122)'''

比赛中期，pb到达网吧，并且开始安装dev。安装过程中，pb秒掉了H，C，K，并且把F丢给了cxt。

于是之后的一段时间中，cxt写了H，F，pb又写了C，K。其中最后一个通过的是'''K2(246)'''

比赛后期，cxt不会做E，于是把E丢给pb，自己去做I。最后两人分别过题。

于是9题。

= 总结 =

=== pb： ===
中途加入比赛，把前面看见的签到题写了写，然后就快结束了。E前期对题意没有看清，也没看出结论，就一直不会，后来队友丢个结论就会了，所以还是有点菜。

=== Creatix： ===
其实这场谈不太上什么配合，因为队伍并没有齐。

这个B让人好不爽。为什么python不让我过呢？

没什么经验，要说的话就是tarjan应该整理一套不错的板子，以后就不用现场推了。

upd：补了G。orz rng58

=== yyc： ===
~~并没有参加比赛所以没有总结~~

= 题解 =

 * A：没有思维难度

 * B：以后别随便手贱用python。。。

 * C：f[i][j]为第i行第j个位置经过的球的个数，f[i][j]=floor(f[i-1][j-1]/2)+ceil(f[i-1][j]/2)，令f[1][1]=k-1,k分别做一次，找到f[n][i]不一样的，i就是答案

 * D：

 * E：f[i][j]代表i到j能否全部消除，g[i][j][k]代表i到j能否全部消成k这个颜色最多剩下多少个，-1代表不可能只剩下k，两种转移，记忆化搜索即可

 * F：基环树贪心。先每棵树贪心在处理环。思维难度较小。

 * G：树哈希+环哈希。树哈希参见rng58的博客，环哈希则找出最小表示（记得两个方向都要找）然后字符串hash。要双模。

 * H：队友怎么说你就怎么写就行了（捂脸）

      第一个限制是树，然后做最大生成树满足第二个限制，考虑统计答案的方式可知最小生成树是第三种限制。

 * I：你需要黏合三个板子：点双，边双，圆方树。注意割点个数不等于圆方树方点个数-1。

 * J：

 * K：数位DP，第二种需要二分，两种都需要dp出f[i][mask][lim]代表还剩下i位，现在拿到的数是mask，是否达到上限，注意到不达到上限时，f[i][mask][0]=A(base-__builtin_popcount(mask),i)，所以这部分可以优化

 * L：

 * M：没有思维难度

[/wiki/2020-team2 返回]

概述

solved: 9/13

rank: 10

流水账

队长不在，pb去看病了，前期cxt单打，后来pb找了个网吧云参赛，但是我们在力所能及的范围内保证了只有一台机子写代码。

比赛前期，cxt单人18min签到A，M，然后在签到B的时候，看到表达式求值，一个激动想用python的eval函数，结果惨遭宇宙射线攻击——本地和评测机python解释器行为不同。

一番debug无果，只好重新用c++再写一遍。B2(122)

比赛中期，pb到达网吧，并且开始安装dev。安装过程中，pb秒掉了H，C，K，并且把F丢给了cxt。

于是之后的一段时间中，cxt写了H，F，pb又写了C，K。其中最后一个通过的是K2(246)

比赛后期，cxt不会做E，于是把E丢给pb，自己去做I。最后两人分别过题。

于是9题。

总结

pb：

中途加入比赛，把前面看见的签到题写了写，然后就快结束了。E前期对题意没有看清，也没看出结论，就一直不会，后来队友丢个结论就会了，所以还是有点菜。

Creatix：

其实这场谈不太上什么配合，因为队伍并没有齐。

这个B让人好不爽。为什么python不让我过呢？

没什么经验，要说的话就是tarjan应该整理一套不错的板子，以后就不用现场推了。

upd：补了G。orz rng58

yyc：

并没有参加比赛所以没有总结

题解

  • A：没有思维难度
  • B：以后别随便手贱用python。。。
  • C：f[i][j]为第i行第j个位置经过的球的个数，f[i][j]=floor(f[i-1][j-1]/2)+ceil(f[i-1][j]/2)，令f[1][1]=k-1,k分别做一次，找到f[n][i]不一样的，i就是答案
  • D：
  • E：f[i][j]代表i到j能否全部消除，g[i][j][k]代表i到j能否全部消成k这个颜色最多剩下多少个，-1代表不可能只剩下k，两种转移，记忆化搜索即可
  • F：基环树贪心。先每棵树贪心在处理环。思维难度较小。
  • G：树哈希+环哈希。树哈希参见rng58的博客，环哈希则找出最小表示（记得两个方向都要找）然后字符串hash。要双模。
  • H：队友怎么说你就怎么写就行了（捂脸）

第一个限制是树，然后做最大生成树满足第二个限制，考虑统计答案的方式可知最小生成树是第三种限制。

  • I：你需要黏合三个板子：点双，边双，圆方树。注意割点个数不等于圆方树方点个数-1。
  • J：
  • K：数位DP，第二种需要二分，两种都需要dp出f[i][mask][lim]代表还剩下i位，现在拿到的数是mask，是否达到上限，注意到不达到上限时，f[i][mask][0]=A(base-__builtin_popcount(mask),i)，所以这部分可以优化
  • L：
  • M：没有思维难度
附加文件