Topcoder srm496 div2 1000【最小表示法】

渐渐 posted @ 2011年2月13日 15:03 in 生活 , 2527 阅读

寒假真是悠闲了一个寒假。。。现在写代码什么都不会了 。。。今天开始写写TC

250,500都很水

1000分是一个找子串个数的题:求用小写字母组成的长度为N,并且包含至少K个长度为M的回文串的不同连续子串,的字符串的个数

第一次写1000分的题,想了一阵子,不知道怎么排除重复的字符串。看了别人的报告,学习了大神们的写法

大意是,用搜索找出一种字符串模式,用C个字母表示整个字符串可能的最小表示法:

如:可能有aaa,bbb,ccc,ddd.....zzz那么全可以用aaa表示

dfs(int pos,int C)
{
        if(pos==N)if(check())ans+=calc(C);
        REP(i,C)Rec[pos]=i,dfs(pos+1,max(C,i+1));
}

dfs的含义是:找出当前位置为pos,之前的出现过的数字最大为C的字符串。

当pos==N时,判断是否合法

若合法,加上该最小表示的字符串所包含的字符串个数,既:26个字符放入C个空的全排列数


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter