Prime Distance
|
簡單刷表
|
| Yahtzee |
DP |
| Request for Proposal |
簡單題 |
| Australian Voting |
模擬 |
| Chocolate Chip Cookies |
geometry |
Prime Distance
題目大意就是給你一個區間[l，r]，找出這里相鄰素數的最大距離和最小距離
刷表是經典而實用的方法Yahtzee
給十三種5個骰子的狀態，十三種規則，每種規則下每個狀態有一個得分，問怎樣分配規則與狀態之間的對應關系，讓得分最大，同時要注意的是如果前六種規則下的得分如果>=63，那么總得分要加上35！
首先預處理出每種規則下每個狀態的得分情況！
如果沒有最后一個限制，那么我們可以有兩種做法：1，二分圖的最大權匹配；2，DP！但是有了最后一個限制，用匹配的話不知怎么下手，我只能想到dp！dp[i][j][k]表示前i種骰子狀態已經分配好，分配的情況壓縮成一個整數j，并且前六種規則的得分是k的狀態，那么狀態轉移就是 dp[i][j][k] = {max(dp[ i - 1 ][ j - (1<<h) ][ k - score[h][i] ] ) (0<=h<=6)，max(max(dp[ i - 1 ][ j - (1<<h) ][ k ])( 7<=h<13) } (j的第h位為1) ! 復雜度大概是13*2^13*64 ; 中間記錄前一個狀態， 最后遞歸輸出就好了~
Request for Proposal：
Australian Voting：
按照題意模擬就好了~
Chocolate Chip Cookies
題目大意就是有一些點（200個）， 用一個給定半徑（r==5cm）的圓，最多能罩住多少個點
200個點的話 o ( n^3 )能過，這樣我們有了算法，要罩住最多的點，那個圓必須至少要
卡住兩個點
枚舉每兩個點確定圓心，在檢查所有的點是否在圓內。想法很自然
細節問題上就是如何找到圓心（確定半徑和兩個圓上的點）
這是基本功 如果說直接解方程有些繁瑣這里有好方法：
這樣只要解二元一次方程，可參考以下代碼：
1 struct point {double x, y;};
2
3 bool centre(point p, point q, double r,point &o1, point &o2)
4 //兩點一半徑會確定兩個圓心 o1 o2
5 {
6 double rise,run,theta;
7 double chordlen, perplen;
8 double tantheta,tantheta1;
9
10 chordlen = sqrt( (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y) );
11 if (chordlen > 2*r) { return false; }
12 tantheta = sqrt(r*r*4 - chordlen*chordlen)/(chordlen);
13 //圓心角<poq的半角的正切值
14
15 run = (p.x-q.x)/2;
16 rise = (p.y-q.y)/2;
17 o1.x= (p.x+q.x)/2 + rise * tantheta;
18 o1.y= (p.y+q.y)/2 + -run * tantheta;
19 o2.x= (p.x+q.x)/2 + -rise * tantheta;
20 o2.y = (p.y+q.y)/2 + run * tantheta;
21 //結合點積就能得出上式
22 return true;
23 }
24