随笔-141  评论-9  文章-3  trackbacks-0
 
USACO 3.1.5 Contact (位运算)

位运算,

输入一位,  先用B 位的掩码mask之, 得到str ,  对str从A位到B位mask之, 再最前头加个1, 以免忽略前导0,  然后hash..

sort一下, 再输出..

输出很ws...小心...写得很烂...

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

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

using namespace std;

const int MAX = 200005;

typedef struct Sequence{
    Sequence():cnt(0),value(0){}
    int cnt, value;
}Seq;

Seq hash[MAX];    
char str[MAX];
int A,B,p,N;

ifstream fin;
ofstream fout;

int cmp(const Seq &a , const Seq &b){
    return a.cnt>b.cnt || (a.cnt==b.cnt&&a.value<b.value);
}

void my_print_bin(int value){
    int  tmp[100], cnt=0;
    memset(tmp, 0 , sizeof(tmp));
    do{
        tmp[cnt++] = value & 1;
        value>>=1;
    }while(value);
    
    for(int i=cnt-2; i>=0; i--)
        fout<<tmp[i];
}

int main(){
    int i, j;
    unsigned mask, mask1, mask2;
    unsigned int str=0, c;
    char ch;

    fin.open("contact.in");
    fout.open("contact.out");

    fin>>A>>B>>N;

    fin.get(ch);


    mask = (1<<B)-1;
    while(fin.get(ch)){
        if(ch=='0' || ch=='1'){
            p++;
            c = ch-'0';
            str = ((str<<1)+c)&mask;

            for(i=A; i<=B&&i<=p; ++i){
                mask1 = (1<<i)-1;
                mask2 = mask1+1;

                unsigned int t = (str&mask1)|mask2;
                hash[t].cnt++;
                hash[t].value= t;
            }
        }    
    }

    sort(hash, hash+MAX, cmp);

    int tc=-1;
    char* seq=" ";
    bool flag = false;
    i=0,j=0;
    int count=0;
    while(true){
        if(hash[j].cnt == tc){
            if(count==6){
                seq="\n";
                count=0;
            }
            fout<<seq;
            my_print_bin(hash[j].value);
            seq=" ";
            count++;
        }else{
            if(flag)
                fout<<endl;
            if(hash[j].cnt==0 || ++i>N)
                break;

            fout<<hash[j].cnt<<endl;
            my_print_bin(hash[j].value);
            count = 1;
            
            tc=hash[j].cnt;
            flag =true;
        }
        j++;
    };
    return 0;
}


posted @ 2010-12-18 15:52 小阮 阅读(268) | 评论 (0) | 编辑 收藏
USACO 3.1.4 Shaping Regions 上浮法+矩阵分割
上浮法 + 矩阵分割

以逆序来进行放置，即n to 1。逆序的好处在于放置一个矩形后，俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了，所以可直接统计，为递归创造了条件。每放一个矩形，可以想象成将其扔入一密度很大的海水底部，海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形，继续上浮，直到浮出水面。于是想到用个递归来模拟上浮过程。

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

#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 10010;
const int MAXC = 2510;

int N;
int x1[MAX], y1[MAX], x2[MAX], y2[MAX], color[MAXC], area[MAXC];

void cover(int lx, int ly, int rx, int ry, int c, int k){

    while(k<=N &&(    lx >= x2[k] ||
                    rx <= x1[k] ||
                    ly >= y2[k] ||
                    ry <= y1[k] ))
        k++;
    if(k>N){ area[c] += (ry-ly) * (rx-lx); return; }
    if(lx<x1[k]) { cover(lx, ly, x1[k], ry, c, k+1); lx=x1[k]; }
    if(rx>x2[k]) { cover(x2[k], ly, rx, ry, c, k+1); rx=x2[k]; }
    if(ly<y1[k]) { cover(lx, ly, rx, y1[k], c, k+1); ly=y1[k]; }
    if(ry>y2[k]) { cover(lx, y2[k], rx, ry, c, k+1); ry=y2[k]; }
}

int main(){

    int i;

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

    fin>>x2[0]>>y2[0]>>N;

    x1[0]=0; 
    y1[0]=0; 
    color[0]=1;

    for(i=1; i<=N; ++i)
        fin>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>color[i];

    for(i=N; i>=0; i--)
        cover(x1[i], y1[i], x2[i], y2[i], color[i], i+1);

    for(i=0; i<MAXC; ++i)
        if(area[i])
            fout<<i<<" "<<area[i]<<endl;

    return 0;
}
posted @ 2010-12-16 15:41 小阮 阅读(211) | 评论 (0) | 编辑 收藏
USACO 3.1.3 Humble Numbers

看了官方题解才略懂....囧..

我们在数组hum中计算出前n个丑数。为了实现起来更简单，我们把1也作为一个丑数，算法也要因此略微调整一下。
当我们已知前k个丑数，想得到第k+1个，我们可以这样做：


对于每个质数p 寻找最小的丑数h 使得 h * p 比上一个丑数大

取我们找到的 h * p 中最小的一个：它就是下一个丑数为了使搜索更快，我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数，每次都从那里开始，而不是再从头再来。


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

#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 100000;
const int INF = 0x7FFFFFFF;

int prim[MAX], pindex[MAX];
long hum[MAX];

int K,N,n;

int main(){
    int i,min,minp;
    ifstream fin("humble.in");
    ofstream fout("humble.out");

    fin>>K>>N;

    for(i=0; i<K; ++i)
        fin>>prim[i];

    hum[n++]=1;

    while(n<N+1){
        min = INF; minp=-1;
        for(i=0; i<K; ++i){
            while((double)prim[i]*hum[pindex[i]] <= hum[n-1])
                pindex[i]++;

            if((double)prim[i]*hum[pindex[i]] < min){
                min = prim[i]*hum[pindex[i]];
                minp = i;
            }

        }
        hum[n++] = min;
        pindex[minp]++;
    }

    fout<<hum[N]<<endl;

    return 0;
}

posted @ 2010-12-15 11:23 小阮 阅读(447) | 评论 (0) | 编辑 收藏
USACO 3.1.2 Score Inflation (完全背包)
标准的完全背包问题。练练手吧。

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

#include <fstream>

using namespace std;

int f[10005], mark[10005], cost[10005];
int N,V;

int main(){
    int i,j;

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

    fin>>V>>N;

    for(i=1; i<=N; ++i)
        fin>>mark[i]>>cost[i];

    for(i=1; i<=N; ++i)
        //complete pack
        for(j=cost[i]; j<=V; ++j)
            if(f[j]<f[j-cost[i]]+mark[i])
                f[j] = f[j-cost[i]]+mark[i];

    fout<<f[V]<<endl;
    return 0;
}
posted @ 2010-12-14 20:41 小阮 阅读(197) | 评论 (0) | 编辑 收藏
USACO 3.1.1 Agri-Net (最小生成树)

标准的最小生成树问题. Prim, kruskal 均可.

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

#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 105;
const int INF = 100000000;

int g[MAX][MAX];
int lowcost[MAX], s[MAX]; 
int ans, n;

void prim(int n){
    int i,j,k,min;
    ans = 0;

    for(i=1; i<n; ++i)
        lowcost[i] = g[0][i];

    s[0]=1;

    for(i=0; i<n-1; ++i){
        min = INF;
        j=0;

        for(k=1; k<n; ++k)
            if(!s[k]&&lowcost[k]<min){
                min=lowcost[k];
                j=k;
            }

        ans+=min;
        s[j]=1;

        for(k=1; k<n; ++k)
            if(!s[k] && j!=k && g[j][k]<lowcost[k])
                lowcost[k]= g[j][k];
    }
}

