2016年2月

树剖裸题。
用了一点线段树的小trick,就是处理信息区间加法是直接用operator+来连结,这样在函数里操作起来简单点(个人觉得),只不过写好这个operator+不简单……(因此WA若干次的DEL桑真是……)
总之傻逼数据结构题都能写5k赛场上还是只能狗带……

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T>
inline void read(T& x, T& y){read(x), read(y);}
template<class T>
inline void read(T& x, T& y, T& z){read(x), read(y), read(z);}

const int maxn = 1e6;
int n;

struct Edge
{
    int to;
    Edge* next;
} pool[maxn * 4], *header[maxn];

int pcnt = 0;
void add_edge(int u, int v)
{
    Edge *newedge = &pool[pcnt++];
    newedge -> to = v;
    newedge -> next = header[u];
    header[u] = newedge;
}

int size[maxn] = {0}, hson[maxn] = {0}, fa[maxn] = {0}, depth[maxn] = {0};
int dfs(int i = 1)
{
    size[i] = 1, hson[i] = 0;
    for(Edge *e = header[i]; e; e = e -> next)
    {
        if(e -> to != fa[i])
        {
            fa[e -> to] = i;
            depth[e -> to] = depth[i] + 1;
            dfs(e -> to);
            size[i] += size[e -> to];
            if(size[e -> to] > size[hson[i]])
                hson[i] = e -> to;
        }
    }
}

int number[maxn] = {0}, ncnt = 1, top[maxn] = {0};
int build_tree(int i = 1, int tp = 1)
{
    number[i] = ncnt++, top[i] = tp;
    if(hson[i])
        build_tree(hson[i], tp);
    for(Edge *e = header[i]; e; e = e -> next)
        if(e -> to != hson[i] && e -> to != fa[i])
            build_tree(e -> to, e -> to);
}

namespace SegTree
{
    struct Info
    {
        int color;
        int lc, rc;
        int blocks;
        Info(int x = -1, int n = 0) : color(x), lc(x), rc(x), blocks(n){}
        Info(int x, int l, int r, int b) : color(x), lc(l), rc(r), blocks(b){}
        Info operator+(Info& a)
        {
            if(lc == -1)
                return Info(-1, a.lc, a.rc, a.blocks);
            if(a.rc == -1)
                return Info(-1, lc, rc, blocks);
            if(color != -1)
                lc = rc = color, blocks = 1;
            if(a.color != -1)
                a.lc = a.rc = a.color, a.blocks = 1;
            int t = rc == a.lc ? 1 : 0;
            return Info(-1, lc, a.rc, blocks + a.blocks - t);
        }
    } I[maxn * 4];

    void maintain(int o, int L, int R)
    {
        if(L < R)
        {
            int c = I[o].color;
            I[o] = I[o << 1] + I[(o << 1) + 1];
            I[o].color = c;
        }
    }

    int x, y, c;
    void change(int o = 1, int L = 1, int R = n)
    {
        if(x <= L && R <= y)
            I[o] = Info(c, 1);
        else
        {
            if(I[o].color != -1)
                I[o << 1] = I[(o << 1) + 1] = Info(I[o].color, 1), I[o].color = -1;
            int M = (L + R) / 2;
            if(x <= M) change(o << 1, L, M); else maintain(o << 1, L, M);
            if(M < y) change((o << 1) + 1, M + 1, R); else maintain((o << 1) + 1, M + 1, R);
            maintain(o, L, R);
        }
    }

    Info ans;
    void query(int o = 1, int L = 1, int R = n)
    {
        if(I[o].color != -1)
            ans = ans + I[o];
        else if(x <= L && R <= y)
            ans = ans + I[o];
        else
        {
            int M = (L + R) / 2;
            if(x <= M) query(o << 1, L, M);
            if(M < y) query((o << 1) + 1, M + 1, R);
        }
    }
}

int change(int a, int b, int co)
{
    using namespace SegTree;
    x = a, y = b, c = co;
    change();
}

SegTree::Info que(int u, int v)
{
    using namespace SegTree;
    x = u, y = v; ans = Info();
    query();
    return ans;
}

int modify(int u, int v, int c)
{
    int tu = top[u], tv = top[v];
    while(tu != tv)
    {
        if(depth[tu] < depth[tv])
            swap(u, v), swap(tu, tv);
        change(number[top[u]], number[u], c);
        u = fa[tu], tu = top[u];
    }
    if(u == v)
        change(number[u], number[u], c);
    else
    {
        if(depth[u] < depth[v])
            swap(u, v);
        change(number[v], number[u], c);
    }
}

int query(int u, int v)
{
    int tu = top[u], tv = top[v];
    int ans = 0;
    int uc = -1, vc = -1;
    SegTree::Info i;
    while(tu != tv)
    {
        if(depth[tu] < depth[tv])
            swap(u, v), swap(tu, tv), swap(uc, vc);
        i = que(number[top[u]], number[u]);
        ans += i.blocks;
        if(uc == i.rc)
            ans--;
        uc = i.lc;
        u = fa[tu], tu = top[u];
    }
    if(u == v)
    {
        i = que(number[u], number[u]);
        ans += i.blocks;
        if(i.lc == uc)
            ans--;
        if(i.rc == vc)
            ans--;
    }
    else
    {
        if(depth[u] < depth[v])
            swap(u, v), swap(uc, vc);
        i = que(number[v], number[u]);
        ans += i.blocks;
        if(vc == i.lc)
            ans--;
        if(uc == i.rc)
            ans--;
    }
    return ans;
}

