2015 Multi-University Training Contest 7 Solutions

官方题解:2015 Multi-University Training Contest 7 solutions BY UESTC


 

 

 

1003 Hotaru's problem

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

题意:求最长的N-sequence

定义N-sequence由3部分组成,满足下面2个条件:

1、第一部分和第三部分相同

2、第一部分和第二部分对称

\( 1\leqslant n\leqslant 10^5 \)

manacher算法
可以用manacher算法求出 \(p[i]\) ,表示以下标为 \(i\)\(i+1\) 为中心的最长回文长度

那么问题可以转化成,相距 \(x\) 的两个数 \(a[i],a[i+x]\) ,满足 \( \frac{a[i]}{2}\geqslant x\) 并且 \(\frac{a[i+x]}{2}\geqslant x\) ,要求 \(x\) 尽量大

可以枚举第一个数下标 \(i\) 和长度 \(x\) 。姿势好就可以水过。(正解是二分)

 

 


 

 

 

1005 The shortest problem

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

题意:将数n各位上的数加起来的和接在n末尾形成一个新的数。求进行t次这样的操作后的数是否是11的倍数

\( 1 \leqslant n \leqslant 10^4 , 1 \leqslant t \leqslant 10^5 \)

能被11整除的数的特征
奇位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除。

知道这个性质之后按题意模拟就行

 

 


 

 

 

1007 Gray code

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

题意:给出一个二进制数,‘?'表示当前位为0和1都可以。以及长度为n的数组a。如果格雷码第 \(i\) 位为1,那么可以得到 \(a_i\) 点,求最多能得多少点

\( 1 \leqslant n \leqslant 2 \times 10^5 \)

格雷码转换公式: \(G_i=B_i\otimes B_{i+1}(n-1\geqslant i\geqslant 0)\) (G:格雷码,B:二进制码,最低位下标为0)
DP
\(dp[i][j]\) 表示第 \(i\) 位为 \(j\) 时最大的点数

根据第 \(i\) 位和第 \(i-1\) 位的情况很容易写出状态转移方程

 

 


 

 

(待续...)

Categories: ACM