不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/12/03 03:51 | 评论(0) | 阅读(4832)
【题目大意】
      统计在N*M的点阵上有多少个点和左下角的连线不经过其它点。
      (M,N<=50000)

【题目分析】
      不难发现,点(C,D)能在以(A,B)和(1,1)为端点的线段上的充要条件是:
            A = k*C , B = k*D , k是正整数。
      所以显然原问题等价于{1,2,...,M}和{1,2,...,N}中各取一个数能得到多少组互质数对。
      先考虑一个更简单的问题:
            如何快速求出{1,2,3...N}中有多少个数和X互质?
      对于这个简化的问题我在这里不加证明地套用容斥原理来处理:
            将X分解质因数,设质因数的集合为{F},枚举它的子集{F_sub},那么简化问题的答案是:
                  ∑(N / ∏F_sub_i)*(-1)^|F_sub|
      解决了上面的简化问题,我们只需在1~M间枚举这个X,然后求出简化问题的答案,加起来即可,实际运行速度非常快。
      核心代码如下:

void Dfs(int Step,int Frac,int Tot)
{
    if(Step >= F.size())
    {
        if(Tot&1)
            Ans -= (long long)(M/Frac);
        else
            Ans += (long long)(M/Frac);
        return;
    }
    Dfs(Step+1,Frac*F[Step],Tot+1);
    Dfs(Step+1,Frac,Tot);
}

void Count(int Num)
{
    int Cur = Num;
    F.clear();
    for(int i=2;i*i<=Num;i++)
        if(Cur%i == 0)
        {
            F.push_back(i);
            while(Cur%i == 0)
                Cur /= i;
        }
    if(Cur > 1) F.push_back(Cur);
    Dfs(0,1,0);
}

Ans = 0;
for(int i=1;i<=N;i++)
    Count(i);
cout<<Ans<<'\n';

Tags: ,
数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/12/03 02:28 | 评论(2) | 阅读(16941)
【题目大意】
        给出N个正整数,若将其分成三组,每组的和作为三角形一条边的长度,能得到多少种合法的三角形。
        (N<=200,N个数的和Sum不超过600)

【题目分析】
        这题应该不难想到可以递推来做。
        F[i,j,k]表示前i个整数能否凑出一个边长分别为j,k,Sum-j-k的三角形,那么有递推式:
              F[i,j,k] = F[i-1,j,k] or F[i-1,j-Li,k] or F[i-1,j,k-Li]
        这个题时限比较紧,而上面这个递推复杂度是O(NSum^2),很容易超时,所以得注意一下常数优化,核心代码如下:

        F[0][0][0] = 1;
        int Cnt = 0;
        for(int i=1;i<=N;i++)
        {
            int L;
            int Cur = i&1 , Pre = (i-1)&1;
            scanf("%d",&L);
            Cnt += L;
            memset(F[Cur],0,sizeof(F[Cur]));
            for(int j=0;j<=Cnt;j++)
                for(int k=0;k<=Cnt-j;k++)
                {
                        if(F[Pre][j][k])
                        {
                            F[Cur][j][k] = 1;
                            continue;
                        }
                        if(j >= L)
                            if(F[Pre][j-L][k])
                            {
                                F[Cur][j][k] = 1;
                                continue;
                            }
                        if(k >= L)
                            if(F[Pre][j][k-L])
                            {
                                F[Cur][j][k] = 1;
                                continue;
                            }
                }
        }

        做完上面这个递推,我们只需要枚举目标三角形两条边的长度,对于合法的目标三角形利用递推出的F判断其是否可以得到,统计即可。
      
Tags: , ,
数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/05/22 19:39 | 评论(3) | 阅读(5553)
【题意简述】
      给定N个点和M条有向边,试判断是否能够成一个由外向树构成的森林。
      若可以,请输出所有节点中最大的深度,和同一深度的最大节点数。
      (N,M<=100)

【分析】
      我们首先来解决第一个问题,如何判断是否该森林由外向树构成。
      外向树应该满足这么几个条件:
          1.  每个点入度为0或者1
          2.  不存在自环
          3.  不存在环。
      我们在读入后可进行判断。
      确定是森林后我们即可在每棵树上进行递推,求出所有点的深度,
      然后Hash统计每种深度的节点数,
      最后输出即可。
Tags: ,
数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | felix021 @ 2009/05/17 02:47 | 评论(0) | 阅读(3812)
并查集,需要一定的改进。

典型的并查集是每个元素固定一个编号,用一个数组保存其父节点,然后在查找父节点的时候进行路径压缩;代码如下:
int parent[10000];
void init(int n){ //初始化,每一个元素自成一组
    for(i = 0; i < n; ++i) parent[i] = i;
}

int get_parent(int i){
    if(parent[i] != i){
        p[i] = get_parent(p[i]); //路径压缩, 改用非递归效率更高
    }
    return p[i];
}

int union_set(int a, int b){ //合并两个集合,如果可以按秩合并则更佳
    int pa= get_parent(a), pb = get_parent(b);
    parent[pa] = pb;
}


在本题中,需要删除一些元素,而又不希望被删除的元素(记为d)的改变影响到其他和 d 在同一组的元素(比如d是所有同组元素的祖先)
因此可以另外开一个数组 pid[], pid[i]存放的是元素 i 的编号,这个编号在程序运行过程中是逐渐变化的。
当删除了 元素 i 以后,将元素 i 的编号更改为当前最大的编号+1(新的pid[i]),再把parent[i]赋值为新的pid[i]
这样可以使得元素 i 原先的同组元素不受影响,且元素 i 被分配到一个只包含元素 i 的新组。
在程序中将原先的 i 题换成 pid[i],即得到对应程序(注意:get_parent(int i)中的 i 不需要改变,为什么?)。
Tags:
数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | felix021 @ 2009/05/16 23:54 | 评论(4) | 阅读(5192)
这是腾讯创新大赛(tic)复赛的E题,Felix自己生成了一组数据加在WOJ上面。

