{{{2013-03-16-sgu-321.markdown}}}
(
data State = Null | |
| Node String State State | |
valid :: State -> Bool | |
valid state = case state of | |
Null -> undefined | |
Node string _ _ -> null string | |
match :: String -> String -> [Int] | |
match pattern = map fst . filter (valid . snd) . scanl step (0, root) |
#include <cmath> | |
#include <cstdio> | |
#include <cstdlib> | |
#include <cstring> | |
#include <cassert> | |
#include <errno.h> | |
#include <pwd.h> | |
#include <unistd.h> | |
#include <sys/resource.h> |
// Contributor: gxx, mxh, lty, lmy, yzh | |
digraph { | |
// 2023 | |
唐靖淇->李南锡 | |
唐靖淇->谢尚航 | |
唐靖淇->冯启豫 // replacement | |
杨宗翰->张建军 | |
杨宗翰->张明驰 | |
刘泳霖->戴之恒 | |
刘泳霖->李青峰 |
/* | |
* 假设l = aa..a, r = bb..b,则题目等价于计算树上距离恰好是m的点对数量。不难发现本题需要树分治, | |
* | |
* 分治点u时,假设v到u对应的字符串是S = s1 s2 ... sk,需要比较S和l, r长度为k的前后缀的字典序大小。 | |
* | |
* (作减法之后,只讨论上界r) | |
* 1. 对reverse(r)建立后缀自动机。 | |
* 从u开始dfs树,在自动机上对应转移。 | |
* 因为所在节点的right集合不一定包含前缀0, | |
* 所以需要预处理节点(沿着parent)最近的包含前缀0的祖先, |
POJ3222.txt | |
misaka.99999: 11:20:53 | |
题目等价于给边定向,使得每个点的度都是偶数。既然如此,如果一个连通分量有奇数条边,那么总点度 = 边数 = 奇数,就无解。否则,求出连通分量的一颗生成树,对于非树边随意定向。现在相当于要给树边定向,使得点度是奇数(或偶数,取决于非树边随意定向的结果)。在生成树上dfs构造,对于每个点u,考虑它父亲p到它的边(p, u),根据下面定向的结果,我总能定向(p, u)使得点u满足。只剩下根,因为总点度是个偶数,所以根是天然满足的。证毕。 | |
SPOJ_PGCD.txt | |
: 08:51:10 | |
问一下spoj4491的miu函数到底怎么构造? | |
: 08:56:25 | |
4491是什么? | |
: 08:56:37 |
crypto = require 'crypto' | |
request = require 'request' | |
cookieJar = request.jar() | |
request = request.defaults {jar: cookieJar} | |
#require('request').debug = true | |
class Client | |
constructor: (@id, @password) -> |
import Control.Monad | |
import Control.Monad.State.Lazy | |
import Data.ByteString.Lazy.Char8 (ByteString) | |
import qualified Data.ByteString.Lazy.Char8 as BS | |
import Data.Char | |
import Data.List | |
import Data.Maybe | |
data Operation = Update { index :: Int, multiple :: Int } |
Date: 2015-01-19 14:47
分享一个题目和解法: 用正整数对树的节点编号,要求相邻节点的编号不同,同时编号的总和最小。
假设$n$是树的节点数,编号一个显然的上界是$n$,所以可以得到一个$O(n^2)$的dp,令$f(u, x)$表示$u$的父亲编号是$x$,$u$子树编号总和的最小值。 则$$f(u, x) = \min_{y \neq x} \sum_{v} f(v, y)$$
接下来我们证明$x$的上界是$O(\sqrt{n})$,就可以得到一个$O(n^{2/3})$的算法。 因为树是二分图,总可以用两种颜色染色,由对称性,$2$的数量不会超过一半,所以这种方案的总和不超过$\frac{3}{2} n$。
import Data.Vector (Vector) | |
import qualified Data.Vector as V | |
newtype Zp = Z Int deriving (Show, Eq) | |
modulo :: Int | |
modulo = 10 ^ 9 | |
z :: Int -> Zp | |
z a | a >= 0 = Z a' |