SQYBI.com

Always Challenge Miracle

Archive for the ‘题解’ tag

Time Limit Exceeded 结束 && Happy Valentine’s Day~

with 8 comments

昨天搞完了 Time Limit Exceeded, 现在还有一道题TESTGEN没有测试, 其余题目我们 YaohuaFree 的 Rank 是 41, 得分很诡异地竟然是 1234 分 (Rank List). 还算可以接受吧, 不过很可惜最后还是没有达成超过 lonelycorn 和搞掉 CLASS 这两个目标.
简单的说一下题目.

  1. Key to C (KEY)
    这道题是我们第一道出的题目, 也是搞得最久的一道题目, 不过事实证明这道题根本拉不开分差 — 最高的 154 分, 而我们 126 分就 20 多名了. 和其他的题目的 rank 1 动辄上千分比起来, 这道题做了基本相当于没做.
    题目要求读入一些数, 判断它们的二进制表示是否回文. 评分标准和很多东西有关, 比如程序中关键字的个数 (这个权重最大), 比如空格个数, 比如代码长度… 总之这些东西都是越多得分越低. 然后代码回文会得到 extra bonus, 貌似是 4 倍多分数吧.
    基本的做法就是?:操作符加main递归, 貌似 rank 1 那个也就这么做的.
  2. Play with Code (SHORTEN)
    给出一个代码要求缩短. 这道题最终也不知道那个代码到底啥意思, 只看懂了一段求素数. 而且那个代码在我们几个人的机器上跑貌似都 RE 掉了… 评分规则是代码长度越长分数越少.
    最终的做法是物理缩短… 也就是 define 一个 for 啊, 改一点变量名啊… 就这样子…
  3. Produce the Code (INPUT)
    给出一个输入文件和一个输出文件, 要求写一个程序, 对于这个输入文件能够输出给出的输出文件. 当然可以不理睬输入文件直接把输出文件打出来 (我的第一个 code 的确是这么干的), 不过这样代码长度会很长, 而这道题的评分规则也是代码长度越长分数越少…
    这道题由三个人合力完成… 先是来帮忙的 xhy 同学看出了替换规则 (我就是一直卡在这里), 然后我折腾出了乱序的规则, 最后是木木同学的 coding… 虽然 rank 不高不过做得很爽.
  4. #ED (CODEHASH)
    给出一段代码, 给一个 hash 函数, 要求代码输出自身的 hash 值.
    貌似有人用 whitespace 来搞, 不过还是比较 orz 那个 rank 1 的, 就一句代码… 很强大.
    这题我们一点没动.
  5. COMPILE ERROR (CLASS)
    我最想做出来的题, 但可惜最后也没做出来.
    要求写一个类 multiply, 里面包括一个函数 mult(int a, int b), 函数的功能是输出 a * b 的结果, a, b 都小于 10000. 变态就变态在不允许用空白字符…
    见到了两种解决方法, 一种是官方的 (之所以说官方因为这道题提示了要用 typedef, 如果认为题目描述的那个 "typedefine a class" 不足以说明问题, 那么自己去翻 forum), 另一种很诡异, 用一个不可见字符替代了空白字符还编译通过了… 据说那个字符是 \f, 从来没见过…
  6. PRINT D PENGUIN (PENGUIN)
    给一个字符画, 是 Linux 那个企鹅. 要求输出这个东西.
    基本就是考压缩, 我因为怕编译器没法处理所以只压缩成了可见字符, 但是事实证明编译器是可以处理不可见字符的, 因为 rank 前几名的都用了不可见字符. 我很无奈, 不过可见字符范围的压缩我基本是搞到极限了, 还比较有成就感.
  7. PRINT ME (PRINT)
    这道题是前来帮忙的 xhy 写的, 题目要求很简单, 输入一个数, 如果是偶数那么输出代码本身, 否则反转代码输出.
    xhy 写了一个回文的代码, 这样就不用管奇数偶数了, 而且根据题目还可以获得 200 pts 的加分.很不错.
    最后一天用了很短的时间完成的 code, 得分还不低 (貌似是所有题里 rank 最高的一个), 或许是性价比最高的一个 code 了.
  8. P=NP (NP)
    这道题的题目描述讨论了半天也没明白, 最终放弃. 直接贴出英文题目描述, 做出来的神牛 (比如 oldherl) 来讲解一下…
    "Given an directed graph, find out the minimal set of vertex such that all vertex not in the set have atleast one edge in the set."
  9. P!=NP (TESTGEN)
    这道题是为上一道题出测试数据 (想起 SRM 了), 以上一道题 submit 的代码跑的情况评分. 因为前一道题没看懂, 加上最后还有 10 分钟的时候才开写, 所以输出了一个基本是完全图的图草草了事. 这道题至今还没出成绩.
  10. Arbit Code (ARBIT)
    此题做的比较爽. 给一段会 TLE 的代码 (实际测试证明还会 RE), 要求改成能够 AC 的代码. 不知道代码是干什么的, 只有数据范围.
    这道题我们的做法是, 把一个范围内 (刚开始是 1~20, 后来为了测试增加到了 1~50) 的所有输入全部打出来, 然后分析规律.
    刚开始的成果是, 求 f(a, b)的时候, 把 b 从 1 到 a 列出表格, 发现每到 a 的约数才发生变化.
    接下来我发现对于素数和素数的幂, 它们的 f 的变化规律是按照比它小的幂变化 (不太好描述, 想知道的话自己输出几个比如 a = 27 或者 16 就能发现了).
    然后木木又发现了 f(a, 1) = phi(a) (这里 phi 是欧拉函数).
    最后时刻木木大胆猜测:
    当 b = 1 时, f(a, b) = phi(a);
    当 b 不是 a 的约数 (a % b != 0) 时, f(a, b) = f(a, b – 1);
    当 b 是 a 的约数时, f(a, b) = f(a, b – 1) + f(a / b, 1).
    然后写了个 code submit 上去, 挂了.
    差点就认为这个推测不对, 但是本地测试 100 以内的数据发现和给出的程序输出完全匹配.
    最后偶然发现, 有一句要做 t * ((i – 1) / i) (不用说也知道是求欧拉函数时候写的), 我当初写的是 t * (i – 1) / i, 而 t * (i – 1) 会爆掉 int… 改成 t / i * (i – 1) 就 AC 了.
  11. Give It a try (THINK)
    这道题是最有意思的, 要求破解三个密码, 没有任何提示.
    第一个密码很简单, 一篇文章, 把里面所有的大写字母挑出来拼在一起, 就是答案了.
    第二个密码是一个 32 * 241的 01 矩阵, 最后也不知道是啥意思, 只知道答案是 2.
    第三个密码, 刚开始一看就感觉是一个简单的 26 个字母的置换, 然后还推出了 p => e, 另外还找到了三个 p 连在一起的一个突破口. 但是无奈没有破解经验, 加上文章里竟然 26 个字母都是齐全的, 让我有点打退堂鼓, 所以没有一鼓作气破解出来, 很遗憾. 其实想想, 当初直接按照统计学的字母出现频率解密, 然后再做微调, 应该都可以把密码破出来了… 很无奈.

比赛基本就是这样, 最后的 1234 分真的不是有意为之… 运气比较好吧.

——————-我是爱情的分隔线——————-

今天情人节, 白天在家待了一天 (本来说要和 lxc, djs 去打台球, 一想今天人应该多就没去), 晚上去 FNOI (还迟到了), 就这么度过了情人节.

放一张图, 从 M67 那里看到的, 来源是 Abstruse Goose (来源页面).

alicenbob 

祝各位情人节快乐, 估计我能在本科上完之前找到第一个 GF 就很不错咯… 光棍节还可以一直过下去, 很满足很满足…
p.s. 文章写完正好 0:00, 情人节过去了… 这篇文章的分类想了很久是 About Computer 还是 About
Life, 最终还是放在了前者里…

Written by sqybi

二月 15th, 2009 at 12:03 上午

Posted in About Computer

Tagged with , , , , ,

NOIP 2008 第四题 双栈排序(twostack) 题解

with 25 comments

这可能是第一份正确的完整题解.

这个帖子: http://www.oibh.org/bbs/thread-26983-1-2.html 是此算法的来源,但是帖子中说的不是很清楚,而且没有证明.题解中将把这些问题解决.
十分感谢inzaghi250(sqybi注:还好我不是inzaghi的fans…)提供的算法.

这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.

这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.

第一步需要解决的问题是,判断是否有解.

考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].

首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.

接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是”如果不满足条件p,那么这两个数一定可以压入同一个栈.”
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.

此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.

这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边,表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~
二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.

此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~

还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了.

附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1.
已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~

xpycc  November 29th, 2008 at 09:24

这位大牛不妨试试以下数据:
1000
2 3 4 5 … 1000 1
对于这组数据 MS 您的程序崩溃了……

原因是这组数据中无向边的条数为 999*999 ,而您的内存只申请了 1002*2 。

sqybi  November 29th, 2008 at 11:29

@xpycc
嗯…程序貌似是有bug的…
而且判无解的地方貌似也有问题…

#include

using namespace std;

