随笔-141  评论-9  文章-3  trackbacks-0
 
点定位问题: 点q是否在多边形P内
     摘要: 判断点q是否在多边形内的一种方法，过q作水平射线L，  如果L与多边形P的边界不相交，则q在P的外部。否则，  L和P的边界相交，具体地说，交点个数为奇（偶）数时，点q在P的内（外）部。（参考 计算几何P19 ） /**//*判断点q是否在多边形内的一种方法，过q作水平射线L，如果L与多边形P的边界不相交，则q在P的外部。否则，L和P的边界相交，具体地说，...  阅读全文
posted @ 2011-02-06 22:55 小阮 阅读(349) | 评论 (0) | 编辑 收藏
USACO 5.1.1 Fencing the Cows (凸包)

凸包入门题目, 我用的是O(nlgn)的graham算法, 该算法的原理可以参照算法导论相关章节

/*
ID: lorelei3
TASK: fc
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

const int STACKSIZE = 1000;
const int MAXN = 10001;
const int INF = 0x7FFFFFFF;

struct Point{
    double x,y;
};

ifstream fin("fc.in");
ofstream fout("fc.out");

Point p0, points[MAXN];

double cross(Point &p1s, Point &p1e, Point &p2s, Point &p2e){
    double x1 = p1e.x - p1s.x; 
    double y1 = p1e.y - p1s.y;

    double x2 = p2e.x - p2s.x;
    double y2 = p2e.y - p2s.y;

    return x1*y2-x2*y1;
}

double dis(Point &p1, Point &p2){
        return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}

int cmp(const void *A, const void *B){
    Point *p1 = (Point*)A;
    Point *p2 = (Point*)B;

    double res = cross(p0, *p1, p0, *p2);
    if(res>0)
        return -1;
    else if(res==0 && dis(p0,*p1) > dis(p0, *p2))
        return  -1;
    else 
        return 1;
}

int n;
void input(){
    int loc=0;
    double minx = INF, miny = INF;
    fin>>n;
    for(int i=0; i<n; ++i){
        fin>>points[i].x >>points[i].y;
        
        if(points[i].y < miny){
            miny = points[i].y;
            minx = points[i].x;
            p0 = points[i];
            loc = i;
        }else if(points[i].y == miny){
            if(points[i].x < minx){
                miny = points[i].y;
                minx = points[i].x;
                p0 = points[i];
                loc = i;
            }
        }        
    }
    points[loc] = points[--n];

    qsort(points, n, sizeof(Point), cmp);
}

Point stack[STACKSIZE];
int top;
void graham(){

    stack[++top] = p0;
    stack[++top] = points[0];
    stack[++top] = points[1];

    for(int i=2; i<n; ++i){
        while(cross(stack[top], points[i], stack[top], stack[top-1])<0 )
            top--;
        stack[++top] = points[i];
    }
}

double ans=0;
void output(){
    int tmp = top;
    while(tmp!=1){
        ans += dis(stack[tmp], stack[tmp-1]);
        tmp--;
    }

    ans += dis(p0, stack[top]);
    
    fout.setf(ios::fixed);
    fout.precision(2);
    fout<<ans<<endl;

}

int main(){

    input();

    graham();

    output();

    return 0;
}

posted @ 2011-02-05 22:16 小阮 阅读(179) | 评论 (0) | 编辑 收藏
USACO 4.4.3 Frame Up (拓扑排序)
     摘要: 根据题意，每个矩形总能找到他的四个角的坐标，先找出各个矩形，再遍历每个矩形的四条边，例如：若在遍历矩形A的四条边时候，遇到B。则图中存在边A->B如此建立边的关系之后即刻拓扑排序。最后对结果进行排序。PS：结果数量比较大。 /**//*ID: lorelei3TASK: frameupLANG: C++*/#include <fstream&g...  阅读全文
posted @ 2011-02-04 16:48 小阮 阅读(350) | 评论 (0) | 编辑 收藏
USACO 4.4.2 Pollutant Control (最大流最小割定理)
根据最大流最小割定理，最大流的值flow就等于最小割的流量。

求最小割的边集：枚举每条边，该边的值为t， 从图中去掉这条边，然后求最大流maxt。

如果 maxt + t = flow 则这条边属于最小割的边集，flow -= t 。继续枚举。

另外，为了构造解，我记录了输入的顺序并对边的大小和答案进行了排序。 我看到有些牛人的题解不需要排序，学习中。

/*
ID: lorelei3
TASK: milk6
LANG: C++
*/

#include <fstream>
#include <queue>
#include <algorithm>
#include <memory.h>

using namespace std;

const int MAXM = 1005;
const int MAXN = 33;
const int INF = 0x7FFFFFFF;

ifstream fin("milk6.in");
ofstream fout("milk6.out");

struct Edge{
    int index, s, t;
    long cost ;

    bool operator < ( const Edge &e)const {
        return (cost>e.cost) || (cost==e.cost && index<e.index );
    }
};

int n,m;
int cnt;
Edge edges[MAXM];

 long c[MAXN][MAXN];
 long tmp[MAXN][MAXN];


void input(){
    fin>>n>>m;
    for(int i=1; i<=m; ++i){
        edges[i].index=i;
        fin>>edges[i].s>>edges[i].t>>edges[i].cost;
        c[edges[i].s][edges[i].t] += edges[i].cost;
    }
    memcpy(tmp, c, sizeof( long)*MAXN*MAXN);
}

long pre[MAXN], delta[MAXN];

bool bfs(int s, int t){

    queue<int> Q;

    memset(pre, 0, sizeof(pre));
    memset(delta, 0, sizeof(delta));

    delta[s]=INF;
    Q.push(s);
    
    while(!Q.empty()){
        int cur = Q.front();
        Q.pop();
        for(int i=1; i<=n; ++i){
            if(delta[i]==0 && c[cur][i]>0 ){
                delta[i] = delta[cur]<c[cur][i] ? delta[cur] : c[cur][i];
                pre[i] = cur;
                Q.push(i);
            }
        }
    }
    if(delta[t]==0)
        return false;

    return true;
}

long edmonds_karp(int s, int t){
    long ans=0;
    while(bfs(s,t)){
        for(int i=t; i!=s; i=pre[i]){
            c[pre[i]][i] -= delta[t];
            c[i][pre[i]] += delta[t];
        }
        ans += delta[t];
    }
    return ans;
}

int tot;
int ans[MAXM];
long maxflow, flow;

void solve(){

    sort(edges+1, edges+m+1);

    flow = edmonds_karp(1, n);
    maxflow = flow;

    for(int i=1; i<=m; ++i){
        long t = edges[i].cost;
        memcpy(c, tmp, sizeof( long)*MAXN*MAXN);

        c[edges[i].s][edges[i].t] -= edges[i].cost;

        long maxt = edmonds_karp(1, n);

        if(maxt+t == flow){
            ans[tot++] = edges[i].index;
            flow -= edges[i].cost;
            tmp[edges[i].s][edges[i].t] -= edges[i].cost;
        }
    }
}

void output(){
    fout<<maxflow<<" "<<tot<<endl;

    sort(ans, ans+tot);
    for(int i=0; i<tot; ++i)
        fout<<ans[i]<<endl;

}

int main(){

    input();

    solve();

    output();

    return 0;
}

posted @ 2011-02-02 13:57 小阮 阅读(811) | 评论 (0) | 编辑 收藏
USACO 4.4.1 Shuttle Puzzle (构造法求解)
一开始想到暴搜，但是状态太多，肯定TLE。

了USACO上给出构造法求解：

3

3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1

4

4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

5

5 7 8 6 4 3 5 7 9 10 8 6 4 2 1 3 5 7 9 11 10 8 6 4 2 3 5 7 9 8 6 4 5 7 6

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

6

6 8 9 7 5 4 6 8 10 11 9 7 5 3 2 4 6 8 10 12 13 11 9 7 5 3 1 2 4 6 8 10 12 11 9 7 5 3 4 6 8 10 9 7 5 6 8 7

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 1 -2 -2 -2 -2 -2 -2 1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1


规律很明显。

/*
ID: lorelei3
TASK: shuttle
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAX = 500;

int n;
int two=2, one=1;
int a[MAX];

bool flag = true;

int main(){

    ifstream fin("shuttle.in");
    ofstream fout("shuttle.out");

    fin>>n;

    int loc=0, k=1;
    while(k!=0){

        if(k==n){
            flag=false;
            one = -one;
        }
        int t=k;
        while(t!=0){
            a[loc++] = two;
            t--;
        }
        a[loc++]=one;

        two = -two;
        one = -one;

        if(k<n && flag)
            k++;
        else 
            k--;
    }

    int res=n;
    fout<<n<<" ";

    for(int i=0, cnt=2; i<loc-1; ++i,++cnt){
        if(cnt==20){
            fout<<(res+=a[i])<<endl;
            cnt=0;
        }
        else
            fout<<(res+=a[i])<<" ";
    }
    
    res+=a[loc-1];
    fout<<res<<endl;

    return 0;
}
posted @ 2011-01-30 22:11 小阮 阅读(379) | 评论 (0) | 编辑 收藏
USACO 4.3.4 Letter Game(预处理, 枚举)
     摘要: 对ditch里边的单词进行枚举, 需要预处理, 过滤掉不符合题意的单词. /**//*ID: lorelei3TASK: lgameLANG: C++*/#include <fstream>#include <string>#include <memory.h>using namespace...  阅读全文
