Olympiad in Informatics

对于求解 A^x ≡ B (mod C) (0 <= x < C)这样的问题，可以使用 Baby Step Giant Step及其扩展算法解决。

对于BSGS，AC大神在他的博客中有一篇很详细的介绍，相信大部分人都是看他的文章学会BSGS的。这里我再做出一点整理。

Baby Step Giant Step

原始的BSGS只能解决C为素数的情况。

设m = ceil(sqrt(C)), x = i * m + j，那么A^x = (A^m)^i * A^j, (0 <= i < m, 0 <= j < m)。然后可以枚举i，O(sqrt(C))级别的枚举。

对于一个枚举出来的i，令D = (A^m)^i现在问题转化为求D * A^j ≡ B (mod C)。如果把A^j当作一个整体，那么套上exgcd就可以解出来了（而且因为C是质数，A是C的倍数的情况容易特判，除此之外必有(D, C) = 1，所以一定有解）

求出了A^j，现在的问题就是我怎么知道j是多少？AC大神给出了一个非常聪明的方法，先用O(sqrt(C))的时间，将A^j全部存进hash表里面。然后只要查表就在O(1)的时间内知道j是多少了。

Extended Baby Step Giant Step

扩展过的BSGS不要求C为素数。大致的做法和没扩展的一样，只是有些修改。

Read on →
Olympiad in Informatics

上星期只做了两天的动态树，而且光是理解动态树就花了我一天的时间。不过，理解完了以后就很好写了，写起来很愉悦，不比树链剖分难写。

参考资料

什么是动态树 (Dynamic Tree) 什么是 Link/cut tree

根据杨哲的论文，动态树是一类问题的总称，而解决这类问题的数据结构就是 Link/cut tree ，简称 LCT 。

根据个人理解，就是要：

  1. 给你一些森林，维护他们的联通性
  2. 在某棵树上的链（或链上节点）上做查询或修改。

很容易想到，如果没有第一点，那么第二点可以用树链剖分轻松解决。

Link/cut tree 的实现

Read on →
Olympiad in Informatics

题目很简洁，我就不复述了。

序列中的颜色段统计

首先要知道如果题目给的不是一棵树而是一个数列应该怎么办，这个还是比较简单的，用线段树维护下面三个东西：

  • 当前节点下有多少个颜色段 count
  • 当前节点最左边和最右边的颜色 clef crig

接下来就很好办了，对于一个线段树的非叶子节点，其颜色段就是两边孩子颜色段数之和，当然，如果中间那个两个点颜色是一样的话，还得扣掉： count = lchild.count + rchild.count - (lchild.crig == rchild.clef)

树上的颜色段统计

很明显，用 Link Cut Tree 可以轻松的做掉。但是这题没有修改，打一个LCT略蛋疼，可以试下树链剖分。

但是树链剖分有一个问题需要注意：因为我们是剖分成若干个连续的段再去查线段树，因此可能会导致之前那段和现在这段的连接处颜色相同，对于这种情况要特判扣掉。具体地说就是记下上次剖分的末端的颜色。

Read on →
Olympiad in Informatics

题目大意

给定拥有n个单元的内存，有以下操作：

  • Reset 清空内存，输出 Reset
  • New x 在尽量左端插入一个长度为x的块，输出 New at ... 或 Reject New
  • Free x 清空单元x所在块的整个块，输出 Free from ... to ... 或 Reject Free
  • Get x 找到第x个内存块的起始地址，输出 Get at ... 或 Reject Get

题解

据网上说是线段树，但是我是在平衡树练习题里面看到的，所以就打 Splay 练习一下。

平衡树表示

因为有询问第x个块的操作，所以我们把一整个块 [L, R] 作为平衡树的一个节点。注意到因为每个内存单元只会被一个块包含，所以完全可以当作只有 L 是平衡树的 key 。因为会需要查询第k大，所以顺便记下以每个平衡树节点为根的子树大小 size 。

New

如何找到最左边能容得下x的空间？每个节点可以维护两个值：当前节点和其前驱的距离差 dist 以及以当前平衡树节点为根的子树中最大的连续空间大小 maxspare 。

接下来就非常愉悦了，对于 New x 从根开始遍历平衡树。如果当前节点的 maxspare >= x 那么就考虑：向左走（ left->maxspare >= x ）或者取自己（ dist >= x ）或者向右走。

最终我们找到了一个节点 node ，满足这个节点和它前驱之间的空隙能够容得下新建的块。现在我们要进行插入，那就先把 node 旋到根，然后找到 node 的前驱，在前驱的右子树新建节点。新建节点的同时，需要注意更新父亲节点的 size maxspare dist 。 Read on →

