#CF1492E

#CF1492E

  通过这道题,我对dfs有了更深的理解。

  拿完快递走回来的路上突然想到可以以第一个作为标准答案,然后一个一个比对下去,不行的话就改。

  不同的位置元素过多时,就没有答案。

  想到这里就卡着了,第一个卡点是那我要修改哪位?修改完后会不会对原来的序列造成伤害?

  标解是枚举可以修改的位置,再去check这应改行不行。

  我的思路卡在了认为要通过现有的信息一下子就判定当前为能不能改,而事实上可以先假设能再check。

  因为只通过现有的信息判定能不能改的话,需要记录前面每个序列不同的个数,不同的数的位置,并且每次改完后还要对其进行维护。理论上可以啦,代码成本根本写不出来。

  那么假如枚举的位置都可以,我选择哪个呢?不同的选择对下面的序列会有影响的,我需不需要再对下面进行一个贪心,比如选择下面重复次数最多的数?

  我无法证明贪心是对的,至此,代码已经根本写不出来++;

  标解是dfs。

  咦.

  .

  ..

  ...

  结构上,我有想到的这种不断循环的比较,且出现多个选项,答案在其中,和dfs的结构是相近的。

  证明上,因为最多只能修改2个位置,所以dfs的层数不会满。

  标解给我的启发一是:判断可不可行不一定要直接出答案,force check也很香;不知道当前答案是否可行,且仍有可能可行的备选答案时,就都去试试,试完之后会走向不同的分支,那是dfs的美妙。

  p.s:其实有个检查每列出现次数最多的数填进去最后check一遍的思路,但不知道是否可行,猜测罢了。没啥依据。

 

上一篇:5 个最受人喜爱的开源 Django 包


下一篇:P1083 [NOIP2012 提高组] 借教室