int main(){
    int i,j;

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

    fin>>n;

    for(i=0; i<n; ++i){
        lowcost[i] = INF;
        s[i]=0;
    }

    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            fin>>g[i][j];

    prim(n);

    fout<<ans<<endl;
    return 0;
}
posted @ 2010-12-14 16:49 小阮 阅读(392) | 评论 (0) | 编辑 收藏
USACO 2.4.5 Fractions to Decimals
长除法, 当发现余数一样时候, 出现循环.

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

#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 100000;

char ans[MAX],ch[MAX];

typedef struct Num{
    bool flag;
    int index;
}Num;

Num f[MAX];

int main(){
    int a,b,c,i,j,k, start, stop;
    bool p=false;;

    for(k=0; k<MAX;++k){
        f[k].flag = false;
        f[k].index = -1;
    }

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

    fin>>a>>b;

    c = a/b;
    a = a%b;
    sprintf(ans, "%d.", c);
    f[a].flag=true;
    f[a].index=0;
    int len = strlen(ans);

    k=0;
    while(true){
        a*=10;
        c=a/b;
        a=a%b;

        ch[k] = (char)('0'+c);

        if(a==0){
            p=true;
            break;
        }

        if(f[a].flag==true){
            start = f[a].index;
            stop = k;
            break;
        }else{
            f[a].flag = true;
            f[a].index = k+1;
            k++;
        }
    }

    if(p){
        strcat(ans, ch);
    }else{
        for(i=0, j=len; i<start; ++i, ++j)
            ans[j] = ch[i];
        
        ans[j++]='(';

        for(i=start; i<=stop; ++i, ++j)
            ans[j] = ch[i];

        ans[j++]=')';
        ans[j]='\0';
    }

    bool con = true;
    i=0;
    while(con){
        k=76;
        while(k--){
            if(ans[i]=='\0'){
                con=false;
                break;
            }
            else
                fout<<ans[i++];
        }
        fout<<endl;
    }

    return 0;
}
posted @ 2010-12-14 14:43 小阮 阅读(205) | 评论 (0) | 编辑 收藏
USACO 2.4.4 Bessie Come Home (SPFA)
SPFA, Dijkstra, Floyd 都可以.

注意两点之间有重边, 所以要选择最小的.

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

#include <fstream>
#include <queue>

using namespace std;

const int MAX = 256;
const int INF = 999999999;
int map[MAX][MAX];
int dist[MAX];
bool isInQ[MAX],f[MAX];
int N;

inline bool relax(int u, int v){
    int len = dist[u]+map[u][v];
    if(len<dist[v]){
        dist[v] = len;
        return true;
    }
    return false;
}

void spfa(){
    queue<int> Q;
    int be = 'Z',t=0;

    dist[be]=0;
    map[be][be]=0;
    Q.push(be);
    isInQ[be]=true;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        isInQ[u]=false;
        for(int v=0; v<MAX; ++v)
            if(relax(u, v) && !isInQ[v]){
                Q.push(v);
                isInQ[v]=true;
            }
    }
}

int main(){
    int i,j,v,ans=INF, loc=0;
    char ch1,ch2;

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

    for(i=0; i<MAX; ++i){
        for(j=0; j<MAX; ++j)
            map[i][j]=INF;
    dist[i] = INF;
    }


    fin>>N;

    for(i=0; i<N; ++i){
        fin>>ch1>>ch2>>v;
        if(v<map[ch1][ch2]){
            map[ch1][ch2]=v;
            map[ch2][ch1]=v;
        }
        if(ch1>='A' && ch1<'Z')
            f[ch1]=true;
        if(ch2>='A' && ch2<'Z')
            f[ch2]=true;
    }
    
    spfa();

    for(i=0; i<MAX; ++i)
        if(dist[i]<ans && f[i] ){
            ans = dist[i];
            loc= i;
        }


    fout<<(char)loc<<' '<<ans<<endl;

    return 0;
}
posted @ 2010-12-10 21:23 小阮 阅读(317) | 评论 (0) | 编辑 收藏
USACO 2.4.3 Cow Tours (Floyd)
先用floyd 求两点之间的最短距离map[i][j] ，再求各点与牧区内其他结点距离的最大值d[i]。

