ftiasch

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)

ftiasch

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <errno.h>

#include <pwd.h>
#include <unistd.h>
#include <sys/resource.h>

ftiasch

// Contributor: gxx, mxh, lty, lmy, yzh
digraph {
// 2023
唐靖淇->李南锡
唐靖淇->谢尚航
唐靖淇->冯启豫 // replacement
杨宗翰->张建军
杨宗翰->张明驰
刘泳霖->戴之恒
刘泳霖->李青峰

ftiasch

/*
 * 假设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的祖先，

ftiasch

{{{2013-03-16-sgu-321.markdown}}}

SGU 321 The Spy Network

Problem

$N$个点的有根树，边有黑白两色，将最少的黑边改成白边，使得从根到任意点的路径上，白边的数量不少于黑边。

($N \leq 200000$)

Solution

ftiasch

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

ftiasch

crypto  = require 'crypto'
request = require 'request'

cookieJar = request.jar()
request   = request.defaults {jar: cookieJar}

#require('request').debug = true

class Client
  constructor: (@id, @password) ->

ftiasch

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 }

ftiasch

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$。

ftiasch

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'