P3640 [APIO2013] 出題人 題解

原題鏈接

題意簡述

提交答案題

你是一個出題人，有兩個問題：

• \(\text{SSSP}\)：最短路

  點數不超過 \(300\)，邊權的絕對值小于 \(10^6\)，總邊數不超過 \(5000\)，詢問不超過 \(10\) 次

• \(\text{Mystery}\)：無向圖染色

  點數小于 \(1000\) 且大于 \(70\)，邊數小于 \(10^6\) 且大于 \(1500\)，

對于每個測驗點：

給定源程式 \(A\) 和源程式 \(B\)，需要造一組資料使得源程式 \(A\) 能跑過而源程式 \(B\) 不行且整數個數小于 \(T\)，

一個程式是否能跑過一個問題不在意其答案是否正確，僅關心是否超時

解法

首先我們明確一下每個代碼演算法及其時間復雜度：

注意這里 \(V\) 是點數，\(E\) 是邊數，\(Q\) 是詢問數

point 1

目的

卡 \(\text{Floyd}\)

做法

構造 \(V=101\)

顯然因為要輸出 \(101\) 個點，至少就要 \(101\) 個數，所以我們把每一個點的出度都描述為 \(0\)，

最后詢問只需要一個，問題隨你，這里使用 0 99

共計 \(105\) 個數

code

為了防止抄襲，所有代碼均無 print 函式，望周知，

#include<bits/stdc++.h>
using namespace std;
const int maxv=305,maxq=15;
int V,E,Q;
vector<pair<int,int>> G[maxv];
int s[maxq],t[maxq];
int main(){
    V=101;
    Q=1;
    for(int i=1;i<=Q;i++){
        s[i]=0;
        t[i]=99;
    }
    print();
    return 0;
}

point 2

目的

卡 \(\text{Bellman-Ford}(\Theta(VEQ))\)

且需要讓 \(\text{Floyd}(\Theta(V^3))\) 過

做法

這個點其實看著難卡，實際上不難，

就是要讓 \(V\) 恰好為 \(100\)（讓 \(\text{Floyd}\) 過），便盡量多加，在 \(10\) 次詢問就行了（主要是詢問上限為 \(10\)）

可以去 oi-wiki 上看一下這個演算法的原理，就可以發現如果我們在一條鏈上狂加自環，這個演算法就會被卡飛，

最后的詢問要按照你建邊的方向，否則卡不掉，

最后算一下邊能放多少邊：\(E_{\max}=\frac{2222(T)-1(V)-100(出度)-1(Q)-2\times10(詢問)}{2(點編號及權值)}-99(鏈)=951\)

code

#include<bits/stdc++.h>
using namespace std;
const int maxv=305,maxq=15;
int V,E,Q;
vector<pair<int,int>> G[maxv];
int s[maxq],t[maxq];
int main(){
    V=100;
    E=951;
    for(int i=0;i<V;i++){
        int k=min(E,10);
        E-=k;
        if(i!=0){
            G[i].push_back(make_pair(i-1,rand()%114514+114514));
        }
        for(int j=1;j<=k;j++){
            G[i].push_back(make_pair(i,rand()%114514+114514));
        }
    }
    Q=10;
    for(int i=1;i<=Q;i++){//由于我是反著建的鏈，所以輸出99 0
        s[i]=99;
        t[i]=0;
    }
    print();
    return 0;
}

point 3

同 point 1，這里不加贅述

point 4

目的

卡 \(\text{Dijkstra}(\Theta(QE+Q\log_2 E))\)

且需要讓 \(\text{Floyd}(\Theta(V^3))\) 過

做法

不了解 \(\text{Dijkstra}\) 的可以去 oi-wiki 上看看，我們可以看到：

在稀疏圖中，\(m=\Theta(n)\)，使用二叉堆實作的 Dijkstra 演算法較 Bellman-Ford 演算法具有較大的效率優勢；而在稠密圖中，\(m=\Theta(n^2)\)，這時候使用暴力做法較二叉堆實作更優，

但是這個題沒有給我們建稠密圖的機會，我們不能這么卡，

于是，我們只能從 \(\text{Dijkstra}\) 松弛操作的漏洞來卡，

就如 Abzilurtahv 大佬所說的那樣，只要構造出如下圖的情況， \(\text{Dijkstra}\) 就去世了，

那么為什么？這里是很多題解沒有說到的，

我們來簡單的證明一下：

我們截取一個片段：

那么整個演算法會按如下步驟進行：

而發現節點 \(V\) 外每一個節點都擁有這個性質，所以時間復雜度為 \(\Theta(2^{\frac{V-1}{2}})\)，忽略常數相當于 \(\Theta(2^V)\)，

證畢，

所以對于這道題，構造一組 \(V=33,Q=10\) 的資料即可

code

