60年前情诗生成器

作者: 数理科学  发布:2019-10-05

德意志联邦共和国一名计算机考古学家开荒出计算机写作情诗程序,但她绝不这一前后相继的原创者。 早在60多年前,情诗生成程序已经出版。 计算机作诗 1948年6月,世界上首先台能一心推行存款和储蓄程序的电子Computer原型机在英帝国圣Louis高校落地。大家给它取名“婴儿”。 那时候琢磨人口为它编写了几十种新颖程序,不过到现在非常多早已屏弃。 大不列颠及英格兰联合王国商讨人口克Rees多夫·Strachey也涉足了“婴儿”的研制。他为考试这台原型机随机选撤废息的力量,编写出自动创作情诗程序。 “婴孩”自己蕴藏了汪洋诗篇数据。每一回运转作诗程序,大家只需输入几百个意思罗曼蒂克的动词和名词,它就可以自动生成一首短情诗。 Strachey把“婴孩”的“大作”打印出来贴在文告栏上。即便那些情诗不自然能打动女性的芳心,但作诗程序开创了微型Computer文本生成程序的起头。 后来随着Computer才干赶快进步,“婴儿”和作诗程序被群众稳步淡忘。 历史重演 德意志联邦共和国Computer考古学家David·瓦尔德前段时间在United Kingdom印度孟买理工高校博德利体育地方商讨Strachey故事集时发掘这一先后。 他花3个月时间编写出同样的在线“情诗生成器”程序供网友自由使用。 顾客在线运转这一顺序,输入一些词语,每一遍点击“重载”键,网页上就能冒出一首新的情诗。 英帝国《天津新闻日报》10日推荐瓦尔德的话电视发表:“那牵涉到一部分有国际影响力的大不列颠及苏格兰联合王国计算机文化遗产。编写程序的那3个月十三分折磨人,因为根据现行反革命专门的职业,这一主次特别原始。” 瓦尔德将于3月下旬在英帝国London就作诗程序宣布演说。他构建的“婴孩”复制机不久后就要德意志联邦共和国展览,届时她会用那台机械演示“表白信程序”。 Computer“艺术” Strachey1916年诞生于苏格雷汉姆普斯Ted,老爹爱好音乐和图案,老妈是一名地教育学家和电气技术员。那让Strachey从小受到艺术和理工科知识的再次影响。 他1935年跻身加州伯克利分校大学始祖学院学习,结业后做过物农学家和校长,并从20世纪40年间早先对计算机技艺发生兴趣。 1951年1月,Strachey第贰遍接触有囤积程序的Computer并开首编写程序。1952年,他得了校长工作,成为大不列颠及英格兰联合王国国家钻探发展公司的全职Computer本事钻探员。 同年夏日,Strachey从三嫂这里得到灵感,利用同事、出名计算机地医学家艾伦·图灵的任意数字生成器,开采出作诗程序,那是全人类第贰次利用计算机生成历史学文章。 Strachey还编写过最初的Computer音乐软件。他于1975年在加州洛杉矶分校大学逝世。

STREAM既然是前景的大方向,那奇宝为何偏偏重申是小孩子编制程序(Coding)并不是其余课程呢?能够从这几地点看的

题目:

黑客们经过对已有的病毒反编写翻译,将众多不一的病毒重组,并再次编写翻译出了新式的重组病毒。这种病毒的增殖和产生本事极强。为了阻碍这种病毒传播,某安全体门策划了一遍实行,来研商这种病毒。
实践在二个查封的局域网内进行。局域网内有n台Computer,编号为1~n。一些管理器之间通过网线直接相接,形成树形的结构。局域网中有一台十分的管理器,称之为核心计算机。依照一些上马的商讨,探究员们拟订了三个累计m步的实践。实验始于以前,主旨Computer的号码为1,每台微机中都有病毒的八个变种,并且每台Computer中的变种都差异样。实验中的每一步会是上边中的一种操作:

  1. RELEASE x
    在号码为x的Computer中植入病毒的三个新变种。这么些变种在植入在此以前不设有于局域网中。
  2. RECENTER x
    将基本计算机改为编号为x的微型Computer。可是那一个操作会变成原先基本Computer中的病毒产生新变种,并感染过来。换言之,若是操作前的着力计算机编号为y,相当于在操作后附加了贰回RELEASE y的操作。
    基于钻探的定论,在植入贰个新变种时,病毒会在局域网中寻觅宗旨Computer的职位,并顺着网络中最短的路径感染过去。
    而首先轮实验揭发了一个耸人听他们讲的精神:病毒的两样变种是排斥的。新变种在感染一台已经被旧变种感染的微管理器时,会把旧变种完全销毁之后再感染。但钻探员开掘了落到实处进度中的漏洞。假使新变种在耳熟能详进度中尚无销毁过那类旧变种,需求先费用1单位时间深入分析旧变种,本领销毁。假如在此以前销毁过这类旧变种,就能够以为销毁不花费时间。病毒在两台Computer之间的散布亦可以为不费用时间。
    研讨员对任何感染进度的耗费时间特意感兴趣,因为那是消灭病毒的最佳时机。于是在m步实验之中,商讨员一时还有大概会做出如下的摸底:
    3,REQUEST x
    问询一旦在数码为x的管理器的首要集结中的Computer中植入贰个新变种,平均感染时间为多少长度。编号为y的Computer在号码为x的Computer的首要集合中,当且仅当从y沿互连网中的最短路径感染到中央Computer必需经过x。由于有RECENTEOdyssey操作的留存,这些集结併不一定是始终不改变的。
    由来,安全单位认为已经不必要实际的实践了,于是他们拜托你编写贰个程序,模拟实验的结果,并回复全体的打听。

一向对图灵在世界二战中带头用Computer原理破解德军密码这段历史很感兴趣,《模仿游戏》这部电影刚刚重现了当年的好玩的事,并还原地拾叁分优质。向图灵先生致敬,越发是在斯图加特生活读书过两年,听得多了就能说的清楚非常多他的传说,看了电影感受更加深。


题解:

题目真**长

大家用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. 编制程序于今曾经渗透各行各业,前程的十年,相信会周密覆盖任何行当,尚无哪贰个行当不会和编制程序搭上关系

    图片 1

    6949359_3_thumb.jpg

    ###### *到市镇买菜也能够用手提式有线电话机付费

  2. 既然任何行当都和编程有联系,那尽早的今后就能相当不足多量人才,而人才须要培养,且培育速度要求够快!

  3. 工业4.0甚现今后的进化,机器人会代替部分产业的人手操控,懂编程的人会优于于不懂编制程序的人
  4. 为国家持续性发展提供丰富的调查研商本事,提高今后国家竞争力

图灵的密码传说要从二个“谜”初阶,ENI培洛霉素A (谜) 源自于希腊共和国(The Republic of Greece)文,既是战役时代所用的密码(在富有用于军事和外交的密码里,最盛名的也许应属第二遍世界大战中德国行使的ENI丙胺博莱霉素A),而破解这么些密码的难为Alan• 麦席森• 图灵。

本文由东方彩票app发布于数理科学,转载请注明出处:60年前情诗生成器

关键词:

上一篇:“鲨鱼皮”高科技泳衣被禁
下一篇:没有了