不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/12/03 03:51 | 评论(0) | 阅读(4764)
【题目大意】
      统计在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) | 阅读(16842)
【题目大意】
        给出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) |
不指定 类别: 数据结构和算法 | felix021 @ 2009/07/29 14:46 | 评论(5) | 阅读(7922)
发信人: Felix021 (Felix), 信区: ACM_ICPC
标  题: STL简析(PPT+示例代码+手册)
发信站: 珞珈山水 (Wed Jul 29 14:03:40 2009), 站内

花了一天多的时间整理的,希望对大家有用吧。

PPT最后提到的那些东西在这里可以down到:
ftp://acm.whu.edu.cn/eBooks/STL/


数据结构和算法 | 引用(0) |
不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/05/22 19:39 | 评论(3) | 阅读(5498)
【题意简述】
      给定N个点和M条有向边,试判断是否能够成一个由外向树构成的森林。
      若可以,请输出所有节点中最大的深度,和同一深度的最大节点数。
      (N,M<=100)

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

典型的并查集是每个元素固定一个编号,用一个数组保存其父节点,然后在查找父节点的时候进行路径压缩;代码如下:
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) | 阅读(5133)
这是腾讯创新大赛(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数量即可。
以上将线段树的基本操作进行简单修改以后即可实现,具体参见
下载文件 (已下载 2079 次)

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

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

然后考虑这样一种情况:
如果一组输入数据是
5
2 2 2 2 2
那么你需要扫描5遍才能得出结果。
事实上再仔细思考一下就会发现——其实只要找出重复次数最多的那个数字,输出它的重复次数就可以了。
Tags: ,
数据结构和算法 » WOJ | 引用(0) |
分页: 1/10 第一页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]