目錄

寫在前面

7-1 懂得都懂

題目

輸入格式:

輸出格式:

輸入樣例:

輸出樣例:

題意

思路

代碼

7-2 芬蘭木棋

題目

輸入格式:

輸出格式:

輸入樣例:

輸出樣例:

題意

思路

代碼

7-3 打怪升級

題目

輸入格式:

輸出格式:

輸入樣例:

輸出樣例:

題意

思路

代碼

7-4 疫情防控

題目

輸入格式:

輸出格式:

輸入樣例:

輸出樣例:

題意

思路

代碼

反思

寫在前面

這是一個新的比賽，上周六考了4個題，雖然晉級了后面的比賽，但是情況很不理想，我覺得進入最后的決賽有點危險了，補一下這四個題，我覺得挺好的，正好反思反思自己，

雖然說這是天梯賽L2的難度，但是我當時考試的時候感覺并不好，只A了第一個題，覺得應該是L3的難度，但是自己后面補題發現沒有到L3難度，大概在L2-L3之間，總的來看，第一題A了，第二題17分，不知道哪里寫錯了，后面補題也wa了一個點（好多人都是沒有A），第三題是圖論，我當時看錯題了，只有16分，跑dij也不至于16分，第四題當時暴力dfs只有1分，很離譜，有的點竟然是wa...后面大佬們教了教正解如何去寫，

7-1 懂得都懂

題目

眾所周知，在互聯網上有很多話是不好直接說出來的，不過一些模糊的圖片仍然能讓網友看懂你在說什么，然而對這種言論依然一定要出重拳，所以請你實作一個簡單的匹配演算法，

現在我們采集了原圖的一些特征資料，由 N 個小于 255 的非負整陣列成，假設對于給定的若干張由 Mi? 個同樣小于 255 的非負整陣列成的新圖的特征資料，每個資料都可以由原圖中任意四個不同資料的平均值計算而來，則稱新圖為原圖的相似圖片，對于給出的資料，請你判斷是不是相似圖片，

注意，不同資料指的并非是資料的值不同，而是不能取同一個資料多次，對于兩個相同值的資料，如果給出兩次，則可以取兩次，

輸入格式:

輸入第一行是兩個整數 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原圖的特征資料個數和新圖的張數，

接下來一行為 N 個小于 255 的非負整數，表示原圖的特征資料，

最后的 K 行，每行第一個數是 Mi? (1 ≤ Mi? ≤ 200)，表示新圖的特征資料個數，然后是 Mi? 個小于 255 的非負整數，表示新圖的特征資料，

輸出格式:

對于每一張新圖，如果為相似圖片，則在一行中輸出 Yes，否則輸出 No，

輸入樣例:

5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11

輸出樣例:

Yes
No
Yes

題意

給出n個數，n小于等于50，有k個詢問，每個詢問里有若干個數字x，問是否能用一開始n個數中不同下標的4個數字來表示4*x

思路

考試的時候，一個簡單題目被寫成這個樣子，真的很讓人炸心態（吐槽一下）

因為n不大，我們可以用dfs模擬所有情況出來，大致就是50個里面選4個嘛，C(50,4)，時間復雜度不大，然后存下來表示可以組成這個數字，最后在詢問的時候判斷是否可以即可

代碼

