随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Asia Hefei Online 2008 解题报告


A. Constellations

PKU 3690 http://poj.org/problem?id=3690

题意:给定N*M(N<=1000, M <= 1000)01矩阵S,再给定T(T <= 100)P*Q(P <= 50, Q <= 50)01矩阵,问P*Q的矩阵中有多少个是S的子矩阵。

题解:位压缩 + KMP

由于P <= 50,所以我们可以把所有P*Q的矩阵进行二进制位压缩,将P*Q的矩阵的每一列压缩成一个64位整数,这样P*Q的矩阵就变成了一个长度为Q的整数序列,用同样的方式对N*M的矩阵进行压缩,总共可以产生(N-P+1)个长度为M的整数序列,剩下的就是进行最多(N-P+1)KMP匹配了。

       KMP相关算法可以参阅:

http://www.cppblog.com/menjitianya/archive/2014/06/20/207354.html


1 ‘*’代表二进制的1, ’0’代表二进制的0

 

B. DNA repair

       PKU 3691 http://poj.org/problem?id=3691

       题意:给定N(N <= 50)个长度不超过20的模式串,再给定一个长度为M(M <= 1000)的目标串S,求在目标串S上最少改变多少字符,可以使得它不包含任何的模式串(所有串只有ACGT四种字符)。

       题解:AC自动机 + 动态规划

利用模式串建立trie图,trie图的每个结点(即下文讲到的状态j)维护三个结构,

Node{

              Node *next[4];   // 能够到达的四个状态 的结点指针

              int  id;         // 状态ID,用于到数组下标的映射

              int  val;        // 当前状态是否是一个非法状态 (以某些模式串结尾)

}

 

DP[i][j]表示长度为i (i <= 1000),状态为j(j <= 50*20 + 1)的字符串变成目标串S需要改变的最少字符,设初始状态j = 0,那么DP[0][0] = 0,其他均为无穷大。从长度ii+1进行状态转移,每次转移枚举共四个字符(ACGT),如果枚举到的字符和S对应位置相同则改变值T=1,否则T=0;那么有状态转移方程 DP[i][j] = Min{ DP[i-1][ fromstate ] + T, fromstate为所有能够到达j的状态 };最后DP[n][j]中的最小值就是答案。

 

C. Kindergarten

       PKU 3692 http://poj.org/problem?id=3692

       题意:给定G(G <= 200)个女孩和B(B <= 200)个男孩,以及M(0 <= M <= G*B)条记录(x, y)表示x号女孩和y号男孩互相认识。并且所有的女孩互相认识,所有的男孩互相认识,求找到最大的一个集合使得所有人都认识。

题解:二分图最大匹配

一个点集中所有人都认识表示这个点集是个完全图,该问题就是求原图的一个最大团(最大完全子图),可以转化为求补图的最大独立集,而补图恰好是个二分图。二分图的最大独立集 = 总点数 - 二分图的最大匹配。于是问题就转化成了求补图的最大匹配了。

 

D. Maximum repetition substring

PKU 3693 http://poj.org/problem?id=3693

题意:给定长度为N(N <= 105)的字符串S,求它的一个最多重复子串(注意:最多重复子串不等于最长重复子串,即abababaaaa应该取后者)

题解:后缀数组 + RMQ

枚举重复子串的长度L,如果对于某个i,有S[i*L ... N]S[(i+1)*L ... N]的最长公共前缀大于等于L(这一步可以利用后缀数组求解height数组,然后通过RMQ查询区间最小值来完成),那么以i*L为首,长度为L的子串至少会重复两次。


2

如图,L=3i=3的情况,S[3...10]S[6...10]的最长公共前缀为3,即S[3...5]S[6...8]完全匹配,所以S[3...5]重复了两次。反之,如果最长公共前缀小于L,必定不会重复(因为两个子串之间出现了断层)。

推广到更一般的情况,如果S[i*L ... N]S[(i+1)*L ... N]的最长公共前缀为T,那么以S[i*L]为首的重复子串的重复次数为T / L + 1,而且我们可以发现如果以S[i*L]为首,长度为L的子串的重复次数大于等于2,那么它一定不会比以S[(i+1)*L]为首的子串的重复次数少,这个是显然的,比如L2的时候,ababab一定比abab多重复一次,基于这个性质,我们定义一个new_flag标记,表示是否需要计算接下来匹配到的串(ababababab的情况,前者计算过了,就把new_flag置为false,就不会计算abab的情况了),得出完整算法:

