L2-3 智能護理中心統計
智能護理中心系統將轄下的護理點分屬若干個大區，例如華東區、華北區等；每個大區又分若干個省來進行管理；省又分市，等等，我們將所有這些有管理或護理功能的單位稱為“管理結點”，現在已知每位老人由唯一的一個管理結點負責，每個管理結點屬于唯一的上級管理結點管轄，你需要實作一個功能，來統計任何一個管理結點所負責照看的老人的數量，
注意這是一個動態問題，即隨時可能有老人加入某個管理結點，并且老人是有可能從一個管理結點換到另一個管理結點去的，
輸入格式：
輸入在第一行中給出 2 個正整數：N（≤104）是老人的總數量，即老人們從 1 到 N 編號；M（≤105）是歸屬關系的總數，
接下來是 M 行，每行給出一對歸屬關系，格式為：
A B表示 A 歸屬于 B，A 或 B 如果是某個管理結點，則用不超過 4 個大寫英文字母表示其名稱；如果是某位老人，則用老人的編號表示，這里每個 A 保證只有唯一的上級歸屬 B，且只有這個中心系統本身是沒有上級歸屬的，此外，輸入保證沒有老人自己承擔管理結點的角色，即 B 一定是一個管理結點，不可能是老人的編號，但一個管理結點既可以管轄下級結點，也可以直接護理一部分老人，
隨后每行給出一個指令，格式為：
指令 內容如果 指令 為 T，則表示有老人要入院或轉院，內容 是某老人的編號和要去的管理結點的名稱，以空格分隔；如果 指令 為 Q，則 內容 是一個管理結點的名稱，意思是統計這個結點所負責照看的老人的數量；如果 指令 為 E，則表示輸入結束，題目保證指令總數不會超過 100 個，
輸出格式：
對每個 T 指令，將對應的老人轉存到對應的管理結點名下；對每個 Q 指令，在一行中輸出對應管理結點所負責照看的老人的數量，讀到 E 指令就結束程式，
輸入樣例：
10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E輸出樣例：
5
4
4
3
0
9
題解：老人為葉子節點，考慮到每次只有葉子節點的變化，所以只需要貪心計算葉子節點對對應的這條鏈的貢獻即可
// #include<bits/stdc++.h> using namespace std; #define maxn 610938 int n,m; int cnt1=0,cnt2=0,cnt=200000; unordered_map<string,int>mapp; int cot[maxn]; int yezi[maxn]; int pre[maxn]; int main() { cin>>n>>m; string s1,s2; for(int i=1;i<=m;i++) { cin>>s1>>s2; if(s1[0]>='0'&&s1[0]<='9') { if(!mapp[s2]) { ++cnt; mapp[s2]=cnt; } pre[stoi(s1)]=mapp[s2]; } else { if(!mapp[s1]) { ++cnt; mapp[s1]=cnt; } if(!mapp[s2]) { ++cnt; mapp[s2]=cnt; } pre[mapp[s1]]=mapp[s2]; } } for(int i=1;i<=n;i++) { if(pre[i]!=0) { int x=pre[i]; cot[i]=1; while(pre[x]!=x) { cot[x]++; x=pre[x]; } cot[x]++; } } while(1) { char c; cin>>c; if(c=='E') { break; } if(c=='T') { int a; string b; cin>>a>>b; int x=pre[a]; cot[a]=1; while(pre[x]!=x) { cot[x]--; x=pre[x]; } cot[x]--; pre[a]=mapp[b]; int y=pre[a]; cot[a]=1; while(pre[y]!=y) { cot[y]++; y=pre[y]; } cot[y]++; } if(c=='Q') { string x; cin>>x; cout<<cot[mapp[x]]<<endl; } } }View Code
--------------------
L3-1 塔防游戲
有一種簡單的塔防游戲是這樣的：給定一張由 n 行 m 列個方格子構成的地圖，玩家可以任選一個格子放置自己的大本營，還可以在任意一個格子里放置自己的防御堡壘，大本營和每個防御堡壘都有自己的防御能力值 d，表示可以抵御 d 個僵尸的攻擊，每一輪游戲開始時，玩家在規定時間內將本級別可以用的防御堡壘布置在地圖中，然后僵尸們就從地圖邊界涌入地圖中，向著大本營發起攻擊，每輪進攻持續一個固定的時長，結束后剩余的僵尸就原地蒸發，
每隊僵尸可以向一個方格的上下左右四個方向移動，如果相鄰的目標方格沒有堡壘，它們就可以用 1 秒的時間移動過去，否則會被堡壘阻擋或者消滅，對每一隊僵尸（從同一地點出發的所有僵尸）而言，每秒會被堡壘消滅 1 個隊友，同時消耗掉該堡壘 1 個單位的防御能力，當防御能力降為 0，則該堡壘消失，剩下的僵尸則用 1 秒移動到這個方格繼續行進，注意：如果有多支僵尸隊都進入了同一個方格，它們并不會合并成一支隊伍，
所有的僵尸隊都會根據進攻開始時的地圖選擇被殲滅最少的到達大本營的路線，并且一直按照這個路線行進，中途不因為地圖狀態的改變而改變，當這樣的進攻路徑不唯一時，選擇能最快到達大本營的路徑，題目保證這樣的路徑所打掉的堡壘的布局是唯一的，
本題就要求你計算出一輪攻擊結束時，地圖上的布局情況，
輸入格式：
輸入首先在第一行中給出三個正整數：不超過 100 的 n 和 m，為地圖的尺寸；不超過 1000 的 T，為一輪攻擊持續的時長，
隨后給出 n+2 行，每行給出 m+2 個數字，每行中的數字都用空格分隔，表示攻擊開始前地圖上的布局，其中第 1 行、第 1 列、第 n+2 行、第 m+2 列是地圖邊界外僵尸們出發的位置，這些位置上，0 表示沒有僵尸，其他正整數表示從該位置出發的僵尸們的數量，而地圖中的每個位置上，0 表示沒有堡壘，其它正整數表示該位置上堡壘的防御能力值，大本營是一個特殊的建筑，我們用一個負數 ?D 表示這里是大本營，其防御能力值為 D，這里的防御值和任一隊僵尸的數量都不超過 100，
注意：僵尸不可在地圖邊界外移動，它們的第一個移動目標必須在地圖中，所以四個角落里出現的僵尸可以被忽略，因為它們沒有進入地圖的途徑，
輸出格式：
輸出 n 行，每行 m 個數字，對應攻擊結束后地圖上每個方格的狀態，狀態的表示與輸入相同：沒有堡壘的地方輸出 0，有堡壘的地方輸出其剩余防御值，大本營的位置上輸出其剩余防御值的負值，
注意每行數字間以 1 個空格分隔，行首尾不得有多余空格，
當大本營被攻陷時，游戲即刻結束，此時應輸出結束時的地圖狀態，并且在最后一行輸出一句 Game Over，
輸入樣例 1：
7 5 17
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
輸出樣例 1：
0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 -1 0
0 0 0 2 0
0 8 0 9 0
樣例說明：
地圖布局如下圖所示，
規模為 13 和 8 的兩隊僵尸都有兩種選擇，攻打藍色或者紫色堡壘都是消耗最少的，在這種情況下，規模為 13 的僵尸隊走藍色比較快，需要 1+1+1+2+4+2=11 秒到達大本營邊上；規模為 8 的僵尸隊走紫色比較快，需要 1+2+5=8 秒到達大本營邊上，
規模為 4 的僵尸隊比較慘，只能選擇綠色堡壘，最后被大本營邊上的綠色堡壘消滅，注意到在攻擊程序中，其實它們可以等到紫色堡壘被攻陷之后走紫色原始值為 4 的方格，但是因為路徑是在初始狀態下選定就不能改的，所以它們不能這樣選擇，
攻打大本營時，規模為 8 的僵尸隊剩下了 3 只先到達，在第 11 秒被大本營消滅，此時大本營還剩 7 個單位的防御值，同時規模為 13 的僵尸隊剩下的 8 只進入了大本營相鄰的方格，開始攻擊，但此時距離本輪結束只剩 6 秒，結果大本營在結束時還剩 1 個單位的防御值，玩家勝，
輸入樣例 2：
7 5 20
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
輸出樣例 2：
0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 0 0
0 0 0 2 0
0 8 0 9 0
Game Over題解:
最開始以為是簡單的bfs，然后發現題目中有個很關鍵的點，所有的僵尸隊都會根據進攻開始時的地圖選擇被殲滅最少的到達大本營的路線，并且一直按照這個路線行進，
中途不因為地圖狀態的改變而改變，當這樣的進攻路徑不唯一時，選擇能最快到達大本營的路徑，題目保證這樣的路徑所打掉的堡壘的布局是唯一的，
也就是說行經路線是一開始就定好的，所以不用寬搜，所以考慮spfa和dij的做法，由于這倆都是單源最短路，所以考慮反向從大本營開始跑spfa， dis[i][0]代表破壞堡壘和移動的總消耗的最短路徑，dis[i][1]代表僅破壞堡壘的總消耗的最短路徑，然后我們對于每個網格點，記錄是哪一個最小損失僵尸的點更新的他就行了，
最后按照這個路徑進行模擬就行，
大致思路就是這樣，但是天梯賽的資料真的好多坑，，，不想改了，，，
下面附上一個23分的代碼
// #include<bits/stdc++.h> using namespace std; #define maxn 610938 #define inf 1290311 int n,m,t; struct no { int x,y,nowtime,shu; }; map<pair<int,int> ,pair<int,int>>mp; int mapp[200][200]; queue<no>Q; int dx[6]={1,-1,0,0}; int pre1[200]; int pre2[200]; int dy[6]={0,0,1,-1}; int mark[200][200]; int tx,ty; int dis[200][200][2]; void bfs() { dis[tx][ty][0]=0; dis[tx][ty][1]=0; memset(mark,0,sizeof(mark)); queue<pair<int,int> >K; K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][0]>dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][0]=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]; if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } memset(mark,0,sizeof(mark)); K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][1]>dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][1]=dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } else { if(dis[x+dx[i]][y+dy[i]][1]==dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { if(dis[x+dx[i]][y+dy[i]][0]<=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]])continue; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } } } int main() { cin>>n>>m>>t; for(int i=1;i<=n+2;i++) for(int j=1;j<=m+2;j++) { { dis[i][j][0]=inf; dis[i][j][1]=inf; } cin>>mapp[i][j]; if(i==1||i==n+2||j==1||j==m+2) { if(!mapp[i][j]) continue; if(i==1&&(j==1||j==m+2))continue; if(i==n+2&&(j==1||j==m+2))continue; for(int k=0;k<4;k++) { if(i+dx[k]>=2&&j+dy[k]>=2&&i+dx[k]<=n+1&&j+dy[k]<=m+1) { Q.push(no{i+dx[k],j+dy[k],0,mapp[i][j]}); } } } if(mapp[i][j]<0) { tx=i; ty=j; } } int fla=0; bfs(); while(Q.size()) { no tmp=Q.front(); Q.pop(); int x=tmp.x; int y=tmp.y; int pret=1+mapp[x][y]; int num=tmp.shu; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; continue; } while(!(x==tx&&y==ty)) { pair<int,int>R; R=mp[make_pair(x,y)]; x=R.first; y=R.second; if(mapp[x][y]) { if(x==tx&&y==ty)continue; pret=pret+1+mapp[x][y]; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; break; } } else { if(x==tx&&y==ty)continue; pret++; } } if(x==tx&&y==ty) { int w=max(0,min(t-pret,num)); mapp[tx][ty]+=w; mapp[tx][ty]=min(mapp[tx][ty],0); if(mapp[tx][ty]==0) { fla=1; } } } for(int i=2;i<=n+1;i++) for(int j=2;j<=m+1;j++) { if(j==2) cout<<mapp[i][j]; else { cout<<" "<<mapp[i][j]; if(j==m+1&&i!=n+1) cout<<endl; } } if(fla==1) { cout<<endl; cout<<"Game Over"; } }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/550423.html
標籤：其他
上一篇：對JSP（Java Server Pages）的一些理解
下一篇：計算機網路高頻面試八股文