ftiasch

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 100000;

int n, m, w[N], a[N], b[N], order[N];

ftiasch

require 'rexml/document'
require 'open-uri'

task :default => :run

task :run do
    sh '(java -classpath "lib/*" com.topcoder.client.contestApplet.runner.generic www.topcoder.com 5001 >/dev/null 2>&1 &)'
end

task :update do

ftiasch

import java.io.*;
import java.math.*;
import java.util.*;

public class Brute {
    public void run() {
        try {
            int testCount = reader.nextInt();
            for (int t = 1; t <= testCount; ++ t) {
                int n = reader.nextInt();

ftiasch

CCFLAGS=-w
main: main.c
	${CC} ${CCFLAGS} main.c -o main

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

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'

ftiasch

window.MathJax = {
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"] ],
        displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
        showProcessingMessages: false,
        processEscapes: true,
	processSectionDelay: 0
    }
};