随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

2010年9月13日

Giant For (2010天津网赛 1007)

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

posted @ 2010-09-13 14:56 acleast 阅读(111) | 评论 (0)编辑 收藏

2010年5月17日

zju 1484 hdu 1394 求最小逆序(点树)

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

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




 

posted @ 2010-05-17 17:17 acleast 阅读(551) | 评论 (0)编辑 收藏

2010年5月6日

POJ 1990 MooFest 数状数组

题目大意:
  有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中所有牛的坐标之和。

posted @ 2010-05-06 17:20 acleast 阅读(130) | 评论 (0)编辑 收藏

2010年5月4日

POJ 3686 The Windy's 拆点+KM

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

posted @ 2010-05-04 21:30 acleast 阅读(347) | 评论 (0)编辑 收藏

POJ 1639 Picnic Planning 最小限度生成树

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

posted @ 2010-05-04 21:12 acleast 阅读(2116) | 评论 (8)编辑 收藏

2010年5月3日

POJ 2230 Watchcow 有向图的欧拉回路

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

posted @ 2010-05-03 15:55 acleast 阅读(317) | 评论 (0)编辑 收藏

2010年5月2日

POJ 1041 欧拉回路

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

posted @ 2010-05-02 22:14 acleast 阅读(779) | 评论 (2)编辑 收藏

2010年4月24日

poj 3214

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

posted @ 2010-04-24 17:53 acleast 阅读(152) | 评论 (0)编辑 收藏

2010年4月17日

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

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

posted @ 2010-04-17 21:59 acleast 阅读(246) | 评论 (0)编辑 收藏

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

又贡献了一版的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;
}

posted @ 2010-04-17 11:41 acleast 阅读(137) | 评论 (0)编辑 收藏