PTA團(tuán)體程序設(shè)計(jì)天梯賽

• 數(shù)據(jù)結(jié)構(gòu)類(lèi)型
• • L3-002 特殊堆棧(樹(shù)狀數(shù)組)
  • L3-003 社交集群(并查集)
• 搜索
• • L3-004 腫瘤診斷(三維bfs)
  • • 確保bfs只遍歷一次的方法
• 圖論
• • L3-005 垃圾箱分布(多次SPFA)
  • L3-007 天梯地圖 (最短路+輸出指定路徑)

數(shù)據(jù)結(jié)構(gòu)類(lèi)型

L3-002 特殊堆棧(樹(shù)狀數(shù)組)

題目鏈接

題目大意
本題的難點(diǎn)是維護(hù)一個(gè)動(dòng)態(tài)的中值。

解題思路
因?yàn)橹悼赡苁遣话创笮№樞蚪o出的，因此我們無(wú)法利用優(yōu)先隊(duì)列來(lái)維護(hù)，原因是在進(jìn)行pop的時(shí)候可能彈出的是下邊或者中間的值，而不是優(yōu)先隊(duì)列頂部的值。對(duì)于中值，我們對(duì)于每一個(gè)值如果出現(xiàn)一次，那么其次數(shù)加1，那么中值就轉(zhuǎn)變?yōu)榱诉@個(gè)次數(shù)序列中出現(xiàn)次數(shù)的中值(因?yàn)檫@個(gè)序列是單調(diào)的)，那么可以單點(diǎn)修改與單點(diǎn)查詢的數(shù)據(jù)結(jié)構(gòu)，就是樹(shù)狀數(shù)組了。

• 對(duì)于求中值，我們可以在0 ~ N 中進(jìn)行二分。

代碼：

#include<iostream> #include<string> #include<stack> #include<algorithm> using namespace std; const int N = 1e5 + 10; int t[N]; stack<int>st; int n ,x;int lowbit(int x){ return x & -x; }void add(int k , int v){for( ; k < N ; k += lowbit(k)) t[k] += v; }int get(int n){int ans = 0;for( ; n ; n -= lowbit(n))ans += t[n];return ans; }int PeekMedian(){int l = 1 , k = (st.size() + 1)/2 , r = N - 1;while(l < r){int mid = (l + r)>>1;if(get(mid) >= k) r = mid;else l = mid + 1;}return l; }int main(){cin>>n;while(n--){string s;cin>>s;if(s == "Pop"){if(st.size() == 0)cout<<"Invalid\n";else{x = st.top();cout<<st.top()<<endl;st.pop() , add(x , -1);}}else if(s == "Push"){cin>>x;st.push(x) ,add(x,1);}else{if(st.size() == 0)cout<<"Invalid\n";else cout<<PeekMedian()<<endl;}}return 0; }

L3-003 社交集群(并查集)

題目鏈接

題目大意
題目是給出了每一個(gè)人的興趣的編號(hào)的集合，對(duì)于存在一個(gè)興趣相同的人我們認(rèn)為其在一個(gè)圈子中。然后問(wèn)你有多少興趣圈，與每一個(gè)圈子有多少人。

解題思路
對(duì)于每一個(gè)人我們存下，其興趣圈中的一個(gè)代表元素(不妨是第一個(gè)元素)，之后將其興趣圈中的所有值進(jìn)行合并。對(duì)于沒(méi)一個(gè)人都這樣操作以后。我們枚舉這n個(gè)人，我們

代碼：

#include<iostream> #include<algorithm> using namespace std; const int N = 1100;int p[N]; char ch; int n , f[N]; int pos[N] ,cnt , p[N];bool cmp(int a, int b){return a > b;}void init(){for(int i = 1 ;i < N ; ++i) f[i] = i; }int find(int x){if(x == f[x])return x;else return f[x] = find(f[x]); }void join(int x,int y){x = find(x) , y = find(y);if(x != y)f[x] = y; }int main(){cin>>n;init();for(int i = 1 ; i <= n ; ++i){int k , y ;cin>>k>>ch;for(int j = 1 ;j <= k ; ++j){int x;cin>>x;if(j == 1)y = x , p[i] = y;else join(x ,y);}}for(int i = 1; i <= n ; ++i){int x = find(p[i]);pos[x] ++;}sort(pos ,pos + N , cmp);for(int i = 0 ; pos[i] ; ++i)cnt++;cout<<cnt<<endl;for(int i = 0 ; i < cnt ; ++i){if(i)cout<<" ";cout<<pos[i];}return 0; }

搜索

L3-004 腫瘤診斷(三維bfs)

題目鏈接

