NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » xavier13540 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - xavier13540

頁: [1]
1
NPSC2012高中組初賽 / pC. 好多星星
« 於: 十一月 26, 2012, 01:16:53 pm »
先對百科全書中的星座點集合 P 做以下處理:
1. 將所有的點座標減掉 P0(即將圖形平移使 P0 位於原點)
2. 設 θ = Arg(P1),將圖形旋轉 -θ,即新座標 (x', y') 滿足
┌ x '┐  ┌ cosθ  sinθ ┐┌ x ┐
│    │=│                ││    │
└ y' ┘  └ -sinθ cosθ ┘└ y ┘
3. 設 r=|P0P1|,將圖形縮小成 1/r 倍;這樣,就可以使 P0 在 (0, 0) 而 P1 在 (1, 0)
4. 對所有點對 x 座標做排序,若 x 座標相同,對 y 座標做排序
接著,對星空中的星座,枚舉兩個點,透過上述的座標變換方式,將一點變換到 (0, 0),另一點變換到 (1, 0),並同樣對點座標排序,檢查是否有一個星空中的星座可以變換成百科全書上的星座。
有 n 個百科全書上的星座要檢查,枚舉 m 的星空中的星座,枚舉 w(w-1) 個變換方式,排序時間複雜度 O(wlog w),所以總時間複雜度 O(nmw3log 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;
}


2
NPSC2009高中組決賽 / NPSC 2009 高中組決賽 F. 飛機上有蛇
« 於: 十一月 10, 2012, 01:43:08 pm »
構造一個最小費用最大流模型,將每個空格視作節點,並對於每個節點 i 拆成兩個節點 i 和 i'。設源點為 s 且匯點為 t,構造這些邊:
1. s->i, 其中容量為 2, 費用為 0
2. i'->t, 其中容量為 2, 費用為 0
3. 若 i 與節點 j 相鄰則構造 i->j', 其中容量為 1, 費用為 0
4. 若 i 位於邊界(牆壁)則構造 i->i', 其中容量為 1, 費用為 1
一個迴路(貪食蛇)在模型中有順逆時針兩種,而一個邊界到邊界的路徑(不貪食蛇)在模型中亦有兩種方向。設模型中的最小費用為 mc,最大流為 mf,原圖空格數為 sp,則有
Case 1: mf<2*sp,表示空格無法被填滿
Case 2: mf=2*sp,此時邊界到邊界的路徑數即為 mc/2
此外,若 sp=0,要輸出 -1。
我最小費用最大流是用 spfa 實作,時間複雜度為 O(n3m3),在 ZJ 上跑了 4.7 秒。
代碼: [選擇]
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define N 25
#define INF 1000000000
using namespace std;
struct edge{int to,flow,cap,cost,rev;};
char map[N][N];
int d[2*N*N],a[2*N*N],s,t,mc,mf;
vector<edge>G[2*N*N];
queue<int>spfa;
bool inspfa[2*N*N];
pair<int,int>p[2*N*N];
void push_edge(int from,int to,int cap,int cost){
    edge e;
    e.to=to,e.flow=0,e.cap=cap,e.cost=cost,e.rev=G[to].size();
    G[from].push_back(e);
    e.to=from,e.cap=0,e.cost=-cost,e.rev=G[from].size()-1;
    G[to].push_back(e);
}
void mcmf(){
    mc=mf=0;
    while(1){
        for(int i=0;i<=t;i++)d[i]=INF;
        d[s]=0;
        a[s]=INF;
        spfa.push(s);
        while(!spfa.empty()){
            int i=spfa.front();
            spfa.pop();
            inspfa[i]=0;
            for(int j=0;j<G[i].size();j++){
                int to=G[i][j].to;
                if(G[i][j].cap>G[i][j].flow&&d[to]>d[i]+G[i][j].cost){
                    d[to]=d[i]+G[i][j].cost;
                    a[to]=min(a[i],G[i][j].cap-G[i][j].flow);
                    p[to]=make_pair(i,j);
                    if(!inspfa[to]){
                        spfa.push(to);
                        inspfa[to]=1;
                    }
                }
            }
        }
        if(d[t]==INF)return;
        for(int i=t;i!=s;i=p[i].first){
            int rev=G[p[i].first][p[i].second].rev;
            G[p[i].first][p[i].second].flow+=a[t];
            G[i][rev].flow-=a[t];
        }
        mc+=d[t]*a[t];
        mf+=a[t];
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,sp=0,ans;
        scanf("%d%d",&n,&m);
        s=0,t=2*n*m+1;
        for(int i=s;i<=t;i++)G[i].clear();
        for(int i=0;i<n;i++)scanf("%s",map[i]);
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(map[i][j]=='.'){
            push_edge(s,i*m+j+1,2,0);
            push_edge(n*m+i*m+j+1,t,2,0);
            if(i+1<n&&map[i+1][j]=='.'){
                push_edge(i*m+j+1,n*m+(i+1)*m+j+1,1,0);
                push_edge((i+1)*m+j+1,n*m+i*m+j+1,1,0);
            }
            if(j+1<m&&map[i][j+1]=='.'){
                push_edge(i*m+j+1,n*m+i*m+j+2,1,0);
                push_edge(i*m+j+2,n*m+i*m+j+1,1,0);
            }
            if(!i||i+1==n||!j||j+1==m)push_edge(i*m+j+1,n*m+i*m+j+1,1,1);
            sp++;
        }
        mcmf();
        if(!sp||mf<2*sp)ans=-1;
        else ans=mc/2;
        printf("%d\n",ans);
    }
    return 0;
}


