1、智能紅綠燈

為了最大化通行效率同時照顧老年人穿行馬路，在某養(yǎng)老社區(qū)前，某科技公司設(shè)置了一個智能紅綠燈。

這個紅綠燈是這樣設(shè)計的：

路的兩旁設(shè)置了一個按鈕，老年人希望通行馬路時會按下按鈕；
在沒有人按按鈕的時候，紅綠燈一直為綠燈；
當(dāng)紅綠燈為綠燈時，有人按下按鈕，第一次按下按鈕的 15 秒后綠燈會轉(zhuǎn)紅；
轉(zhuǎn)紅后，紅燈會持續(xù) 30 秒，方便老年人穿行馬路；
在 30 秒的紅燈期間，假如有人再次按下按鈕，則紅燈會再延續(xù) 15 秒；
延續(xù)一次后不會再次延續(xù)。
現(xiàn)在給定按鈕被按下的時間點，請你輸出這個智能紅綠燈的紅燈時間區(qū)間。

注意：我們假設(shè)同一秒內(nèi)，紅綠燈先變化，然后按鈕再被按下。每 1 秒理解為一個時間點。例如：在第 1 秒按下按鈕，則第 16 秒開始變紅；如果沒有人在第 16 - 45 秒這個閉區(qū)間內(nèi)按下按鈕，則到第 46 秒開始變綠。而在第 46 秒按下按鈕的人，需要等 15 秒后才有紅燈。

輸入格式:
輸入第一行為 N (1≤N≤1000)，表示按鈕被按下的次數(shù)。

接下來一行 N 個非負整數(shù)，表示按鈕被按下的時間點。一個時間點按鈕有可能會被多次按下，給出的時間點保證是不遞減的。

時間點的范圍不超過 10
4
。

輸出格式:
輸出若干行，按起始時間從小到大輸出互不相交的紅燈的時間區(qū)間。

輸入樣例:
10
3 4 5 6 33 45 49 70 90 100
輸出樣例:
18 62
85 129
代碼長度限制
16 KB
時間限制
400 ms
內(nèi)存限制
64 MB

題意：

• 模擬題

思路：文章來源地址http://www.zghlxwxcb.cn/news/detail-583714.html

• 枚舉每次按下按鈕的時間， 維護區(qū)間數(shù)組表示紅燈對應(yīng)的時間段，根據(jù)題目規(guī)則修改即可。

//T1, AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn];
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    vector<pair<int,int> >vc;
    int l = a[1]+15, r = a[1]+15+30-1, ok = 0;
    for(int i = 2; i <= n; i++){
        if(a[i]<=r && a[i]>=l){
            if(ok==0){
                r += 15;
            }
            ok = 1;
        }else{
            if(a[i]>r){
                ok = 0;
                if(vc.empty() || vc.back()!=make_pair(l,r))vc.push_back(make_pair(l,r));
                l = a[i]+15;
                r = a[i]+15+30-1;
            }
        }
    }
    vc.push_back(make_pair(l,r));
    for(auto x:vc){
        cout<<x.first<<" "<<x.second<<"\n";
    }
    return 0;
}

2、女王的大敕令

副本是游戲里的一個特色玩法，主要為玩家?guī)硌b備、道具、游戲資源的產(chǎn)出，滿足玩家的游戲進程。

在 MMORPG《最終幻想14》里，有一個攻略人數(shù)最大達到 48 人的副本“零式貢希爾德神廟”，其中守關(guān) BOSS “天佑女王”有一個很有趣的技能：“女王的大敕令”。

技能在一個 5×5 的棋盤上展開。每位玩家根據(jù)給定的兩個步長，從某個方格出發(fā)，在棋盤上先走 D
1
?
步，再走 D
2
?
步。其中“步長”指的是曼哈頓距離，即：設(shè)兩個方格的坐標(biāo)分別為 (X
i
?
,Y
i
?
) 以及 (X
j
?
,Y
j
?
)，則這兩個方格的曼哈頓距離 D=∣X
i
?
?X
j
?
∣+∣Y
i
?
?Y
j
?
∣。

