2021-team3-001

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team3 返回]

== Ranklist ==




== 概述 ==

solved: 8/12  dirt: ??

rank: 8



==  ==

== 总结 ==

szb:

这场是读题场，第一场训练因为题意理解问题和交流上的问题导致大半场无所事事，正常基本没能够做出贡献，在写了一个题之后另外三个题都是队友重构（其中一个题是数据错误，另外两题是题意理解细节出了问题）

hjq:

~~这里是总结~~

wd:

~~这里是总结~~

== 题解 ==

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-team3 返回]

Ranklist

概述

solved: 8/12 dirt: ??

rank: 8

总结

szb:

这场是读题场，第一场训练因为题意理解问题和交流上的问题导致大半场无所事事，正常基本没能够做出贡献，在写了一个题之后另外三个题都是队友重构（其中一个题是数据错误，另外两题是题意理解细节出了问题）

hjq:

这里是总结

wd:

这里是总结

题解

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)。转移即可。