hihocoder 前两题思路

时间:2023-02-10 10:50:56

1800 : 玩具设计师

二维前缀和的写法有很多,最常见的是s[x-1][y]+s[x][y-1]-s[x-1][y-1]+a[x][y];

涉及二维矩阵求和,联想前缀和,求>=指定面积的最大耐用指数(和)。暴力也可以,枚举所有可能的i,j 满足i*j>=s,后在平面上扫。

有更巧妙的方法,联想一维情况,带负数的数列,连续区间最大和问题,idea就有了,扩展到二维时,依旧只做行的前缀和,枚举y1和y2的位置后化为一维的情况。枚举行,当和<-INF时,舍去重新记录。

1801 : 剪切字符串

找规律题,长度为n的不重复序列,从中截取连续的k个字符的片段,可以贴在开头或结尾,重复操作任意次,问多少种。

当k==n时,1

当k==n-1时,n

当k为奇数时,全排列

当k为偶数时,全排列/2