2020-team1-044

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 7/12  dirt: 63%

rank: 23

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



== 流水账 ==



== 总结 ==

哭哭，赛后2min过的L

Sakuya:C题确实有点可惜，只是我的代码能力写+调试这道题要一个小时，场上放弃掉也无可厚非。

== 题解 ==

A: 容斥，组合数

B: 枚举底边，假设底边两端点贴着边界，推式子判是否有在外面的部分

C: 贡献矩阵中本质不同元素只有k<O(logn)种，求幂后也只有k种，推一推转移算贡献

D: 奇*奇和奇*偶显然，2*偶和4*偶如下
{{{
()  (())
()  ()()
()  (())
()  ()()
}}}
其余偶*偶如下
{{{
((((((
(()())
()()()
(()())
()()()
))))))
}}}
E: 签到模拟

F: 

G: 牌的两面的数字视作点，每张牌连一条边，发现对于一个联通块，如果边数>点数一定无解，边数=点数就是一棵环套树，这时候这个联通块至多只有两种方案，边数=点数-1就做一个treedp

H: 

I: 广义SAM

J: 单调栈外变小无影响，单调栈外变大在单调栈上二分

单调栈内变大在单调栈上二分，单调栈内变小相当于把序列用单调栈内元素切成若干段，在每一段的单调栈上二分

K: 

L: 建个费用流图S->Ai->Bi->T，所有Ai可以用S到Ai的最短路更新费用，然后Bi从上往下扫，用map维护每一种权值有多少个数，每行做完后删除map中最大数以保持map大小<=Ei。

[/wiki/2020-team1 返回]

概述

solved: 7/12 dirt: 63%

rank: 23

流水账

总结

哭哭，赛后2min过的L

Sakuya:C题确实有点可惜，只是我的代码能力写+调试这道题要一个小时，场上放弃掉也无可厚非。

题解

A: 容斥，组合数

B: 枚举底边，假设底边两端点贴着边界，推式子判是否有在外面的部分

C: 贡献矩阵中本质不同元素只有k

D: 奇*奇和奇*偶显然，2*偶和4*偶如下

()  (())
()  ()()
()  (())
()  ()()

其余偶*偶如下

((((((
(()())
()()()
(()())
()()()
))))))

E: 签到模拟

F:

G: 牌的两面的数字视作点，每张牌连一条边，发现对于一个联通块，如果边数>点数一定无解，边数=点数就是一棵环套树，这时候这个联通块至多只有两种方案，边数=点数-1就做一个treedp

H:

I: 广义SAM

J: 单调栈外变小无影响，单调栈外变大在单调栈上二分

单调栈内变大在单调栈上二分，单调栈内变小相当于把序列用单调栈内元素切成若干段，在每一段的单调栈上二分

K:

L: 建个费用流图S->Ai->Bi->T，所有Ai可以用S到Ai的最短路更新费用，然后Bi从上往下扫，用map维护每一种权值有多少个数，每行做完后删除map中最大数以保持map大小<=Ei。

附加文件