例如下圖中的 A 點與 B 點的曼哈頓距離為 5：

image.png

技能開始時，場地外圍會出現(xiàn) 4 只小怪，東南西北（即棋盤的右、下、左、上）方向各出現(xiàn)一只小怪，且小怪一定出現(xiàn)在某行或某列對應(yīng)的位置上。第 i 只小怪會順時針朝固定方向移動 n
i
?
步（題目保證不會移出界，即移動后仍然在對應(yīng)著某行/某列的位置上），且：

北邊的小怪固定向右移動；
東邊的小怪固定向下移動；
南邊的小怪固定向左移動；
西邊的小怪固定向上移動。
小怪出現(xiàn)后，棋盤上還會出現(xiàn)一個發(fā)光的格子，這是玩家移動的目標(biāo)點，如圖所示：

image.png

玩家必須在不被小怪殺死的前提下，按規(guī)定步長，用兩個回合到達目標(biāo)點。技能流程如下：

1、玩家先選擇一個起始方格；

2、東、西兩側(cè)的小怪開始按照固定方向移動，移動完畢后 4 只小怪會同時開展攻擊，其中東、西兩側(cè)的小怪攻擊自己所對應(yīng)的一整行，南、北兩側(cè)的小怪攻擊自己所對應(yīng)的一整列。玩家若處在攻擊區(qū)內(nèi)則任務(wù)失敗。

3、玩家移動 D
1
?
步，到達某個方格；

4、南、北兩側(cè)的小怪開始按照固定方向移動，移動完畢后 4 只小怪會同時開展攻擊，同第 2 步；

5、玩家移動 D
2
?
步，此時必須到達目標(biāo)點，否則任務(wù)失敗。

以下是上面的 4 只小怪都移動后的攻擊范圍的示意圖：

image.png

給定小怪起始位置以及移動步數(shù) n
i
?
和目標(biāo)點位置，請輸出所有安全的移動方案，包括起始點以及第一次移動的目的地。

輸入格式:
輸入第一行是四個數(shù) C
1
?
,C
2
?
,R
1
?
,R
2
?
，分別表示：

北邊（上面）的小怪 1 在第 C
1
?
列的位置上；
南邊（下面）的小怪 2 在第 C
2
?
列的位置上；
西邊（左邊）的小怪 3 在第 R
1
?
行的位置上；
東邊（右邊）的小怪 4 在第 R
2
?
行的位置上。
輸入第二行是四個數(shù) n
i
?
（i=1,?,4），按照上面的順序給出小怪移動的步數(shù)，保證小怪移動后仍然處于某行或某列對應(yīng)的位置上。

輸入第三行是四個數(shù) row,col,D
1
?
,D
2
?
，依次表示目標(biāo)點的位置，以及玩家要走的兩個步長。這里某方格的“位置” (row,col) 指的是該方格的行號、列號組成的二元組。

我們假設(shè)左上角的方格位置為 (1, 1)。

輸出格式:
輸出安全移動的方案，方案由兩個位置共四個數(shù)組成，前兩個數(shù)為初始選擇的方格的位置，后兩個數(shù)為第一次停留的位置。

對于多個方案的情況，先按初始方格位置從小到大輸出，初始方格相同時按第一次停留位置從小到大輸出。一個坐標(biāo) (r
i
?
,c
i
?
) 比另一個坐標(biāo) (r
j
?
,c
j
?
) 小，當(dāng)且僅當(dāng) r
i
?
<r
j
?
，或 r
i
?
=r
j
?
的同時有 c
i
?
<c
j
?
。

輸入樣例:
2 4 4 2
1 2 3 2
5 3 3 4
輸出樣例:
2 1 2 4
2 3 3 1
2 3 3 5

題意：

• 模擬題

思路：

