2012 Multi-University Training Contest 1 Solution Report - HDOJ的日志,人人网,HDOJ的公共主页
test(谄笑)
2012 Multi-University Training Contest 1 Solution Report
1001& Clairewd's message
这道题问的就是将1个串如何变为stringA+stringB的形式，使得stringA是stringB经过映射得到相同的串。映射那步其实没有什么价值，假设str为原串s经过映射后得到的串，我们可以以str为模式串，以s为原串做一次扩展KMP，得到extend数组，extend[i]表示原串以第i开始与模式串的前缀的最长匹配。经过O(n)的枚举，我们可以得到,若extend[i]+i=len且i&=extend[i]时，表示stringB即为该点之前的串，stringA即为该点之前的str串，最后输出即可。
1002& Divide Chocolate
给定一个2*n的矩形，求把这个矩形分割为k部分的方法，且对称的切割方法视为不同，输出时模上。
(1&=n&=1000,1&=k&=2*n)
看到这个题目，很容易想到DP。
状态表示 f[i][0][j]:前i行已经出现了j部分且第i行的两个格子属于同一部分的方法数
&&&&&&&& f[i][1][j]:前i行已经出现了j部分且第i行的两个格子属于不同部分的方法数
初始条件 f[1][0][1]=f[1][1][2]=1
状态转移 f[i+1][0][j]=(f[i+1][0][j]+f[i][0][j]+f[i][1][j]*2)%
&&&&&&&& f[i+1][0][j+1]=(f[i+1][0][j+1]+f[i][0][j]+f[i][1][j])%
&&&&&&&& f[i+1][1][j]=(f[i+1][1][j]+f[i][1][j])%
&&&&&&&& f[i+1][1][j+1]=(f[i+1][1][j+1]+f[i][0][j]*2+f[i][1][j]*2)%
&&&&&&&& f[i+1][1][j+2]=(f[i+1][1][j+2]+f[i][0][j]+f[i][1][j])%
共12种不同的状态转移（见下图）
1003& Holedox Eating
每次吃蛋糕的时候，都要找离当前位置最近的蛋糕。可以利用线段树求区间[0, now]已经存在的蛋糕的最大位置，,[now,L]已经存在的蛋糕的最小位置。按照输入顺序模拟就可以了。
1004& Hourai Jeweled
一次dfs就能搞定的问题，其实没什么复杂的算法，主要难点在于统计时的一些小技巧，个人难度评价是偏难的中档题。从任意一点开始深搜，每颗子树搜索完毕之后向上返回pair&可以延伸到该点且最后一条边与由父节点到该点的边颜色不同的gorgeous边的条数 , 所有这种边分数的总和&每次深搜完一个子节点之后，增加的过这一点的gorgeous边的总分数为：&&& 之前深搜的所有子节点向上返回的边数之和 * 当前子节点返回的分数 +&&& 之前深搜的所有子节点向上返回的分数之和 * 当前子节点返回的边数 +&&& 之前深搜的所有子节点向上返回的边数之和 * 当前子节点返回的边数 * 当前点的权 用O(n)的时间把所有的累计起来就好了什么的
才没有呢 = =如果有当前节点分别到两个子节点的边的颜色相同的话也是不行的,由于数据中添加了度数很大的点，理论上O(儿子数^2)的两两统计也是要被卡掉的 （希望确实的做到了正确的做法是对所有的儿子按边的颜色排个序，然后在按这个序深搜和统计
1005& Let's Hit Our Head
这个问题等价于把N因数***，不能有1然后将序列交替组合的方案数算出来就可以了 比如6=2*3我们有[6],[2,3],[3,2]交替组合有A6B6 B6A6A2B6A3 A3B6A2 B2A6B3 B3A6B2A2B2A3B3 A2B3A3B2 A3B3A2B2 A3B2A2B3B2A2B3A3 B2A3B3A2 B3A3B2A2 B3A2B2A3共14种 再比如8=2*2*2=2*4我们有[8],[2,4],[4,2],[2,2,2]交替组合有A8B8 B8A8A2B8A4 A4B8A2 B2A8B4 B4A8B2A2B2A4B4 A2B4A4B2 A4B2A2B4 A4B4A2B2B2A2B4A4 B2A4B4A2 B4A2B2A4 B4A4B2A2A2B2A2B4A2 A2B4A2B2A2 B2A2B2A4B2 B2A4B2A2B2A2B2A2B2A2B2 B2A2B2A2B2A2共20种 1006& Lightning
题目模型：给定平面上N个点。如果两点距离小于等于R，且两点间线段上没有其他点的时候，两点可以建立一条边。得到这个图后，求此图的生成树个数 mod 10007，如果图不连通则输出-1.第一部分：构图。枚举两点是否符合距离限制，如果符合则对比此两点方向向量上是否有距离更小的其他点，然后根据情况建边删边。（O（N*N*log(N)））第二部分：如果图连通，则根据生成树定理，从建好的图中构建M矩阵，高斯消元法求出行列式的值（由于是整数高消，需要提出系数，最后求其逆元）（O（N^3））
1007& Mahjong
这道题目需要用2-sat解决，但要成功转化出模型需要一些巧妙的构造和基础图论知识的证明，最后还要注意一些细节。 首先，题目中的前三段可以直接无视(偶已经很体贴的用图隔开了不是么)。。 要解决这道题目，我们首先可以构造证明，一个状态经过最多三段操作(每段操作指若干次某种操作)之后可以到达任意状态。我们不妨假设操作顺序为A...AB...BA...A（反之类似）。原图中的一个格子坐标为(x0,y0)，要转移到目标的坐标为(x1,y1),则显然最后一段操作之前坐标为(x1,y2).依次类推，它的转移路径应该为：(x0,y0)---&(x0,y2)---&(x1,y2)---&(x1,y1)，则唯一影响路径的是y2。那么这种构造方式能否成功就取决于从(x0,y2)是否能转换到(x1,y2)。换言之，就是我们第一段操作需要使每一列各点所要到达的x1互不相等。再换言之，如果我们以每个点的原始位置集x0到其目标位置集x1构建二分图，则如果能够找到n个不相交的完美匹配就构造成功了。显然每行有n个点，则x集每个点的度都是n；同理y集每个点的度也是n。对于x集的任意子集S，其在y集中的相邻集记作...
阅读(7322)|
1010我一次费用流过的，是数据太弱了吗？
人人移动客户端下载