@kaike

第一題太簡(jiǎn)單我不想說(shuō)什么

來(lái)說(shuō)第二題。

1．小x的旅行

? (travel.pas/c/cpp)

【問(wèn)題描述】

??? 小x大學(xué)畢業(yè)后，進(jìn)入了某個(gè)公司做了高層管理，他每年的任務(wù)就是檢查這個(gè)公司在全國(guó)各地N個(gè)分公司的各種狀況，每個(gè)公司都要檢查一遍，且只能檢查一遍，也就是說(shuō)這N個(gè)地方只能也必須去一次。

當(dāng)然，小x每年可以選擇從任意一個(gè)城市開(kāi)始，任意一個(gè)城市結(jié)束。

現(xiàn)在給出這N個(gè)公司所在地任意兩個(gè)地點(diǎn)飛機(jī)票的價(jià)格，現(xiàn)在小x為了給公司省下交通費(fèi)，需要設(shè)計(jì)一個(gè)程序，來(lái)計(jì)算一下如何花費(fèi)最低能夠完成任務(wù)。

作為一名有過(guò)信息學(xué)競(jìng)賽經(jīng)歷的有志青年，小x給自己的路線又規(guī)定了一個(gè)約束條件：如果要訪問(wèn)編號(hào)為K的城市，那么編號(hào)比K小的所有城市或者在訪問(wèn)K之前訪問(wèn)，或者在訪問(wèn)K之后訪問(wèn)。這個(gè)條件也必須遵守。

比如：如果有3個(gè)城市：2 1 3和 3 1 2 的順序都是合法的，但是 1 3 2的順序就是非法的，因?yàn)楸?小的1在3之前，2在3之后，和小x的要求沖突。

【輸入】

第一行：一個(gè)整數(shù)N。

接下來(lái)N行，每行N個(gè)整數(shù)。第i行第j列的值a[i][j]表示第i個(gè)城市到第j個(gè)城市飛機(jī)票的價(jià)格。保證這N個(gè)整數(shù)在[0..1000]之間。

【輸出】

一個(gè)整數(shù)，表示滿足要求的最小花費(fèi)。

?

【輸入輸出樣例1】

travel.in	travel.out
3 0 5 2 5 0 4 2 4 0	7

?

【輸入輸出樣例2】

travel.in	travel.out
4 0 15 7 8 15 0 16 9 7 16 0 12 8 9 12 0	31

【樣例解釋】順序?yàn)?, 1, 2, 4 或者 4, 2, 1, 3.

【數(shù)據(jù)范圍】

?? 30% 數(shù)據(jù)保證N<=10

?? 50% 數(shù)據(jù)保證 N<=20

?? 100% 數(shù)據(jù)保證 N<=1500

?

第一眼看上去：咦這不是個(gè)最小生成樹(shù)？

后來(lái)覺(jué)得不對(duì)，應(yīng)該算出頂點(diǎn)和圖的關(guān)系...后來(lái)我就不會(huì)寫(xiě)了

生成頂點(diǎn)了太多..不會(huì)寫(xiě)

后來(lái)看他們都寫(xiě)得dfs，dfs現(xiàn)在剛復(fù)習(xí)完....

看題解，原來(lái)如此簡(jiǎn)單。

反著推，從1開(kāi)始，這個(gè)我考試的時(shí)候也想到了。不同的是枚舉左端點(diǎn)和右端點(diǎn)

根據(jù)兩個(gè)城市之間的關(guān)系+記憶化搜索，可以A。

不加的話大概能到70分。

然而苦于思維打不開(kāi)想不到QAQ

1 /* 2 by kaike 3 11/14/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 #include<cstdio> 8 using namespace std; 9 #define FILE "travel" 10 const int MAXN=1510; 11 int mo[MAXN][MAXN],a[MAXN][MAXN],n; 12 int dp(int l,int r) 13 { 14 if(mo[l][r]) return mo[l][r]; 15 int next=max(l,r)+1; 16 if(next==n) return 0; 17 return mo[l][r]=min(a[next][l]+dp(next,r), 18 a[r][next]+dp(l,next)); 19 } 20 int main() 21 { 22 //freopen(FILE".in","r",stdin); 23 //freopen(FILE".out","w",stdout); 24 cin>>n; 25 for(int i=0;i<n;i++) 26 for(int j=0;j<n;j++) 27 cin>>a[i][j]; 28 cout<<dp(0,0)<<endl; 29 return 0; 30 } 哈哈哈

?

第三題是樹(shù)狀數(shù)組求和。

它每循環(huán)一次，就是找二進(jìn)制的1，同時(shí)ans++;

x被計(jì)算的次數(shù)=右端點(diǎn)x的個(gè)數(shù)+左端點(diǎn)為x+1的個(gè)數(shù) = ?x+n-x ?= ?n

這樣就可以從1枚舉到n并對(duì)bitcount(i)求和。

70分到手。

要A的算法是要用數(shù)位DP？并不會(huì)。

1 /* 2 by kaike 3 11/14/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 #define FILE "bit" 9 int map[51000],t,x; 10 const int ss=1000000007; 11 int lowbit(int x) 12 { 13 return x&(-x); 14 } 15 int sum(int x) 16 { 17 int ans=0; 18 while(x>0) 19 { 20 ans++; 21 x-=lowbit(x); 22 } 23 return ans; 24 } 25 int main() 26 { 27 freopen(FILE".in","r",stdin); 28 freopen(FILE".out","w",stdout); 29 cin>>t; 30 for(int i=1;i<=t;i++) 31 { 32 cin>>x; 33 long long s=0; 34 for(int j=1;j<=x;j++) 35 s+=(sum(j)*x)%ss; 36 cout<<s<<endl; 37 } 38 return 0; 39 } 懶到不想打標(biāo)題

?

轉(zhuǎn)載于:https://www.cnblogs.com/Kaike/p/6063085.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Test on 11/14/2016的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。