2020-team1-073

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 8/15  dirt: 47%
rank: 37
[[Image(Rank.png,800px)]]
== 总结 ==
三开比赛，毒瘤题目
Grammy又看错题了，但他根据错误题意得出了一个idea并出了一道题（？）
封榜后三人讨论了一会B，不会正解觉得是爆搜题，讨论了一些剪枝后，因为三个人给了不同的剪枝，但是Oscar不想都加进去，于是三人三机写同一道题（草）。最后都没写完B。（悲）
== 题解 ==
A: 如果有2就把2放在根，否则把1放在根；对于剩下的点如果2有偶数个就两个子树平分，然后1尽量平分，如果2有奇数个就把一边多放一个，此时如果没有1则no，否则尽量平分，最后往两边递归
B: 暴力枚举10种字母和10个数字的对应关系，可以得出结果字符串应满足的形式，将所有输入的C串编码后塞进map里查。编码方式如下：
例如给出的串形如ZZFEDZCCFE，其中ZF在输入的AB串中出现过，我们就将这个串编码为ZZFABZCCFA
另一种暴搜过法：结果数字只能位数和两个加数一样或者多一位，且总字符种类数不超过10，将仍然可能的字符串建倒着的trie树。从低位到高位枚举每种字符对应什么数字，计算出结果和进位后再枚举字符；每位结束后在trie树上查一下还有没有可能成为答案。 加上这几个剪枝跑得飞快（全场第2
C: 每次合并两个子节点可以不断进行ans1+ans2的第一个+倒着的ans1+ans2的第二个+...
D: dp。考虑到每个点i只能转移到[i+1,i+8]中的点，我们要求点1一定是必胜态，可以推演出[2,9]的胜负态的情况。于是dp,f[i][mask]表示当前考虑的是[i,i+7]内的点，胜负态为mask时，先手是否必胜。
E: 签到，瞎jb推一下柿子
F: 
G: 按斜线求和可以直接表示成组合数，求三角形和每条斜线的交，注意平行情况（考虑边的两侧）和精度
H: 
I: 
J: 
K: 签到。枚举
L: 考虑会访问到的区间的父亲，一定是和询问区间有交的区间（根节点特殊考虑），用线段树合并统计这些区间的数量。
M: 签到，贪心地放 
N: 
O:

[/wiki/2020-team1 返回]

概述

solved: 8/15 dirt: 47%

rank: 37

总结

三开比赛，毒瘤题目

Grammy又看错题了，但他根据错误题意得出了一个idea并出了一道题（？）

封榜后三人讨论了一会B，不会正解觉得是爆搜题，讨论了一些剪枝后，因为三个人给了不同的剪枝，但是Oscar不想都加进去，于是三人三机写同一道题（草）。最后都没写完B。（悲）

题解

A: 如果有2就把2放在根，否则把1放在根；对于剩下的点如果2有偶数个就两个子树平分，然后1尽量平分，如果2有奇数个就把一边多放一个，此时如果没有1则no，否则尽量平分，最后往两边递归

B: 暴力枚举10种字母和10个数字的对应关系，可以得出结果字符串应满足的形式，将所有输入的C串编码后塞进map里查。编码方式如下：

例如给出的串形如ZZFEDZCCFE，其中ZF在输入的AB串中出现过，我们就将这个串编码为ZZFABZCCFA

另一种暴搜过法：结果数字只能位数和两个加数一样或者多一位，且总字符种类数不超过10，将仍然可能的字符串建倒着的trie树。从低位到高位枚举每种字符对应什么数字，计算出结果和进位后再枚举字符；每位结束后在trie树上查一下还有没有可能成为答案。 加上这几个剪枝跑得飞快（全场第2

C: 每次合并两个子节点可以不断进行ans1+ans2的第一个+倒着的ans1+ans2的第二个+...

D: dp。考虑到每个点i只能转移到[i+1,i+8]中的点，我们要求点1一定是必胜态，可以推演出[2,9]的胜负态的情况。于是dp,f[i][mask]表示当前考虑的是[i,i+7]内的点，胜负态为mask时，先手是否必胜。

E: 签到，瞎jb推一下柿子

F:

G: 按斜线求和可以直接表示成组合数，求三角形和每条斜线的交，注意平行情况（考虑边的两侧）和精度

H:

I:

J:

K: 签到。枚举

L: 考虑会访问到的区间的父亲，一定是和询问区间有交的区间（根节点特殊考虑），用线段树合并统计这些区间的数量。

M: 签到，贪心地放

N:

O:

附加文件