1) 枚举重复子串的长度L,初始化new_flag标记为true

2) 枚举i,计算S[i*L ... N]S[(i+1)*L ... N]的最长公共前缀T

a) 如果T < Lnew_flag标记为true

b) 如果T >= L,判断new_flag是不是为false,如果为false,说明以S[i*L]为首的串和S[(i-1)*L]为首的串的最长公共前缀大于等于T,跳转到2);否则转3)

3) 因为S[i*L, (i+1)*L]有重复子串,但是字典序不一定最小,所以还需要枚举区间 [i-L+1, i+L],看是否存在字典序更小的子串,比较字典序这一步可以直接使用后缀数组计算出来的rank值进行比较。

       RMQ相关算法可以参阅:

       http://www.cppblog.com/menjitianya/archive/2014/06/26/207420.html

 

E. Network

       PKU 3694 http://poj.org/problem?id=3694

题意:给定N(N <= 105)个点和M(N-1 <= M <= 2*105)条边的无向连通图,进行Q(Q <= 1000)次加边,每次加入一条边要求输出当前图中有多少条割边。

       题解:无向图割边、最近公共祖先

利用tarjan求出原图的割边,由于这题数据量比较大,所以用递归可能会爆栈,需要栈模拟实现递归过程,tarjan计算的时候用parent[u]保存u的父结点,每个结点进出栈各一次,出栈时表示以它为根结点的子树访问完毕,然后判断(u, parent[u])是否为割边。每次询问u, v加入后会有多少割边,其实就是求uv的到它们的最近公共祖先lca(u, v)的路径上有多少割边,由于在进行tarjan计算的时候保存了每个结点的最早访问时间dfn[u],那么有这么一个性质:dfn[ parent[u] ] < dfn[u],这是显然的(父结点的访问先于子结点)。于是当dfn[u] < dfn[v],将parent[v]赋值给v,反之,将parent[u]赋值给u,因为是一棵树,所以进过反复迭代,一定可以出现u == v 的情况,这时候的u就是原先uv的最近公共祖先,在迭代的时候判断路径上是否存在割边,路径上的割边经过(u, v)这条边的加入都将成为非割边,用一个变量保存割边数目,输出即可。


3

       如图3,图中实线表示树边,虚线表示原图中的边,但是进行tarjan计算的时候7这个结点被(6, 7)这条边“捷足先登”了,于是(4, 7)成为了一条冗余边,计算完后这个图的割边为(1, 2)(1,3)(3, 4)(3, 5),分别标记bridge[2]bridge[3]bridge[4]bridge[5]true

当插入一条边(7, 5),那么沿着7的祖先路径和5的祖先路径最后找到的最近公共祖先为3(路径为7 -> 6 -> 4 -> 3 5 -> 3)(3, 4)(3, 5)这两条割边因为加入了(7, 5)这条边而变成了普通边,将标记bridge[4]bridge[5]置为false

 

F. Rectangles

       PKU 3695 http://poj.org/problem?id=3695

       题意:给定N(N <= 20)个矩形,以及M(M <= 105)次询问,询问R(R <= N)个矩形的并。

       题解:离散化 + 暴力( 容斥原理 )

       离散化:由于矩形很少,所以可以将它们的XY坐标分别离散到整点,两个维度分别离散,点的总数不会超过2N,对于本次询问,利用前一次询问的结果进行面积的增减,对每个矩形进行判断,一共有两种情况:

1)这个矩形前一次询问出现,本次询问不出现,对它的所有离散块进行自减操作,如果某个离散块计数减为0,则总面积减去这个离散块的面积;

