2017-C09-team8
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
}}}
=== A ===
题意：给定一个w*h网格和内部两个不同整点，要求在边界上选择两个整点，连线不经过给定整点并将网格分为两部分，每一部分有一个给定整点。
取横坐标差为1或纵坐标差为1的两个整点。O(1)。
=== B ===
题意：n个人站成一个环，x个人身边有男生，y个人身边有女生，问是否可能并输出方案。
容易计算出两侧均为男生b，两侧均为女生g和两侧分别是男生女生的人数k。环长为奇数时，x->x+2变换成另一个环，两侧性别不同相当于切换，因此k必须是偶数。bg插入即可。环长为偶数时当成两个环处理，枚举BG的数量。O(n)。
=== C ===
题意：给定n个pair，若A有一维比B高问，则A能打败B。若A能打败B，B能打败C，则A也能打败C。问每个人能打败多少人。
连2n-2条边之后缩点，所得图必定是链。O(nlogn)。
=== D ===
题意：三行LED数字，可以组成合法和式。相邻行有50%重合，给定重合后图形，输出任意一组合法原始数字。
按列做状压DP，和式需要额外维护一个进位或借位。O(w10^6^)。
=== E ===
题意：给定一个udlr组成的字符串和一个01矩阵。玩家按照字符串方向移动，初始为0，经过格子染为1。问是否存在子串能绘制出给定矩阵。
{{{
#!html
用two pointers优化到O(n)次判定。多项式哈希，$\sum{value(x,y)a^{x}b^{y}} \mod m$，abm为随机选定的质数。可以乘上$a^{dx}b^{dy}$快速平移。平移距离可以用目标图像和当前图像中1的最小横纵坐标确定。O(nlogn)。
}}}
=== F ===
题意：将W*H的网格折叠为w*h，至少需要多少次，折叠方向与边界平行。
枚举长宽的两种对应关系，取ceil(log(W/w))之类即可。O(1)。
=== G ===
题意：给定一棵有根树，上面有一些点为黑色，求最少断多少条边能使所有黑点与根分离，同时有多少白点被分离。初始时所有点为白色，询问会改变某个点颜色，对每个询问输出改变后答案。
显然根的每个儿子最多只能使用一条边。对每棵子树按DFS序维护一个set，每次变更后取首尾两个元素做LCA。O(nlogn)。
=== H ===
题意：给定一个整边长矩形，问最少能将其划分为多少个整正方形。
用dp[x][y][cutx][cuty]来表示 一个x*y的矩形左上角被切掉了一个cutx*cuty的矩形之后的图案 最少需要多少被拼出来，以及下一步的转移情况。
转移一共有五种，一种是cutx==cuty==0的时候，可以考虑切掉一个正方形来转移。剩下四种转移分别如下图所示。
[[Image(Summer2017-C09-team8-H-solution-1.png)]]
暴力dp的复杂度是O(60^5^)，可能会TLE。可以考虑打表，但直接打表太大了，压一压应该就好啦~
=== I ===
题意：给定一个整点凸多边形，问有多少条对角线满足其两侧面积均为整数。
{{{
#!html
$S=(1/2)\sum{x_{i}y_{i+1}-y_{i}x_{i+1}}$。若指定对角线一侧点i。面积和式中除对角线外均在边界上连续，可以用前缀和处理。枚举边界上和的奇偶性，和对角线对应乘积的奇偶性即可。O(nlogn)。
}}}
=== J ===
题意：给了一种语法，没有常数，支持宏，模256。要求构造一个表达式使得求值结果至少有1/2概率为指定常数。
{{{
#!html
特判0。用宏和max构造一个宏，使其为255的概率极高，k步可以做到$1-(\frac{255}{256})^{2^k}$，相当于-1。然后用7个宏构造2的幂，组合成答案，指定值为1时概率为$(1-(\frac{255}{256})^{2^k})^{255}$。
}}}
=== K ===
题意：给定n个人的生日和当前时间，求其中年纪最小且慢18岁的人的序号。不考虑闰年。
把yyyymmdd当成整数即可。O(n)。A
题意：给定一个w*h网格和内部两个不同整点，要求在边界上选择两个整点，连线不经过给定整点并将网格分为两部分，每一部分有一个给定整点。
取横坐标差为1或纵坐标差为1的两个整点。O(1)。
B
题意：n个人站成一个环，x个人身边有男生，y个人身边有女生，问是否可能并输出方案。
容易计算出两侧均为男生b，两侧均为女生g和两侧分别是男生女生的人数k。环长为奇数时，x->x+2变换成另一个环，两侧性别不同相当于切换，因此k必须是偶数。bg插入即可。环长为偶数时当成两个环处理，枚举BG的数量。O(n)。
C
题意：给定n个pair，若A有一维比B高问，则A能打败B。若A能打败B，B能打败C，则A也能打败C。问每个人能打败多少人。
连2n-2条边之后缩点，所得图必定是链。O(nlogn)。
D
题意：三行LED数字，可以组成合法和式。相邻行有50%重合，给定重合后图形，输出任意一组合法原始数字。
按列做状压DP，和式需要额外维护一个进位或借位。O(w106)。
E
题意：给定一个udlr组成的字符串和一个01矩阵。玩家按照字符串方向移动，初始为0，经过格子染为1。问是否存在子串能绘制出给定矩阵。
用two pointers优化到O(n)次判定。多项式哈希，$\sum{value(x,y)a^{x}b^{y}} \mod m$，abm为随机选定的质数。可以乘上$a^{dx}b^{dy}$快速平移。平移距离可以用目标图像和当前图像中1的最小横纵坐标确定。O(nlogn)。F
题意：将W*H的网格折叠为w*h，至少需要多少次，折叠方向与边界平行。
枚举长宽的两种对应关系，取ceil(log(W/w))之类即可。O(1)。
G
题意：给定一棵有根树，上面有一些点为黑色，求最少断多少条边能使所有黑点与根分离，同时有多少白点被分离。初始时所有点为白色，询问会改变某个点颜色，对每个询问输出改变后答案。
显然根的每个儿子最多只能使用一条边。对每棵子树按DFS序维护一个set，每次变更后取首尾两个元素做LCA。O(nlogn)。
H
题意：给定一个整边长矩形，问最少能将其划分为多少个整正方形。
用dp[x][y][cutx][cuty]来表示 一个x*y的矩形左上角被切掉了一个cutx*cuty的矩形之后的图案 最少需要多少被拼出来，以及下一步的转移情况。
转移一共有五种，一种是cutx==cuty==0的时候，可以考虑切掉一个正方形来转移。剩下四种转移分别如下图所示。
暴力dp的复杂度是O(605)，可能会TLE。可以考虑打表，但直接打表太大了，压一压应该就好啦~
I
题意：给定一个整点凸多边形，问有多少条对角线满足其两侧面积均为整数。
$S=(1/2)\sum{x_{i}y_{i+1}-y_{i}x_{i+1}}$。若指定对角线一侧点i。面积和式中除对角线外均在边界上连续，可以用前缀和处理。枚举边界上和的奇偶性，和对角线对应乘积的奇偶性即可。O(nlogn)。J
题意：给了一种语法，没有常数，支持宏，模256。要求构造一个表达式使得求值结果至少有1/2概率为指定常数。
特判0。用宏和max构造一个宏，使其为255的概率极高，k步可以做到$1-(\frac{255}{256})^{2^k}$，相当于-1。然后用7个宏构造2的幂，组合成答案，指定值为1时概率为$(1-(\frac{255}{256})^{2^k})^{255}$。K
题意：给定n个人的生日和当前时间，求其中年纪最小且慢18岁的人的序号。不考虑闰年。
把yyyymmdd当成整数即可。O(n)。