2020-team1-034

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 6/10  dirt: 40%

rank: 26

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



== 流水账 ==


中间因为以为G是区间修改，Oscar让Grammy写了个四叉树，写完才发现是单点修改，然后四叉树他T了。于是Grammy又写了个树套树。


== 总结 ==

《卡题》

树套树里外面那棵树好像不太能下传标记。

Grammy：感觉晚上训的场我都不知道在干什么？

Sakuya: 我要开始喷B题了，场上的人过的飞快的原因是他们全用暴力，我还辛辛苦苦地想了个比他们快100倍地做法。（暴力居然能过）

== 题解 ==

A: 签到

B: 记a为黄金分割数，a^n^ + (-1/a)^n^ 为整数且为卢卡斯数列中的数，所以可以按卢卡斯数列从高往低取来写出a^k^和a^-k^位上的数（每一位上的数只能取1，0，-1）

   （其中2到-2这些位置上的数要特殊处理），然后再从低位到高位把-1向高位推进直到只有0和1，最后把相邻的1往前推即可

C: 背包

D: 双指针扫一遍，把分出的每一段拿出来三分

E: 

F: 

G: 树套树

H: 

I: 哈希

J:

[/wiki/2020-team1 返回]

概述

solved: 6/10 dirt: 40%

rank: 26

流水账

中间因为以为G是区间修改，Oscar让Grammy写了个四叉树，写完才发现是单点修改，然后四叉树他T了。于是Grammy又写了个树套树。

总结

《卡题》

树套树里外面那棵树好像不太能下传标记。

Grammy：感觉晚上训的场我都不知道在干什么？

Sakuya: 我要开始喷B题了，场上的人过的飞快的原因是他们全用暴力，我还辛辛苦苦地想了个比他们快100倍地做法。（暴力居然能过）

题解

A: 签到

B: 记a为黄金分割数，an + (-1/a)n 为整数且为卢卡斯数列中的数，所以可以按卢卡斯数列从高往低取来写出ak和a-k位上的数（每一位上的数只能取1，0，-1）

（其中2到-2这些位置上的数要特殊处理），然后再从低位到高位把-1向高位推进直到只有0和1，最后把相邻的1往前推即可

C: 背包

D: 双指针扫一遍，把分出的每一段拿出来三分

E:

F:

G: 树套树

H:

I: 哈希

J:

附加文件