2)这个矩形前一次询问没出现,本次询问出现,对它的所有离散块进行自增操作,如果某个离散块计数累加后为1,则总面积加上这个离散块的面积;

       容斥原理:对于每个询问,利用dfs枚举每个矩形取或不取,取出来的所有矩形作相交操作,所有[奇数个矩形交]的面积和所有[偶数个矩形交]的面积和 就是答案,因为是dfs枚举,所以在枚举到某次相交矩形面积为0的时候就不需要再枚举下去了,算是一个比较强的剪枝。

       如图4,红色区域为被覆盖了一次的区域,橙色区域为被覆盖了两次的区域,黄色区域为被覆盖了三次的区域,那么先将所有的三个矩形加起来,然后需要减掉重叠的部分,重叠的减掉后发现,重叠的部分多减了,即图中黄色的部分被多减了一次,需要加回来。所以容斥原理可以概括为:奇数加,偶数减。


4

      

G. The Luckiest number

PKU 3696 http://poj.org/problem?id=3696

题意:给定L(L <= 2*109),求一个最小的数T,满足T仅由数字’8’组成,并且TL的倍数。

题解:欧拉定理

首先,长度为N的仅由8组成的数字可以表示为8*(10N-1)/9

如果它能被L整除,则可以列出等式(1)

8*(10N-1)/9 = KL     (其中K为任意正整数)  (1)

将等式稍作变形得到等式(2)

(10N-1) = 9KL/8                            (2)

由于存在分母,所以我们需要先对分数部分进行约分,得到等式(3)

A = L/GCD(8, L),  B = 8/GCD(8, L)

(10N-1) = 9K*A / B                          (3)

因为AB已经互质,所以如果B不为1,为了保证等式右边仍为整数,K必须能被B整除,而K为任意整数,所以一定能够找到一个K正好是B的倍数,所以可以在等式两边同时模9A,得到(10N-1) mod (9A) = 0,稍作变形,得到等式(4):

                         (4)       

于是需要引入一个定理,即欧拉定理。

欧拉定理的描述为:若n, a为正整数,且n, a互质,则:


5

(ψ(n)表示n的欧拉函数,即小于等于n并且和n互素的数的个数)

这样一来,我们发现只要109A互质,只需要求9A的欧拉函数,但是求出来的欧拉函数是不是一定使得N最小呢,并不是,所以还需要枚举欧拉函数的因子,如果它的某个因子T也满足(4)的等式,那么T肯定不会比ψ(9A)大,所以T一定更优。

这里9A有可能超过32位整数,所以计算过程中遇到的乘法操作不能直接相乘(两个超过32位整数的数相乘会超过64位整数),需要用到二分乘法,即利用二进制加法模拟乘法,思想很简单,就直接给出一段代码吧。

 

 1 #define LL __int64
 2  
 3 //计算 a*b % mod
 4 LL Produc_Mod(LL a, LL b, LL mod) {
 5        LL sum = 0;
 6        while(b) {
 7               if(b & 1) sum = (sum + a) % mod;
 8               a = (a + a) % mod;
 9               b >>= 1;
10        }
11        return sum;
12 }
13  
14  
15 //计算a^b % mod
16 LL Power(LL a, LL b, LL mod) {
17        LL sum = 1;
18        while(b) {
19               if(b & 1) sum = Produc_Mod(sum, a, mod);
20               a = Produc_Mod(a, a, mod);
21               b >>= 1;
22        }
23        return sum;
24 }

 

H. USTC campus network

PKU 3697 http://poj.org/problem?id=3697

题意:给定N, M(N <= 104, M <= 106),求N个点的完全图删掉M条边后,和1这个结点相邻的点的数目。

题解:BFS

利用前向星存边(这里边的含义是反的,ij有边表示ij不直接连通)。然后从1开始广搜,将和1有边的点hash掉,然后枚举hash数组中没有hash掉的点(这些点是和1连通的),如果点没有被访问过,标记已访问,入队;然后不断弹出队列首元素进行相同的处理。

这里可以加入一个小优化,将所有点分组,编号0-9的分为一组,10-19的分为一组,20-29的分为一组,然后用一个计数器来记录每个组中的点是否被访问,每次访问到一个点的时候计数器自增,当某个组的计数器为10的时候表示这个组内所有点都被访问过了,不需要再进行枚举了,这样可以把最坏复杂度控制在 O( N*N/10 ) 以下。

 

 

posted on 2014-06-28 19:48 英雄哪里出来 阅读(2150) 评论(0)  编辑 收藏 引用 所属分类: 区域赛 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理