#include<bits/stdc++.h>
using namespace std;
const int maxv=305,maxq=15;
int V,E,Q;
vector<pair<int,int>> G[maxv];
int s[maxq],t[maxq];
int main(){
    V=33;
    int dis=200000;
    for(int i=0;i<V;i++){
        if(i==V-1){
            continue;
        }
        if(i&1){
            dis/=2;
            G[i].push_back(make_pair(i+1,-dis));
        }
        else{
            G[i].push_back(make_pair(i+1,-1));
            G[i].push_back(make_pair(i+2,-2));
        }
    }
    Q=10;
    for(int i=1;i<=Q;i++){
        s[i]=0;
        t[i]=32;
    }
    print();
    return 0;
}

point 5

目的

卡掉 \(\text{Bellman-Ford}(\Theta(VEQ))\)

且需要讓 \(\text{Dijkstra}(\Theta(QE+Q\log_2 E))\) 過

做法

同 point 2，我們需要在一條鏈上狂加自環，

另外我們發現其實 \(\text{Dijkstra}\) 的時間復雜度是不會受 \(V\) 的影響的，然后我們就讓 \(V\) 盡量大，也就是 \(V=300\)，\(Q\) 也設為 \(10\)，

簡單計算發現 \(E_{\max}=\frac{1016-1(V)-300(出度)-1(Q)-2\times10(詢問)}{2}-299(鏈)=48\)

code

#include<bits/stdc++.h>
using namespace std;
const int maxv=305,maxq=15;
int V,E,Q;
vector<pair<int,int>> G[maxv];
int s[maxq],t[maxq];
int main(){
    V=300;
    E=48;
    for(int i=0;i<V;i++){
        int k=min(E,10);
        E-=k;
        if(i!=0){
            G[i].push_back(make_pair(i-1,rand()%114514+114514));
        }
        for(int j=1;j<=k;j++){
            G[i].push_back(make_pair(i,rand()%114514+114514));
        }
    }
    Q=10;
    for(int i=1;i<=Q;i++){
        s[i]=299;
        t[i]=0;
    }
    print();
    return 0;
}

point 6

同 point 4，只是 \(Q\) 過大導致超出限制，\(Q\) 改為 \(6\) 即可，

point 7

目的

卡掉 \(\text{Backtrack}\)，讓 \(\text{Gamble1}\) 過，

做法

首先明確一點，這個 \(\text{Gamble1}\) 是個永遠不會被卡掉的程式，所以你只需要管 \(\text{Backtrack}\)，

而你其實可以很顯然的發現 \(\text{Backtrack}\) 的時間復雜度大無比，所以可以直接隨機一組資料，

點數是隨意的，而 \(E_{\max}=\frac{3004-1(V)-1(E)}{2}=1501\)，

所以我們讓 \(V=999,E=1501\)，

code

#include<bits/stdc++.h>
using namespace std;
const int maxv=1005;
int V,E;
bool G[maxv][maxv];
vector<pair<int,int>> e;
int main(){
    V=999;
    E=1501;
    for(int i=1;i<=E;i++){
        int x=rand()%V;
        int y=rand()%V;
        while(G[x][y]||G[y][x]||x==y){
            x=rand()%V;
            y=rand()%V;
        }
        G[x][y]=G[y][x]=1;
        e.push_back(make_pair(x,y));
    }
    reverse(e.begin(),e.end());
    print();
    return 0;
}

point 8

目的

卡掉 \(\text{Gamble2}\) ，\(\text{Backtrack}\) 讓過，

做法

首先明確以下， \(\text{Gamble2}\) 是一個永遠都過不去的演算法，所以不用管，

而這個 \(\text{Backtrack}\) 是暴力染色，所以我們良心一點，讓它能夠一遍染完，

所以我們再造資料的時候先提前染好色，這樣就能過了，

注意這里 \(V\) 不能過大，否則會把 \(\text{Backtrack}\) 卡掉，

code

#include<bits/stdc++.h>
using namespace std;
const int maxv=1005;
int V,E;
int col[maxv];
bool G[maxv][maxv];
vector<pair<int,int>> e;
int main(){
    V=101;
    E=1501;
    for(int i=1;i<=V;i++){
        col[i]=rand()%2;
    }
    for(int i=1;i<=E;i++){
        int x=rand()%V;
        int y=rand()%V;
        while(col[x]==col[y]||G[x][y]||G[y][x]||x==y){
            x=rand()%V;
            y=rand()%V;
        }
        G[x][y]=G[y][x]=1;
        e.push_back(make_pair(x,y));
    }
    reverse(e.begin(),e.end());
    print();
    return 0;
}

完結撒花！

后記

這篇題解我是邊寫題邊寫的

一共提交 \(26\) 次才獲得 AC

下面是通過各個測驗點的時間：

歷時共 \(16134\text{s}\)，合計 \(268.9\text{min}\)，相當于約 \(4.18167\text{h}\)，

全文共 \(11664\) 個字，

碼字不易，點個贊再走吧～

標籤：其他

上一篇：TFRecord的Shuffle、劃分和讀取

下一篇：leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少數量的箭引爆氣球(中等)