Web Design

自从换上了Crayon Syntax Highlighter，发现原来<>&“符号被WP替换成了&lt;  &gt; &quot; &amp; 而Crayon Syntax Highlighter又不需要转换，只好转回来，于是写了下面这个脚本，成功地替换回来了。 
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

<?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("&lt;", "&gt;", "&quot;", "&amp;");
$replace = array("<"   , ">"   , """    , "&"    );
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();
?>
Olympiad in Informatics

在学校自娱自乐的作品。讲了2题：
  1. 区间第k大，在线，无修改
  2. 区间第k大，在线，有修改
介绍几种方法：
  1. 归并树（无修改）
  2. 划分树（无修改）
  3. 树套树（线段树套平衡树，有修改）
  4. 块状数组（有修改）
  5. 可持久化线段树（无修改）

有一些错误，比如说树套树的修改复杂度是：O(2*log^2n)

SlideShare（被墙自重）： [slideshare id=13746519&doc=k-120724213841-phpapp02]  

zip下载：

kth-number.zip

Olympiad in Informatics

很容易想到一个很朴素的状态表示，f[i, j, k, l]表示前i个房间住了j个男的k个女的以及l对夫妇。显然TLE＋MLE！

现在让我们考虑一下这道题的一些有意思的性质。
  • 大部分情况下，把夫妇拆掉会比合起来住更优。考虑一个2人间，如果合起来住，占一间，拆开来和别人住（假设人够多的话），也是占一间；如果是3人间或者更多人一个房间的话，那么合起来住之能够在1间n人间里面住2个人，拆开住却能够在2个n人间里面住2n个人。不管如何，拆开住的房间利用率总是不比合起来住。
  • 但是有一种特殊情况要考虑。比方说恰巧有3対夫妇，有3个2人间，如果按照上面安排的话，就住不下了。但是如果我们让一对夫妇住在一起，那么剩下的人就可以按照上面的做了。这种情况只出现在奇数对夫妇的时候。
根据上述性质，我们可以把l那一维缩减一下，变成0或者1，因为最多安排一对夫妇住在一起。转移方程： 
f[i, j, k, 0] = 
min { f[i-1, j, k, 0],
      price[i] + min{ f[i-1, j-p, k, 0], 
                      f[i-1, j, k-p, 0] } 
}

f[i, j, k, 1] = 
min { f[i-1, j, k, 1],
      price[i] + min{ f[i-1, j-1, k-1, 0],
                      f[i-1, j-p, k, 1],
                      f[i-1, j, k-p, 1] }
}
时间复杂度O(roommalefemale2)，勉强不会超时。但是MLE！解决办法可以：滚动数组，或者跟01背包一样，倒着做，直接覆盖，空间复杂度降到O(malefemale) Read on →
Olympiad in Informatics

朴素的动规很好考虑，f[i, x, y]表示第i个时间段结束的时候在(x, y)位置的最大滑动距离。那么就有朴素方程： 
f[i, x, y] = max{ f[i-1, x+s, y] + s }  (d[i] = 1)
             max{ f[i-1, x-s, y] + s }  (d[i] = 2) 
             max{ f[i-1, x, y+s] + s }  (d[i] = 3)
             max{ f[i-1, x, y-s] + s }  (d[i] = 4)

其中s为0到最远滑行距离，也就是min{第i时间段的时间, 障碍物到当前点的距离}

时间复杂度O(knm*最大时间)，其中最大时间<=max(n, m)

优化：

考虑d[i] = 1的情况：

f[i, x, y] = max{ f[i-1, x+s, y] + s }  (d[i] = 1)
           = max{ f[i-1, x+s, y] + (x+s) } - x
令g(k) = f[i-1, x+s, y] + (x+s)，那么：
f[i, x, y] = max{ g(k) } - x

于是我们可以对于同一个i和y的每一个x，维护一个单调递减的队列，每次取出队头-x就是f[i, x, y]的值。

Read on →
Olympiad in Informatics

一开始想到了在两条之间范围内的直线焦点数，也就是逆序对。但是题目给的是圆，不像两条直线那样可以直接确定在两条直线上的位置，也就无法逆序对……

但是，跟上面有点类似的，这题也可以将直线转化掉。

考虑每一条跟圆相交的直线，它必与圆交于两点，相切的话当作两个相同的点。那么，一条直线就变成了圆上的一段弧。至于是优弧还是劣弧并不重要，原因如下：考虑两条与圆相交的直线A和B，那么把它们两个端点按照极角排序后的顺序只有两种（可以移动）：ABAB或者ABBA。显然，只有当出现ABAB这种情况，也就是两条弧相交且不包含时，两条直线相交。那么回到优弧和劣弧的问题上，假设B是优弧还是劣弧确定了，且A的劣弧与B的弧相交，那么A的优弧必与B的弧相交。因此，优弧或者劣弧并不影响结果。

现在，我们就把问题转化成：在数轴上有一些长度不等的线段，问有多少对线段相交且不包含。

解决方法：

称某条直线与圆的2个交点中，按照极角排序后较小的为左括号，较大的为右括号。设数组C[]，初始化为0。 
for i ∈ 所有交点
  if i 为某条直线L的左括号
    C[i] = 1
  else
    j = i对应的该条直线的左括号
    ans += C[j+1]+...+C[i]
    C[j] = 0

实际上，每一次遇到右括号，就统计出当前直线L与在其左端点以后的直线的相交次数，当所有点做完之后，C[]数组全部为0，ans即为所求的交点数量。

可以用树状数组或者线段树维护区间和。 Read on →
Olympiad in Informatics

首先，并不是同一个时刻保留获益最大的工作，因为可能闲着没事做，比方说： 
1 100
3 100
3 100

这样可以获利300。

接着，在当前时刻，我们肯定先挑利益最大的做。

但是有个截止时间很讨厌。我们不妨把问题转化一下：我们不着急着马上求出最优方案，我们把所有可能在最优工作安排集合当中的工作放在一起，然后逐步修改这个集合，到最后就是最优的安排集合了。

做法如下：

按照截止时间从小到大排序，用小根堆维护所有可能要做的工作。那么堆中的元素个数+1就是当前时间。遍历每一个工作。
  1. 如果当前工作的截止时间不超过当前时间的话，我们可以先去做这个工作，扔进堆里面。
  2. 如果当前工作的截止时间超过了当前时间的话，我们看看堆中获利最小的工作，如果比当前工作优，不做也罢；如果比当前工作劣，那么扔掉，把当前工作加进来。

最后的答案就是把堆中工作相加。

Hint:这题要用long long

P.S.:C++的priority_queue很好用！ Read on →
Olympiad in Informatics

比较水的动规。

注意到这题主要的变量就是时间和能力值，而且时间能力值<=10000100，因此空间上能够承受二维的状态。

用f[i, j]表示在第i时刻，能力值为j的情况下，所能滑的最大距离。

每一天最多有三种事情可以做：喝果汁、滑雪，有时还可以上课。
  1. 如果喝果汁的话，那么可以直接从f[i, j]转移到f[i+1, j]
  2. 如果滑雪的话，显然我们要滑当前能力值能滑的最短的雪道，因为越短所需的时间越少，而且就算有零星的时间没法用到，也可以通过喝果汁解决。转移方法：f[i, j]+1转移到f[i+pre[j], j]，其中pre[j]为能力值j能滑的雪道中最短的长度。
  3. 如果当前这个时刻有一门课程的话，那么我们得考虑学习是否更优。注意：同一个时刻可能有多门课程！转移方法：f[i, j]转移到f[i+L[k], A[k]]，其中L[k]、A[k]分别为当天某个课程的学习时间和能力值

怎么计算pre[j]呢？

主程序的复杂度达到了O(t(s+100))，那么预处理采用O(n100)的朴素做法也未尝不可。当然也可以双关键字排序+线性扫描，快不了多少，而且写起来麻烦。

Read on →