3
想法:
考慮一個圖 G0,若處理事件 i 後能處理事件 j,節點 i 和節點 j 就用有向邊連接。題目要求的就是找圖上盡量少的路徑,使得所有點都被涵蓋。

做法:
構造一個二分圖 G,把在 G0 的節點 v 拆成 v 和 v'。若在 G0 中,節點 u 和節點 v 之間存在有向邊,則連接二分圖中的 u 和 v'。題目所求即為 (G0 節點數) - (G 的最大配對數)。
求二分圖的最大配對可用 maximum flow 解決,我的程式碼使用 Ford-Fulkerson Algorithm,時間複雜度 O(m3),在 ZJ 上跑了 2 秒。

代碼: [選擇]
//我習慣測資數用 T,所以事件數就用 n 了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define N 1010
using namespace std;
struct accident{
    int t,x,y;
}acc[N];
struct edge{
    int to,rev;
    bool cap;
};
int n;
bool visited[2*N];
pair<int,int>p[2*N];
vector<edge>G[2*N];
bool cmp(accident a,accident b){
    return a.t<b.t;
}
void push_edge(int from,int to){
    edge e;
    e.to=to,e.rev=G[to].size(),e.cap=1;
    G[from].push_back(e);
    e.to=from,e.rev=G[from].size()-1,e.cap=0;
    G[to].push_back(e);
}
bool dfs(int i){
    visited[i]=1;
    if(i==2*n+1){
        for(int j=i;j;j=p[j].first){
            int rev=G[p[j].first][p[j].second].rev;
            G[p[j].first][p[j].second].cap=0;
            G[j][rev].cap=1;
        }
        return 1;
    }
    for(int j=0;j<G[i].size();j++)if(!visited[G[i][j].to]&&G[i][j].cap){
        p[G[i][j].to]=make_pair(i,j);
        if(dfs(G[i][j].to))return 1;
    }
    return 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int mf=0;//最大配對或最大流量
        scanf("%d",&n);
        for(int i=0;i<2*n+2;i++)G[i].clear();
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&acc[i].t,&acc[i].x,&acc[i].y);
            push_edge(0,i+1);
            push_edge(n+i+1,2*n+1);
        }
        sort(acc,acc+n,cmp);
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
            if(abs(acc[j].x-acc[i].x)+abs(acc[j].y-acc[i].y)<=acc[j].t-acc[i].t)push_edge(i+1,n+j+1);
        }
//Ford-Fulkerson Algorithm
        while(1){
            memset(visited,0,2*n+2);
            if(dfs(0))mf++;
            else break;
        }
        printf("%d\n",n-mf);
    }
    return 0;
}


頁: [1]