NPSC補完計劃

構造一張圖 G = (V, E)，其中

• V 裡的任一元素代表兩人的所在位置，以無序對 (i, j) (若 h_i = h_j)，或有序對 (i, j+1/2) (若 min{h_j, h_j+1} < h_i < max{h_j, h_j+1}) 表示。
• 設 u, v ∈ V。規定 uv ∈ E 若且唯若兩人可以在只上山或下山一次的情況下從 u 到達 v。

不難發現題目要問的就是從 (0, n+1) 到任意 (i, i) 的最短路徑長度減 1，可用一次 BFS 解決。因為 |V| = O(n²)，且每個頂點的度數 (degree) 都不超過 4，可知整體的時間複雜度是 O(n²)。
值得一提的是，一定存在一條從 (0, n+1) 到某個 (i, i) 的路徑。我們把 G 裡的頂點分成下面這幾種，並討論它們的度數。

• (0, 0), (0, n+1), (n+1, n+1) 的度數都是 1。
• 若 i ≠ 0, n+1 且 h_i = 0，則 (0, i) 和 (i, n+1) 的度數都是 2。
• 若 i ≠ 0, n+1，則 (i, i) 的度數是 3。
• 若 i ≠ j 且 h_i = h_j，則 (i, j) 的度數是 4 (若 i, j 同為山頂或山谷) 或 0 (若 i, j 一者是山頂另一者是山谷)。
• 設 v := (i, j+1/2) 為一合法頂點，則 v 的度數是 2。

令 H 為 G 中包含頂點 (0, n+1) 的連通部分 (connected component)。因為 H 的頂點度數和為偶數，可知 H 必定包含某個 (i, i)，亦即存在從 (0, n+1) 到某個 (i, i) 的路徑。

以下是我的 C++ code：
#include<cassert>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define N 210
typedef pair<int, int> pii;
int n, h[2*N];
vector<int> g[4*N*N];
bool vis[4*N*N];
int state(int i, int j){
    if(i > j){
        swap(i, j);
    }
    return i*(2*n+3)+j;
}
int move(int i, int j, int di, int dj){
    int c = (i&2)-1;
    if(j&1){
        if(c*h[i+2*di] < c*h[j+dj]){
            return state(i+di, j+dj);
        }else if(c*h[i+2*di] == c*h[j+dj]){
            return state(i+2*di, j+dj);
        }else{
            return state(i+2*di, j);
        }
    }else{
        if(c*h[i+2*di] < c*h[j+2*dj]){
            return state(i+di, j+2*dj);
        }else if(c*h[i+2*di] == c*h[j+2*dj]){
            return state(i+2*di, j+2*dj);
        }else{
            return state(i+2*di, j+dj);
        }
    }
}
bool meet(int v){
    return v/(2*n+3) == v%(2*n+3);
}

int main(){
    while(scanf("%d", &n), n){
        h[0] = h[2*n+2] = 0;
        for(int i=1; i<=n; i++){
            scanf("%*d%d", h+2*i);
        }
        scanf("%*d");
        for(int i=0; i<(2*n+3)*(2*n+3); i++){
            g[i].clear();
        }
        g[state(0, 0)].push_back(move(0, 0, 1, 1));
        g[state(0, 2*n+2)].push_back(move(0, 2*n+2, 1, -1));
        g[state(2*n+2, 2*n+2)].push_back(move(2*n+2, 2*n+2, -1, -1));
        for(int j=4; j<=2*n-2; j+=4) if(h[j] == 0){
            g[state(0, j)].push_back(move(0, j, 1, -1));
            g[state(0, j)].push_back(move(0, j, 1, 1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, -1, -1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, 1, -1));
        }
        for(int i=2, c=1; i<=2*n; i+=2, c*=(-1)){
            for(int j=i; j<=2*n; j+=4) if(h[i] == h[j]){
                g[state(i, j)].push_back(move(i, j, -1, -1));
                g[state(i, j)].push_back(move(i, j, -1, 1));
                g[state(i, j)].push_back(move(i, j, 1, -1));
                g[state(i, j)].push_back(move(i, j, 1, 1));
            }
            for(int j=1; j<=2*n-1; j+=4) if(h[j-1]<h[i] && h[i]<h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, -c));
                g[state(i, j)].push_back(move(i, j, 1, -c));
            }
            for(int j=3; j<=2*n+1; j+=4) if(h[j-1]>h[i] && h[i]>h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, c));
                g[state(i, j)].push_back(move(i, j, 1, c));
            }
        }
        bool sol = false;
        memset(vis, false, sizeof(vis));
        queue<pii> bfs;
        bfs.push(make_pair(0, state(0, 2*n+2)));
        vis[state(0, 2*n+2)] = true;
        while(!bfs.empty()){
            pii p = bfs.front(); bfs.pop();
            int d=p.first, v=p.second;
            if(meet(v)){
                printf("%d\n", d-1);
                sol=true; break;
            }
            for(int i=0; i<(int)g[v].size(); i++) if(!vis[g[v][i]]){
                bfs.push(make_pair(d+1, g[v][i]));
                vis[g[v][i]] = true;
            }
        }
        assert(sol);
    }
    return 0;
}



