Prime Distance
|
簡(jiǎn)單刷表
|
| Yahtzee |
DP |
| Request for Proposal |
簡(jiǎn)單題 |
| Australian Voting |
模擬 |
| Chocolate Chip Cookies |
geometry |
Prime Distance
題目大意就是給你一個(gè)區(qū)間[l，r]，找出這里相鄰素?cái)?shù)的最大距離和最小距離
刷表是經(jīng)典而實(shí)用的方法Yahtzee
給十三種5個(gè)骰子的狀態(tài)，十三種規(guī)則，每種規(guī)則下每個(gè)狀態(tài)有一個(gè)得分，問怎樣分配規(guī)則與狀態(tài)之間的對(duì)應(yīng)關(guān)系，讓得分最大，同時(shí)要注意的是如果前六種規(guī)則下的得分如果>=63，那么總得分要加上35！
首先預(yù)處理出每種規(guī)則下每個(gè)狀態(tài)的得分情況！
如果沒有最后一個(gè)限制，那么我們可以有兩種做法：1，二分圖的最大權(quán)匹配；2，DP！但是有了最后一個(gè)限制，用匹配的話不知怎么下手，我只能想到dp！dp[i][j][k]表示前i種骰子狀態(tài)已經(jīng)分配好，分配的情況壓縮成一個(gè)整數(shù)j，并且前六種規(guī)則的得分是k的狀態(tài)，那么狀態(tài)轉(zhuǎn)移就是 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) ! 復(fù)雜度大概是13*2^13*64 ; 中間記錄前一個(gè)狀態(tài)， 最后遞歸輸出就好了~
Request for Proposal：
Australian Voting：
按照題意模擬就好了~
Chocolate Chip Cookies
題目大意就是有一些點(diǎn)（200個(gè)）， 用一個(gè)給定半徑（r==5cm）的圓，最多能罩住多少個(gè)點(diǎn)
200個(gè)點(diǎn)的話 o ( n^3 )能過，這樣我們有了算法，要罩住最多的點(diǎn)，那個(gè)圓必須至少要
卡住兩個(gè)點(diǎn)
枚舉每兩個(gè)點(diǎn)確定圓心，在檢查所有的點(diǎn)是否在圓內(nèi)。想法很自然
細(xì)節(jié)問題上就是如何找到圓心（確定半徑和兩個(gè)圓上的點(diǎn)）
這是基本功 如果說直接解方程有些繁瑣這里有好方法：
這樣只要解二元一次方程，可參考以下代碼：
1 struct point {double x, y;};
2
3 bool centre(point p, point q, double r,point &o1, point &o2)
4 //兩點(diǎn)一半徑會(huì)確定兩個(gè)圓心 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 //結(jié)合點(diǎn)積就能得出上式
22 return true;
23 }
24