2021-team16-C210810

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210810-standings.png,800px)]]



== 概述 ==

solved: 10/12  dirt: 50%

rank: 6



==  ==

== 总结 ==

whn:
整个感觉就是读题+模拟场，每个人读完的题基本都可以自己写。
罚时上天的K题主要是一直没有读到会使用tab分隔，以后遇到类似的题目要注意使用“下载样例”而不是直接复制pdf，
最终决策有些贪，不过也反应代码能力不够。如果我和yja代码能力再强一些的话是有机会AK的


== 题解 ==

A: 模拟。

B: 最少线路覆盖是一个经典问题。跑一边floyd后,建一张两边点数均等于线路数的二分图，枚举每对线路看是否可以同一趟走，如果路线i后可以接着走路线j，就在新图上左半边的第i个点连一条到右半边的第j个点的边，然后在新图上跑一个最大匹配，方案数就是总线路数-匹配大小。

C：简单数位DP

D：由于数据范围很小，枚举每个子串判断是否符合要求即可

E：套公式计算即可，注意形如.09,.12这样的数也是可以用scanf%f直接读入的，不需要复杂化读入。

F：k=1时求树的直径，k>=2的时候所有边必可以到达。

G：读题意+大模拟。

H：根据题意模拟

I：模拟

J：小搜索

K：根据题意模拟，tab的ascii码是9，记住下载样例

L：状压+博弈dp,记dp(i=0/1,mask)表示轮到第i方选择提示词，已经被猜到的词语为mask时获胜的概率, f(i=0/1,mask,j,k)表示轮到第i方猜词，已经被猜到词语集合为mask,使用了线索j，至多还可以猜k次获胜的概率
转移时在f中枚举接下来要猜到的词语，在己方全中时胜率为1，敌方全中或猜到刺客时胜率为0，然后如果是己方特工则调用f(i,newmask,j,k-1),否则需要换边就是1-(i^1,nmask)。转移即可。

[/wiki/2021-team6 返回]

Ranklist

概述

solved: 10/12 dirt: 50%

rank: 6

总结

whn:

整个感觉就是读题+模拟场，每个人读完的题基本都可以自己写。

罚时上天的K题主要是一直没有读到会使用tab分隔，以后遇到类似的题目要注意使用“下载样例”而不是直接复制pdf，

最终决策有些贪，不过也反应代码能力不够。如果我和yja代码能力再强一些的话是有机会AK的

题解

A: 模拟。

B: 最少线路覆盖是一个经典问题。跑一边floyd后,建一张两边点数均等于线路数的二分图，枚举每对线路看是否可以同一趟走，如果路线i后可以接着走路线j，就在新图上左半边的第i个点连一条到右半边的第j个点的边，然后在新图上跑一个最大匹配，方案数就是总线路数-匹配大小。

C：简单数位DP

D：由于数据范围很小，枚举每个子串判断是否符合要求即可

E：套公式计算即可，注意形如.09,.12这样的数也是可以用scanf%f直接读入的，不需要复杂化读入。

F：k=1时求树的直径，k>=2的时候所有边必可以到达。

G：读题意+大模拟。

H：根据题意模拟

I：模拟

J：小搜索

K：根据题意模拟，tab的ascii码是9，记住下载样例

L：状压+博弈dp,记dp(i=0/1,mask)表示轮到第i方选择提示词，已经被猜到的词语为mask时获胜的概率, f(i=0/1,mask,j,k)表示轮到第i方猜词，已经被猜到词语集合为mask,使用了线索j，至多还可以猜k次获胜的概率

转移时在f中枚举接下来要猜到的词语，在己方全中时胜率为1，敌方全中或猜到刺客时胜率为0，然后如果是己方特工则调用f(i,newmask,j,k-1),否则需要换边就是1-(i^1,nmask)。转移即可。