解題思路
這可以說(shuō)是一個(gè)三維bfs的板子題，這里x，y，z的順序不重要只要你清楚就可以了。一般對(duì)于二維，三維的移動(dòng)我們都會(huì)建立一個(gè)坐標(biāo)變化的數(shù)組。我們?cè)谶M(jìn)行bfs的時(shí)候要確保每一個(gè)點(diǎn)只遍歷一次。這里我們有兩種方式確保只遍歷一次。

確保bfs只遍歷一次的方法

我們?cè)诿恳淮纬鲫?duì)的時(shí)候?qū)⒊鲫?duì)的元素置為1，為了確保遍歷一次我們?cè)谥脼?的上邊先判斷一下，如果該元素已經(jīng)是1了就跳過(guò)。這樣做可行的原因是，即使前后兩個(gè)節(jié)點(diǎn)指向的節(jié)點(diǎn)又交集，但是由于隊(duì)列的先進(jìn)先出，如果我們?cè)谥脼?之前跳過(guò)已經(jīng)是1的點(diǎn)，也就是對(duì)于交集雖然都在隊(duì)列中不過(guò)我們只會(huì)遍歷先進(jìn)去的節(jié)點(diǎn)，這樣就確保了正確性。
代碼:

void bfs(int z ,int x ,int y){queue<node>q;q.push({z,x,y});while(q.size()){node u = q.front();q.pop();if(st[u.z][u.x][u.y])continue;s ++ ; st[u.z][u.x][u.y] = 1;for(int i = 0 ;i < 6 ; ++i){int zz = u.z + dz[i] , xx = u.x + dx[i] , yy = u.y + dy[i];if(zz >= 0 && zz < L && xx >= 0 && xx < n && yy >= 0 && yy < m && !st[zz][xx][yy] && str[zz][xx][yy] == 1)q.push({zz,xx,yy});}} }

第二種是在將滿足條件的節(jié)點(diǎn)壓入隊(duì)列的時(shí)候就置為1，這樣是確保了在隊(duì)列元素中的唯一性，顯然能滿足節(jié)點(diǎn)只遍歷一次的情況。

代碼:

