德意志联邦共和国一名Computer考古学家开垦出计算机写作情诗程序,但他不用这黄金时代程序的原创者。
早在60数年前,情诗生成程序已经问世。 Computer作诗
1948年6月,世界上第朝气蓬勃台能完全实行存款和储蓄程序的电子计算机原型机在United Kingdom圣Louis高校出生。大家给它取名“婴孩”。
那时候商量人口为它编写了几十种新型程序,但是至今好些个早已不见。
大不列颠及苏格兰联合王国商量人口Christopher·Strachey也涉足了“婴儿”的研制。他为考试那台原型机随机选用音信的技能,编写出自动创作情诗程序。
“婴孩”本人蕴藏了汪洋诗文数据。每一次运转作诗程序,大家只需输入几百个意思浪漫的动词和名词,它就能够自动生成生机勃勃首短情诗。
Strachey把“婴孩”的“大作”打字与印刷出来贴在布告栏上。固然那几个情诗不必然能感动女子的芳心,但作诗程序开创了计算机文本生成程序的先例。
后来随着Computer本领飞快发展,“婴孩”和作诗程序被大家稳步忘却。 历史重演
德意志Computer考古学家大卫·瓦尔德近来在United Kingdom哈佛高校博德利教室研商Strachey诗歌时意识那风流倜傥主次。
他花3个月时间编写出相像的在线“情诗生成器”程序供网民自由使用。
客商在线运营那黄金时代前后相继,输入一些词语,每一回点击“重载”键,网页上就能够冒出后生可畏首新的情诗。
大不列颠及英格兰联合王国《圣萨尔瓦多新闻早报》10日引入瓦尔德的话广播发表:“那牵涉到意气风发部分有国际影响力的大不列颠及北爱尔兰联合王国Computer文化遗产。编写程序的那3个月十二分折磨人,因为依据明天行业内部,那风流倜傥程序极其原始。”
瓦尔德将于3月下旬在英国London就作诗程序发布阐述。他制造的“婴儿”复制机不久后将要德意志展览,届时他会用那台机械演示“情书程序”。
Computer“艺术”
Strachey1916年诞生于英格雷汉姆普斯特德,阿爸爱好音乐和雕塑,阿妈是一名地农学家和电气技术员。那让Strachey从小受到艺术和理工科知识的重中央新闻纪录电影制片厂响。
他1935年步向巴黎高等师范高校皇上大学念书,毕业后做过物工学家和校长,并从20世纪40年份开端对Computer才干产生兴趣。
1951年1月,Strachey第二遍接触有囤积程序的Computer并初叶编写程序。1952年,他停止校长工作,成为United Kingdom国家探讨发展集团的全职Computer本事钻探员。
同年九夏,Strachey从小妹这里拿走灵感,利用同事、盛名Computer物军事学家艾伦·图灵的人身自由数字生成器,开垦出作诗程序,那是人类第一回利用计算机生成法学文章。
Strachey还编写制定过最先的微计算机音乐软件。他于1975年在南洋理工科高校葬身鱼腹。

STREAM既然是鹏程的取向,那奇宝为啥偏偏强调是小孩子编制程序(Coding)并不是其余学科呢?能够从这几上面看的

题目:

