第一題：
給你一個長度是n的數列(1<=n<=20)，數值m的範圍是0<=m<=100，我們定義數值<60的數字最大數字是a1，數值>=60的最小數字是a2
題目要求：輸出排序後的陣列，以及a1,a2，若不存在a1，則輸出"best case"，若不存在a2，則輸出"worst case"
Solution: 認真操作一下就好了。排序的畫看要用bubble_sort, selection_sort, merge_sort, ....都可以，要用std::sort也可以，之後就掃過每個數字，稍微判斷一下就OK了。
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int MAX_N = 26; int a[MAX_N]; int main () { int n; while (scanf("%d",&n) != EOF) { for (int i=1;n>=i;i++) { scanf("%d",&a[i]); } sort(a+1,a+n+1); int best=-1,worst=-1; for (int i=1;n>=i;i++) { if (i!=1) printf(" "); printf("%d",a[i]); if (a[i] >= 60 && worst==-1) worst=a[i]; if (a[i] < 60) best=a[i]; } puts(""); if (best==-1) puts("best case"); else printf("%d\n",best); if (worst==-1) puts("worst case"); else printf("%d\n",worst); } }
第二題：
一個R*C的矩陣(1<=R,C<=10)，裡面的數值介於0~9，我們定義兩個操作：翻轉、旋轉。旋轉就是把R*C的矩陣90度順時針轉成C*R的矩陣，翻轉就是把第一列和最後一列對調，第二列和倒數第二列對調......等。
一開始，我們有矩陣A，經過m(1<=m<=10)個操過後，變成矩陣B。
題目要求：給你矩陣B和m個操作，請還原矩陣A
Solution : 我們要把B還原A，那就先把A-->B的順序調回B-->A，之後分兩個部分，兩個部份好好時做就OK了，旋轉注意要改回逆時針(如果不小心寫了順時針的，轉三次就變成逆時針了XD(我就是這個人))，翻轉就小心操作就好了。
實作小技巧：可以開另外一個暫存的陣列，先把原本的陣列操作過後的樣子存到暫存的陣列，之後再還原。
#include <iostream> #include <stdio.h> #include <cstring> using namespace std; const int MAX_N = 12; int a[MAX_N][MAX_N]; int tmp[MAX_N][MAX_N]; int oper[MAX_N]; int main () { int n,m,q; while (scanf("%d %d %d",&n,&m,&q) != EOF) { memset(a,-1,sizeof(a)); for (int i=1;n>=i;i++) { for (int j=1;m>=j;j++) { scanf("%d",&a[i][j]); } } for (int i=1;q>=i;i++) { scanf("%d",&oper[i]); } for (int i=q;i>=1;i--){ int k = oper[i]; memset(tmp,-1,sizeof(tmp)); if (k==1) { for (int i=1,ti=n;n>=i;i++,ti--) { for (int j=1;m>=j;j++) { tmp[ti][j] = a[i][j]; } } for (int i=1;n>=i;i++) { for (int j=1;m>=j;j++) { a[i][j] = tmp[i][j]; } } } else if (k==0) { swap(n,m); for (int i=1,ti=n;n>=i;i++,ti--) { for (int j=1;m>=j;j++) { tmp[i][j] = a[j][ti]; } } for (int i=1;n>=i;i++) { for (int j=1;m>=j;j++) { a[i][j] = tmp[i][j]; } } } } printf("%d %d\n",n,m); for (int i=1;n>=i;i++) { for (int j=1;m>=j;j++) { if (j!=1) printf(" "); printf("%d",a[i][j]); } puts(""); } } }
第三題：
這題就比較難了。以下的題解適用於最大的側資
題目要求：給你n個一維平面線段(1<n<10000)，每個線段包含起始座標L，終點座標R (0<=L,R<=10,000,000)，問說線段覆蓋的長度。
Solution：(1)是可能是你們的想法，但是不可行，(2)才OK
(1)就開一個陣列大小為10^7的bool陣列，每當一筆線段輸入進來的時候，就從L跑到R，在認真實作就好了。==>這樣複雜度是O(n) * O(10^7) //輸入跟跑陣列，時間，空間都有可能炸掉！要怎麼辦呢？
(2)我們把輸入的L,R先按照左界L排序(這時候一定要用merge_sort或std::sort)，之後就開始拜訪我們的輸入，當新的L比舊的R還要大的時候，就代表"目前的線段已經結束"，線段覆蓋面積+=R-L，反之，代表"線段延續"，就跟新R=max(query的R, 原本的R)。==>時間複雜度=O(n lg n) + O(n) = O(n lg n)，過了！！！
實作小技巧：可以把詢問寫一個struct或class，然後簡單定義一下這個struct的小於運算子，然後直接用std::sort，會很方面。或者是直接用std::pair，這個也很好用。
code : http://codepad.org/8LJMBn7p
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int MAX_N = 10004; struct Node { int l; int r; } node[MAX_N]; bool operator< (const Node& n1, const Node& n2) { //sort時候所需要用的 return (n1.l<n2.l || n1.l==n2.l && n1.r<n2.r); }
//其實上面的部分可以用std::pair取代
int main () {
int n;
while (scanf("%d",&n) != EOF) {
for (int x=0;n>x;x++) {
scanf("%d %d",&node[x].l,&node[x].r);
}
sort(node,node+n); //按照左界排序查詢
int nl=node[0].l;
int nr=node[0].r;
int ans=0;
for (int x=1;n>x;x++) {
int tl=node[x].l;
int tr=node[x].r;
if (tl>nr) { //新的左界比現在的右界大 --> 之前的左界~右界任務已經結束
ans += (nr-nl);
nl=tl; //指定新的左界
nr=tr; //指定新的右界
}
else if (tl<=nr && tr>nr) nr=tr; //新的右界比原本的右界好
}
ans+=(nr-nl); //不要忘了
printf("%d\n",ans);
}
}第四題：
這題就比較難了，以下解法適用於最大的側資
題目要求：給你一張血緣關係圖(n個人，n-1個關係，保證不會有環，最早的祖先只會有一個，1<=n<=10^5)，請問血緣關係最遠兩位的距離！(其實就是樹直徑)
Solution :
我一開始想寫最短路，之後又想寫LCA，又想寫並查集(disjoint set)，後來發現都不行
於是來寫個dfs吧！
先討論簡答可能出現的情況：a, 祖先圖是一條直線 b. 兩個兒子有共同的祖先
先把樹存好(需要記錄兒子和祖先，初始值：祖先=自己，兒子=沒有)，然後抓到最頭的點，開始進行dfs，需要維護的是距離，根據兒子的case分成三種情況：
兒子數==0：直接return 0;
兒子數==1：return dfs(兒子) + 1
兒子數>=1 : 先把所有兒子的dfs值算出來，然後抓出最大的兩個於ans做比較，return max(dfs(兒子)) + 1
可是，這樣子寫，b情況考慮進去了，可是a好像沒有。
那就ans = max(ans, dfs(祖先) ); 就好啦！！！
code : http://codepad.org/sJtVSIbi
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100006; struct Node { int ancestor; int num; //小孩的個數 vector<int> child; //因為不知道有多少個，所以使用vector } node[MAX_N]; int ans; int dfs(int x) { if (node[x].num==0) return 0; else if (node[x].num==1) return dfs(node[x].child[0]) + 1; else { int ret[node[x].num]; for (int i=0;node[x].num>i;i++) { ret[i]=dfs(node[x].child[i]) + 1; } sort(ret,ret+node[x].num); reverse(ret,ret+node[x].num); ans=max(ret[0]+ret[1],ans); return ret[0]; } } int main () { int n; while (scanf("%d",&n) != EOF) { for (int x=0;n>x;x++) { //記得先初始化 node[x].ancestor=x; node[x].num=0; node[x].child.clear(); } for (int x=0;n-1>x;x++) { int a,b; scanf("%d %d",&a,&b); //b的祖先是a node[a].num++; //兒子的數量 node[b].ancestor = a; //指定祖先 node[a].child.push_back(b); } int id=0; ans=-1; for (int x=0;n>x;x++) { if (node[x].ancestor==x) id=x; //尋找最老祖先 } ans=max(dfs(id),ans); //一直線情形 printf("%d\n",ans); } }
沒有留言:
張貼留言