2021年寒假热身赛 4

2021年寒假热身赛 4

望江南·超然台作
[宋] 苏轼

春未老,风细柳斜斜。
试上超然台上看,半壕春水一城花。
烟雨暗千家。

寒食后,酒醒却咨嗟。
休对故人思故国,且将新火试新茶。
诗酒趁年华。


A. 风细柳斜斜

判断一个正整数是否为质数,基本操作,现在连小学生都会编这段程序。然后从x开始逐个试验。

(参考代码 JAVA) (参考代码 C++)

B.烟雨暗千家

将原名逆置,依次向后错位并与原名比较,错位步数+相应位不同字符数的最小值即为所求

C. 酒醒却咨嗟

记d2l为到叶子结点的距离,建树之后每个结点计算d2l,取所有结点的{左子结点的d2l(若存在,不存在则为0)+右子结点的d2l (若存在,不存在则为0) +子结点数量}的最大值

D. 休对故人思故国

把每步操作后出现的数字记下来,如果得到1就输出步数,如果操作后的数曾经出现过,那么就会陷入循环,输出-1。可以用一个std::set<int>保存,也可以用数组,因为第1步可能的最大值,是1后边9个9,其平方和为730,可以开一个大小为730的bool数组,表示下标这个数字是否曾出现过。

(参考代码 C++)

E. 且将新火试新茶

0到\( 2^N \)的正整数,可以用它的第k个二进制位,来表示第\( k \) ( \( 1 \le k \le N \) )种茶可否煮出来。

定义如下数组:

dp[i][j] = 第i+1个壶买来后到状态j的最小开销

h是二进制第k-1位为1的数,相应转移方程:

dp[i][j | h] = min(dp[i-1][j | h],dp[i-1][j] + a[i])

时间复杂度\( O(2^N \cdot M ) \),由于此题N仅12,所以指数复杂度也可Accepted

F. 诗酒趁年华

  • 条件1:s1和t的最长公共子串,s2和t的最长公共子串,二者之和等于t的长度
  • 条件2:s1,s2各字母出现次数之和与t各字母出现次数分别相同。

条件1和条件2同时满足则yes,否则no

发表评论

电子邮件地址不会被公开。 必填项已用*标注