const int N = 51;
int n,m,a[N],k,x;
unordered_map<int,int> mp;
inline void dfs(int x,int num,int sum)
{
    if (num==4) 
    {
        mp[sum]=1;
        return;
    }
    for (int i=x+1;i<=n+num-3;i++)
        dfs(i,num+1,sum+a[i]);
}
inline void Case_Test()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    dfs(0,0,0);
    while (m--)
    {
        cin>>k;
        bool boo=true;
        for (int i=1;i<=k;i++)
        {
            cin>>x;
            if (mp[x*4]) continue;
            boo=false;
        }
        if (boo) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

7-2 芬蘭木棋

題目

芬蘭木棋（M?lkky，又稱芬蘭木柱）是源自芬蘭的一項運動，哲哲將這個運動改造成了賽博朋克單人版，現在場上一開始有 N 根立起的小木棋（上面分別標有一個非負整數），哲哲投擲一根大木棋去擊倒這些小木棋以獲得分數，分數規則如下：

• 如果僅擊倒 1 根木棋，則得木棋上的分數，
• 如果擊倒 2 根或以上的木棋，則只得擊倒根數的分數，（例如擊倒 5 根，則得 5 分，）

哲哲固定站在 (0,0) 點上，四周放著若干個小木棋 (Xi?,Yi?)，坐標均為整數，每次哲哲可以朝一個方向扔出大木棋，大木棋會打倒這個方向上離哲哲最近的 k 個小木棋，哲哲游戲水平很高超，所以這個 k 可以自由控制，

請問哲哲最多能拿多少分，在獲得最多分數的情況下最少需要扔出多少次大木棋？

規則與真實規則有較大出入，真實游玩時請以國際莫爾基組織的規則為準

輸入格式:

輸入第一行是一個正整數 N (1 ≤ N ≤ )，表示場上一開始有 N 個木棋，

接下來 N 行，每行 3 個整數 Xi?,Yi?,Pi?，分別表示木棋放置在 (Xi?,Yi?)，木棋上的分數是 Pi?，坐標在 32 位整數范圍內，分數為小于等于 1000 的正整數，

保證 (0,0) 點沒有木棋，也沒有木棋重疊放置，

輸出格式:

輸出一行兩個數，表示最多分數以及獲得最多分數最少需要投擲大木棋多少次，

輸入樣例:

11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999

輸出樣例:

1022 9

題意

給出n個數，每個數在(Xi,Yi)的位置，有著Pi的得分，我們每次站在原點(0,0)往一個方向扔一個大木棋，可以讓它在任何一個地方停，問得分最大是多少，然后問最少需要投多少次，

得分規則有兩種：

• 如果僅擊倒 1 根木棋，則得木棋上的分數，
• 如果擊倒 2 根或以上的木棋，則只得擊倒根數的分數，（例如擊倒 5 根，則得 5 分，）

思路

題目一開始寫的是非負整數，我把0也考慮進去了，比如一個方向只有0，那么就不需要扔，然后如果有{1,0,0,0,1}情況等等...但是按道理來講沒有什么影響，應該還能多幾分的，

這個題很顯然需要把它劃分成很多部分，按照斜率來，每一個斜率有一個vector容器來存位置和Pi得分值，但是這是無序的，所以我們需要對每個vector容器sort一遍，然后開始掃，如果碰到連續的1的話，就不需要多扔一次，按照這個思路可以簡化成如下的：

很明顯，ans1就是Pi的和，因為題目要求是最大的，那么ans2首先就是n（n個物體扔n次），如果對于掃的時候有連續的1，那么就ans2--，因為可以少一次，

對于每一個斜率k，我是用map來存它是第幾條，實際上可以用pair來存分子和分母，因為可能有精度問題（但是這個題應該沒有問題，有人這么寫還是wa掉一個點），

注意的是同一個斜率不是有兩個方向嘛，但是一個從0,1,2,...,+oo，一個從0,-1,-2,...,-oo，排序的方式不一樣，我是用兩個vector來區分，

代碼

const int N = 1e6+7;
vector<pair<ll,ll> > v3,v4;
vector<pair<ll,ll> > v1[N],v2[N];
unordered_map<double,int> mp1,mp2;
int cnt1,cnt2,n,w;
double k,x,y;
ll ans1,ans2;
inline void Case_Test()
{
    cin>>n;
    ans2=n;
    for (int i=1;i<=n;i++)
    {
        cin>>x>>y>>w;
        ans1+=w;
        if (x==0)
        {
             if (y>0) v3.push_back({y,w});
             else v4.push_back({-y,w});
             continue;
        }
        k=y*300/x;
        if (y>0)
        {
            if (!mp1[k]) mp1[k]=++cnt1;
            v1[mp1[k]].push_back({y,w});
        }
        else
        {
            if (!mp2[k]) mp2[k]=++cnt2;
            v2[mp2[k]].push_back({-y,w});
        }
    }
    for (int i=1;i<=cnt1;i++)
    {
        sort(v1[i].begin(),v1[i].end());
        for (int j=1;j<v1[i].size();j++)
            if (v1[i][j].second==1&&v1[i][j-1].second==1) ans2--;
    }
    for (int i=1;i<=cnt2;i++)
    {
        sort(v2[i].begin(),v2[i].end());
        for (int j=1;j<v2[i].size();j++)
            if (v2[i][j].second==1&&v2[i][j-1].second==1) ans2--;
    }
    for (int i=1;i<v3.size();i++) 
        if (v3[i].second==1&&v3[i-1].second==1) ans2--;
    for (int i=1;i<v4.size();i++)
        if (v4[i].second==1&&v4[i-1].second==1) ans2--;
    cout<<ans1<<" "<<ans2;
}

7-3 打怪升級

題目

很多游戲都有打怪升級的環節，玩家需要打敗一系列怪獸去贏取成就和徽章，這里我們考慮一種簡單的打怪升級游戲，游戲規則是，給定有 N 個堡壘的地圖，堡壘之間有道路相連，每條道路上有一只怪獸把守，怪獸本身有能量，手里的武器有價值，打敗怪獸需要的能量等于怪獸本身的能量，而怪獸一旦被打敗，武器就歸玩家所有 —— 當然繳獲的武器價值越高，玩家就越開心，

你的任務有兩件：

• 幫助玩家確定一個最合算的空降位置，即空降到地圖中的某個堡壘，使得玩家從這個空降點出發，到攻下最難攻克（即耗費能量最多）的那個堡壘所需要的能量最小；
• 從這個空降點出發，幫助玩家找到攻克任意一個其想要攻克的堡壘的最省能量的路徑，如果這種路徑不唯一，則選擇沿途繳獲武器總價值最高的解，題目保證這種解是唯一的，

輸入格式:

輸入第一行給出兩個正整數 N (≤1000) 和 M，其中 N 是堡壘總數，M 是怪獸總數，為簡單起見，我們將堡壘從 1 到 N 編號，隨后 M 行，第 i 行給出了第 i 只怪獸的資訊，格式如下：

B1 B2 怪獸能量 武器價值

其中 B1 和 B2 是怪獸把守的道路兩端的堡壘編號，題目保證每對堡壘之間只有一只怪獸把守，并且 怪獸能量 和 武器價值 都是不超過 100 的正整數，

再后面是一個正整數 K（≤N）和玩家想要攻克的 K 個目標堡壘的編號，

輸出格式:

首先在一行中輸出玩家空降的堡壘編號 B0，如果有多種可能，則輸出編號最小的那個，

隨后依次為玩家想要攻克的每個堡壘 B 推薦最省能量的攻克路徑，并列出需要耗費的能量值和沿途繳獲武器的總價值，注意如果最省力的路徑不唯一，則選擇沿途繳獲武器總價值最高的解，格式為：

B0->途經堡壘1->...->B
總耗費能量 武器總價值

輸入樣例:

6 12
1 2 10 5
2 3 16 20
3 1 4 2
2 4 20 22
4 5 2 2
5 3 12 6
4 6 8 5
6 5 10 5
6 1 20 25
1 5 8 5
2 5 2 1
2 6 8 5
4
2 3 6 5

輸出樣例:

5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0

題意

看題吧...圖論題

思路

跑一遍Floyd可以得出我們選擇的那個點s，然后再跑一遍得到到詢問的路徑最小的，然后武器最大的，注意Floyd是如何存路徑的

代碼

const int N = 1007;
int u,v,n,m,g[N][N],w[N][N],temp,s,x;
int path[N][N],dist[N][N];
inline void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if (dist[i][k]+dist[k][j]<dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j],path[i][j]=k,g[i][j]=g[i][k]+g[k][j];
                if (dist[i][k]+dist[k][j]==dist[i][j]&&g[i][k]+g[k][j]>g[i][j])
                    path[i][j]=k,g[i][j]=g[i][k]+g[k][j];
            }
}
inline void output(int i,int j)
{
    if(i==j) return;
    if(path[i][j]==0) cout<<"->"<<j;
    else
    {
        output(i,path[i][j]);
        output(path[i][j],j);
    }
}