posted @ 2011-01-30 11:23 小阮 阅读(194) | 评论 (0) | 编辑 收藏
USACO 4.3.3 Street Race(连通性,DFS)

第一问， 枚举地拿掉每个点u，看能否连通（dfs 到n），能连通的就是必需经过的点，对于点u 进行DFS，看会不会重复经过第一问中已经访问过的点，若都没有经过，则该u点符合第二问。

/*
ID: lorelei3
TASK: race3
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int MAX = 55;

ifstream fin("race3.in");
ofstream fout("race3.out");

int map[MAX][MAX];
int visited[MAX], ans1[MAX], ans2[MAX], cnt1, cnt2, n;

void input(){
    int i=0, in=0;
    while(fin>>in && in!=-2){
        int t=in;
        int c = ++map[i][0];
        map[i][c]=t;
        
        while(fin>>t && t!=-2){
            int c = ++map[i][0];
            map[i][c]=t;
        }
        i++;
    }
    fin>>in;
    n=i;
}

bool dfs1(int u){
    if(u==n)
        return true;

    for(int i=1; i<=map[u][0]; ++i){
        int v = map[u][i];
        if(visited[v]==0){
            visited[v]=1;
            if(dfs1(v))
                return true;
        }
    }
    return false;
}

bool rep;
void dfs2(int u){
    if(rep)
        return;
    if(visited[u]==2)
        return;

    visited[u]=2;
    for(int i=1; i<=map[u][0]; ++i){
        int v = map[u][i];
        if(visited[v]==1){
            rep=true;
            return;
        }
        dfs2(v);
    }
}

void solve(){
    for(int i=1; i<n; ++i){
        memset(visited, 0, sizeof(visited));
        visited[i]=1;
        visited[0]=1;
        if(!dfs1(0)){
            ans1[cnt1++] = i;
            rep = false;
            dfs2(i);
            if(rep == false)
                ans2[cnt2++] = i;
        }
    }
}

void output(){
    int i;
    fout<<cnt1;

    if(cnt1!=0){
        fout<<" ";
        for(i=0; i<cnt1-1; ++i)
            fout<<ans1[i]<<" ";
        fout<<ans1[cnt1-1];
    }
    fout<<endl;

    fout<<cnt2;
    if(cnt2!=0){
        fout<<" ";
        for(i=0; i<cnt2-1; ++i)
            fout<<ans2[i]<<" ";
        fout<<ans2[cnt2-1];
    }
    fout<<endl;
}

int main(){

    input();

    solve();

    output();

    return 0;
}
posted @ 2011-01-29 20:01 小阮 阅读(353) | 评论 (0) | 编辑 收藏
USACO 4.3.2 The Primes( 筛法求素数, 搜索)
     摘要: 做了一天. AC的速度还可以,  时间最长的 0.16s.1. 开始做之前，要确定下搜索顺序, 这个很关键.                         &...  阅读全文
posted @ 2011-01-29 00:07 小阮 阅读(684) | 评论 (0) | 编辑 收藏
USACO 4.3.1 Buy Low, Buy Lower(最长下降子序列, 高精度加法)

第一问，求最长下降子序列长度。

设a表示数据，len(i)=前i个数中最长下降子序列长度，状态转移方程 len (i)=max{len(j)+1}(j<i,a[j]>a[i]), 初始化f[i]=1 (i=0...n-1);

第二问：

对于c[i]=前i个数中最长下降子序列的个数，状态转移方程  c[i]=sigma(c[j]) (j<i,a[j]>a[i], len[i]==len[j]+1)

对于重复情况， 每一个可能重复的下降的子序列，它一定是a , b, b (a>b)的情况，开一个数组visited记录b是否出现过，若出现了，就不再计算。

状态转移方程： c[i]=sigma(c[j]) (j<i,a[j]>a[i], len[i]==len[j]+1)，visited[j]=false)。

最后是高精度加法，我的版本是每一位存一个数，有待改进。

PS：这次代码风格有点变化。

/*
ID: lorelei3
TASK: buylow
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int  MAXN = 5000;
const int MAXP = 50;

class HPNum{
public:
    int length;
    int num[MAXP];

    HPNum(){
        length=1;
        memset(num,0,sizeof(num));
    }

    void plus(HPNum &p){
        int len = length>p.length ? length : p.length;
        for(int i=0; i<len; ++i){
            num[i] = num[i]+p.num[i];
            if(num[i]>=10){
                num[i]-=10;
                num[i+1]++;
            }

        }
        if(num[len]>0)
            len++;
        length=len;
    }
};

int n;
long maxlen;
long a[MAXN], len[MAXN];
bool visited[20000];
HPNum c[MAXN];

ifstream fin("buylow.in");
ofstream fout("buylow.out");

void input(){
    fin>>n;
    for(int i=0; i<n; ++i){
        fin>>a[i];
        len[i]=1;
    }
}

void dp(){
    int i,j;
    maxlen=1;
    for(i=1; i<n; ++i)
        for(j=i-1; j>=0; --j){
            if(a[i]<a[j] && len[i]<len[j]+1)
                len[i] = len[j]+1;
            if(maxlen<len[i]) 
                maxlen = len[i];
        }
    
    for(i=0; i<n; ++i)
        if(len[i]==1){
            c[i].length=1;
            c[i].num[0]=1;
        }else{
            memset(visited, false, sizeof(visited));
            for(j=i-1; j>=0; --j){
                if(len[i]==len[j]+1 && !visited[a[j]] && a[i]<a[j]){
                    c[i].plus(c[j]);
                    visited[a[j]]=true;
                }
            }
        }
}

void output(){
    int i;
    HPNum sum;
    sum.length=1;
    sum.num[0]=0;
    memset(visited, false, sizeof(visited));
    for(i=n-1; i>=0; --i)
        if(len[i]==maxlen && !visited[a[i]]){
            sum.plus(c[i]);
            visited[a[i]]=true;
        }

    fout<<maxlen<<" ";

    for(i=sum.length-1; i>=0; --i)
        fout<<sum.num[i];

    fout<<endl;
}

int main(){

    input();

    dp();

    output();
    
    return 0;
}


 

posted @ 2011-01-27 00:59 小阮 阅读(445) | 评论 (0) | 编辑 收藏
USACO 4.2.4 Cowcycles (DFS, 剪枝)

参考了USACO上的提示:

1. 最大传动比率至少是最小的3倍。这个其实不用算出比率再判断，只要不满足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉 .

2. 用memcpy函数会更快.

3. 用插入排序对于规模较小的数据速度比较客观.

/*
ID: lorelei3
TASK: cowcycle
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int MAX = 100;

int F, R, F1, F2, R1, R2;
int s1[MAX], s2[MAX];
int ans1[MAX], ans2[MAX];
double rate[MAX*MAX], diff[MAX*MAX];
double minf = 0x7FFFFFFF;

void count(){
    int i,j,k=0;
    double sum1=0, sum2=0, t=0;

    for(i=1; i<=F; ++i)
        for(j=1; j<=R; ++j){
            t = (double)s1[i]/s2[j];
            int p=++k;
            while(rate[p-1]>=t){
                rate[p] = rate[p-1];
                p--;
            }
            rate[p] = t;
        }

    int cnt = F*R;
    for(i=1; i<=cnt-1; ++i){
        diff[i] = rate[i+1] - rate[i];
        sum1 += diff[i];
    }

    double mean = sum1/(cnt-1);

    for(i=1; i<=cnt-1; ++i)
        sum2+=(diff[i]-mean)*(diff[i]-mean);

    double var = sum2/cnt-1;

    if(var<minf){
        minf = var;
        memcpy(ans1+1, s1+1, sizeof(int)*F);
        memcpy(ans2+1, s2+1, sizeof(int)*R);
    }
}

void dfs2(int k, int w){
    if(k==R+1){
        if(s1[F]*s2[R]<3*(s1[1]*s2[1]) )
            return;
        count();
        return;
    }else{
        for(int i=w; i<=R2-(R-k); ++i){
            s2[k]=i;
            dfs2(k+1, i+1);
        }
    }
}

void dfs1(int k, int w){
    if(k==F+1){
        dfs2(1, R1);
        return;
    }else{
        for(int i=w; i<=F2-(F-k); ++i){
            s1[k]=i;
            dfs1(k+1, i+1);
        }
    }
}

int main(){

    ifstream fin("cowcycle.in");
    ofstream fout("cowcycle.out");

    fin>>F>>R>>F1>>F2>>R1>>R2;

    dfs1(1,F1);

    int i;
    for(i=1; i<=F-1; ++i)
        fout<<ans1[i]<<" ";
    fout<<ans1[F]<<endl;

    for(i=1; i<=R-1; ++i)
        fout<<ans2[i]<<" ";
    fout<<ans2[R]<<endl;

    return 0;
}
posted @ 2011-01-26 12:03 小阮 阅读(244) | 评论 (0) | 编辑 收藏
仅列出标题
共14页: First 2 3 4 5 6 7 8 9 10 Last 
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