| 題目分類(lèi) |
| Gopher II |
圖論，二分圖匹配 |
| Tight words |
DP |
| WERTYU |
簡(jiǎn)單題 |
| Division |
math（高精）
|
| Hotter Colder |
半平面交（geometry）
|
Gopher II：
只需要把老鼠看著一個(gè)集合，鼠洞看著一個(gè)集合，然后鼠與洞之間有邊相連僅當(dāng)鼠能在規(guī)定時(shí)間跑到洞中，然后求最大匹配，用總數(shù)減去最大匹配即為答案！
Tight words ：
題意：給一個(gè)字母表 {0, 1, ... , k}, 0 <= k <= 9 ，問(wèn)一串長(zhǎng)度為 n 的字符串（只含給定字母表中的字符）是否是緊湊的，緊湊的定義是相鄰字符之差的絕對(duì)值不大于 1
dp中狀態(tài)是長(zhǎng)度為 i 最后一個(gè)字符為 j 的概率p[i][j]，狀態(tài)轉(zhuǎn)移為
p[i][j] = 1/k (i=0; j=1,2..k)
p[i][0] = p[i-1][0]/k + p[i-1][1]/k (i>0)
p[i][k] = p[i-1][k]/k + p[i-1][k-1]/k (i>0)
p[i][j] = p[i-1][j-1]/k + p[i-1][j]/k + p[i-1][j+1]/k (i>0, j=1, 2, 3... k-1)
Division :
這道題要高精度， 建議用 java
題目問(wèn) (t^a - 1)/(t^b -1) 是不是小于 100位 的整數(shù)，如果是，求出它的值
t, a, b 為小于2147483647 的正整數(shù)
我做的時(shí)候是先猜出他的判斷條件，判斷條件比較容易猜：
猜想 ：僅當(dāng) b | a 時(shí)，上述表達(dá)式是整數(shù)
有這個(gè)猜想，就可以把上述表達(dá)式化減成等比數(shù)列
1 + t^b + (t^b)^2 + (t^b)^3 + ... + (t^b)^(a/b - 1)
接下來(lái)只要二分求出這個(gè)式子的和，由于和有最大100位，所以要用高精度，還有要注意特判 t==1 的特殊情況，我在這里wa了好幾次
做題時(shí)因?yàn)槭遣碌模坏暮莒?><！現(xiàn)在貼出證明，從discuss里淘出來(lái)的
gcd(a^m - 1, a^n - 1) (m > n)
if m = p*n + r (0<r<n)
then
a^m - 1 = a^(p*n+r) - a^r + a^r - 1
= a^r(a^(p*n)-1) + (a^r-1)
since (a^n-1) | (a^(p*n)-1)
and (a^r-1) < (a^n-1)
so r==0
所以 m%n==0
Hotter Colder：
題目不贅述了，有興趣的可以直接看題目
這道題中的游戲很像一個(gè)人不斷報(bào)價(jià)，另一個(gè)人不斷告訴你是多了還是少了，
與報(bào)價(jià)不同，報(bào)價(jià)是一維的，這道題是二維的
很裸的半平面交， 數(shù)據(jù)很弱，而且就題目本身來(lái)說(shuō)，它是切割一次輸出一次答案，
這里用 o(n^2) 的算法反而比 o(nlogn)的算法好