inline void Case_Test()
{
    cin>>n>>m;
    memset(w,0x7f/3,sizeof(w));
    memset(g,0,sizeof(g));
    memset(dist,0x7f/3,sizeof(dist));
    for (int i=1;i<=n;i++) w[i][i]=g[i][i]=0;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>u>>v>>x>>y;
        dist[u][v]=dist[v][u]=x;
        w[v][u]=w[u][v]=x;
        g[v][u]=g[u][v]=y;
    }
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (w[i][j]>w[i][k]+w[k][j])
                    w[i][j]=w[i][k]+w[k][j];
    /*for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            cout<<w[i][j]<<" ";
        cout<<endl;
    }*/
    temp=inf;
    for (int i=1;i<=n;i++)
    {
        int tmp=-1;
        for (int j=1;j<=n;j++)
        {
            if (i==j) continue;
            if (w[i][j]>tmp) tmp=w[i][j];
        }
        if (tmp<temp) temp=tmp,s=i;
    }
    cout<<s<<endl;
    floyd();
    cin>>m;
    while (m--)
    {
        cin>>x;
        cout<<s;
        output(s,x);
        if (s==x) cout<<"\n0 0\n";
        else
        cout<<endl<<dist[s][x]<<" "<<g[s][x]<<endl;
    }
}

ps：我不知道為什么s==x的時候會出錯...不是0，0

