2020-team1-038

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 4/11  dirt: 73%
rank: 74
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
Grammy: 又看错题了，不过出了正解（草）。 数组开小了呜呜呜
Sakuya:以后我可以多做一点容斥的题目，现在的实力还没有到场上做出K的地步。
（K题已补，加了random_shffle之后居然TLE了）
== 题解 ==
A: 
B: trie树上按位根据X这一位的状况搞一下
C: 
D: 
E: 给(u,v)边权加上(1<<(u+60))|(1<<(v+60))后跑线性基
F: 
G: 可以得知删除左边和删除右边的情况相同时当且仅当这个串只由一种字母构成，而且到了这种情况之后就只有单一选择了，所以只要减去在边界上的这种串的贡献即可。
H: 
I: 每次找重心，贪心分成size最接近总size/2的两块询问一边，直到剩一个子树为止；1~2个点要特判
J: 
K: 考虑容斥，若一个限制加入后，并查集没有变，说明当前状态和加入这个限制的状态产生的所有贡献带上容斥系数后是抵消的。 暴力搜，带上这个剪枝。 可能跑不过去要打表，不过打表挺快的。

[/wiki/2020-team1 返回]

概述

solved: 4/11 dirt: 73%

rank: 74

流水账

总结

Grammy: 又看错题了，不过出了正解（草）。 数组开小了呜呜呜

Sakuya:以后我可以多做一点容斥的题目，现在的实力还没有到场上做出K的地步。

（K题已补，加了random_shffle之后居然TLE了）

题解

A:

B: trie树上按位根据X这一位的状况搞一下

C:

D:

E: 给(u,v)边权加上(1<<(u+60))|(1<<(v+60))后跑线性基

F:

G: 可以得知删除左边和删除右边的情况相同时当且仅当这个串只由一种字母构成，而且到了这种情况之后就只有单一选择了，所以只要减去在边界上的这种串的贡献即可。

H:

I: 每次找重心，贪心分成size最接近总size/2的两块询问一边，直到剩一个子树为止；1~2个点要特判

J:

K: 考虑容斥，若一个限制加入后，并查集没有变，说明当前状态和加入这个限制的状态产生的所有贡献带上容斥系数后是抵消的。 暴力搜，带上这个剪枝。 可能跑不过去要打表，不过打表挺快的。

附加文件