• 地圖大小只有5*5，因此可以直接四層循環(huán)暴力枚舉起點的位置和第一次轉(zhuǎn)彎的位置，然后判斷一下是否會被攻擊到即可。

//T2, AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
typedef pair<int,int> PII;
int c[5], cc[5];  //上下左右
int getd(int x1, int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}
int main(){
    int n = 5;
    for(int i = 1; i <= 4; i++)cin>>c[i];
    for(int i = 1; i <= 4; i++){
        cin>>cc[i];
        // int x = cc[i];
        // if(i==1||i==4)c[i]+=x;//上右
        // if(i==2||i==3)c[i]-=x;//下左
    }
    vector< pair<PII,PII> >vc;
    int ex, ey, d1, d2;  cin>>ex>>ey>>d1>>d2;
    for(int x1 = 1; x1 <= n; x1++){
        for(int y1 = 1; y1 <= n; y1++){
            for(int x2 = 1; x2 <= n; x2++){
                for(int y2 = 1; y2 <= n; y2++){
                    if(getd(x1,y1,x2,y2)==d1 && getd(x2,y2,ex,ey)==d2){
                        //左右攻擊初始位置
                        if(x1==c[3]-cc[3] || x1==c[4]+cc[4] || y1==c[1] || y1==c[2]){
                            continue;
                        }
                        //上下攻擊第一次位置
                        if(y2==c[1]+cc[1] || y2==c[2]-cc[2] || x2==c[3]-cc[3] || x2==c[4]+cc[4]){
                            continue;
                        }
                        vc.push_back({{x1,y1},{x2,y2}});
                    }
                }
            }
        }
    }
    for(auto x : vc){
        cout<<x.first.first<<" "<< x.first.second<<" "<<x.second.first<<" "<<x.second.second<<"\n";
    }
    return 0;
}

3、戰(zhàn)利品分配

在某個戰(zhàn)爭游戲中，多個玩家組成一個大型軍團，攻下若干城池，并獲得戰(zhàn)利品。

具體而言，游戲中有 N 個城市，并以 M 條長度為 1 的無向道路連接，玩家們組成的軍團從 S 號城市開始進攻，目的地是 T 號城市，每個城市攻下后的戰(zhàn)利品價值為 p
i
?
。

為了合理地分配戰(zhàn)利品，軍團們定下了規(guī)矩：假設(shè)軍團里有 K 位玩家，那么從 S 號城市開始，第 1 個攻下的城市分配給第 1 位玩家，第 2 個攻下的分配給第 2 位玩家，……，第 K 個攻下的分配給第 K 位玩家，第 K+1 個攻下的則重新開始計算，分配給第 1 位玩家，以此類推。

軍團很強，路上所有的城市都可以輕松進攻下來。你作為軍團的指揮，可以指定玩家的進攻路線。但玩家們都希望盡快結(jié)束游戲，因此 S 到 T 的距離必須是最短的。你需要做的是在最短距離的限制下選擇對自己最好的線路，獲得盡可能高的戰(zhàn)利品價值。請輸出你的答案。

輸入格式:
輸入第一行是四個數(shù) N,M,K,P (1≤N,M≤10
5
,1≤K≤10
4
,1≤P≤K)，表示城市數(shù)量（于是城市從 1 到 N 編號）、連接道路數(shù)量以及你在軍團中的 K 位玩家中排第 P 位（即你戰(zhàn)利品分配在第 P 位）。

第二行是 N 個被空格隔開的非負整數(shù)，第 i 個數(shù)對應(yīng) p
i
?
(0≤p
i
?
≤10
4
)，表示編號為 i 的城市的戰(zhàn)利品價值（i=1,?,N）。

然后的 M 行，每行給出兩個用空格分隔的正整數(shù) U 和 V，表示編號為 U 和 V 的城市之間有道路連接。

最后的一行是兩個正整數(shù) S,T，表示開始的城市編號與目的地的城市編號。開始和目的地的城市也是可以進攻并獲取戰(zhàn)利品的。