p.s. 有一点小变化:数据中日期出现的次数不是升序了,是随机的。

这道题目是典型的动态统计题目,而且查询/更新次数最高是10w,
也就是说,每次查询/更新的效率必须控制在O(logN)才行,
所以必须考虑使用线段树这类查询和更新都是O(logN)的、适合动态统计的数据结构。

想到这点,就可以转为考虑怎样在线段树的节点中存储合适的信息,思路也就清晰了:

在线段树的每个节点表示线段[a, b] (包括左右端点),其中存储积分介于[a, b]之间的QQ数量。
题目给的数据看起来很大,10w * 30 = 300w,这样会MLE。
但是仔细看看就会发现,每天的上限是100,每次增加的是10,20,30,都是10的倍数。
所以我们可以把这个上限缩小到10w * 3 = 30w,这样就能够在给定的空间限制下使用线段树。

在这个基础上,另外使用map(或者用更高效的hash)来存储QQ号的对应信息(总积分和每天的积分)
其中每天的积分最好再用一个map/hash来存储。

在每次需要更新的时候,记更新前积分为m,更新后为n,则需要进行如下操作:
  decrease(m) ---- 递归地将线段树中包含 m 的区间的QQ数量减少一
  increase(n) ---- 递归地将线段树中包含 n 的区间的QQ数量增加一
在每次需要查询的时候,递归地计算大于该QQ积分的QQ数量即可。
以上将线段树的基本操作进行简单修改以后即可实现,具体参见
下载文件 (已下载 2083 次)

数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | felix021 @ 2009/05/15 15:24 | 评论(0) | 阅读(3683)
描述:给出一组数字,将其分成n组,每组包含的数字是从小到大互不相同。求最小的n。
分析:

首先很容易想到模拟:
读入所有数字,排序(将相等的数字放在了一起),然后一遍一遍地扫描,每次扫描从中尽可能多地抽出一组互不相同的数字(每一堆相等的数字里面抽出来一个),直到数组中所有数字都被抽出。由于需要数字的删除,所以显然用链表比较合适。

然后考虑这样一种情况:
如果一组输入数据是
5
2 2 2 2 2
那么你需要扫描5遍才能得出结果。
事实上再仔细思考一下就会发现——其实只要找出重复次数最多的那个数字,输出它的重复次数就可以了。
Tags: ,
数据结构和算法 » WOJ | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | felix021 @ 2009/05/13 04:25 | 评论(0) | 阅读(3062)
求解最长递增子序列的长度。
由于数据量比较大,O(N^2)的普通DP会TLE,所以需要使用O(NlogN)的优化算法。
简而言之就是用一个同样大的数组B[1..N], B[i]存储的是所有长度为 i 的递增子序列的最小末尾。可以从B[1] = Data[0]开始,逐个将Data[i]有序地插入B数组中,而插入过程可以使用二分进行优化。

------

详细:

最长递增子序列,Longest Increasing Sequence 下面我们简记为 LIS。
排序+LCS算法 以及 DP算法就忽略了,这两个太容易理解了。

假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7,可以看出来它的LIS长度为5。
下面一步一步试着找出它。
我们定义一个序列B,然后令 i = 1 to 9 逐个考察这个序列。
此外,我们用一个变量Len来记录现在最长算到多少了

首先,把d[1]有序地放到B里,令B[1] = 2,就是说当只有1一个数字2的时候,长度为1的LIS的最小末尾是2。这时Len=1

然后,把d[2]有序地放到B里,令B[1] = 1,就是说长度为1的LIS的最小末尾是1,d[1]=2已经没用了,很容易理解吧。这时Len=1

接着,d[3] = 5,d[3]>B[1],所以令B[1+1]=B[2]=d[3]=5,就是说长度为2的LIS的最小末尾是5,很容易理解吧。这时候B[1..2] = 1, 5,Len=2

再来,d[4] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时候B[1..2] = 1, 3,Len = 2

继续,d[5] = 6,它在3后面,因为B[2] = 3, 而6在3后面,于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6,还是很容易理解吧? Len = 3 了噢。

第6个, d[6] = 4,你看它在3和6之间,于是我们就可以把6替换掉,得到B[3] = 4。B[1..3] = 1, 3, 4, Len继续等于3

第7个, d[7] = 8,它很大,比4大,嗯。于是B[4] = 8。Len变成4了

第8个, d[8] = 9,得到B[5] = 9,嗯。Len继续增大,到5了。

最后一个, d[9] = 7,它在B[3] = 4和B[4] = 8之间,所以我们知道,最新的B[4] =7,B[1..5] = 1, 3, 4, 7, 9,Len = 5。

于是我们知道了LIS的长度为5。

!!!!! 注意。这个1,3,4,7,9不是LIS,它只是存储的对应长度LIS的最小末尾。有了这个末尾,我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这组数据没有什么意义,但是如果后面再出现两个数字 8 和 9,那么就可以把8更新到d[5], 9更新到d[6],得出LIS的长度为6。

然后应该发现一件事情了:在B中插入数据是有序的,而且是进行替换而不需要挪动——也就是说,我们可以使用二分查找,将每一个数字的插入时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN)~!
数据结构和算法 » WOJ | 引用(0) |
分页: 1/9 第一页 1 2 3 4 5 6 7 8 9 下页 最后页 [ 显示模式: 摘要 | 列表 ]