TCO 2014 Round 1A 题解

贪心专场?。。

250:给出一个字符串s和一个整数L,每次可以选择一个下标i(0\le i\le length(s)-L)进行一个操作:保持0\sim i-1这些字符不变,i\sim (i+L-1)这些字符按照字典序重新排序,(i+L)\sim n这些字符全部删除。问最后能剩下的字典序最小的序列是什么。。

直觉这么写是对的。。然后就这么写了。。

500:给出一个字符串s,需要把字符串中的字符重新排列,要求一个字符移动的距离不能超过maxDistance,求字典序最小的序列。

0n-1扫。。扫到位置i的时候,如果原串中位置为i-maxDistance的那个字符还没放,就把它放在这里,否则在允许范围内选一个最小的字符放在这里

1000:有n个灯和n个开关,开关i一定控制灯i,也可能控制灯i-1,也可能控制i+1,也可能都控制,然而你并不知道它会控制哪些(如果控制的话按下开关相应的灯状态会改变)。问在最坏情况下,至少有多少灯会一直亮着(即所有可能的状态中,亮灯最少的那个状态亮灯的个数)

通过分析发现,只有'YN' 或者'YN'或者'YYY'这三种情况可能会导致至少有一盏灯会在这2(3)盏灯中亮着。。数一下有多少这种情况就行了。

 

发表评论

电子邮件地址不会被公开。

*