輸出格式:
輸出一行，表示你可以取得的最大價值。

輸入樣例:
9 11 2 2
100 150 130 50 30 20 200 0 70
1 2
1 3
2 3
2 4
2 5
3 6
4 7
5 7
6 8
7 9
8 9
1 9
輸出樣例:
350

• 樣例圖
  

題意：

• n個點，m條權(quán)為1的無向邊，從S出發(fā)到T。
• 每個點有個價值pi，軍團里有K個人，你的排名為P，如果第i個走到的城市滿足i%K=P，那么可以獲得對應(yīng)點的價值pi，求滿足最短路的前提下，最大化能獲得的價值。

思路：

• 乍一看S到T最短路，多維護一個最大點權(quán)，DIjkstra秒。 畢竟PTA，PAT，天梯，Robocom都喜歡出這種題，然后無腦往上敲，敲完樣例沒過，咋只有120

• 重新考慮一下限制條件，起點，終點固定了，最短路長度其實也固定了，也就是說，在滿足上述條件的情況下，最大化中途經(jīng)過的第P+i*K個點的權(quán)值之和，不考慮效率的情況下，我們可以再跑一遍bfs，統(tǒng)計所有路徑的價值之和。

• 那么再優(yōu)化一下效率，其實Dijkstra是個多余的存在，因為bfs本身也可以找最短路，所以只要跑一遍bfs，邊找最短距離邊記錄自己沿途獲得的價值即可。

• 賽后補題的時候發(fā)現(xiàn)我賽時寫的Dijkstra是對的（無語了，繞了一大圈重寫bfs）。
  單個Dijk其實跟bfs一樣，多維護一個數(shù)組表示到達i能拿到的最大價值即可，轉(zhuǎn)移的時候一起更新即可。 當(dāng)時錯是因為初始值 考慮第i個點而不是第i條邊時，起點步數(shù)初始化沒改成1，所以WA的。。。ohhh是我sb

//3, Dij, AC
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int maxn = 1e5+10, inf = 1e9+7;

int n, m, k, p, w[maxn];
int check(int x){ return (x>=p && (x-p)%k==0); }  //當(dāng)前這步是拿得到的

vector<int>G[maxn];
int st, ed;
int dist[maxn], vis[maxn];
int dd[maxn];                          //維護到第i個點位置能拿到的最大價值
void Dijkstra(){
    for(int i = 0; i <= n; i++){dist[i] = inf; vis[i] = 0; }
    dist[st] = 1;                      //WA：因為是第i個點，不是邊，所以起點要+1，（賽時1分版）
    priority_queue<PII,vector<PII>, greater<PII> > q;
    q.push({1,st});
    while(!q.empty()){
        PII t = q.top();  q.pop();
        if(vis[t.second])continue;
        vis[t.second] = 1;
        for(int to : G[t.second]){
            if(dist[to] > dist[t.second]+1){
                dist[to] = dist[t.second]+1;
                if(check(dist[to]))dd[to] = dd[t.second]+w[to];
                else dd[to] = dd[t.second];
                q.push({dist[to],to});
            }else if(dist[to] == dist[t.second]+1){
                if(dd[t.second]>dd[to]){
                    dd[to] = dd[t.second];
                    q.push({dist[to],to});
                }
            }
        }
    }
}

int main(){
    cin>>n>>m>>k>>p;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= m; i++){
        int u,v ;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>st>>ed;
    Dijkstra();
    if(p==1)dd[ed] += w[st];  //p==1的時候，可以多拿到一個起點的價值
    cout<<dd[ed]<<'\n';
    return 0;
}

//3, Dij+bfs, AC
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int maxn = 1e5+10, inf = 1e9+7;

int n, m, k, p, w[maxn];

