2020-team12-032

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(210305-standing.png, 1000px)]]
[[Image(210305-submission.png, 1000px)]]
[[Image(210305-submission2.png, 1000px)]]
[[Image(210305-submission3.png, 1000px)]]


== 问题 ==

近期打的最为爆炸的一场，全程节奏都不对。 具体表现为szb全程无输出， 写出来的题也多为简单的分类讨论之类，最后有开出的两题卡在wa2...


== 题解 == 

A:待补

B:应该是经典计数，可ctc 到结束还在爆2，待补。

C:读题细节：虽然gen上面写着个rand，但后面还有distinct number保证每个节点数字是不一样的……

字典树上贪心，每个节点记录val,mark和flag(0,1)(表示能否合并，一个节点可被合并当且仅当它的子树只有一种标记）。先进行正常的insert操作（在单词末尾的节点修改val），然后进行dfs，每个父亲节点如果原先没有标记，则可以合并对应可合并儿子sz之和最大的那个儿子，（把对应儿子与父亲直接切断，并在父亲节点补这种标记）；否则就只能合并相同标记的那些。

dfs完之后再计算一遍被断边的树的大小即可。

题目还会有子串和val相同的情况……

D:崩盘签到题，szb的二分check由于写法问题会爆longlong一直挂。。

E:应该是分层图dp，可szb 到结束还在爆2，待补。

F:

G: 打表博弈题，szb糊出了无视0和3直接打表1和2sg函数的做法挂了很久。问题在于0卡片的游戏和12卡片的游戏的sg值需要取异或（相当于两堆石子）才能得到正确sg，而不是12sg>=1,0sg>=1就意味着总和=0.

H: 更难的……分类讨论。 核心是发现曼哈顿距离之下依旧存在的三角关系；在两边之和<第三边以及三边之和为奇数的时候直接为0；三边重合为1；否则两边之和=第三边那么答案是4*(a[0]+a[1]+a[0]*a[1])，任意三角形则是4*(a[0]+a[1]+a[2]).

I: 

J: 相同时间间隔的灯泡只需要保留一个，这样一个个覆盖区间总的区间就不会超过nlnn。扫描线即可。注意加入和删除需要使用multiset，multiset的erase操作要先找到一个元素的指针然后删指针以实现“许多元素单独删除一个”。

K: 分类讨论，但是whn操之过急，想出一两种状态急于上机。核心是n与n+1,n+2必定互质，而n与n+3在n不可被3整除时互质。所以可以分几种情况：①n为奇数，答案=1②n被3除于0，答案=2(n/3-1,n/3,n/3+1)，③n被3除于1或余2，
则分别考虑n/3-1,n/3,n/3+3或n/3-1，n/3+1,n/3+2，如果不可就是4

L: ctc的记忆化搜索套map一度MLE，改成普通递推+map，省下一般的空间即可通过。（奇怪的MLE点....能写成dp就不要记忆化了）

[/wiki/2020-team12 返回]

问题

近期打的最为爆炸的一场，全程节奏都不对。 具体表现为szb全程无输出， 写出来的题也多为简单的分类讨论之类，最后有开出的两题卡在wa2...

题解

A:待补

B:应该是经典计数，可ctc 到结束还在爆2，待补。

C:读题细节：虽然gen上面写着个rand，但后面还有distinct number保证每个节点数字是不一样的……

字典树上贪心，每个节点记录val,mark和flag(0,1)(表示能否合并，一个节点可被合并当且仅当它的子树只有一种标记）。先进行正常的insert操作（在单词末尾的节点修改val），然后进行dfs，每个父亲节点如果原先没有标记，则可以合并对应可合并儿子sz之和最大的那个儿子，（把对应儿子与父亲直接切断，并在父亲节点补这种标记）；否则就只能合并相同标记的那些。

dfs完之后再计算一遍被断边的树的大小即可。

题目还会有子串和val相同的情况……

D:崩盘签到题，szb的二分check由于写法问题会爆longlong一直挂。。

E:应该是分层图dp，可szb 到结束还在爆2，待补。

F:

G: 打表博弈题，szb糊出了无视0和3直接打表1和2sg函数的做法挂了很久。问题在于0卡片的游戏和12卡片的游戏的sg值需要取异或（相当于两堆石子）才能得到正确sg，而不是12sg>=1,0sg>=1就意味着总和=0.

H: 更难的……分类讨论。 核心是发现曼哈顿距离之下依旧存在的三角关系；在两边之和<第三边以及三边之和为奇数的时候直接为0；三边重合为1；否则两边之和=第三边那么答案是4*(a[0]+a[1]+a[0]*a[1])，任意三角形则是4*(a[0]+a[1]+a[2]).

I:

J: 相同时间间隔的灯泡只需要保留一个，这样一个个覆盖区间总的区间就不会超过nlnn。扫描线即可。注意加入和删除需要使用multiset，multiset的erase操作要先找到一个元素的指针然后删指针以实现“许多元素单独删除一个”。

K: 分类讨论，但是whn操之过急，想出一两种状态急于上机。核心是n与n+1,n+2必定互质，而n与n+3在n不可被3整除时互质。所以可以分几种情况：①n为奇数，答案=1②n被3除于0，答案=2(n/3-1,n/3,n/3+1)，③n被3除于1或余2，

则分别考虑n/3-1,n/3,n/3+3或n/3-1，n/3+1,n/3+2，如果不可就是4

L: ctc的记忆化搜索套map一度MLE，改成普通递推+map，省下一般的空间即可通过。（奇怪的MLE点....能写成dp就不要记忆化了）

附加文件