红客们通过对已某个病毒反编写翻译,将众多见仁见智的病毒重新整合,并再次编写翻译出了风尚的三结合病毒。这种病毒的增殖和多变技术极强。为了挡住这种病毒传播,某安全单位策划了一遍实践,来探究这种病毒。
实行在一个查封的局域网内举办。局域网内有n台Computer,编号为1~n。一些Computer之间通过网线直接相接,产生树形的结构。局域网中有后生可畏台湾特务殊的微电脑,称之为大旨Computer。依照部分方始的商讨,研究员们制订了二个共计m步的实践。实验始于以前,主题Computer的号码为1,每台微微处理器中都有病毒的一个变种,何况每台Computer中的变种都分裂。实验中的每一步会是底下中的豆蔻梢头种操作:

  1. RELEASE x
    在数码为x的Computer中植入病毒的三个新变种。那些变种在植入以前不设有于局域网中。
  2. RECENTER x
    将挑建邺计算机改为编号为x的微型机。但是这些操作会形成原来基本Computer中的病毒爆发新变种,并感染过来。换言之,假如操作前的中坚计算机编号为y,也正是在操作后附加了一遍RELEASE
    y的操作。
    据他们说商讨的定论,在植入多个新变种时,病毒会在局域网中搜索主题Computer的地点,并沿着互连网中最短的门径感染过去。
    而首先轮实验揭破了三个惊人的面目:病毒的两样变种是排挤的。新变种在耳熟能详黄金年代台曾经被旧变种感染的微型机时,会把旧变种完全绝迹之后再感染。但研商员开采了达成进度中的漏洞。假若新变种在感染进程中绝非销毁过这类旧变种,供给先花销1单位时间剖判旧变种,工夫销毁。假诺以前销毁过那类旧变种,就足以以为销毁不耗时。病毒在两台微微处理机之间的扩散亦可认为不花费时间。
    斟酌员对一切感染进程的耗费时间特别感兴趣,因为那是排除病毒的优良机遇。于是在m步实验之中,研究员一时还有恐怕会做出如下的问询:
    3,REQUEST x
    询问意气风发旦在号码为x的计算机的最首要会集中的Computer中植入三个新变种,平均感染时间为多少长度。编号为y的微计算机在编号为x的处理器的十分重要集结中,当且仅当从y沿互联网中的最短路线感染到骨干计算机必需经过x。由于有RECENTEEscort操作的留存,那些集归并不一定是始终不改变的。
    到现在,安全机构认为曾经没有必要实际的尝试了,于是他们拜托你编写一个主次,模拟实验的结果,并答复全体的领悟。


题解:

题目真**长

笔者们用LCT来缓慢解决那道题。
率先大家要求注重到几本性质.每叁次步向的病毒一定是新变种。
约等于说其实各样点究竟是这种颜色并不根本,因为每叁次都投入新颜色
之所以随便怎么样颜色都会被直接xx掉。

所以大家的能够摄取那样的一条结论

  • 一个点到根的分化的水彩数即为这么些点到根时透过的虚边的个数
    也正是说我们间接把第八个操作当作access操作
    咱俩发掘这么前四个操作都消释了
    而是我们询问二个点的时候并不可能暴力跳fa找经过的虚边数.
    据此大家须要外表维护一下.
    鉴于大家要询问的是一个子树内的权和,这大家理应自然地想到用dfs序
    由此大家在举办LCT的进度中在外界动态维护一个dfs序.

Wait !!这是有换跟操作的呦,dfs序不是原则性的.
咱俩可以依据当下的根节点rt与查询节点u的关联来分类研究.
具体是:

if rt == u: query all
if lca(rt,u) == rt : query tree of u
if lca(u,rt) == u :
    find point p has min depth and (lca(p,rt) = p,lca(p,u) = u)

上述lca是指在起始树中.
我们开采lca 只是用来祖孙判别的,我们得以用dfs序来代替这些大致的难点.

还不亮堂的话,,能够看本人那从晚自习起头中一年级贯调到第二天早自习的代码.

假设有人想问小编是怎么产生拍了后生可畏晚上没搜索错交到bzoj上4msRE却只因为本人写多少生成器的时候只生成了查询操作的话作者是会要命愿意地告知你以后写多少生成器写到四分之二的时候不要因为有事就编写翻译好生成器然后关掉生成器的cpp去干一些别样的美观的会让您忘了您的生成器还从未写完的事务比方说在大降水天去学园满是水的塑料像胶跑道上去跑操何况跑完后躺在全都以水的假草坪上然后会机房的时候再感个冒.

。。。 。。。

