C++博客-Victordu

PKU 3193 STL

Victordu — Wed, 10 Sep 2008 13:00:00 GMT

好久没写了太懒了太菜了
这个题因为不会写虽然不难但是STL我实在知道的太少了所以贴一下备忘

#include
#include
#include

using namespace std;

int main()
{
    int i,j,sum=0;
    int m,n;
    char str[100],word[10000][100];
    sets;
    set::iterator it;

    cin>>m>>n;
    getchar();
    for(i=0;i    {
        gets(str);
        s.insert(str);
    }

    for(it=s.begin(),i=0;it!=s.end();it++)
        strcpy(word[i++],(*it).c_str());

    int high,low,mid;

    for(i=0;i    {
        gets(str);
        low=0;high=m-1;
        while(low        {
            mid=(low+high)/2;
            if(strcmp(word[mid],str)<0) low=mid;
            else high=mid;
        }
        for(j=low;j<=high;j++)
        {
            if(strstr(word[j],str)==word[j]) {sum++;break;}
        }

    }

    cout<
}

Victordu 2008-09-10 21:00 发表评论

POJ 2453 强大的位运算

Victordu — Fri, 22 Aug 2008 04:48:00 GMT

这个是说给你一个数找出比他大的最小的一个数满足二进制中1的个数和他相同

看到了一个人写的很强大的位运算代码

#include
int main()
{
    int n,x;
    while(scanf("%d",&n),n)
    {
        x=n&-n;
        printf("%d\n",n+x+(n^n+x)/x/4);
    }
}

x呢是最后一个1出现的
n＋x 是从后往前第一个01转化为10
n^n+x/x/4就是把所有后面的1后移了

Orz阿Orz。。。。。。

Victordu 2008-08-22 12:48 发表评论

POJ 2546 简单几何

Victordu — Tue, 19 Aug 2008 13:13:00 GMT

求两圆相交面积两个弧形面积之和减去两个三角形面积
噢如果没有相交或者内含内切的话就是0
好吧还是水题。。。

Victordu 2008-08-19 21:13 发表评论

POJ 2363 枚举

Victordu — Tue, 19 Aug 2008 12:47:00 GMT

这一题是说给N个1＊1＊1的立方体问把他们堆一起表面积最小是多少
就是枚举吧找到三个数乘积等于体积记录最小表面积

好吧我只会做水题
下午的比赛做得极其郁闷吃饭的时候三个人都不很爽

BLESS 一下

Victordu 2008-08-19 20:47 发表评论

POJ 2959 简单几何

Victordu — Tue, 19 Aug 2008 03:15:00 GMT

题意就是在轴承里面放珠子给出轴承和珠子的直径还有珠子的间距问最多可以放多少颗

oh yeah 又是一道水题把大圆圆心和两个小圆圆心连接起来就比较容易看了

#include
#include

int main()
{
    int t;
    double D,d,s;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf",&D,&d,&s);
        int m=0;
        m=(int)(acos(-1)/asin((d+s)/(D-d)));
        printf("%d\n",m);
    }
}

Victordu 2008-08-19 11:15 发表评论

POJ 2492 并查集

Victordu — Mon, 18 Aug 2008 13:29:00 GMT

这个题好邪恶。。。
给的就是n个虫子 m对虫子发生过关系然后问有没有虫子是同性恋。。。

用并查集作的根据他们发生关系来建树－－！
对虫子分情况讨论
如果是同一棵树相距层数为偶数那就是同性恋
如果是不同树如果两只虫子是异性那就合并否则就根据层数大小对虫子和另一只虫子的父结点合并

Victordu 2008-08-18 21:29 发表评论

POJ 2524第一个并查集

Victordu — Mon, 18 Aug 2008 11:41:00 GMT

并查集的入门题目阿为什么又是一道水题。。。。

void make_set(int x)
{
    p[x]=x;
    rank[x]=0;
}

int find_set(int x)
{
    if(x==p[x]) return x;
    else p[x]=find_set(p[x]);
}

void union_set(int x,int y)
{
    x=find_set(x);
    y=find_set(y);
    if(rank[x]>rank[y]) p[y]=x;
    else
    {
        p[x]=y;
        if(rank[x]==rank[y]) rank[y]++;
    }
}

Victordu 2008-08-18 19:41 发表评论

POJ 2366 HASH

Victordu — Mon, 18 Aug 2008 08:49:00 GMT

题意就是两组数中找是否有一对数的和等于10000
HASH来作因为数据量不大
大的话可以用一下二分

恩继续刷水题

Victordu 2008-08-18 16:49 发表评论

POJ 3267 拓扑排序

Victordu — Mon, 18 Aug 2008 08:13:00 GMT

恩就是一个拓扑排序我又做了一道水题。。。

Victordu 2008-08-18 16:13 发表评论

POJ 2502 FLOYD

Victordu — Mon, 18 Aug 2008 06:15:00 GMT

这题是说起点终点然后有若干条线路线路上有若干点求起点到终点最短路
稍稍建模一下同线路上的点距离是其他点对距离的四分之一
用DIJ或者FLOYD求一下就OK了
输入处理有一点小麻烦

Victordu 2008-08-18 14:15 发表评论