Olympiad in Informatics

略颓废啊，用了两个半星期才搞完了计算几何的基础，而且还没做多少题，觉得晕呼呼的，还是在进入数据结构之前先总结一下吧，不然就忘掉了。

0 - Preface

题目列表大概就是 http://blog.renren.com/share/347994200/7898523786 ，做的很少。

1 - Vector

叉积

a × b = x1y2 - x2y1

叉积主要是用来判断向量的位置关系，如果 **a** × **b** > 0 说明 b 在 a 的顺时针方向。

1
2
3
4
5
6

inline double CrossProduct(const Point& A, const Point& B, const Point& C, const Point& D)
{
  const double x1 = B.x-A.x, y1 = B.y-A.y;
  const double x2 = D.x-C.x, y2 = D.y-C.y;
  return x1*y2 - x2*y1;
}

点积

a ・ b = x1x2 + y1y2

点积觉得除了数学书上写的一般也就没什么特殊用处了，无非就是判断共线，不然就是求角（求余弦）。

直线和线段相交

只要做半次跨立试验就可以了，线段P1P2 和 直线AB 相交，只需要考察 (**AP1** × **AB**) * (**AP2** × **AB**) < 0 即可，也就是 直线AB 跨过 线段P1P2

线段交点 ( Method 1 )

这个问题比较棘手，如果是解析几何的话非常愉悦，但是如果用向量方法来解决就有点不舒服了。我一开始是在 http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect 这里看到了一个方法，然后打了POJ1269，这个方法很好理解，运用叉积的分配率，但是缺点是Point类必须使用浮点，而且有向量相加。

Read on →
Linux Studies, Programming Studies

由于NOIP报名的问题，谢老师想把照片根据Excel表格中的信息重命名。原来的照片格式为：名字.jpg或者编号+名字.jpg。我觉得这个要去网上找软件也很麻烦，应该拿来用Python搞搞就好了，于是就自告奋勇地接下了这个任务，结果花了我半个小时不止……（没办法Python不熟）

首先，当然要处理Excel表格，我的做法是把编号和名字那列提出来，然后另存为csv文件。这样csv文件里面每一行都是编号,名字

然后要对csv文件进行处理，转成UTF-8编码，这样Python处理的时候就省事很多了

然后就是程序如下（Python2.7）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#!/usr/bin/python2.7
import os
import sys

names = {}
for line in open('name.csv', 'r'):
    info = line.split(',')
    names[info[1].replace('r', '').replace('n', '')] = info[0]

for f in os.listdir(os.getcwd()):
    if f.split('.')[1].upper() != 'JPG':
        continue
    name = f.split('.')[0]
    old = filter(lambda ch: ch not in '0123456789 ', name)
    if old in names:
        oldname = f
        newname = names[old] + old + '.jpg'
        #print '[%20s]  =>  [%20s]' % (oldname, newname)
        os.rename(oldname, newname)
        del names[old]
    else:
        print old, 'not in names'

for name in names:
    print name, names[name]

大概的流程就是先把名字和编号存到字典names里面，然后对于目录当中的每个.jpg文件，得到那个人的姓名（也就是old），再在字典中查询，生成新的文件名并重命名。还有一个就是能显示出哪些人在名表中但是没有照片，以及哪些人有照片但不在名表中。

Read on →
Olympiad in Informatics

昨天给一小部分机房党略微讲了下《竞赛中C++语言拾遗》。时间不对，卡到饭点上去了，效果不是很好，但是听的人多少有点收获我就很高兴了。

这个主要是根据我读C++ Primer, Effective C++, More Effective C++, The C++ Standard Library的体会以及平时竞赛的经验整理出来的。考虑到大部分人没有看过这些书，就写出来跟机房党们分享。

昨天讲之前发现有个问题不是很清楚：{cpp}const int foo() { }{/cpp} 和 {cpp}int foo() { }{/cpp} 有什么区别。然后在StackOverflow上发了一个Question，结果收了200 Reputation + 4 Badges，具体看：int foo() or const int foo()?

这份PDF拾遗内容如下：

  • Debug
  • C++ Syntax
  • Habit && Optimization
  • Trick
  • Trap
  • Reference

下载：supplement-to-cpp-in-oi

或者在我的Google Docs上：My Articles

SlideShare (被墙自重):

[slideshare id=14035366&doc=c-120821223229-phpapp01]

Olympiad in Informatics

上周很颓废的就完成了一个数论的同余专题……总结一下吧，也是备忘。