呵呵

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 410000;
const double eps = 1e-8;
inline int dcmp(const double &x){
    return (x > -eps) - (x < eps);
}
int a[maxn],n,dep[maxn],rt;
namespace Graph{
    struct Edge{
    int to,next;
    }G[maxn<<1];
    int head[maxn],cnt;
    void add(int u,int v){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
    }
    int ind[maxn],oud[maxn];
    int dfs_clock,fa[maxn][23];
#define v G[i].to
    void dfs(int u){
    ind[u] = ++ dfs_clock;a[dfs_clock] = u;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa[u][0]) continue;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;dfs(v);
    }
    oud[u] = dfs_clock;
    }
#undef v
}
namespace seg{
    double T[maxn<<2],lazy[maxn<<2];
    void build(int rt,int l,int r){
    if(l == r){
        T[rt] = dep[a[l]];
        return ;
    }
    int mid = (l+r) >> 1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    T[rt] = T[rt<<1] + T[rt<<1|1];
    }
    inline void pushdown(int rt,int l,int r){
    if(rt == 0 || dcmp(lazy[rt] == 0) ) return;
    int mid = (l+r) >> 1;
    lazy[rt<<1] += lazy[rt];
    lazy[rt<<1|1] += lazy[rt];
    T[rt<<1] += lazy[rt]*(mid - l + 1);
    T[rt<<1|1] += lazy[rt]*(r - mid);
    lazy[rt] = 0;
    }
    void modify(int rt,int l,int r,int L,int R,int val){
    if(L <= l && r <= R){
        lazy[rt] += val;
        T[rt] += (r-l+1)*val;
        return ;
    }
    int mid = (l+r) >> 1;pushdown(rt,l,r);
    if(L <= mid) modify(rt<<1,l,mid,L,R,val);
    if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,val);
    T[rt] = T[rt<<1] + T[rt<<1|1];
    }
    void modify(int x,int val){
    using namespace Graph;
    if(x == rt) modify(1,1,n,1,n,val);
    else if(ind[rt] < ind[x]||oud[x] < ind[rt])modify(1,1,n,ind[x],oud[x],val);
    else{
        int p = rt;
        for(int j=20;~j;--j){
        if(dep[fa[p][j]] <= dep[x]) continue;
        p = fa[p][j];
        }
        if(1 <= ind[p] - 1) modify(1,1,n,1,ind[p]-1,val);
        if(oud[p] + 1 <= n) modify(1,1,n,oud[p]+1,n,val);
    }
    }
    double query(int rt,int l,int r,int L,int R){
    if(L <= l && r <= R) return T[rt];
    int mid = (l+r) >> 1;pushdown(rt,l,r);
    if(R <= mid) return query(rt<<1,l,mid,L,R);
    if(L >  mid) return query(rt<<1|1,mid+1,r,L,R);
    return query(rt<<1,l,mid,L,R) + query(rt<<1|1,mid+1,r,L,R);
    }
}
namespace lct{
    struct Node{
    Node *ch[2],*fa;
    int id,tag;
    }mem[maxn],*it,*null;
    inline Node* newNode(){
    Node *p = it++;p->ch[0] = p->ch[1] = p->fa = null;
    p->id = -1;p->tag = 0;return p;
    }
    inline void init(){
    it = mem;null = it++;null->id = -1;
    null->ch[0] = null->ch[1] = null->fa = null;
    null->tag = 0;
    for(int i=1;i<=n;++i) newNode()->id = i;
    for(int i=2;i<=n;++i){
        (mem+i)->fa = (mem+Graph::fa[i][0]);
    }
    }
    inline void rever(Node *p){
    p->tag ^= 1;swap(p->ch[0],p->ch[1]);
    }
    inline void pushdown(Node *p){
    if(p == null || p->tag == 0) return ;
    if(p->ch[0] != null) rever(p->ch[0]);
    if(p->ch[1] != null) rever(p->ch[1]);
    p->tag = 0;
    }
    inline void rotate(Node *p,Node *x){
    int k = p == x->ch[1];
    Node *y = p->ch[k^1],*z = x->fa;
    if(z->ch[0] == x) z->ch[0] = p;
    if(z->ch[1] == x) z->ch[1] = p;
    if(y != null) y->fa = x;
    p->fa = z;p->ch[k^1] = x;
    x->fa = p;x->ch[k] = y;
    }
    inline bool isroot(Node *p){
    return (p == null) || (p->fa->ch[0] != p && p->fa->ch[1] != p);
    }
    inline void splay(Node *p){
    pushdown(p);
    while(!isroot(p)){
        Node *x = p->fa,*y = x->fa;
        pushdown(y);pushdown(x);pushdown(p);
        if(isroot(x)) rotate(p,x);
        else if((x->ch[0] == p)^(y->ch[0] == x)) rotate(p,x),rotate(p,y);
        else rotate(x,y),rotate(p,x);
    }
    }
    inline Node* find(Node *p){
    pushdown(p);
    while(p->ch[0] != null){
        p = p->ch[0];
        pushdown(p);
    }
    return p;
    }
    inline void access(Node *x){
    for(Node *y = null;x != null;y=x,x=x->fa){
        splay(x);
        if(x->ch[1] != null){
        Node *p = find(x->ch[1]);
        seg::modify(p->id,1);
        }
        x->ch[1] = y;
        if(y != null){
        Node *p = find(y);
        seg::modify(p->id,-1);
        }
    }
    }
    inline void makeroot(Node *p){
    access(p);splay(p);rever(p);
    rt = p->id;
    }
}
inline double query(int x){
    using namespace Graph;
    if(rt == x) return 1.0*seg::query(1,1,n,1,n)/n;
    if(ind[rt] < ind[x] || oud[x] < ind[rt])
    return 1.0*seg::query(1,1,n,ind[x],oud[x])/(oud[x]-ind[x]+1);
    int p = rt;
    for(int j=20;~j;--j){
    if(dep[fa[p][j]] <= dep[x]) continue;
    p = fa[p][j];
    }
    double upside = .0;
    if(1 <= ind[p] - 1) upside += seg::query(1,1,n,1,ind[p]-1);
    if(oud[p] + 1 <= n) upside += seg::query(1,1,n,oud[p]+1,n);
    double dnside = (ind[p]-1) + (n-(oud[p]+1)+1);
    return upside/dnside;
}
char cmd[12];
int main(){
    int m;read(n);read(m);
    for(int i=1,u,v;i<n;++i){
    read(u);read(v);
    Graph::add(u,v);
    Graph::add(v,u);
    }
    dep[1] = 1;rt = 1;Graph::fa[1][0] = 1;
    Graph::dfs(1);seg::build(1,1,n);lct::init();
    for(int j=1;j<=20;++j){
    for(int i=1;i<=n;++i){
        Graph::fa[i][j] = Graph::fa[Graph::fa[i][j-1]][j-1];
    }
    }
    int x;
    while(m--){
    scanf("%s",cmd);read(x);
    if(cmd[2] == 'L'){
        lct::access(lct::mem+x);
    }else if(cmd[2] == 'C'){
        lct::makeroot(lct::mem+x);
    }else{
        double ans = query(x);
        printf("%.10lfn",ans);
    }
    }
    return 0;
}

