C2第六次作業解題報告

看過題解後如果覺得還算有用，請幫忙加點我所在團隊部落格通路量

http://www.cnblogs.com/newbe/

http://www.cnblogs.com/newbe/p/4069834.html

http://www.cnblogs.com/newbe/p/4072005.html

求贊求祝福啊！！！

http://www.cnblogs.com/newbe/p/4058097.html

軟工老師太狠心，還請可憐一下同課不同命的我們吧~點一下文章末尾的推薦什麼的呗，有個回複什麼的就更好了！

1、組合

老生常談的題

dfs即可

dfs出組合的元素滿足以下性質：

（1） a[i+1]>a[i]，後一個數字比前一個大；

（2） a[i]-i<=n-m+1。

隻要在每個循環中核心代碼大概是這樣：

<span style="font-size:14px;">    ans[m+1] = ans[m] + 1;
    dfs(m+1);
    ans[m]++;
    dfs(m);</span>
           

2、Antiprime

我們設p = 2^t1 * 3^t2 * …… * p^tk（其中p是第k大的質數）是Antiprime數，則必有：t1 >= t2 >= t3 >= … >= tk >= 0。

反證法證明：若不然可将{ti}由大到小排序，設形成的新有序序列是{ti’}，t1' >= t2' >= t3' >= … >= tk'；令p’ = 2^t1' * 3^t2' * …… * p^tk'，則：p' < p，但p'的約數個數卻不少于p，這與p是Antiprime數沖突。是以必有：t1 >= t2 >= t3 >= … >= tk。

求一個數的約數個數可以用乘法原理，例如75=3^15^2，則75有(1+1)(2+1)=6個約數。

是以我們隻要按照質因數從小到大依次枚舉指數，找出最多的約數個數情況下最小的正整數即可，而且由于n隻有2*1e9，素數打表隻需打到23即可。

然後就是dfs可搞，傳遞三個參數：構造的t序列長度，構造出的數的約數的個數，構造出的數的大小。

如果覺得這題有意思的話不妨看下

hdu的http://acm.hdu.edu.cn/showproblem.php?pid=4542和

cf上的http://codeforces.com/problemset/problem/27/E同類型題

3、有窮自動機

第六次作業最惡心的一題，純模拟，dfa什麼的編譯裡面也學過了，不難了解

資料弱的一逼，隻判斷字元串第一位居然都能過...

題意不清的一逼，各種...

說幾個注意點吧：

第一行的其餘各列為M個可能的輸入字元串，長度在5以内。

第i行第j列的形式為’qk,z’，其中q是一定出現的字元，k是整數(qk是所有狀态中的一個，k=1,2,3,……)，','必然出現且k和z直接隻有一個','，z是字元串

空白符有' '和‘\t'兩種

4、字母頻度

幾乎沒有難度的模拟題，注意一下題目中所說特殊情況即可..

5、“數獨”遊戲

C1做過的題，暴力即可..

給每行每列每塊各給開個數組維護已經出現的數字(1表示用過，0表示沒有，這樣第19個點就能過了)，回溯爆搜即可

轉載于:https://www.cnblogs.com/zibaohun/p/4106657.html