//Dijkstra找最短路
vector<int>G[maxn];
int st, ed, dist[maxn], vis[maxn];
void Dijkstra(){
    for(int i = 0; i <= n; i++){dist[i] = inf; vis[i] = 0; }
    dist[st] = 1;
    priority_queue<PII,vector<PII>, greater<PII> > q;
    q.push({0,st});
    while(!q.empty()){
        PII t = q.top();  q.pop();
        if(vis[t.second])continue;
        vis[t.second] = 1;
        for(int to : G[t.second]){
            if(dist[to] > dist[t.second]+1){
                dist[to] = dist[t.second]+1;
                q.push({dist[to],to});
            }
        }
    }
}

//bfs找最大價值
int val[maxn];  //到點i的最大價值
void bfs(){
    for(int i = 0; i <= n; i++){val[i] = -inf; vis[i] = 0; }
    queue<int>q;
    q.push(st);
    val[st] = 0;  vis[st] = 1;
    while(q.size()){
        int t = q.front();  q.pop();
        if(dist[t]>=p && (dist[t]-p)%k==0){
            val[t] += w[t];
        }
        if(t==ed)break;
        for(int to : G[t]){
            if(dist[to]>dist[t] && val[to]<val[t]){
                val[to] = val[t];
            }
            if(!vis[to]){
                vis[to] = 1;
                q.push(to);
            }
        }
    }
}

int main(){
    cin>>n>>m>>k>>p;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= m; i++){
        int u,v ;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>st>>ed;
    Dijkstra();
    // cout<<dist[ed]<<"\n";
    bfs();
    cout<<val[ed]<<"\n";
    return 0;
}

//3, bfs, AC
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int maxn = 1e5+10, inf = 1e9+7;

int n, m, k, p, w[maxn], st, ed, ans;

//bfs找最短路（維護當(dāng)前獲得的價值）
vector<int>G[maxn];
int vis[maxn];
struct node{ int u, step, val; };
void bfs(){
    queue<node>q;
    if(p==1)q.push({st, 0, w[st]});  //p==1可以多拿到一個起點的價值
    else q.push({st, 0, 0});
    vis[st] = 1;
    p--;  //方便后面計算
    int res = inf;
    while(q.size()){
        int u = q.front().u, v = q.front().val, dd = q.front().step;  q.pop();
        if(dd > res)break;
        if(u==ed){
            res = dd;
            ans = max(ans, v);
            continue;
        }
        for(int to : G[u]){
            if(vis[to] && to!=ed)continue;
            vis[to] = 1;
            if((dd+1)%k == p)q.push({to, dd+1, v+w[to]});
            else q.push({to, dd+1, v});
        }
    }
}

