2021-team06-C211016

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

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

== submission ==

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


== 概述 ==

solved: 7/13  dirt: 74.07%

rank: 19



==  ==

== 总结 ==

状态一般的一场，罚时多得飞起，可能也和题目有关系。。
M题whn思路很对的情况下无限WA靠yja救起，
H题一度WA后面的点
最令人印象深刻的是G题因为一个小于号在相等的时候return 1导致std爆了引发的大量罚时...


== 题解 ==

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: 7/13 dirt: 74.07%

rank: 19

总结

状态一般的一场，罚时多得飞起，可能也和题目有关系。。

M题whn思路很对的情况下无限WA靠yja救起，

H题一度WA后面的点

最令人印象深刻的是G题因为一个小于号在相等的时候return 1导致std爆了引发的大量罚时...

题解

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一个均摊复杂度是对的。

附加文件