7-4 疫情防控

題目

疫情尚未結束，嚴防疫情反復，為了做好疫情防控作業，國內設定了地區風險等級，對于中高風險地區的人員采取限制移動、居家隔離等手段，

為了研究疫情防控對于跨地區交通運輸的影響，假設現在有 N 個機場，M 條航線，每天都會新增一個防控地區，一個防控地區會導致一個機場無法正常運作，航線也自然無法正常運行，每天會有 Qi? 對旅客從 Xi? 機場前往 Yi? 機場，請計算有多少對旅客會受到影響無法完成行程，

旅客只要能直達或通過若干次中轉，且乘坐的所有航線的出發和到達機場都正常運作，即視作可完成行程，

輸入格式:

輸入第一行是三個整數 N,M,D (1≤N≤5×104, 1≤M≤2×105, 1≤D≤103), 表示機場數、航線數以及新增防控地區的天數，

接下來首先有 M 行，每行給出空格分隔的兩個數字 A 和 B，表示編號為 A 和 B 的機場之間有一條航線，航線是雙向的，機場編號從 1 到 N，

然后是 D 塊輸入，每塊輸入內第一行為空格分隔的兩個整數 C 和 Q （1≤Q≤103)，表示新增機場編號為 C 所在的城市為防控地區，今天有 Q 段行程，資料保證新增的城市之前一定不是防控地區，

接下來的 Q 行，每行是空格分隔的兩個數字 X 和 Y，表示編號為 X 和 Y 的機場的一段行程，行程有可能包括之前就已經成為防控地區的城市，

輸出格式:

對于每天的詢問，請在一行中輸出在新增了一個防控地區后當天的行程有多少不能成行，

輸入樣例:

5 5 3
1 2
1 3
1 5
2 5
3 4
4 3
1 3
1 4
2 3
5 3
3 4
2 3
3 5
1 3
2 3
2 5
3 4

輸出樣例:

1
2
3

題意

給出一個無向圖，有D次，依次關閉當前節點，每次都有若干個詢問問你x,y是否還是連接的，

思路

用并查集的思想，

這個題實在是沒有想到反向，將輸入全部讀入存下來，反向開始加入，這樣就只需要一遍，處理完當前的就去一次加入看是否能加，然后以此類推，

一開始要注意，把所有無論如何都滿足的條件的邊加入，

代碼

const int N =2e5+7;
int father[N];
inline int find(int x)
{
    return father[x]==x?x:father[x]=find(father[x]);
}
struct node
{
    int to,next,x;
}edge[N<<1];
int head[N],cnt;
vector<int> que,ans;
inline void add(int x,int to)
{
    edge[++cnt].next=head[x];
    edge[cnt].x=x;
    edge[cnt].to=to;
    head[x]=cnt;
}
int n,m,d,x,y,c,q,fx,fy;
vector<pair<int,int> > v[1007];
bool vis[N];
inline void Case_Test()
{
    cin>>n>>m>>d;
    for (int i=1;i<=n;i++) father[i]=i;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y);add(y,x);
    }
    for (int i=1;i<=d;i++)
    {
        cin>>c>>q;
        que.push_back(c);
        vis[c]=1;
        for (int j=1;j<=q;j++)
        {
            cin>>x>>y;
            v[i].push_back({x,y});
        }
    }
    for (int i=1;i<=cnt;i++)
    {
        x=edge[i].x;
        y=edge[i].to;
        //cout<<i<<" "<<x<<" "<<y<<endl;
        if (!vis[x]&&!vis[y])
        {
            fx=find(x);fy=find(y);
            if (fx!=fy) father[fy]=fx;
        }
    }
    for (int i=d;i>=1;i--)
    {
        c=que[i-1];q=v[i].size();
        cnt=0;
        for (auto p:v[i])
        {
            x=p.first;y=p.second;
            fx=find(x);fy=find(y);
            if (fx!=fy) cnt++;
        }
        ans.push_back(cnt);
        x=c;
        for (int j=head[x];j;j=edge[j].next)
        {
            y=edge[j].to;
            if (vis[y]) continue;
            fx=find(x);fy=find(y);
            if (fx!=fy) father[fy]=fx;
        }
        vis[c]=0;
    }
    for (int i=ans.size()-1;i>=0;i--)
        cout<<ans[i]<<endl;
}

反思

下次考試要好好考，爭取進入最后的決賽，

這幾個題提醒我有的時候反過來考慮能使問題簡單化，還有Floyd如何去存路徑，對于圖論這方面做的題目還是太少了，因為隊里有個大佬，我就一直不負責圖論部分...