2021-team06-C211017

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(211017-standing.png,800px)]]

== submission ==

[[Image(211017-submission3.png,800px)]]
[[Image(211017-submission2.png,800px)]]
[[Image(211017-submission1.png,800px)]]


== 概述 ==

solved: 4/10  dirt: 74.07%

rank: 10




== 总结 ==

lxy背锅场，因为下午就是面试于是状态挺糟糕的……
E题糊了一个正方形假做法，yja实现了快两个小时以后发现实际上是个应该五分钟出的DP……，J题写了很久，还一直在WA4……，于是赛后过两题
看来以后队员遇到这种大事还是不必训练了0.0


== 题解 ==

A: 签到

B: 待补

C: 打表找规律发现，在模998244353意义下任何的卷积卷998244353次会得到(1,0,0...0)，再卷一次就变回原形，因此直接将输入的函数卷k对mo的乘法逆元次即可。

D：转移较复杂的树形DP，设f[u][0]表示希望从节点u进然后出来所需要最晚出发时间，f[u][1]表示只希望从节点v进来然后出来所需要的最晚出发时间。
首先发现由于遍历一棵子树的时间是2*sz[u],最优的遍历子树顺序是按照(f[v][0]+2*sz[u])从小到大排序遍历。
因此对于每个节点，dfs完儿子以后将儿子排序，然后f[u][0] = min(a[u]+min(0,k-2sz[u]),最小的f[v][0]-1-(走完前面儿子所用的时间)); 在维护一个suf(i)表示儿子后缀i要得以全部走进走出的最晚时间、dp(i)表示儿子前缀i要得以全部走进走出的最晚时间，则f[u][1]需要保证能成功的走完儿子前缀、走完儿子后缀，回到u,在到达最优的儿子v
;因此f[u][1]为最大的min(a[u]+min(0,k-2(sz[u]-sz[v])),dp(i-1), suf(i+1)-(走完前面儿子所用的时间）,f[v][1]-(走完两边儿子的时间）)

E: 待yja写题解

F：随机即可，最优的方式不是靠军棋知识在重要的棋子里面ran，而是每次随机交换一堆棋子。

G：模拟，yja由于重载小于号时对相等的情况返回了1于是导致std::sort不稳定挂了奇怪的地方...

H：直接统计间隔四个数以内的所有商统计出来，选出现次数的10个dp求最长子序列即可。

I：待补

J: 待补

K: 待补

L：待补

M：签到，单独把每个i^0^,i^1^,...的集合拉出来，发现这样的集合都不大，2^size^一个均摊复杂度是对的。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 4/10 dirt: 74.07%

rank: 10

总结

lxy背锅场，因为下午就是面试于是状态挺糟糕的……

E题糊了一个正方形假做法，yja实现了快两个小时以后发现实际上是个应该五分钟出的DP……，J题写了很久，还一直在WA4……，于是赛后过两题

看来以后队员遇到这种大事还是不必训练了0.0

题解

A: 签到

B: 待补

C: 打表找规律发现，在模998244353意义下任何的卷积卷998244353次会得到(1,0,0...0)，再卷一次就变回原形，因此直接将输入的函数卷k对mo的乘法逆元次即可。

D：转移较复杂的树形DP，设f[u][0]表示希望从节点u进然后出来所需要最晚出发时间，f[u][1]表示只希望从节点v进来然后出来所需要的最晚出发时间。

首先发现由于遍历一棵子树的时间是2*sz[u],最优的遍历子树顺序是按照(f[v][0]+2*sz[u])从小到大排序遍历。

因此对于每个节点，dfs完儿子以后将儿子排序，然后f[u][0] = min(a[u]+min(0,k-2sz[u]),最小的f[v][0]-1-(走完前面儿子所用的时间)); 在维护一个suf(i)表示儿子后缀i要得以全部走进走出的最晚时间、dp(i)表示儿子前缀i要得以全部走进走出的最晚时间，则f[u][1]需要保证能成功的走完儿子前缀、走完儿子后缀，回到u,在到达最优的儿子v

;因此f[u][1]为最大的min(a[u]+min(0,k-2(sz[u]-sz[v])),dp(i-1), suf(i+1)-(走完前面儿子所用的时间）,f[v][1]-(走完两边儿子的时间）)

E: 待yja写题解

F：随机即可，最优的方式不是靠军棋知识在重要的棋子里面ran，而是每次随机交换一堆棋子。

G：模拟，yja由于重载小于号时对相等的情况返回了1于是导致std::sort不稳定挂了奇怪的地方...

H：直接统计间隔四个数以内的所有商统计出来，选出现次数的10个dp求最长子序列即可。

I：待补

J: 待补

K: 待补

L：待补

M：签到，单独把每个i0,i1,...的集合拉出来，发现这样的集合都不大，2size一个均摊复杂度是对的。

附加文件