int color[maxn] = {0};
int main()
{
    int m;
    read(n, m);
    for(int i = 1; i <= n; i++)
        read(color[i]);
    for(int i = 1, x, y; i < n; i++)
    {
        read(x, y);
        add_edge(x, y);
        add_edge(y, x);
    }
    dfs();
    build_tree();
    for(int i = 1; i <= n; i++)
    {
        change(number[i], number[i], color[i]);
    }
    while(m--)
    {
        char com[2];
        scanf("%s", &com);
        int a, b, c;
        if(com[0] == 'C')
        {
            read(a, b, c);
            modify(a, b, c);
        }
        else
        {
            read(a, b);
            printf("%d\n", query(a, b));
        }
    }
    return 0;
}

被某公众号约稿,在高速公路上顶着头晕目眩写下这篇文章。
明明只是兴趣所在,并没有深究过,然后感觉好像写到最后变民科了?

好虚好虚,求不被婊……

之前几星期跟人谈起人工智能(Artificial Intelligence,下略AI),就说AI还没办法在围棋上战胜人类。恐怕至少得五年后才能有突破。
这几天就被新闻打脸了。来自Google的Deep Mind实验室的AlphaGo(阿法狗)战胜了欧洲围棋冠军。
关于机器学习的内容,毕竟了解不多,若有错漏敬请指教。
事实上令我惊异的并非是深度学习(Deep Leaning)的使用,而是没想到其竟会发展得如此迅速。深度学习的话学术界早已提出多年,理论也相对成熟,只是实现和实践带来的突破好像还没跟这次一样应发如此关注过。

谈谈两代AI,深蓝与阿法狗

国际象棋世界冠军在上个世纪败在了深蓝面前,这是旧闻。但为什么围棋方面机器直到现在才在开始“胜于”人类?仅仅因为规则不同?
事实上是,深蓝那时的算法仅仅是枚举情况,搜索和剪枝。就是分析出所能走的几个情况,然后对每个局面进行估分,取一个最优解。估分大概就是丢掉一个兵扣分吃掉一个兵加分之类的。所以这只是对搜索和计算能力的要求,对于局面的选择依赖于给定的参数,而这些参数只能靠工程师的经验和直觉了。
围棋就不一样了,没办法搜索,甚至没办法估分。十九乘十九个格点均可成为下棋的位置。所以仅靠枚举搜索是没办法下赢围棋的。
所以阿法狗自然就不是靠枚举的。使用深度学习模型,工程师只需要告诉它规则,然后给他数以万计的棋局让它自己去“学习”下法,自己去“领悟”。
据言,阿法狗的研究人员并不都是围棋专家。
今年阿法狗要挑战世界冠军。不知经过这几月的棋局训练和自己跟自己博弈,是否能再胜一次?

通用领域的深度学习

阿法狗可以作为一个极好的例子:只需要给一套规则,再辅以足够多的样本通过深度学习模型自己去“学习”。
那这很明显不止可以用来下棋,对吧。
几乎是所有领域,经过如此“训练”的AI大都取代人是不成问题的吧。
事实也是如此。Deep Mind这个小组本身就是做通用领域的。
这些模型,可以用来下各种棋,甚至……拿来做应试教育的题?
想象一下将来,所有领域都无需专业人员了。

现在的机器学习

不知大家有没有玩过微软的人脸识别。
现在的人脸识别技术,可是可以精确将一个人的特征识别出来,做到无错漏。
而这,是人类经过几千万年演化才得到的技能。
国内类似技术的还有Face++。
还有微软小冰(没错我是软粉)的(不是完美的)语言识别,图片识别,小娜的(更不完美的)语音识别。
更还有其它方面机器在努力学习人类,赶超人类。

未来

AI可以为我们做了我们能想到的任何事。
当你感觉哪里不方便,或是厌烦了,AI可以自动帮你做好规划并且马上修改/制作。无需动脑子。
甚至,基础科学也可以由AI研究呢?

更远的未来

AI开始思考,地球文明要往外发展,人类已经是累赘了。

有这样一句话“人工智能是一辆火车,你远远听到了它的汽笛并心怀期待。当他终于近了,你却发现它没有停下,最终把你远远甩在身后。”

后记

跟King Chess同学辩论了一下AI对人类究竟是有益还是有害的。
我是更倾向于人类药丸论。
AI是双刃剑。只要人类能控制他,就对人类有益;但是人类不能控制他,就只能说明人类活该被淘汰。

参考

Nature 论文
知乎讨论
果壳公众号-AI战胜人类职业棋手,围棋界怎么看?围棋天才柯洁:如果AI下赢了我,我还想赢回来