| class MyString < String | |
| attr_reader :flag | |
| def initialize(s, f) | |
| super s | |
| @flag = f | |
| end | |
| end | |
| s1 = MyString.new ' misa', :misa |
| #!/bin/bash | |
| tmpfile=$(mktemp) | |
| for f in `git diff --cached --name-only --diff-filter=ACMR | egrep '\.(cc|cu|cuh|h)$'`; do | |
| git show :"$f" > $tmpfile | |
| if ! diff -q "$tmpfile" <(clang-format "$tmpfile") 2>&1 >/dev/null; then | |
| echo "$f" is not clang-formatted. | |
| rm -rf $tmpfile | |
| exit 1 | |
| fi | |
| done |
| #include <bits/stdc++.h> | |
| const int N = 40; | |
| const int MOD = 1e9 + 7; | |
| using Mask = uint64_t; | |
| void update(int &x, int a) { | |
| x += a; |
| prebuilt_cxx_library( | |
| name = 'test', | |
| exported_headers = ['test.h'], | |
| shared_lib = 'libtest.so', | |
| preferred_linkage = 'shared', | |
| ) | |
| cxx_binary( | |
| name = 'main', | |
| srcs = ['main.cpp'], |
| #include<stdio.h> | |
| #include<stdlib.h> | |
| #include<cstring> | |
| #include<iostream> | |
| #include<ctype.h> | |
| #include<algorithm> | |
| #include<vector> | |
| #include<string> | |
| #include<set> | |
| #include<map> |
| window.MathJax = { | |
| tex2jax: { | |
| inlineMath: [ ['$','$'], ["\\(","\\)"] ], | |
| displayMath: [ ['$$','$$'], ["\\[","\\]"] ], | |
| showProcessingMessages: false, | |
| processEscapes: true, | |
| processSectionDelay: 0 | |
| } | |
| }; |
| import SimpleHTTPServer | |
| import SocketServer | |
| PORT = 8000 | |
| class Handler(SimpleHTTPServer.SimpleHTTPRequestHandler): | |
| pass | |
| Handler.extensions_map['.shtml'] = 'text/html' |
| PublicTransitHard http://community.topcoder.com/stat?c=problem_statement&pm=13797 | |
| SimilarNames http://community.topcoder.com/stat?c=problem_statement&pm=12868 | |
| n个字符串s_1, s_2, …, s_n，m个条件(a_i, b_i)，统计满足s_{p(a_i)}是s_{p(b_i)}前缀的排列p_1, p_2, …, p_n数量 | |
| n <= 50, |s_i| <= 50, m <= 8 | |
| BichromeSky http://community.topcoder.com/stat?c=problem_statement&pm=13711 | |
| n个红点，m个蓝点，没有三点共线，第i个红点以p_i的概率出现，求红点的凸包包含所有蓝点的概率 | |
| n, m <= 100 |
| 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' |
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$。