void bfs(int z ,int x ,int y){queue<node>q;q.push({z,x,y});st[z][x][y] = 1;while(q.size()){node u = q.front();q.pop();s ++ ; for(int i = 0 ;i < 6 ; ++i){int zz = u.z + dz[i] , xx = u.x + dx[i] , yy = u.y + dy[i];if(zz >= 0 && zz < L && xx >= 0 && xx < n && yy >= 0 && yy < m && !st[zz][xx][yy] && str[zz][xx][yy] == 1){q.push({zz,xx,yy});st[zz][xx][yy] = 1; // 在這里才不會(huì)重復(fù)加入}}} }

代碼:

#include <iostream> #include <string> #include <cstring> #include<queue> using namespace std;const int N = 1300 , M = 130; int n, m, L, t; int str[M][N][M]; bool st[M][N][M];int s, ans, dx[6] = {0, 0, 1, -1,0,0}, dy[6] = {1, -1, 0, 0, 0, 0},dz[6] = {0,0,0,0,1,-1};struct node{int z,x,y; };void bfs(int z ,int x ,int y){queue<node>q;q.push({z,x,y});// st[z][x][y] = 1;while(q.size()){node u = q.front();q.pop();if(st[u.z][u.x][u.y])continue;s ++ ; st[u.z][u.x][u.y] = 1;for(int i = 0 ;i < 6 ; ++i){int zz = u.z + dz[i] , xx = u.x + dx[i] , yy = u.y + dy[i];if(zz >= 0 && zz < L && xx >= 0 && xx < n && yy >= 0 && yy < m && !st[zz][xx][yy] && str[zz][xx][yy] == 1){q.push({zz,xx,yy});// st[zz][xx][yy] = 1; // 在這里才不會(huì)重復(fù)加入}}} }void solve() {memset(st, 0, sizeof st);for(int k = 0 ; k < L ; ++k)for (int i = 0 ; i < n ; ++i)for (int j = 0 ; j < m ; ++j)if (str[k][i][j] == 1 && !st[k][i][j]) {s = 0;bfs(k , i , j);if ( s >= t)ans += s;} }int main() {cin >> n >> m >> L >> t;for(int k = 0 ; k < L ; ++k) for (int i = 0 ; i < n ; ++i)for (int j = 0 ; j < m ; ++j)cin>>str[k][i][j];solve();cout << ans << endl;return 0;}

圖論

L3-005 垃圾箱分布(多次SPFA)

題目鏈接

解題思路
對(duì)于這里首先我們要求的是垃圾箱到各個(gè)居名點(diǎn)的最短距離，這里有一個(gè)小技巧就是將垃圾箱也進(jìn)行編號(hào)是 n + c ，c 是垃圾箱的編號(hào)，然后一起建邊。之后每一次都以垃圾箱為起點(diǎn)進(jìn)行spfa，大致步驟如下

分析：
這道題對(duì)每個(gè)垃圾點(diǎn)進(jìn)行spfa即可，然后找到符合以下條件的垃圾點(diǎn)：

居民點(diǎn)與垃圾箱之間的最短距離不超過(guò)Dist
垃圾箱到居民點(diǎn)的最短距離最長(zhǎng)
若符合2的不唯一，則選擇平均距離最短的
若符合3的不唯一，則選擇編號(hào)最小的

• 對(duì)于對(duì)某一位數(shù)進(jìn)行四舍五入的辦法是，先將該數(shù)擴(kuò)大倍數(shù)，使得要四舍五入的位數(shù)變成小數(shù)點(diǎn)的第一位，四舍五入之后再縮小相同倍數(shù)。

代碼:

#include<iostream> #include<queue> #include<string> #include<algorithm> #include<cstring> #include<cmath> using namespace std;const int N = 1e4 + 100 , M = 1e5 + 10;int n , m , L,t; int h[N] ,e[M] , ne[M] ,w[M] ,cnt; bool st[N]; int d[N];struct rub{int id ;double mix ,avg;bool operator < (rub w){if(mix == w.mix && avg == w.avg)return id < w.id;else if(mix == w.mix)return avg < w.avg;else return mix > w.mix;} }a[N];void add(int u , int v ,int val){e[++cnt] = v , ne[cnt] = h[u] , w[cnt] = val , h[u] = cnt; }void spfa(int s){memset(st, 0 ,sizeof st);memset(d , 0x3f , sizeof d);queue<int>q;q.push(s);d[s] = 0;while(q.size()){int u = q.front();q.pop();st[u] = false;for(int i = h[u]; ~i ; i = ne[i]){int v = e[i];if(d[v] > d[u] + w[i]){d[v] = d[u] + w[i];if(!st[v]) q.push(v) , st[v] = true;}}} }int main(){memset(h,-1,sizeof h);cin>>n>>m>>L>>t;while(L--){string a ,b;int d , x,y;cin>>a>>b>>d;if(a[0] == 'G') x = n + atoi(a.substr(1).c_str());else x = atoi(a.c_str());if(b[0] == 'G') y = n + atoi(b.substr(1).c_str());else y = atoi(b.c_str());add(x,y,d) ,add(y,x,d);}int tot = 0 , mx ;for(int i = n + 1 ; i <= n + m ; ++i ){spfa(i);double sum = 0.0;mx = 0;a[tot] = {i - n ,1e10 , 0};for(int j = 1 ; j <= n ; ++j) a[tot].mix = min(a[tot].mix , d[j] + 0.0) , mx = max(mx , d[j]) , sum += d[j];if(mx > t)continue; // 有超過(guò)最大距離限制的就跳過(guò)a[tot++].avg = sum * 1.0 / (n + 0.0);}sort(a , a + tot); if(!tot)cout<<"No Solution\n";else {printf("G%c\n",a[0].id + '0');printf("%.1lf %.1lf\n",a[0].mix , round(a[0].avg * 10.0) / 10.0 );}return 0; }

L3-007 天梯地圖 (最短路+輸出指定路徑)

題目:題目鏈接
內(nèi)容：

本題要求你實(shí)現(xiàn)一個(gè)天梯賽專(zhuān)屬在線地圖，隊(duì)員輸入自己學(xué)校所在地和賽場(chǎng)地點(diǎn)后，該地圖應(yīng)該推薦兩條路線：一條是最快到達(dá)路線；一條是最短距離的路線。題目保證對(duì)任意的查詢請(qǐng)求，地圖上都至少存在一條可達(dá)路線。

輸入格式：

輸入在第一行給出兩個(gè)正整數(shù)N（2 ≤ N ≤ 500）和M，分別為地圖中所有標(biāo)記地點(diǎn)的個(gè)數(shù)和連接地點(diǎn)的道路條數(shù)。隨后M行，每行按如下格式給出一條道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的兩個(gè)端點(diǎn)的編號(hào)（從0到N-1）；如果該道路是從V1到V2的單行線，則one-way為1，否則為0；length是道路的長(zhǎng)度；time是通過(guò)該路所需要的時(shí)間。最后給出一對(duì)起點(diǎn)和終點(diǎn)的編號(hào)。

輸出格式：

首先按下列格式輸出最快到達(dá)的時(shí)間T和用節(jié)點(diǎn)編號(hào)表示的路線：
Time = T: 起點(diǎn) => 節(jié)點(diǎn)1 => … => 終點(diǎn)

然后在下一行按下列格式輸出最短距離D和用節(jié)點(diǎn)編號(hào)表示的路線：
Distance = D: 起點(diǎn) => 節(jié)點(diǎn)1 => … => 終點(diǎn)

如果最快到達(dá)路線不唯一，則輸出幾條最快路線中最短的那條，題目保證這條路線是唯一的。而如果最短距離的路線不唯一，則輸出途徑節(jié)點(diǎn)數(shù)最少的那條，題目保證這條路線是唯一的。
如果這兩條路線是完全一樣的，則按下列格式輸出：
Time = T; Distance = D: 起點(diǎn) => 節(jié)點(diǎn)1 => … => 終點(diǎn)

解題思路
思路就是分別以time，length為權(quán)值跑兩邊Dijkstra，記住要用上堆優(yōu)化。
我們用一個(gè)數(shù)組存路徑，這個(gè)數(shù)組p[v]的含義是 指向 v 節(jié)點(diǎn)的是p[v]。同時(shí)為了找到正確的路徑，我們還需要nc[v]表示到達(dá)v 節(jié)點(diǎn)走過(guò)的最小節(jié)點(diǎn)數(shù)量 ， 與 fd[v]表示走到v的最短距離。

• 測(cè)試點(diǎn)2的意思就是：最快的最短是距離最短而不是節(jié)點(diǎn)最少！
  所以說(shuō)雖然你其他的測(cè)試點(diǎn)都過(guò)了，只是數(shù)據(jù)恰好距離最短和節(jié)點(diǎn)最少等效而已，你的代碼還是存在問(wèn)題的！
• 對(duì)于檢測(cè)路徑是否一樣，我們可以利用迭代來(lái)進(jìn)行，從終點(diǎn)依次向前推，如果遇到不同的節(jié)點(diǎn)就返回false ， 否則只到起點(diǎn)都是一樣的那么就返回true。

代碼:

#include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std;typedef pair<int ,int>PII; const int N = 5100 , M = 5e5 + 10;int n , m , v1 ,v2; int h[N] , e[M] , ne[M] ,w1[M] ,w2[M] ,cnt; bool st[N]; int dd[N] ,dt[N] ,pd[N],pt[N] ,nc[N] , fd[N];void add(int u , int v ,int val1,int val2){e[++cnt] = v , ne[cnt] = h[u] , w1[cnt] = val1 , w2[cnt] = val2 , h[u] = cnt; }void dijstra1(int s){memset(dd , 0x3f ,sizeof dd);dd[s] = 0 ;priority_queue<PII>heap;heap.push({0 , s});st[s] = true;while(heap.size()){int u = heap.top().second;heap.pop();for(int i = h[u] ;~i ; i = ne[i]){int v = e[i];if(dd[v] >= dd[u] + w2[i]){if(dd[v] > dd[u] + w2[i]){dd[v] = dd[u] + w2[i] , pd[v] = u , fd[v] = fd[u] + w1[i];if(!st[v]) heap.push({-dd[v] ,v}) , st[v] = true;}else if(fd[v] > fd[u] + w1[i]){pd[v] = u ,fd[v] = fd[u] + w1[i];}}}} }void dijstra2(int s){memset(dt , 0x3f ,sizeof dt);dt[s] = 0;priority_queue<PII>heap;heap.push({0 , s});st[s] = true;while(heap.size()){int u = heap.top().second;heap.pop();for(int i = h[u] ;~i ; i = ne[i]){int v = e[i];if(dt[v] >= dt[u] + w1[i]){if(dt[v] > dt[u] + w1[i]){dt[v] = dt[u] + w1[i] , pt[v] = u ,nc[v] = nc[u] + 1;if(!st[v]) heap.push({-dt[v] ,v}) , st[v] = true;}else if(nc[v] > nc[u] + 1){pt[v] = u , nc[v] = nc[u] + 1;}}}} }bool check(){int ed = v2 ;while(ed != v1){if(pd[ed] != pt[ed])return false;ed = pd[ed];}return true; }void dfs(int u , int p[]){if(u == v1){cout<<v1;return ;}dfs(p[u] , p);cout<<" => "<<u; }int main(){memset(h , -1 ,sizeof h);cin>>n>>m;while(m--){int a,b,op , c,d;cin>>a>>b>>op>>c>>d;add(a,b ,c,d);if(!op)add(b,a,c,d);}cin>>v1>>v2;dijstra1(v1);memset(st , 0 ,sizeof st);dijstra2(v1);if(check()){printf("Time = %d; Distance = %d: ",dd[v2] ,dt[v2]);dfs(v2 ,pd);}else{printf("Time = %d: ",dd[v2]);dfs(v2 ,pd);puts("");printf("Distance = %d: ",dt[v2]);dfs(v2 ,pt);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的PTA团体程序设计天梯赛篇(五)---- 难题篇一(30分题目)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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