2017年8月

一首我读了一遍后就摆脱不开其引力的诗。

十月之水

九五 :鸿渐于陵,妇三岁不孕终莫之胜。吉。——《易经·渐》

1

你不可能知道那有什么意义

对面的圆圈们只死于白天

你已穿上书页般的衣冠

步行在恭敬的瓶形尸首间

花不尽的铜币和月亮,嘴唇也

渐渐流走,冷的翠袖中止在途中

机密的微风从侧面撤退

一缕缕,唤醒霜中的眉睫

就这样珍珠们成群结队

沿十月之水,你和她行走于一根琴弦

你从那天起就开始揣测这个意义

十月之水边,初秋第一次听到落叶

2

我们所猎之物恰恰只是自己

鸟是空气的邻居,来自江南

一声枪响可能使我们中断蒙汛

可能断送春潮,河商的妻子

她的眺望可能也包含你

你的女儿们可能就是她抽泣的腰带

山丘也被包含在里面,白兔往往迷途

十年前你追逐它们,十年后你被追逐

因为月亮就是高高悬向南方的镜子

花朵随着所猎之物不分东西地逃逸

你翻掌丢失一个国家,落花也拂不去

一个安静的吻可能撒网捕捉一湖金鱼

其中也包括你,被抚爱的肉体不能逃逸

3

爻辞由干涸之前的水波表情显现

你也显现在窗口边,水鸟飞上了山

而我的后代仍未显现在你里面

水鸟走上了山洞,被我家长河止

我如此被封锁至再次的星占之后

大房子由稀疏的茅草遮顶

白天可以望到细小手指般的星星

黄狗往缝隙里张望 我早已不在里面

我如此旅程不敢落宿别人的旅店

板桥霜迹,我礼貌如一块玉坠

如此我承担从前某个人的叹息和微笑

如此我又倒映我的后代在你里面

4

你不知道那究竟有什么意义

开始了就不能重来,圆圈们一再扩散

有风景若鱼儿游弋,你可能是另一个你

当蝴蝶们逐一金属般爆炸、焚烧、死去

而所见之处仅仅遗留你的痕迹

此刻你发现北斗星早已显现

植物齐声歌唱,白昼缓缓完结

你在停步时再次闻到自己的香味

而她的热泪汹涌,动情地告诉我们

这就是她钟情的第十个月

落日镕金,十月之水逐渐隐进你的肢体

此刻,在对岸,一定有人梦见了你

Definition: each edge of the graph at most belongs to a single circle.

We can process tree easily, so consider how to convert a cactus into a tree.

[Circle-Square Tree]

Basic definition:
内固集 外固集 核
BZOJ 2275

Fibonacci game.

Theorem The game with initial state of Fibonacci number will get failed.
Proof. By induction.
(i) Obv $ i = 2 $ get failed. Checked.
(ii) Assume $ i \le k $ valid. Let $ i = k + 1 $. Denote $ x $ as the first amount, $ y $ as the second.
We have $ x \ge \frac{1}{3} f_{k-1}, y \le \frac{2}{3} f_{k-1} \le \frac{1}{2} f_k $. The second one get the last stone, which means the first failed. QED.

Theorem(Zeckendorf) $\forall n \in \mathbb{N}\_+ $, n can be represented by a discontiniousness sequence of Finobaccis.
Proof: By induction.
(i) $ n = 2, 3 $, obv.
(ii) Assume $n = 1..m-1$ valid. Consider the case of $ n = m $.
(a) $ m \in \mathcal{F} $, valid.
(b) $ m \not\in \mathcal{F} $, let $ F_{n_1} < m < F_{n_1+1} $, we have $ m' = m - F_{n_1} < F_{n_1-1} $, by assumption, follow the previous we can define such $ n_i $ s. Since $ n_2 < n_1-1 $, we get the conclusion. QED

By the 2 thms above, we know the previous player who take $ \min F_n $ at the very first time will win the game.

Code (8632 kb 4 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
template<class T> void read(T& x)
{
    T p = 1, n = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
    x = p * n;
}
const int maxn = 1e6;
long long f[maxn];
int main()
{
    long long n; read(n);
    f[0] = 1, f[1] = 2;
    int cur;
    for(cur = 2; f[cur - 1] <= n; cur++) f[cur] = f[cur - 2] + f[cur - 1];
    cur--;
    while(n)
    {
        while(f[cur] > n) cur--;
        if(f[cur] == n)
        {
            printf("%lld\n", f[cur]);
            return 0;
        }
        n -= f[cur];
    }
    return 0;
}

HDU 2516

Code(1540K,0)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
template<class T> void read(T& x)
{
    T p = 1, n = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
    x = p * n;
}
const long long maxn = 1e6, maxm = 1LL << 31;
long long f[maxn];
set<long long> S;
int main()
{
    long long n;
    f[0] = 0, f[1] = 1; S.insert(0); S.insert(1);
    for(int cur = 2; f[cur - 1] <= maxm; cur++) 
        f[cur] = f[cur - 2] + f[cur - 1], S.insert(f[cur]);

    while(read(n), n)
        puts(S.count(n) ? "Second win" : "First win");
    return 0;
}

Wythoff Game

Theorem(Beatty) Let $ \frac{1}{\alpha} + \frac{1}{\beta} = 1, \alpha, \beta \text{~irrational}, a_n = \lfloor \alpha n \rfloor, b_n = \lfloor \beta n \rfloor $, then we have
(1) $ {a_n}, {b_n} $ is increasing;
(2) $ {a_n} + {b_n} = \mathbb{N_+} $.
Proof. (1) It's easy to find out $ \alpha,\beta > 1 $, which implies the increasing.
(2) Assume that $ a_p \le k, a_{p+1} > k, k \in \mathbb{N}_+ $. We have

$$ \begin{align} \alpha p < k+1 \\\\ \alpha(p+1)>k+1 \end{align} \Rightarrow p = \lfloor \frac{k+1}{\alpha} \rfloor \\\\ \Rightarrow S = \frac{k+1}{\alpha} + \frac{k+1}{\beta} \\\\ \Rightarrow k-1<S<k+1 \\\\ \Rightarrow S = k $$

which means the previous k numbers get the first k numbers in natural number set.
Q.E.D.

By definition of the game, we can easily figure out that each odd situation (shown by a pair (a, b)) satisfies the following proposition: (Assume the first element of the pair is less than the second)
(i) We have $ (a_i, a_i + k) $ for the $ k $-th odd;
(ii) a_i is the minimum excluded integer from the previous pairs;
(iii) The first non-trial odd is $ (1,2) $.

By Beatty's Theorem, we let $ \beta - \alpha = 1 $, then we know the sequence $ a, b $ is what we find to describe the odds of the game. In general, each odd has a form as $ (\lfloor \frac{1+\sqrt{5}}{2} n \rfloor, \lfloor \frac{1+\sqrt{5}}{2} n + n \rfloor) $, where $ n $ is an integer meaning the order.