枚举分别在两个牧区的两个点i,j，

tmp =  d[i] + d[j] + ( i, j 之前的距离）

/*
ID: lorelei
TASK: cowtour
LANG: C++
*/

#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <memory.h>

using namespace std;

const double INF = 999999.0;

typedef pair<int, int> PAIR;
PAIR loc[200];

double map[200][200];
double d[200];
int N;

inline double dist(int x1, int y1, int x2, int y2){
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

int main(){
    int i,j,k;
    double ans= INF;

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

    fin>>N;

    for(i=0; i<N; ++i)
        fin>>loc[i].first>>loc[i].second;

    char ch;
    for(i=0; i<N; ++i)
        for(j=0; j<N; ++j){
            fin>>ch;
            if(ch=='1') 
                map[i][j] = map[j][i] = dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
            else if(ch=='0') 
                map[i][j] = map[i][j] = INF;
            if(i==j) 
                map[i][j] = 0;

        }

    for(k=0; k<N; ++k)
        for(i=0; i<N; ++i)
            for(j=0; j<N; ++j)
                if(map[i][j] > map[i][k]+map[k][j])
                    map[i][j] = map[i][k]+map[k][j];

    memset(d, 0, sizeof(d));
    for(i=0; i<N; ++i)
        for(j=0; j<N; j++)
            if(map[i][j]>d[i] && map[i][j]!=INF)
                d[i] = map[i][j];

    for(i=0; i<N; ++i)
        for(j=0; j<N; ++j)
            if(map[i][j]==INF){
                double tmp = d[i]+d[j]+dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
                if(tmp<ans)
                    ans = tmp;
            }

    for(i=0; i<N; ++i)
        if(d[i]>ans)
            ans = d[i];

    fout<<setprecision(6)<<setiosflags(ios::fixed | ios::showpoint)<<ans<<endl;

    return 0;
}
posted @ 2010-12-10 19:49 小阮 阅读(183) | 评论 (0) | 编辑 收藏
USACO 2.4.2 Overfencing (Floodfill)
     摘要: floodfill /**//*ID: lorelei3TASK: maze1LANG: C++*/#include<stdio.h> const int dx1[4] = {1, -1, 0, 0}; const int dy1[4] ...  阅读全文
posted @ 2010-12-09 22:42 小阮 阅读(402) | 评论 (0) | 编辑 收藏
pku 1948 Triangular Pastures (01背包)

1. 在三角形的周长l一定时，最长边c的取值范围是l/3≤c＜l/2

2. 用01背包枚举两条边.

#include <iostream>
#include <cmath>

using namespace std;

bool f[1000][1000];
int len[50];
int N;

double area(int a, int b, int c){
    double p = (a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));    
}

int main(){
    int i,j,k,sum=0;
    double ans = 0.0 ;//,tmp=0.0;
    cin>>N;

    for(i=1; i<=N; ++i){
        cin>>len[i];
        sum+=len[i];
    }

    int max = sum/2;

    f[0][0]=true;

    for(i=1; i<=N; ++i)
        for(j=max; j>=0; j--)
            for(k=max; k>=0; k--)
                f[j][k] = f[j][k] | (j>=len[i]&&f[j-len[i]][k]) |(k>=len[i]&&f[j][k-len[i]]);

    for(i=1; i<=max; ++i)
        for(j=1; j<=max; ++j)
            if(f[i][j]){
                k = sum-i-j;
                if( (i+j>k) && (i+k>j) && (k+j>i) ){
                    double tmp = area(i,j,k);
                    if(tmp>ans)
                        ans = tmp;
                }

            }

    if(ans == 0.0)
        cout<<-1<<endl;
    else
        cout<<(int)(ans*100)<<endl;

    //system("pause");
    return 0;

}
posted @ 2010-12-09 11:07 小阮 阅读(345) | 评论 (1) | 编辑 收藏
仅列出标题
共14页: First 6 7 8 9 10 11 12 13 14 
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