2015 Multi-University Training Contest 8 Solutions

官方题解:2015 Multi-University Training Contest 8 solutions BY 绍兴一中


 

 

1005 Danganronpa

HDU 5384:http://acm.hdu.edu.cn/showproblem.php?pid=5384

题意:给n个字符串 \(A_i\) ,m个字符串 \(B_j\) ,定义 \(f(A,B)\) 为B字符串在A字符串中出现的次数,可以重叠。求对于每个 \(A_i\)\(\sum_{j=1}^{m}f(A_i,B_j)\) 的值

\(n,m\leqslant 10^5, 1\leqslant |A_i|,|B_j|\leqslant 10^4, \sum|A_i|\leqslant 10^5, \sum|B_j|\leqslant 10^5\)

AC自动机。
用所有 \(B_j\) 字符串构造一个AC自动机

对于每个 \(A_i\) 扫描一次即可求出答案

 

 


 

 

 

1007 Cover

HDU 5386:http://acm.hdu.edu.cn/showproblem.php?pid=5386

题意:有一个n*m的矩阵,定义两种操作:

L x y: for(int i=1;i<=n;i++)color[i][x]=y;
H x y:for(int i=1;i<=n;i++)color[x][i]=y;
现在给出矩阵的初始状态和终态,以及m个操作,求能满足条件的操作顺序

我们只要每次找一行或一列颜色除了0都相同的,然后如果有对应的操作,就把这行这列都赋值成0即可
答案只与终态有关。

 

 


 

 

 

1008 Clock

HDU 5387:http://acm.hdu.edu.cn/showproblem.php?pid=5387

题意:给一个时刻,分别求时针与分针,时针与秒针,分针与秒针的角度

计算一下角度就行,注意分数以及钝角的处理

 

 


 

 

 

1010 Zero Escape

HDU 5389:http://acm.hdu.edu.cn/showproblem.php?pid=5389

题意:n个人,每人有一个标识符 \(id_i\) (可以相同),现有两道门编号为 \(A,B\) (可以相同)。对每个人要选择一个门通过。最后选择同一个门的人的标识符之和的数根和门的编号相同就可以通过。求能让所有人通过的方案数。

\(T\leqslant 100, n\leqslant 10^5, \sum n\leqslant 10^6, 1\leqslant A,B,id_i\leqslant 9\)

DP
定义 \(dr(x)\)\(x\) 的数根

数根有一个性质: \(dr(a+b)\equiv dr(a)+dr(b)\space (\mod 9\space )\)

所以可以用 \(dp[i][j]\) 表示从前 \(i\) 个数中选出一些数使其和的树根对9取模为 \(j\) 的方案数有多少

状态转移方程:

\(for \ each \ j \in [0,9]\)

\(\qquad dp[i][j]=dp[i-1][j]\)
\(\qquad dp[i][(j+d[i]) \% 9]=dp[i][(j+d[i]) \% 9]+dp[i-1][j]\)

 

 


 

 

(待续...)

Categories: ACM