這題用 STL 的 string + stack 程式碼可以寫得超短。

先對百科全書中的星座點集合 P 做以下處理：
1. 將所有的點座標減掉 P₀（即將圖形平移使 P₀ 位於原點）
2. 設 θ = Arg(P₁)，將圖形旋轉 -θ，即新座標 (x', y') 滿足
┌ x '┐  ┌ cosθ  sinθ ┐┌ x ┐
│    │=│                ││    │
└ y' ┘  └ -sinθ cosθ ┘└ y ┘
3. 設 r=|P₀P₁|，將圖形縮小成 1/r 倍；這樣，就可以使 P₀ 在 (0, 0) 而 P₁ 在 (1, 0)
4. 對所有點對 x 座標做排序，若 x 座標相同，對 y 座標做排序
接著，對星空中的星座，枚舉兩個點，透過上述的座標變換方式，將一點變換到 (0, 0)，另一點變換到 (1, 0)，並同樣對點座標排序，檢查是否有一個星空中的星座可以變換成百科全書上的星座。
有 n 個百科全書上的星座要檢查，枚舉 m 的星空中的星座，枚舉 w(w-1) 個變換方式，排序時間複雜度 O(wlog w)，所以總時間複雜度 O(nmw³log w)
說個感想，我原本輸出答案後面有多一個空格收到 WA，抱著不太可能過的心情把空格去掉，在結束前兩分鐘上傳居然收到了 YES（有點失望？）
以下是我寫的爛爛的 code
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define N 90
#define V 20
#define EPS 1e-8
using namespace std;
struct point{
    double x,y;
    bool operator!=(point another){
        return fabs(another.x-x)>EPS||fabs(another.y-y)>EPS;
    }
}p[N][V],q[N][V],temp[V];
int v[N],w[N];
bool found[N];
bool cmp(point a,point b){
    if(fabs(a.x-b.x)<EPS)return a.y<b.y;
    return a.x<b.x;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        bool sad=1;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",v+i);
            for(int j=0;j<v[i];j++)scanf("%lf%lf",&p[i][j].x,&p[i][j].y);
            for(int j=1;j<v[i];j++){
                p[i][j].x-=p[i][0].x;
                p[i][j].y-=p[i][0].y;
            }
            p[i][0].x=p[i][0].y=0;
            double dx=p[i][1].x,dy=p[i][1].y;
            double r=hypot(dx,dy);
            double COS=dx/r,SIN=dy/r;
            for(int j=0;j<v[i];j++){
                double x=p[i][j].x,y=p[i][j].y;
                p[i][j].x=(x*COS+y*SIN)/r;
                p[i][j].y=(-x*SIN+y*COS)/r;
            }
            sort(p[i],p[i]+v[i],cmp);
        }
        memset(found,0,sizeof(found));
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",w+i);
            for(int j=0;j<w[i];j++)scanf("%lf%lf",&q[i][j].x,&q[i][j].y);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)if(v[i]==w[j]){
                bool found2=0;
                for(int k=0;k<w[j];k++){
                    bool found3=0;
                    for(int l=0;l<w[j];l++)if(k!=l){
                        for(int i2=0;i2<w[j];i2++){
                            temp[i2].x=q[j][i2].x-q[j][k].x;
                            temp[i2].y=q[j][i2].y-q[j][k].y;
                        }
                        bool found4=1;
                        double dx=q[j][l].x-q[j][k].x,dy=q[j][l].y-q[j][k].y;
                        double r=hypot(dx,dy);
                        double COS=dx/r,SIN=dy/r;
                        for(int i2=0;i2<w[j];i2++){
                            double x=temp[i2].x,y=temp[i2].y;
                            temp[i2].x=(COS*x+SIN*y)/r;
                            temp[i2].y=(-SIN*x+COS*y)/r;
                        }
                        sort(temp,temp+w[j],cmp);
                        for(int i2=0;i2<w[j];i2++)if(p[i][i2]!=temp[i2]){
                            found4=0;break;
                        }
                        if(found4){
                            found3=1;break;
                        }
                    }
                    if(found3){
                        found2=1;break;
                    }
                }
                if(found2){
                    found[i]=1;break;
                }
            }
        }
        for(int i=0;i<n;i++)if(found[i]){
            if(sad){
                printf("%d",i+1);
                sad=0;
            }
            else printf(" %d",i+1);
        }
        if(sad)puts("so sad");
        else putchar('\n');
    }
    return 0;
}



