集训

Quick Challenge 2007

终于还是再回来 ACM/ICPC 队里玩, 陪大家一起玩, 继续去年的 KO Challenge, 只是改成了 Quick Challenge. 找题真是个很郁闷的事情, 现在有太多的人在 POJ 上做题了, 找一个合适的题真是麻烦, 要能在一个小时内过掉, 并且又不是所有人都能很轻松的过掉, 不能太复杂, 也不能完全弱智完全拼 APM, 最重要的是, 尽量没人做过.

前天下午开始找题吧, 随便翻了一下, Mid-Atlantic 2005 的套题里随便弄了一个出来, 看半天觉得是硬搞, 偏偏去看了下 Discuss 成了 DP, 很恶心的还不说是集合 DP, 并且给的那个递推式貌似有 bug, 错了一个小时后怒了去 POJ 上交官方标程居然都很慢, 果然全排列还是慢了. 改自己很恶心的喜欢敲的集合 DP, 顺利 AC, 0ms. 比较了一下觉得 POJ 上数据不全, 放 WOJ 上, 没人过, 然后在 POJ 上居然能卡过去, 还有在 WOJ 上 WA 而 POJ 上 AC 的, 比较了一下是最后一组数据, 有一个条件他们判错了. 无语了, 联系 POJ 的 admin, 把数据加全, 然后 rejudge, 放倒一片… 我不是故意的… 大家就当从我身上获取 rp 吧…

今天去找了个有点像计算几何的, 结果被一群人用模拟水掉… ft. 无语了. 到底是我的敏感程度不一样还是无知无谓? 异或还是数据太弱? 回头我去加强…

还是要坚持唯心论的

今天做timus, NEERC, Eastern Subregion, Yekaterinburg, 算是Moonmist很失败的比赛了吧. 开场10分钟有人过4题, 而我却看错简单题题目意思白白WA了一次, 然后是另一个简单题直接没看懂意思, 让Moon去写又慢了很多. G自己一直觉得很迷惑, 那个Sample… 但是自己一直没去怀疑Sample是错的, 还是努力的去理解俄式英语, 同时刷页面期待有更正, 到1个半小时并且错了2次(其中一次是完全理解错误)后才AC, 太失败了.

现在已经很少去怀疑数据了, 特别是像今天这种根本对题意没理解的情况下, 因为看不明白英语在说什么, 只能从Sample上去理解题意了, 结果还是很郁闷. 周四的Romania2006, 那个C, 错的也太那个什么了, 差点跟DC吵起来. 后来到了89min的时候KO觉得很奇怪再看了一下数据发现前面还有个case_total, 不然还是有问题的, 其实前面两次错的都一样, 我的唯心论还是对的. 那个并查集的, 自己对tank的程序已经几乎优化到极限了还是TLE, PC^2提问DC也不理, 最后还是KO给ReJudge发现已经过了, 2s多, 比tank的快了5s左右.

我要重新唯心起来, 这样才会有那种舍我其谁的霸气, 才会让80%的实力发挥到120%.
今天重新听五月天的倔强: 我就是我自己的神, 在我活的地方

NWERC 2005 Unequalled Consumption

以下内容引用自frkstyc’s Blog, 原文地址:
http://www.blog.edu.cn/user2/frkstyc/archives/2006/1180760.shtml

——————————————————-我是分隔线——————————————————

有人曾经在POJ webboard上声称生成函数是“没用的东西”。但这个题却是利用生成函数解决问题的一个很好的例子。

题目的大意是有不超过5种重量在10以内的糖果(不同的糖果可以有相同重量),给一个整数P<= 1015,要求一个最小的重量w,只得做一个重量为w的糖果盒的不同方法数至少是P

看到P的规模就可以立即否决普通的动态规划解法。容易联想到的算法是二分法,但这个题乍看之下没有明显的单调性。尝试用生成函数解决。为描述方便,以下直接用一个实例来说明。

假设有3种糖果,重量分别为2, 3, 5。用生成函数中xn项的系数表示做重量为n的糖果盒的方法数,那么对应的生成函数就是

f(x) = 1 / ((1 – x2)(1 – x3)(1 – x5))。

这个形式是没有办法直接利用的,因为里面三个因子的展开式都有无穷项,要直接找系数的通项公式也不容易。但是利用一个很简单的技巧就可以解决这两个问题。(应当说明,这个技巧虽然看起来很简单,但的确是要费一番思考的。)注意到2, 3, 5的最小公倍数[2, 3, 5] = 30,因此将上面的式子改写一下,变成

g(x) = ((1 – x30) / (1 – x2)) ((1 – x30) / (1 – x3)) ((1 – x30) / (1 – x5)),
h(x) = 1 / (1 – x30)3,
f(x) = g(xh(x)。

这样,g(x)是一个一般的多项式,h(x)虽然有无穷项但形式很规整,f(x)只是g(x)和h(x)的乘积。

g(x)只需直接展开即可,展开的结果是一个次数小于3 * 30 = 90次的多项式。对于h(x),为方便起见,作一个换元,记

h’(y) = 1 / (1 – y)3。

通过计算或者查阅工具书可以知道h’(y)中yn项的系数为组合数C(3 – 1, n + 3 – 1),其中的3就是h’(y)的解析式中1 – y的次数。因此h(x)中x30 n的次数也是C(3 – 1, n + 3 – 1),而其他项的系数都是0。

综合上面的讨论,可以得到计算f(x)中xn项的系数的方法。记p(x)中xn项的系数为c(pn)。对于n< 90,c(fn)可以直接利用动态规划或者限制次数地直接展开f(x)得到。(注意:这个不是c(g,n)!)对于n >= 90,记n = 30 k + r,其中0 <= r < 30,那么根据f(x) = g(xh(x),有以下公式

c(fn) = C(2, k + 2) c(gr) + C(2, k + 1) c(gr + 30) + C(2,  kc(gr + 60)。

f(x)直接相关的计算已经基本解决。剩下求最小的问题,方法还是二分法。虽然从整体看,c(f,n)关于n不一定是单调的,但是假如把n写成n = 90 k + r,其中0 <= r < 90,就可以发现对固定的r,c(f, 90 k + r)关于k是单调的。因此只需枚举r,对k应用二分法,然后从所有候选的n = 90k + r中选取最小的即可。

We failed

This afternoon we did a practice with yzf, but all the three team failed, sigh~

Problems from NordicCPC2005, one of my favorite regional, I typed the first 4 code, then helped moon to finished our 5th code, we kept silence in the middle, which makes us looks like a second-class team. We failed on the Problem B, a Min-Max game, which should be a part of my knowledge architectonic, but which makes me unacceptable is that yzf used a greedy algorithm to solved it.

We need a long way to go, to be a first-class team. We are the Moonmist~

底线

Moonmist, 在这个秋天, 注定是我这段生命里最重要的部分.

今年, 我们有很多惊喜, 有太多的意外收获, 同时, 也有大家的辛勤努力和前辈们的积累. 今年, 我们依然会说我们要银牌, 不过, 这只能是Moonmist的底线.

从现在的成绩来看, 出线甚至都是可以想象的事情, 而不像去年, 如果出线了那才撞鬼. 我现在都可以YY明年初夏的夏威夷了.

比较切实一点的目标是, 我们要在银牌的领先军团中拿到金牌, 这是一个可以实现, 并且也不是太难实现的一个目标. 我有看过我们做的练习赛别人的成绩, 有过比较有过分析才得出此结论, 并且现在队内认可这一点并且我们也都在为这个努力. 今年的武大没有虚华, 我们要将朴实无华演绎成绚烂夺目.

遵守KO的规则, 不透露其他的, 遵循我们队的原则, 好好努力. Moonmist.snoopy, 你需要加油, 不要让Moonmist因你而失色.

这里在荒废…

一个原因是因为我开始写spaces来练英文写作了, 那个可是真的每天更新.

不过重要的应该是现在自己不想说话了, 现在我沮丧的时候就会不说话, 很多时候会莫明其妙的沮丧… 并且我现在说的都是不开心的事情, 开心的都是和ACM/ICPC有关的啦, 可惜KO不让说 :(

最后欢迎大家去我的spaces做英文改错啦, 给你们自信, 看看还有英文这么挫的人让你们bs:
http://whusnoopy.spaces.live.com/?mkt=en-us

个人赛,后两天

编号.题目                    来源        简单说明
D3A.Bishops                 not found   简单公式题
D3B.Football Coach          not found   最大流
D3C.CLRS                    not found   DFS或者强联通分量
D3D.Sequence Again          POJ2478     筛素数法求欧拉函数
D3E.Intervals               not found   线段树
D3F.Matrix                  not found   矩阵构造+矩阵乘法

D4A.area                    not found   DP+凸包
D4B.Prime                   not found   求素数距离,筛法求素数到3*10^7
D4C.Traveling Queen Problem POJ2919     BFS+集合DP,BT题,我看标程都头大
D4D.Squares                 not found   BFS+Hash打表或双向BFS
D4E.Candies                 not found   贪心带硬搞
D4F.Card Game               POJ2062     最大匹配或者贪心

p.s.来源标注为not found均为目前还未找到来源的题,其中部分为KO原创,部分为
只改描叙的陈题

个人赛,前两天

发信人: snoopy (Snoopy@T13), 信区: ACM_ICPC
标  题: 个人赛前两天题目来源
发信站: 珞珈山水BBS站 (Sat Aug 12 10:05:22 2006), 转信

非官方版本,今天早上找了一个小时找全了的
第二天的G据KO说是原创,但是和Tongji的1004防御导弹是一样的

编号.题目            来源        简单说明
D1A.dna             POJ1080     DP
D1B.Game            POJ1143     集合DP+博弈?
D1C.spell           POJ1035     直接硬搞
D1D.Frames          POJ1128     模拟?
D1E.Cable           POJ1064     转换成整数二分
D1F.2046            POJ1733     并查集+Hash
D1G.Transmitters    POJ1106     简单计算几何,算叉乘

D2A.Excel-lent      POJ2273     模拟,类进制转换
D2B.Dice            POJ1481     简单双重DFS
D2C.Rocket Height   POJ2276     初等几何,推公式
D2D.Slides          POJ1486     类匹配思想,硬搞
D2E.Lotto           POJ2193     DP,要用longlong
D2F.Optimal         POJ1480     BFS硬搞
D2G.Sequence        Tongji1004  贪心

除了第二天的G,全部都是没做过的...ft

最优匹配(Kuhn_Munkras算法)

// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v&lt;=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&amp;&amp;(fy[v]&lt;0)) {
            fy[v]=1;
            if((maty[v]&lt;0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i&lt;=nx;i++) {
        lx[i]=-INF;
        for(j=1;j&lt;=ny;j++)
            if(w[i][j]&gt;lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i&lt;=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k&lt;=nx;k++)
                if(fx[k]&gt;0)
                    for(j=1;j&lt;=ny;j++)
                        if((fy[j]&lt;0)&amp;&amp;(lx[k]+ly[j]-w[k][j]&lt;p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j&lt;=ny;j++) ly[j]+=(fy[j]&lt;0?0:p);
            for(k=1;k&lt;=nx;k++) lx[k]-=(fx[k]&lt;0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i&lt;=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v&lt;=ny;v++)
        if((mat[u][v])&amp;&amp;(fy[v]&lt;0)) {
            fy[v]=1;
            if((maty[v]&lt;0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i&lt;=nx;i++)
        if(matx[i]&lt;0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************