武汉大学ACM/ICPC协会——主页

光庭杯第五届华中北区程序设计邀请赛

Thu, 18 Mar 2010 16:00:59 +0000

详情请点击：赛事主页

WHUACM的Wiki建立起来啦

Mon, 08 Mar 2010 13:45:40 +0000

http://acm.whu.edu.cn/wiki
这个wiki建立起来有两个目的：
一是为了保存集训队历史和记录各种成绩。
二是发布解题报告。
希望退役的老队员和现役的队员还有校外的ACM朋友们都能够把这个wiki的资料完善起来。
wiki有着很强的共享精神，写的差或者简单点没有关系，因为会有后来的读者帮你编辑和完善：）

WHUACM新年贺辞

Thu, 31 Dec 2009 15:59:59 +0000

　　值此2010年来临之际，WHUACM向所有关心、支持、参与武汉大学ACM/ICPC赛事活动的各位领导、兄弟高校、全体ACMer致以衷心的感谢。向大家致以诚挚的问候和衷心的祝福。祝大家新年愉快，身体健康!

　　2009年，是WHUACM腾飞的一年。经过这一年多的努力和付出，我们取得了前所未有的成绩，摘金夺银时更是连年闯入World Final，开创了武汉大学在此类竞赛的新里程碑。在此，我们为这份荣耀自豪。

　　展望2010年，我们面临着更大的机遇与挑战，但我们相信2010的到来也意味着新的奋斗的开始，希望全体WHUACMer继续满怀自信地以自己的行动为武汉大学争光。

　　最后，再一次对关心和支持WHUACM发展的各界朋友，致以衷心的感谢!祝大家节日期间，共度美好时光，新年新气象。

ACM集训队新队员名单

Tue, 15 Dec 2009 11:01:29 +0000

（排名不分先后）
曹玮，罗宸，徐正奇，蒲凡，朱海帆，郑宇石，郑宇航，陈兴委，孙谋，马程杰，马跃超，陈尧，曹寅，孙斌，许光，王忠祥，张莆林，李亚，刘博，盛伟，王凌霄

请新队员加入集训队QQ群：12275369，验证信息为自己的名字，进群后修改自己的名片为自己的名字

集训队的相关讯息会在珞珈山水BBS ACM版公布，请新队员们注意查看

另外请因为没有及时看到通知而错过面试的同学直接联系李嘉琦同学（QQ：68390616）

集训队新队员面试

Sat, 12 Dec 2009 09:58:33 +0000

集训队新队员面试定于12月13日（星期日）下午2点在计算机学院5楼集训队机房进行

请所有有兴趣加入集训队的icc或EmingCup的大一大二参赛队员届时前来参加面试

请注意：比赛成绩不是能否进入集训队的决定因素！

Eming杯程序设计大赛圆满结束

Sat, 05 Dec 2009 12:43:38 +0000

      2009年12月5日，武汉大学Eming杯程序设计大赛在武汉大学计算机学院（信息学部）503机房顺利举行！本次比赛共计40多支参赛队伍报名，参赛选手涵盖计算机学院、国际软件学院、电信院、数院、资源与环境学院等多个学院。本次比赛参赛选手水平较往年有所提高，竞争更加激烈。经过30分钟的热身赛和4个小时正式赛的激烈角逐，以下队伍获得了较好的成绩，特此公示：

冠军

ACFun （王凌霄、徐来）

一等奖

PersonalComputer（蒲凡、曹玮）  daisy（马跃超、马程杰）

二等奖

C.Y. （曹寅、陈尧） sres-xg（许光、王陈希）Hard&Dark（郑宇石、郑宇航）

三等奖

Ghost（朱海帆、金志威） TAT（孙谋、鲁道沅） PK_Seven（任杰、梁小双）Victorinox（王国熹、张驭宇） Tale（王忠祥、张莆林）

EMING杯比赛时间地点

Thu, 03 Dec 2009 13:39:39 +0000

      由于场地原因，EMING杯决赛将于提前至12月5日举办，具体时间地点如下：

比赛时间：2009年12月5日（周六），13：00 - 17：00

比赛地点：武汉大学计算机学院（信息学部），五楼机房

    希望大家届时按时参加比赛。

WOJ 1420 - 可见点

Wed, 02 Dec 2009 19:51:20 +0000

【题目大意】
      统计在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<

Tags - 搜索 , 数学

WOJ 1418 - 三角形的数量

Wed, 02 Dec 2009 18:28:47 +0000

【题目大意】
        给出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 - 动态规划 , dp , 递推

国软编码挑战赛圆满结束

Sun, 29 Nov 2009 10:41:12 +0000

经过四个小时的激烈角逐，最终来自计算机学院的09级本科生曹玮荣获冠军。

获得一二三等奖的选手分别为：
一等奖
文祎骁朱海帆马跃超
二等奖
王凌霄孙谋涂坤彭星张驭宇
三等奖
陈兴委徐正奇阮桂亮郝春艺魏川博
罗鹏袁伟孙斌朱恒辉 凤娇

冠军将获得直接进入武汉大学ACM/ICPC集训队的资格。
解答出五题及以上的选手将有机会参加集训队招新面试，通过面试后即可入队。
面试时间及方式等相关信息请继续关注本站。

本次比赛的数据及标程可在WHU BBS的ACM板块中下载。
http://bbs.whu.edu.cn/