从大碰着看


  1. 编制程序至今已经渗透五行八作,前途的十年,相信会完善覆盖任何行当,从没哪叁个行业不会和编制程序搭上关系

    威尼斯国际平台app 1

    6949359_3_thumb.jpg

    ###### *到市集买菜也能够用手提式无线话机结账

  2. 既然任何行业都和编制程序有挂钩,那尽早的今后就能够缺少多量颜值,而人才需求植物养育,且培育速度要求够快!

  3. 工业4.0以致以往的升华,机器人会代替部分产业的人手操控,懂编制程序的人会优于于不懂编程的人
  4. 为国家持续性发展提供丰富的调研本领,进步现在国家竞争性

从国家推动教育层面看


  1. 二〇一三年,美中国奥林匹克足球队巴马总理发起全体公民学习编程,全国拓宽“编制程序意气风发钟头”的扩充公共利润活动

    威尼斯国际平台app 2

    obama-code.org-photo.jpg

  2. 二〇一六年,“United Kingdom编制程序年”,英国分明5岁以上男女,都要在校学习编制程序

    威尼斯国际平台app 3

    How-to-code—year-of-code_thumb.jpg

  3. 人数仅130万的小国爱沙尼亚,推广程序万兽之王(ProgeTiiger)安顿,让7~15岁学子演练编写程序

    威尼斯国际平台app 4

    ProgeTiiger_Logo_horisontaal_EST_web.jpg

  4. 澳大波尔多(Australia卡塔 尔(阿拉伯语:قطر‎地区的Singapore、香岛等,都在私学实施编制程序课,香港(Hong Kong卡塔 尔(英语:State of Qatar)更拔出总课时的百分之三十三列入程序编写制定

    威尼斯国际平台app 5

    QQ20160826-0@2x.png

  5. 二零一六年奇宝立项小孩子编程,经过1年支付,前后相继编写出针对5-7岁小儿Computer思维学习玩乐,7-拾五岁幼儿编制程序学习软件火种斯Parker和课程,并前后相继落地10+城市二零一四年更付出小孩子创客编制程序课程落榜Hong Kong。

    威尼斯国际平台app 6

    QQ20160829-0@2x.png


个人观点看


  1. 编制程序是读书费用最低、效果与利益最大的就学课程,它只必要生机勃勃台微电脑和软件,读书范围也仅须要一张桌子和椅子
  2. 别的课程必要购买更加多的用具和提供越来越大的场所也许供给建设二个空中来学习
  3. 编制程序是各个兴趣活动中唯黄金年代能够同期锻练三种力量提高的技艺

总结


  1. 前途的子女不该只是单纯享受科学技术带给的方便人民群众,反而需求改为创作创建之人,发明更加的多科学技术给全部人使用
  2. 天公国家提早认识到”小孩子编制程序教育”是国家现在的竞争性,所以在儿女带有意识形态的年纪时便拉动学习以至纷繁投入大批量能源
  3. 音讯科学技术技能追着太阳追着风,是鹏程世界提升底子,各类孩子都应有学会怎么掌握控制计算机,而编制程序是最直白的路径
  4. 学懂编制程序就相近学会写字,孩子学会编制程序,将会对她们一生受用,因为它教会男女什么构思,作育她们的逻辑思量和化解难题技巧,并且能激发她们的创造本领
  5. 在自己近年与养爸妈依然老师的联络个中,就像他们还不知道小孩子编制程序对大家子女今后的浓郁影响,进而极有相当的大概率失掉孩子读书的机缘

自个儿写那篇随笔,除了分享对小伙子编制程序的接头外,更是因为新一代的儿女从小就在“触摸”的社会风气中成长,任何反响都以即时的信息报告,他们需求学会命令它创制它,而不只是仅仅利用它。
更希望保有老人能够突破守旧观念,让儿女真的接触科学技术,操控科学技术,调控科学和技术。

点击关键字读书编制程序中孩子编制程序法学习文章

本人是父母,对编制程序0领会
了解STEM
STREAM教育
奇宝STREAM课程

我是唐一(微信号11681445),奇宝科技联合创始人。当过几年老师,编写过9本FLASH和PHOTOSHOP教科书,参与过上百集的长篇动画制作,带团队开发了500多个幼教APP。现在全力打造“编程中国”社群项目,旨在普及中国儿童学习编程,给孩子创造未来的力量。希望认识更多朋友分享我的经验和学习你的心得!

相关文章