const int nn = 1002, mm = nn * 2, inf = 1000000000;
int n, tot, now;
int a[nn], b[nn], head[nn], color[nn];
int adj[mm], next[mm];
int stack[3][nn];
bool result;

void addEdge(int x, int y) //加边
{
    ++ tot;
    adj[tot] = y;
    next[tot] = head[x];
    head[x] = tot;
}

bool dfs(int i) //DFS染色,检查图是否是二分图的经典算法
{
    int temp = head[i];
    while (temp) //邻接表,检查每一条边
    {
        if (! color[adj[temp]]) //如果与当前结点的结点还未染色
        {
            color[adj[temp]] = 3 - color[i]; //进行染色
            dfs(adj[temp]); //DFS
        }
        if (color[adj[temp]] == color[i]) return false;
            //如果两个相邻结点染色相同,说明此图不是二分图,返回无解
        temp = next[temp];
    }
    return true;
}

int main()
{
    freopen("twostack.in", "r", stdin);
    freopen("twostack.out", "w", stdout);

    //输入
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    //预处理b数组
    b[n + 1] = inf;
    for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL

    //枚举数对(i,j)并加边
    tot = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
            if (b[j + 1] < a[i] && a[i] < a[j])
            {
                addEdge(i, j);
                addEdge(j, i);
            }

    //DFS染色
    memset(color, 0, sizeof(color));
    result = true;
    for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色1
        if (! color[i]) //当前位置尚未被染色
        {
            color[i] = 1;
            if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中
            {
                result = false; //记录无解
                break;
            }
        }

    if (! result) //无解
        printf("0");
    else //有解
    {
        //模拟求解
        now = 1;
        for (int i = 1; i <= n; ++ i)
        {
            //将当前数字压入对应的栈
            if (color[i] == 1)
                printf("a ");
            else
                printf("c ");
            stack[color[i]][0] ++;
            stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0

            //循环检查,如果可以的话就从栈顶弹出元素
            while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now)
            {
                if (stack[1][stack[1][0]] == now)
                {
                    printf("b ");
                    stack[1][0] --;
                }
                else if (stack[2][stack[2][0]] == now)
                {
                    printf("d ");
                    stack[2][0] --;
                }
                now ++;
            }
        }
    }
}

Written by sqybi

十一月 16th, 2008 at 5:14 下午

TopCoder SRM 413

with 11 comments

Div 2果然是水题.第一次SRM,变黄.
yuhch不好好出题啊…
此文测试插件用 有爱者可以忽略

第一题,纯水.贴TC的标程:

double minTime(int length, int maxAcceleration, int maxVelocity) {
  double t1 = sqrt(length / double(maxAcceleration));
  if(maxAcceleration * t1 > maxVelocity) {
    double t2 = maxVelocity / double(maxAcceleration);
    return (length - maxAcceleration * t2 * t2) / maxVelocity + 2 * t2;
  } else
    return 2 * t1;
}

第二题,我的做法是求解一大堆不等式:
假设给出了a0,a1,a2,…其中a1,a2…分别等于[a1],[a2]…,那么
a1-a0<=d<a1-a0+1
a2-a0<=2*d<a2-a0+1

TC给出的代码如下:

double minCommonDifference(int a0, vector  seq) {
  // fraction representing 0/1 (minimum permissible value)
  pair  res(0, 1);
  // find d
  for(int i = 0; i < seq.size(); ++i)
    if(res.first * (i + 1) < (seq[i] - a0) * res.second) {
      res.first = seq[i] - a0;
      res.second = i + 1;
    }
  // check whether a solution is possible
  for(int i = 0; i < seq.size(); ++i)
    if(seq[i] != a0 + (i + 1) * res.first / res.second)
      return -1;
  return res.first / double(res.second);
}

出现问题了…先测试到这里

刚才看了一下,Zoundry瞎改HTML.没办法,以后只能到blog后台来写了…装个增强的WYSIWYG插件去…

update:WLW竟然可以用!没想到啊.
继续写完.

第三题看似范围很大,实际用到的状态并不多,所以开一个map做记忆化搜索就解决问题.继续贴TC的代码:

map  mem;
long long calc(long long n, int p, int q) {
  if(n == 0)
    return 1;
  if(mem.count(n))
    return mem[n];
  mem[n] = calc(n / p, p, q) + calc(n / q, p, q);
  return mem[n];
}

这次题目就这样,很水了…
WLW似乎也把line参数给吞了…泪奔…

关闭了可视化编辑器,希望这次能行…
以后就得这么发代码了…

Written by sqybi

八月 15th, 2008 at 1:04 上午

Posted in About Computer, [OI, ACM, etc]

Tagged with , ,