讨论 - T^T Online Judge

【解题报告】开幕式专场题解bulid by [正牌管理员]萌萌哒管理员 at 2015-07-26 20:46


萌萌哒管理员 Rating:978	A题如果一个点是负数的话，就把它变成0，然后DP[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j] B题取出这串数组的中位数。如果只有一个中位数，那么这个就是X。如果有两个中位数，那么X取两者之间的范围内所有数sum都是一样的，题目要求最小的X，所以两个数中较小的那个就是X。然后根据X计算sum即可 C题由于字符串长度很短，可以枚举开始点i，然后求出最短的字符串长度满足题目条件。然后取最短即可。 D题问FJUTACM1302的同学，反正我是不会做。。。好吧开玩笑的这题首先要先理解了只有一个数出现奇数次的题目。理解了以后，这题其实也差不多。首先把所有数字异或起来，然后得到一个数字，这个数字假设是z，而要求的答案是x和y，那么可以得z=x^y。^是异或运算符。由于x!=y，可知z!=0。既然z!=0则可以知道z的二进制位必然有一个1，也就是z的二进制最高位。然后根据这一位数为1或0可以把原数组分成两部分。分成的两部分分别是题解开始所说的情况。然后分别异或运算一遍，就可以得到答案了。 E题可以用KMP计算。如果next数组的最后一个数 len%(len-next[len])==0 即是WIN 也可以暴力枚举N表示一共有N个重复串，然后逐个判断是否满足。

Rating:978

A题
如果一个点是负数的话，就把它变成0，然后DP[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]

B题
取出这串数组的中位数。
如果只有一个中位数，那么这个就是X。
如果有两个中位数，那么X取两者之间的范围内所有数sum都是一样的，题目要求最小的X，所以两个数中较小的那个就是X。
然后根据X计算sum即可

C题
由于字符串长度很短，可以枚举开始点i，然后求出最短的字符串长度满足题目条件。然后取最短即可。

D题
问FJUTACM1302的同学，反正我是不会做。。。好吧开玩笑的
这题首先要先理解了只有一个数出现奇数次的题目。
理解了以后，这题其实也差不多。
首先把所有数字异或起来，然后得到一个数字，这个数字假设是z，而要求的答案是x和y，那么可以得z=x^y。^是异或运算符。由于x!=y，可知z!=0。既然z!=0则可以知道z的二进制位必然有一个1，也就是z的二进制最高位。然后根据这一位数为1或0可以把原数组分成两部分。分成的两部分分别是题解开始所说的情况。然后分别异或运算一遍，就可以得到答案了。

E题
可以用KMP计算。如果next数组的最后一个数 len%(len-next[len])==0 即是WIN

也可以暴力枚举N表示一共有N个重复串，然后逐个判断是否满足。