扩展欧几里德算法

Extended Euclidean algorithm

可以求解如Ax+By=C的二元一次不定方程的整数解。

考虑不定方程Ax+By=C，当(A,B)|C时一定有整数解。考虑如何解Ax+By=(A, B)

考虑欧几里德GCD算法GCD(A,B)的最后一步：
当GCD(A, 0)时，(x, y) = (1, 0)为满足Ax+0y=(A, 0)的一组解。考虑倒着推回去：

设
   A1x1 + B1y1 = (A1, B1)
   A2x2 + B2y2 = (A2, B2) = (A1, B1)
由
   (A, B) = (B, A % B)  (B, A - [A / B] * B)
可得
   A1x1 + B1y1 = A2x2 + B2y2 = B1x2 + (A1 - [A1 / B1] * B1)y2
移项得
   (x1-y2)A1 + (y1-x2+[A1/B1]y2)B1 = 0
因此
   x1 = y2, y1 = x2 - [A1 / B1] * y2
如此递推就可以得到Ax+By=(A, B)的解了

可以得到如下算法：

1
2
3
4
5
6
7
8
9
10
11
12

typedef long long Int64;
struct Triple
{
  Int64 x, y, z;
  Triple(const Int64 a, const Int64 b, const Int64 c): x(a), y(b), z(c) { }
};
Triple ExtendedGCD(const Int64 a, const Int64 b)
{
  if (b == 0) return Triple(1, 0, a);
  Triple last(ExtendedGCD(b, a%b));
  return Triple(last.y, last.x - a / b * last.y, last.z);
}

其中Triple是一个三元组，(x, y, z)分别保存(解x, 解y, GCD)。

在我们解出Ax+By=(A, B)的解后，要求Ax+By=(A, B)的解，只需把(x, y)乘上C/(A, B)即可！ Read on →

Web Design

由于Crayon Syntax Highlighter中定义了如[cpp]等短标签，Markdown语法中也有[]用于表示超链接，因此很容易出错。最简单的解决办法还是去掉[cpp]之类短标签的支持，改用【crayon lang="cpp"】的长标签。但是之前的文章还得一篇一篇改，考虑到之前用到的短标签不是很多，干脆直接暴力替换掉。

PHP代码如下（需要把【替换成[）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

<?php
header("Content-type:text/plain");
$conn = new mysqli("localhost", "root", "1234", "wordpress");
$conn->set_charset("utf8");
$result = $conn->query("SELECT post_content, ID FROM wp_posts");
$stmt = $conn->prepare("UPDATE wp_posts SET post_content = ? WHERE ID = ?");


$search = array();
$replace = array();
$reparr = array(
  '[py]'     => '【crayon lang="python"]',
  '[cpp]'    => '【crayon lang="cpp"]',
  '[pas]'    => '【crayon lang="pascal"]',
  '[php]'    => '【crayon lang="php"]',
  '[html]'   => '【crayon lang="html"]',
  '[/py]'    => '【/crayon]'
  '[/cpp]'   => '【/crayon]',
  '[/pas]'   => '【/crayon]',
  '[/php]'   => '【/crayon]',
  '[/html]'  => '【/crayon]',
);
$count = 0;
foreach ($reparr as $key => $value)
{
  $search[$count] = $key;
  $replace[$count] = $value;
  ++$count;
}
while ($row = $result->fetch_array())
{
  $id = $row['ID'];
  $post_content = str_replace($search, $replace, $row['post_content']);
  $stmt->bind_param('si', $post_content, $id);
  if (!$stmt->execute())
  {
    die("n[ERROR!]".$id."n");
  }
  else
  {
    echo "[Success]".$id."n";
  }
}


$result->free();
$conn->close();
?>

下面做几个测试：

Read on →
Olympiad in Informatics

终于半看题解，半讨论地做完了网络流24题（除了Byvoid没做的那题还有最后两题不想做- -||），还是有点感触的，小小总结一下。

经典建模

最大权闭合图问题

  • 从S到正权点连和点权一样的边
  • 从负权点到T连-点权的边
  • 其余按照原图连无穷的边

跑一遍最小割，正权点之和-最小割容量就是答案。引用Byvoid的话：

定义一个割划分出的S集合为一个解，那么割集的容量之和就是 (未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。 A集合中所有顶点的权值之和记为Total，那么Total - Cut就是 (被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。 要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。

输出方案的方法是：从S沿着非零流边跑一遍DFS，和S相连的点与和T相连的点就是两边的方案。

例题：

  1. prog82
Read on →