C++博客-acleast

Giant For （2010天津网赛 1007）

acleast — Mon, 13 Sep 2010 06:56:00 GMT

摘要: 题目大意：输入给出三种操作： 1、add x y&n... 阅读全文

acleast 2010-09-13 14:56 发表评论

zju 1484 hdu 1394　求最小逆序（点树）

acleast — Mon, 17 May 2010 09:17:00 GMT

先说一下逆序数的概念：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那末它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。
如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——这是北大《高等代数》上的定义。

题意：给出一个排列，排列中的数各不相同，都是从0到n-1，要求得到的是一个最短的逆序的长度，这些子序列是转动原来的序列得到的。
一种最基本的做法：就是枚举每一个点求出这个点前面比它的数的个数，然后加起来。还好这种做法没有超时，这里有一种O（nlog(n)）的算法
就是利用点树。我在网上找过，网上关于点树的资料很少，百度百科里面有一篇。还有就是http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html
不过好像是一个人写的. @_@ ^_^
以下借用了他的实现

acleast 2010-05-17 17:17 发表评论

POJ 1990 MooFest 数状数组

acleast — Thu, 06 May 2010 09:20:00 GMT

题目大意：
　　有N头牛，站在X轴上，没有共点的情况，每个牛有一个听力值V(i)，他们交流所消耗的最少volume为abs（X（i）-（X（j）））*MAX{V（i）,V（j）}
最后再求总和。
由于数据量最大为20000,显然O(n^2)的算法会超时。先按V值进行从小到大排序可解决MAX的问题，最后就是对每头牛求V值小于他的权值了。
对于第i个牛，在0~i-1中，用两个数状数组，a表示坐标小于x[i]的个数，b表示坐标小于x[i]的牛的坐标之和，另外c表示0~i-1中所有牛的坐标之和。

acleast 2010-05-06 17:20 发表评论

POJ 3686　The Windy's　拆点+KM

acleast — Tue, 04 May 2010 13:30:00 GMT

摘要: 题目大意：有N个工件要在M个机器上加工，有一个N*M的矩阵描述其加工时间。同一时间内每个机器只能加工一个工件，问加工完所有工件后，使得平均加工时间最小。将工件作为二分图中X部的点，总共N个。将每个机器拆成... 阅读全文

acleast 2010-05-04 21:30 发表评论

POJ 1639 Picnic Planning　最小限度生成树

acleast — Tue, 04 May 2010 13:12:00 GMT

摘要: 这是我有史以来写得最长的一个程序，前段时间就看了这个题，在网上搜了一下算法，当时看得还有点不太明白，大牛也都说这题代码太长不好写，开始写了一些，后面发现不会写了，就放下了。昨天又来看这个题，居然写出来了，不过还是花了我一个晚上的时间来调试，开始交一次结果就RE了，后来在网上找来了官方数据一个一个的运行才发现找圈DFS的时候陷入了死循环，加了一个标志变量，还是WA，后来反复看解思路才知道换边的时候每... 阅读全文

acleast 2010-05-04 21:12 发表评论

POJ 2230 Watchcow 有向图的欧拉回路

acleast — Mon, 03 May 2010 07:55:00 GMT

题目大意：从一点经过所有的边两次，且两次的方向不同，又回到起始点，典型的欧拉回路题

acleast 2010-05-03 15:55 发表评论

POJ 1041 欧拉回路

acleast — Sun, 02 May 2010 14:14:00 GMT

这是一道典型的欧拉回路的题，第一次做这种题，参考了一下别人的代码，结果WA了一晚上，最后照着别人的代码一步一步的改，最后才发现有存在x==y的情况
真是杯具，浪费了一晚上的时间

acleast 2010-05-02 22:14 发表评论

poj 3214

acleast — Sat, 24 Apr 2010 09:53:00 GMT

题目大意：给定一个二叉树，求让它成为孩子结点值不大于父亲结点值，同时左孩子结点值小于右孩子结点值。
用广搜建立二叉树，再后序遍历，求最长不下降子序列，我做了一点变化，将左右孩子交换后先序遍历后求最长不上升子序列。
开始超时了，后来把队列用数组实现就行了，不过注意一下没有右孩子时，左孩子可以和父亲结点值相等。

acleast 2010-04-24 17:53 发表评论

hdu 2222 Keywords Search 典型的ＡＣ自动机入门题目

acleast — Sat, 17 Apr 2010 13:59:00 GMT

摘要: 前段时间学会了trie树之后，今天终于学习了一下AC自动机，这个还是挺难学的，现在我还是有点不太懂，参照了网上的代码才把这道题给Ａ了。让我自己背着写出来还不一定会写。这里有一篇比较好的介绍AC自动机的文章http://www.cppblog.com/mythit/archive/2009/04/21/80633.html先看一下这道题吧，大意是给我们一部字典和一个模式串，让我们求出字典中有多少个单... 阅读全文

acleast 2010-04-17 21:59 发表评论

poj2762 Going from u to v or from v to u? 强连通分支

acleast — Sat, 17 Apr 2010 03:41:00 GMT

又贡献了一版的WA和TLE一道题，本来不是很难，但是由于初始化有问题，一直RE。
先说说这道题的思路吧，两次dfs进行缩点，缩点之后再深搜一次找出最长路径与缩点之后的顶点数相比，
相等则输出Yes,否则输出No。

#include<iostream>
using namespace std;

struct node{
    int v;
    node *next;
};

node pp[6005],qq[6005];
node *dd[1005],*rd[1005];
bool mark[1005];
bool map[1005][1005];
int cal[1005];
int ret[1005];
int n,m,ti;

void init()
{
    memset(mark,false,sizeof(mark));
    memset(cal,0,sizeof(cal));
    memset(dd,0,sizeof(dd));
    memset(rd,0,sizeof(rd));
    memset(ret,0,sizeof(ret));
    memset(map,false,sizeof(map));
}

void input()
{
    int u,v,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        pp[i].v=v;
        pp[i].next=dd[u];
        dd[u]=&pp[i];

        qq[i].v=u;
        qq[i].next=rd[v];
        rd[v]=&qq[i];
    }
}

void dfs(int k)
{
    mark[k]=true;
    node *p=dd[k];
    while(p){
        if(!mark[p->v])
            dfs(p->v);
        p=p->next;
    }
    cal[++ti]=k;
}

void rdfs(int k){
    ret[k]=ti;
    node *p=rd[k];
    while(p){
        if(!ret[p->v])
            rdfs(p->v);
        else if(ti!=ret[p->v]){
            map[ti][ret[p->v]]=true;
        }
        p=p->next;
    }
}

int dfsr(int k){
    int ans=0;
    for(int i=1;i<=ti;i++){
        if(map[k][i]){
            if(!cal[i])
                dfsr(i);
            ans=max(ans,cal[i]);
        }
    }
    cal[k]=ans+1;
    return cal[k];
}

int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--){
        init();
        input();
        ti=0;
        for(i=1;i<=n;i++)
            if(!mark[i])
                dfs(i);
        for(ti=0,i=n;i>0;i--){
            if(!ret[cal[i]]){
                ti++;
                rdfs(cal[i]);
            }
        }
        int ans=0;
        memset(cal,0,sizeof(cal));
        for(i=1;i<=ti;i++){
            if(!cal[i])
                dfsr(i);
            ans=max(ans,cal[i]);
        }
        if(ans==ti) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

acleast 2010-04-17 11:41 发表评论