2016年2月

BZOJ 2243 染色 树链剖分 线段树

树剖裸题。
用了一点线段树的小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;
}

由AlphaGo所想到的

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

之前几星期跟人谈起人工智能(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下赢了我,我还想赢回来

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu