2016-C12-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(2016-08-12 14-59-41屏幕截图.png)]]

'''by shb'''
{{{
感觉yandex好难啊，俄罗斯太强了。
开场feng学长写了比较签到的G和三维几何F。我在旁边推A。可能因为被暴力枚举的题虐了太多，这题我推了一会儿就推出来了。
结果发现过不了样例。仔细看一下题目，发现看错了题目，又推了一会儿就推出来了，交上去竟然1A了，很开心。然后看了一下
E，觉得是个看起来很不可做的数论题。不过反正没题做，随便推推也不亏，写完以后非常开心，交上去WA7了，于是就把电脑给
feng学长写J，我在纸上调试。发现有一个非常SB的错误，还有一些特殊情况没有考虑，等feng学长写完大体的程序开始调试前，
我上去改了一下，交上去竟然A了，开心。前面想了很久J如何减少一些状态，结果竟然还是折半搜索，感觉feng学长太强了。
最后大家一起乱搞了一下B，结果并没什么卵用。。
}}}


== 题解 ==

=== A[shb] ===

给一个点n*m(<=1000)的网格图，求不同pattern数量。一个pattern是一个点三元组，可以沿坐标轴平移或对称变换。

原题要求的即包含向量12、向量23的二元组组数。因为可以对称变换，所以不妨假设向量12在第一象限内，枚举向量12，
当向量12确定后，受网格图大小影响，向量23的x、y方向取值都有上下限，可以O(1)计算。注意特别讨论向量12平行坐标轴
的情况。总复杂度O(nm)

=== B[shb] ===

有一个消牌游戏，有7层牌，第i层有i张牌，叠成金字塔形，每张牌被下层两张牌压住，每步可以选两张不被压住的和为13的牌
消去，或者选一张不被压住的K消去，或从牌堆中选一张牌，弃掉牌堆中这张牌之上的牌，并选择一张不被压住的与这张牌和为
13的牌消去。给定金字塔中牌的排列以及牌堆中牌的排列，问最少剩下几张牌。

每一步可以消的牌很少，事实上状态也很少，只要记下状态，记忆化搜索即可。

=== D[shb] ===
给一个长度为N的序列，实现2个操作：
将一段置为相同值。
询问一个区间是否有数字出现次数超过区间长度的一半。

显然，如果有数字出现次数超过区间长度一半，则必定为中位数。因此可以把操作2看成两个操作：询问区间中位数，询问区间内
某个数字出现次数。
用线段树套主席树即可实现。时间O(nlog^2n),空间O(nlogn)。

=== E[shb] ===

解方程N^x ≡ x(mod M)，以x=ak+b的形式输出所有解。题目保证所有解可以以这个格式输出。

显然N^x在mod M的意义下会循环。找出第一个循环节[L,R],设其长度为p。则对于每一个满足题意的x，必定存在一个i∈[L,R]，使得
x%p = i%p
x%M = N^x % M = N^i % M
枚举i，解这个同余方程组即可。
（L之前的不用考虑，因为特解无法写成ak+b的形式）

=== I[shb] ===
给一个带权图，满足每个点最多在一个环上，求最大带权独立集。

整个图可以看做一棵树，其中树上每个节点是一个点或一个简单环。
对于树上每个节点，先树dp解决子树中节点的问题，再在这个节点内部做环dp。

by shb

感觉yandex好难啊，俄罗斯太强了。
开场feng学长写了比较签到的G和三维几何F。我在旁边推A。可能因为被暴力枚举的题虐了太多，这题我推了一会儿就推出来了。
结果发现过不了样例。仔细看一下题目，发现看错了题目，又推了一会儿就推出来了，交上去竟然1A了，很开心。然后看了一下
E，觉得是个看起来很不可做的数论题。不过反正没题做，随便推推也不亏，写完以后非常开心，交上去WA7了，于是就把电脑给
feng学长写J，我在纸上调试。发现有一个非常SB的错误，还有一些特殊情况没有考虑，等feng学长写完大体的程序开始调试前，
我上去改了一下，交上去竟然A了，开心。前面想了很久J如何减少一些状态，结果竟然还是折半搜索，感觉feng学长太强了。
最后大家一起乱搞了一下B，结果并没什么卵用。。

题解

A[shb]

给一个点n*m(<=1000)的网格图，求不同pattern数量。一个pattern是一个点三元组，可以沿坐标轴平移或对称变换。

原题要求的即包含向量12、向量23的二元组组数。因为可以对称变换，所以不妨假设向量12在第一象限内，枚举向量12，

当向量12确定后，受网格图大小影响，向量23的x、y方向取值都有上下限，可以O(1)计算。注意特别讨论向量12平行坐标轴

的情况。总复杂度O(nm)

B[shb]

有一个消牌游戏，有7层牌，第i层有i张牌，叠成金字塔形，每张牌被下层两张牌压住，每步可以选两张不被压住的和为13的牌

消去，或者选一张不被压住的K消去，或从牌堆中选一张牌，弃掉牌堆中这张牌之上的牌，并选择一张不被压住的与这张牌和为

13的牌消去。给定金字塔中牌的排列以及牌堆中牌的排列，问最少剩下几张牌。

每一步可以消的牌很少，事实上状态也很少，只要记下状态，记忆化搜索即可。

D[shb]

给一个长度为N的序列，实现2个操作：

将一段置为相同值。

询问一个区间是否有数字出现次数超过区间长度的一半。

显然，如果有数字出现次数超过区间长度一半，则必定为中位数。因此可以把操作2看成两个操作：询问区间中位数，询问区间内

某个数字出现次数。

用线段树套主席树即可实现。时间O(nlog^2n),空间O(nlogn)。

E[shb]

解方程N^x ≡ x(mod M)，以x=ak+b的形式输出所有解。题目保证所有解可以以这个格式输出。

显然N^x在mod M的意义下会循环。找出第一个循环节[L,R],设其长度为p。则对于每一个满足题意的x，必定存在一个i∈[L,R]，使得

x%p = i%p

x%M = N^{x % M = N}i % M

枚举i，解这个同余方程组即可。

（L之前的不用考虑，因为特解无法写成ak+b的形式）

I[shb]

给一个带权图，满足每个点最多在一个环上，求最大带权独立集。

整个图可以看做一棵树，其中树上每个节点是一个点或一个简单环。

对于树上每个节点，先树dp解决子树中节点的问题，再在这个节点内部做环dp。

附加文件

• con12.tar.gz by fengsuiyan
• 2016-08-12 14-59-41屏幕截图.png by fengsuiyan