我這題是用 DP 解的 設 dp[ i][j][k][l] = 在第 i 行時三部車的所在位置為 j, k, l ( j < k < l ) 的最小油耗
若第 (0, j), (0, k), (0, l) 格皆非障礙物 則 dp[0][j][k][l] = 3 否則為 INF
接著對於三部車子在第 i 行時的所有可能位置 (i, j), (i, k), (i, l) 枚舉所有可能的換車方式 利用 dp[i-1] 算出在該狀態下到達終點的最小油耗
時間複雜度 O(R³C) 對於 R ≦ 10, C ≦ 50 的數據大小而言可以輕鬆解決 我的程式在 ZJ 上的執行時間為 8 ms
以下是我恐怖的程式碼 ( 換車方式太多種了 )
#include<stdio.h>
#include<algorithm>
#define R 10
#define C 50
#define INF 1000000000
using namespace std;
char map[R][C+1];
int dp[C][R][R][R];
int main(){
    int T,r,c,start[3],start_size;
    scanf("%d",&T);
    while(T--){
        start_size=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<r;i++){
            scanf("%s",map[i]);
            if(map[i][c-1]=='C')start[start_size++]=i;
        }
        for(int i=0;i<r;i++)for(int j=i+1;j<r;j++)for(int k=j+1;k<r;k++){
            if(map[i][0]!='#'&&map[j][0]!='#'&&map[k][0]!='#')dp[0][i][j][k]=3;
            else dp[0][i][j][k]=INF;
        }
        for(int i=1;i<c;i++)for(int j=0;j<r;j++)for(int k=j+1;k<r;k++)for(int l=k+1;l<r;l++){
            dp[i][j][k][l]=INF;
            if(map[j][i]!='#'&&map[k][i]!='#'&&map[l][i]!='#'){
                if(j>0){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l+1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l+1]+5);
                    if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l-1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l+1]+6);
                }
                if(k-j>1){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l+1]+5);
                }
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l-1]+4);
                dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l]+3);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l+1]+4);
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l-1]+5);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l]+4);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l+1]+5);
                if(k-j>2){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l+1]+6);
                }
                if(k-j>1){
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l+1]+5);
                }
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l-1]+6);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l]+5);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l+1]+6);
            }
        }
        if(dp[c-1][start[0]][start[1]][start[2]]<INF)printf("%d\n",dp[c-1][start[0]][start[1]][start[2]]);
        else puts("Impossible");
    }
    return 0;
}