int main(){
    cin>>n>>m>>k>>p;
    for(int i = 1; i <= n; i++)cin>>w[i];
    for(int i = 1; i <= m; i++){
        int u,v ;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>st>>ed;
    bfs();
    cout<<ans<<"\n";
    return 0;
}

4、變牛的最快方法

shu.png niu.png

這里問的是把任意一種動物的圖像變成牛的方法…… 比如把一只鼠的圖像變換成牛的圖像。方法如下：

首先把屏幕上的像素點進行編號；
然后把兩只動物的外輪廓像素點編號按順時針記錄下來；
用最少的變換次數(shù)將鼠的輪廓變成牛的 —— 這里僅允許對鼠的輪廓進行 3 鐘操作：
插入一個像素編號
刪除一個像素編號
更改一個像素編號
輸入格式：
輸入分別在兩行中給出兩種動物的輪廓像素點編號，編號為 (0,10
6
] 區(qū)間內(nèi)的整數(shù)，允許重復(fù)。輪廓以編號 ?1 結(jié)尾，這個編號不算在輪廓內(nèi)。題目保證每種動物的輪廓包含不超過 1000 個像素點。

輸出格式：
在第一行中輸出從第一只動物變換成第二只動物需要的最少變換次數(shù)。

在第二行中順次描述對第一只動物輪廓的每個像素所作的操作：

如果這個像素被刪除，則在對應(yīng)位置輸出 0
如果這個像素被改變，則在對應(yīng)位置輸出 1
如果這個像素不變，則在對應(yīng)位置輸出 2
如果這個像素前面或者后面插入了一個像素，則在插入的位置輸出 3
答案可能不唯一，輸出任何一種可能的解都可以。行首尾和數(shù)字間均無空格。

輸入樣例：
13 5 6 20 2 20 1 13 9 20 3 28 3 34 6 25 233 -1
3 5 6 20 6 20 3 5 9 3 9 20 3 6 6 25 233 -1
輸出樣例：
8
122212112023121222
樣例解釋：
1、13 更改為 3，隨后 5、6、20 不變
2、2 更改為 6，下一個 20 不變
3、1 更改為 3
4、第二個 13 更改為 5，隨后 9 不變
5、刪除下一個 20，后面的 3 不變
6、在 28 的前面插入 9
7、28 更改為 20，后面的 3 不變
8、34 更改為 6，后面的 6、25、233 不變

題意：

• 給出兩個數(shù)組（n<1000），每次操作允許對第一個數(shù)組進行插入，刪除，修改。
• 求最少操作次數(shù)讓第一個數(shù)組變成第二個數(shù)組，打印操作方案。

思路：

• 有點像最短編輯距離，LCS什么的。反正讓dp[i][j]表示從左往右修改，第一個數(shù)組的i位等于第二個數(shù)組的j位的最小修改方案, bfs轉(zhuǎn)移即可， 把方案記錄下來最后遞歸打印。

//T4, AC
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int maxn = 1010;

vector<int>a, b;
int dp[maxn][maxn], in_q[maxn][maxn], id[maxn][maxn];
PII pre[maxn][maxn];

int main(){
    int x; 
    while(cin>>x && x!=-1)a.push_back(x);
    while(cin>>x && x!=-1)b.push_back(x);

    //dp轉(zhuǎn)移
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;
    queue<PII>q;
    q.push({0,0});
    function<void(int,int,int,int,int,int)>zy = [&](int x, int y, int nx, int ny, int w, int op){
        if(dp[nx][ny] > dp[x][y]+w){
            dp[nx][ny] = dp[x][y]+w; //使用0/1次操作
            pre[nx][ny] = {x,y};     //記錄這個像素從哪里轉(zhuǎn)移來的
            id[nx][ny] = op;         //標(biāo)記這個像素(改變/不改)/(刪除/插入)
            if(!in_q[nx][ny])q.push({nx,ny});
            in_q[nx][ny] = 1;
        }
    };
    while(q.size()){
        int x = q.front().first, y = q.front().second;  q.pop();
        in_q[x][y] = 0;
        if(dp[x][y] > dp[a.size()][b.size()])continue;
        if(x==a.size() && y==b.size())continue;
        if(x<a.size() && y<b.size()){
            if(a[x] != b[y]){
                zy(x,y,x+1,y+1,1,1);     //修改
            }else{
                zy(x,y,x+1,y+1,0,2);     //不改
            }
        }
        if(x<a.size())zy(x,y,x+1,y,1,0); //刪除
        if(y<b.size())zy(x,y,x,y+1,1,3); //增加
    }
    cout<<dp[a.size()][b.size()]<<"\n";
    
    //打印方案
    PII cnt = {a.size(), b.size()};
    vector<int>res;
    while(cnt.first || cnt.second){
        res.push_back(id[cnt.first][cnt.second]);
        cnt = pre[cnt.first][cnt.second];
    }
    reverse(res.begin(),res.end());
    for(int x : res)cout<<x;
    return 0;
}

5、養(yǎng)老社區(qū)

作為智能看護的一部分，你需要評估某個養(yǎng)老社區(qū)是否適合開展智能看護的服務(wù)。

這個養(yǎng)老社區(qū)有若干幢住宅樓，每個住宅樓有一個種類，住宅樓之間由長度為 1 的道路連接，道路都是雙向道路且沒有構(gòu)成環(huán) —— 你可以簡單地認為養(yǎng)老社區(qū)的路構(gòu)成了一棵樹。

假設(shè)我們能找到三個住宅樓，這三個住宅樓兩兩之間的最短距離相等，并且三個住宅樓的種類不一樣，那么我們稱這三個住宅樓組成的三元組為適合智能看護的，指的是為了服務(wù)這三個住宅樓，我們可能可以方便地找到適合建設(shè)服務(wù)中心的地方。一個社區(qū)的適合度指的是能夠找到多少本質(zhì)不同的適合智能看護的住宅樓三元組。

本質(zhì)不同兩個的三元組指的是：三元組內(nèi)元素任意排列后，兩個三元組仍然不相等。

給定這個養(yǎng)老社區(qū)的情況，請你求出這個社區(qū)的適合度。

輸入格式:
輸入第一行是一個正整數(shù) N (1≤N≤2×10
3
)，表示養(yǎng)老社區(qū)里住宅樓的數(shù)量（于是住宅樓從 1 到 N 編號）。

接下來 N?1 行，每行給出空格分隔的兩個正整數(shù) U 和 V，表示編號為 U 和 V 的住宅樓之間有一條長度為 1 的道路。

最后一行給出 N 個數(shù)，第 i 個數(shù)表示編號為 i 的住宅樓的種類為 T
i
?
（1≤T
i
?
≤N）。

保證給定的數(shù)據(jù)會將所有住宅樓連接成一棵完整的樹。

輸出格式:
輸出一行一個正整數(shù)，表示社區(qū)的適合度。

輸入樣例:
11
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
1 11
1 2 3 4 5 6 7 8 9 9 10
輸出樣例:
14

題意：

• 給出一棵樹，每個點有一個種類ti， 如果三個點之間兩兩距離相等且種類都不一樣，那么稱該三元組為舒適的。
• 求對于給定的樹有多少個本質(zhì)不同的三元組。

思路：

• 如果只考慮邊長為1的情況，對于每個點掃一遍直接相連的點，map維護每種種類的個數(shù)，如果種類數(shù)>=3，那就C(x,3)乘所有種類對應(yīng)的點的個數(shù)，可以騙3分。
• 考慮到只有2000個點，不妨大膽一點，開個二維數(shù)組，先來個n^2跑以每個點為根跑n邊dfs，預(yù)處理出任意兩點間的距離e[i][j]（即把圖從鄰接表轉(zhuǎn)為鄰接矩陣）。然后枚舉所有不重復(fù)的三元組（n^3）判斷一下是否本質(zhì)不同，統(tǒng)計一下答案即可。 可以騙26分。
• 最后4分是第5個點dfs超的時，優(yōu)化成bfs可以快一點，就可以過了。

//T5, AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;

vector<int>G[maxn];
int n, t[maxn];

int vis[maxn], e[maxn][maxn];
void bfs(int x){
    queue<int>q;
    q.push(x);
    vis[x] = 1;
    while(q.size()){
        int u = q.front();  q.pop();
        for(int to : G[u]){
            if(vis[to])continue;
            vis[to] = 1;
            e[x][to] = e[x][u]+1;
            q.push(to);
        }
    }
}
inline void dfs(int x, int f, int rt){
    if(f!=-1)e[rt][x] = e[rt][f]+1;
    for(int to : G[x]){
        if(to==f)continue;
        dfs(to,x,rt);
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)e[i][j]=1;
    for(int i = 1; i < n; i++){
        int u,v ;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)cin>>t[i];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)vis[j] = 0;
        bfs(i);
        // dfs(i,-1,i);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            for(int k = j+1; k <= n; k++){
                if(e[i][j]==e[j][k] && e[i][j]==e[i][k]){
                    if(t[i]!=t[j] && t[i]!=t[k] && t[j]!=t[k]){
                        cnt++;
                    }
                }
            }
        }
    }
    cout<<cnt<<"\n";
    return 0;
}

到了這里，關(guān)于2022 RoboCom 世界機器人開發(fā)者大賽-本科組（國賽）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！