初涉C#制作扫雷游戏

起因

最近OI退役了,文化课滚粗了,感觉无事可做,于是便准备用C#来搞搞开发。在这篇文章里我只想浅略的谈一谈我的代码实现过程,至于详细的制作,请参阅这篇博文。同时我也要给这位写教程的学长好评,真的是超详细,太赞啦!

代码托管

该项目的代码我已经托管在GitHub上,大家可以自行查看,有什么值得改进的地方欢迎向我指出。

正文

雷区绘制的有关技术问题

Settings.settings的相关操作

UpdateSize函数的有关技术问题

//last update:2015/11/28/01:36

再见 OI!

赛后两天

洛谷的民间数据出来了,貌似只有290?(100+100+0+60+10+20)。Day1T3 hash表没初始化,全炸了?Day2T1 写堆貌似贪心是错的?Day2T2 DP不会打又炸了?Day2T3 不会傻逼枚举然后贪心贪错了,直接20分搞到滚粗?290分在FJ能搞到省二左右(也是踩线),ZJ目测就直接出局了。

这两天过得真的很难受,各种想法都在脑子里浮现:辛辛苦苦努力了一年然后省三滚粗了?以后永远只能待在教室里敲不了代码了?自己想的拿个省一然后自招都是幻想?学校弱自己弱却无法改变? 一切的一切都使我颓废不已,我是真的弱,真的水,真的粗心,明明好不容易有了一个机会,却白白浪费掉了,我要怎么向陈老师去交代,怎么向学长交代,怎么向自己交代?同时,文化课也让我变得十分迷茫,逃了这么多的课,漏了不知道多少东西,各种题目都不会,做出来是错的,已然感觉要双向滚粗了。我能明明白白感受到只有唯一一次机会却失去后而无法弥补的悲哀。我整天想着最后成绩出来了拿了个三=怎么见人,口口声声说着自己弱,经常都颓丧得趴在桌子上想着自己当时写题的时候怎么那么水,状态那么差,各种遗憾之类的。而事实上,这又能有什么用?准确来说,没有半点卵用都没有。去衢州这一次真的就是彻彻底底的失败,就是铩羽而归,而我又能改变得了什么?难不成我有办法去改源码,去改CCF的数据?既然已经失去了一次机会,那就更应该去珍惜去利用现在眼前的一切,而不该在未来的高考之后再去后悔此刻时光的弥足珍贵,去埋怨现在的自己没有好好努力,而是很傻逼的在后悔、在遗憾早已无法改变的东西。我也更能相信,将来的我也一定不会喜欢看到现在颓废的我的。

高考750分,把人生变成750岁;OI600分,让记忆只剩下1S,128MB我应该庆幸当时的自己没有错过OI这有趣的东西,能让自己在高中有过这样一段弥足珍贵的时光,更能接触到许许多多的算法,领略到与别人完全不同的东西,就算最终现实与梦想背道而驰,我也应该为自己有过这样的一段为梦想而执着过的经历而感到高兴

接着我就该退役了,想想自己当时在机房黑板上大大写着的”NOIP2015 RP++”的话还是感觉挺好笑的。也正像Day2的解压密码”2016Xia%MY@jian”虽然我不能坚持到2016夏天与你再见,但我仍会一直记得,我曾经也是个OIer,虽然未曾成功,虽然抱有遗憾,但我也确确实实是广大为自己梦想而执着的OIer中的那一个,并且会为在高中有过这样一段拼搏的时光而感到欣喜与骄傲!

最后,我要给马上回到文化课忙忙碌碌学习中的自己打气,这一段时光同样也是弥足珍贵的,just fighting!

赛后一星期

知道成绩了,没能像想象中那样翻盘,心里还是挺空落的。不止一次地觉得自己弱,自己水,特别是当每次做题被卡,或是看到别人获了什么奖,拿了什么牌时,心里就特别不是滋味。一项奋斗了这么长时间的东西,最终却没有得到自己想要的结果,败兴而归,是多么的遗憾啊。

“当时选择了这条路的我,就是奔着单纯的拿奖去的吗?”我也曾不止一次地这样问过自己,而事实上,我也找不出答案。仔细回顾这一年的时光,发现除了刚开始那段,一级最后比赛前目标清晰过外,其余的,大多是在浑浑噩噩,目标模糊中度过的。而现在的我,却更加感触不到未来,感触不到理想,甚至,开始变得麻木,变得适从。我讨厌这种失去方向失去理想,而只能每天在相同的循环中度过却无法改变的感觉!一个东西,当你曾经拥有并视之如命,而突然之间,突然得你都无法确切感知到,它便失去了踪影,任你怎么寻都无法寻到,或许,现在的我也正是这样一种感受。

我的脑海中,能清晰地记得那个夜晚,一个人独自随坐在机房的讲台上,昏暗的灯光下,津津有味地看着NOI导刊中的线段树,感受着每一次思维的运转;我更加能记得,那些个无数的下午,晚上,我们6个人(gxy,yzy,zsh,ysy,wkw和我)在机房里,占据了前三排,听课,打题,或是不时地聊聊天,使冻结了的空气中,也有了一丝暖气。这一切的一切,便好似昨天刚刚发生过,而现在看来,真是恍如隔世。

“放慢所有 回忆里的感受 只怕听见 谁忽然泪流 那些曾经 不经事的哀愁 如今是最愉快的拥有”

(不知道是巧合还是啥,敲到这里的时候就刚刚听到这段歌词)。或许,回忆也不仅仅只能带给人伤痛,每一个无比清晰的片刻,每一个一起奋斗过的好友,以及那早已被敲得掉了字的键盘和满是污渍的鼠标,都让我真真实实地感受到时间的流逝,感受到灵感突来的欣喜,以及获得新知的激动。现在的我,也足以能够欣慰地回味这一年所经历的一切,并自豪地对别人说:“我用相同的时间,领略到了另一个世界!”这或许才是OI真正的魅力所在:看着每一次的提交由红色的Wrong Answer,变成绿色的Accept,由一百或是几十的分数,一步一步地爬升到300,以及那一次次走上讲台评测时,掩盖不住内心激动的沉着,这才是兴奋,才是喜悦,才是成长!

遗憾的是,现在的我要向OI道别了,而我也无从知道下次相见会是何时,亦或是,后会无期。正如鲁迅先生所说(果真被语文老师说中了……),真的猛士,敢于直面惨淡的人生,敢于正视淋漓的鲜血。文化课固然是枯燥无味而又寥寥无期的,而正是这一天天未曾间断的求索,才给予了你终有一天的辉煌。造化是为庸人所设计的,而也只有庸人,才会被动地屈服,顺从于眼前的一切。每个人,都不想成为庸人,自然,我也不想。

新的一切都还在未来的路上等着你,而那一切,也只有顽强,勇毅而又不失聪慧的人才能得的到,So,just fighting!

....

....

写在NOIP2015复赛之前

现在是2015年11月6日,再过一天就是2015年11月7日

明天就是NOIP2015复赛day1的日子

yzy加油 lzw加油 zbt加油 chp加油 lwq加油!

YZOI加油!

for(rp=1;;rp+=INF);

杭二酱油记

....
终于或许结束了,从一开始的学军到今天的杭二,或许我没有学到许多知识,但却有了常人不容易有的经历。坐在颠簸的火车上,回想着杭二的一切,虽然只有短短的连一天都谈不上,但这一天里我却也明白了许多。比起杭二来说,我们学校只不过是一个处于乡村欠发达地区的弱校罢了,我们没有强大的师资力量,我们没有好的生源,我们更没有足够好的气氛来带动自身的学习,在这样的一种现实下,我想作为一个弱校的蒟蒻,或许会由于各种原因被虐,被D,被瞧不起,但是,既然我们出来了,就不能让别人由于瞧不起我们而瞧不起我们义中。我们是水平低,是弱,但这并不能表明我们会因此而不想上进,会因此而颓废,就像zbt说的那样,既然知道自己是弱,那就不能让自己一直这么弱下去。而我知道,现在离复赛的时间也不多了,因此,我需要做的只是珍惜这最后的来之不易的机会,在自己的OI生涯画上句号之前,好好珍惜在机房最后的时间,认真做好最后的每一道题,不要给退役后的自己留下任何遗憾。

vijos1285 佳佳的魔法药水

题目大意

给出n中个药水的价格,其中只有可能A+B合成C,叫你求出合成0号药水的最少花费和方案数

解题过程

考虑图论模型,即如果A和B能转化成C,那么便在A.B和C中连一条边,然后就直接跑dijkstra,每次取出最小的花费val[i]去更新其他药水的花费,当然这里的其他药水必须是已经更新过了的,至于方案数的话乘法原理一用就跑出来了.

总结

所谓的最短路,并不一定只有在有实际的“路”的题目中才用得到,关键是把题目转化为图论模型,把更新条件转化为”路“。此题没有对dijkstra算法贪心的精髓理解深刻是难以转化为图论模型的。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1000+10;
const int INF=0x7f7f7f;
int n,tot[maxn],val[maxn],a[maxn][maxn];
int x,y,z;
bool v[maxn];
int main()
{
//    freopen("1.sb","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&val[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j]=n+1;
    for(int i=0;i<n;i++)
        tot[i]=1;
    while(cin>>x>>y>>z)
        a[x][y]=a[y][x]=z;
    for(int i=0;i<n;i++)
    {
        int minn=INF,k=0;
        for(int j=0;j<n;j++)
            if(!v[j]&&val[j]<minn)
            {
                minn=val[j];
                k=j;
            }
        if(minn==INF)
            break;
        v[k]=true;
        for(int j=0;j<n;j++)
            if(v[j]&&a[k][j]<n+1)
            {
                if(val[a[k][j]]>val[k]+val[j])
                {
                    val[a[k][j]]=val[k]+val[j];
                    tot[a[k][j]]=tot[k]*tot[j];
                }
                else if(val[a[k][j]]==val[k]+val[j])
                    tot[a[k][j]]+=tot[k]*tot[j];        
            }

    }
    printf("%d %d",val[0],tot[0]);
    return 0;
}

浅谈树形动规的一般解法步骤

一道题目

问题描述

长郡中学校长打算举行建校100周年的晚会。学校的职员是分等级的,也就是说职员之间的上下级关系组成一棵以校长为树根的树。校长要亲自邀请一些职员参见晚会。同时校长亲自到场欢庆这个节日。职员用1~n之间的整数编号,人事处给出了每个职员的搞笑指数。如果一个人和他上司一起参加,那么便可能产生麻烦。为了使晚会的每个参加者都高兴,校长不会同时邀请某个职员和他的顶头上司。
你的任务是给出一个客人列表,使得客人的搞笑指数之和最大。

输入

第一行一个整数n(1≤n≤6000)。以下n行每行是相应编号职员的搞笑指数,该数的返回是[-128..127]。然后是职员的关系树,每行格式是 ,意思是第y个职员是第x个职员的顶头上司。输入以0 0结束。

输出

最大的搞笑指数之和。

题目分析

表示以前几乎就没接触过这种题目是什么鬼…,然后就开始傻逼bfs,然后就爆了。正解:用f[i][0]表示以i为根的子树,且i一定不取所产生的最大权值,用f[i][1]表示以i为根的子树,且i一定取所产生的最大权值,因此对于f[i][1],它的子节点一定不能取,对于f[i][0],它的子节点可以取也可以不取,因此最后的状态转移方程为:$f[i][0]=\sum\limits_{j=1}^{childsize}{\max {f[j][1],f[j][0]}}$.

一般解题方法

  1. 找出所有根节点并入队
  2. 取出队首元素,更新其父亲节点并将其父亲节点入度减1
  3. 判断其父亲节点入度是否为0,若是,则入队
  4. 重复步骤1

    贴个代码

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn=6000+10;
    int x,y,n,a,b,cnt,f[maxn][2],q[maxn],val[maxn],num[maxn],pre[maxn];
    int main()
    {
     freopen("1.sb","r",stdin);
     scanf("%d",&n);
     for(int i=1;i<=n;i++)
         scanf("%d",&val[i]);
     while(cin>>x>>y&&x!=0)
     {
         pre[x]=y;
         num[y]++;
     }
     for(int i=1;i<=n;i++)
         if(num[i]==0)
             q[++cnt]=i;
     for(int k=1;k<=cnt;k++)
     {
         a=q[k];
         f[a][1]+=val[a];
         b=pre[a];
         if(b==0)
             break;
         f[b][1]+=f[a][0];
         f[b][0]+=max(f[a][0],f[a][1]);
         num[b]--;
         if(!num[b])
             q[++cnt]=b;
     }
     printf("%d",f[a][1]);
     return 0;
    }
    

他在一片喧闹中揉了揉惺忪的双眼,这时,同学告诉他得起床了,于是,他一骨碌跳下了床,以极快的速度刷完牙,迷迷糊糊奔出了寝室的大门,并且不小心摔了一跤,将他一把从刚刚未完成的梦中摔醒。他很普通,普通到几乎不会有什么人对他产生过过于深刻的印象。他调皮爱捣蛋,最喜欢在课堂上学着周立“波“的腔儿挑弄老师,为此,老师也没少恼他。他喜欢一个人静静坐在机房,在夜幕降临的那一际,思索着人生,因为,他喜欢,那束最后太阳的余晖洒在地板上所产生的光晕。他喜欢独自一人,独自一人走出喧闹过后的食堂,面朝着空无一人的大道,而或许是他产生幻觉了,因为他分明看到了那些为OI付出一切的学长们,正朝着他挥手。他有着自己喜欢并且热爱的事业,从这一点来说,他是足够幸运的,却也足够无奈。他会莫名其妙地数着一张由一张的作业纸,口中不时吐槽着”这题目真特么鬼畜“,“总有老师想要谋害朕之类的话语,而也只有他自己才能明白,迎接他的是无穷的寂寞与空虚。

他只是那个他,而我也只是那个我。

浅谈线段树及其应用

线段树的定义

线段树(segment tree)是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

线段树的作用

有一列数,初始值全为0,每次可以进行以下三种操作中的一种:
(1)给指定区间每个数加上一个值
(2)将指定区间所有数置成一个统一的值
(3)询问一个区间上的最小值、最大值、所有数的和

线段树的存储

struct Node
{
    int left,right;
    int min,max,sum;
    Node *leftchild,*rightchild;
}

线段树的构造

void build(Node *cur,int l,int r)
{
    cur->left=l;
    cur->right=r;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
    }
    else
        cur->leftchild=cur->rightchild=NULL;
}

在线段树上对元素进行修改

将线段树上位置为x的元素修改成num

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
        cur->min=cur->max=cur->sum=num;
    else
    {
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=lc->sum+rc->sum;
        cur->max=max(lc->max,rc->max);
        cur->min=min(lc->min,rc->min);
    }
}

对线段树的某一个区间进行询问

询问区间[l,r]所有元素和

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=cur->sum;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
    }
    return ret;
}

那么对于整个区间进行操作呢?

是不是需要对每一个元素都进行insert()操作呢?
显然不行,那样的话每一次操作都要$O(nlogn)$,失去了线段树的优势。

lazy-tag技术:

lazy-tag的思想就是在对区间进行更新的时候,在分解出来的区间上打上作用于整个子树的标记
当在对这个区间进行维护或者查询的时候便将这个标记进行分解,并将其传递到它的两个子树上。

对一个区间整体加上一个数

将区间[l,r]整体加上delta

void update(Node *cur,int l,int r,int delta)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if((l<=cur->left)&&(cur->right<=r))
        cur->delta+=delta;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,delta);
        if(r>(cur->left+cur->right)/2)
            update(rc,l,r,delta);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
}

使用lazy-tag技术对元素进行修改

将位置为x的元素修改为num

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
    {
        cur->sum=num;
        cur->delta=0;
    }
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->delta=0;
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
}

使用lazy-tag技术对区间进行查询

询问区间[l,r]上所有元素的和

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=cur->sum+(cur->right-cur->left+1)*cur->delta;
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->delta=0;
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
    return ret;
}

将一个区间整体置为一个数

额外维护两个域en表示一个区间是否为统一的数,若en有效,则data域表示区间统一的数的数值。
同样,我们可以用lazy-tag来维护这种操作

求一个节点表示区间上所有元素的和

inline int clacsum(Node *cur)
{
    if(cur->en)
        return (cur->right-cur->left+1)*cur->data;
    return cur->sum;
}

修改一个节点的值

将位置为x的元素修改为num

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
    {
        cur->sum=num;
        cur->en=false;
    }
    else
    {
        if(cur->en)
        {
            lc->data=rc->data=cur->data;
            lc->en=rc->en=true;
            cur->en=false;
        }
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=clacsum(lc)+clacsum(rc);
    }
}

修改整个区间的值

将区间[l,r]上所有元素的值置为num

void update(Node *cur,int l,int r,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->en)
    {
        if(lc!=NULL)
        {
            lc->data=num;
            lc->en=true;
        }
        if(rc!=NULL)
        {
            rc->data=num;
            rc->en=true;
        }
    }
    if((l<=cur->left)&&(cur->right<=r))
    {
        cur->en=true;
        cur->data=num;
    }
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,num);
        if(r>(cur->left+cur->right))
            update(rc,l,r,num);
        cur->sum=calcsum(lc)+calcsum(rc);
    }
}

查询区间的和

询问区间[l,r]上所有元素的和

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))\
        ret+=clacsum(cur);
    else
    {
        if(cur->en)
        {
            lc->data=cur->data;
            lc->en=true;
            rc->data=cur->data;
            rc->en=true;
            cur->en=false;
        }
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
    return ret;
}

总结

到这里就差不多写完了,把所有操作的代码汇个总:

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

struct Node
{
    int left,right;
    int min,max,sum,delta;
    bool en;
    Node *leftchild,*rightchild;
};

void build(Node *cur,int l,int r)
{
    cur->left=l;
    cur->right=r;
    if(l!=r)
    {
        cur->leftchild=new Node;
        cur->rightchild=new Node;
        build(cur->leftchild,l,(l+r)/2);
        build(cur->rightchild,(l+r)/2+1,r);
    }
    else
        cur->leftchild=cur->rightchild=NULL;
}

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
        cur->min=cur->max=cur->sum=num;
    else
    {
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=lc->sum+rc->sum;
        cur->max=max(lc->max,rc->max);
        cur->min=min(lc->min,rc->min);
    }
}

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=cur->sum;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
    }
    return ret;
}

//range
void update(Node *cur,int l,int r,int delta)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if((l<=cur->left)&&(cur->right<=r))
        cur->delta+=delta;
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,delta);
        if(r>(cur->left+cur->right)/2)
            update(rc,l,r,delta);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
}

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
    {
        cur->sum=num;
        cur->delta=0;
    }
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->delta=0;
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
}

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))
        ret+=cur->sum+(cur->right-cur->left+1)*cur->delta;
    else
    {
        lc->delta+=cur->delta;
        rc->delta+=cur->delta;
        cur->delta=0;
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
    return ret;
}

//all range
inline int clacsum(Node *cur)
{
    if(cur->en)
        return (cur->right-cur->left+1)*cur->data;
    return cur->sum;
}

void insert(Node *cur,int x,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->left==cur->right)
    {
        cur->sum=num;
        cur->en=false;
    }
    else
    {
        if(cur->en)
        {
            lc->data=rc->data=cur->data;
            lc->en=rc->en=true;
            cur->en=false;
        }
        if(x<=(cur->left+cur->right)/2)
            insert(lc,x,num);
        if(x>(cur->left+cur->right)/2)
            insert(rc,x,num);
        cur->sum=clacsum(lc)+clacsum(rc);
    }
}

void update(Node *cur,int l,int r,int num)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    if(cur->en)
    {
        if(lc!=NULL)
        {
            lc->data=num;
            lc->en=true;
        }
        if(rc!=NULL)
        {
            rc->data=num;
            rc->en=true;
        }
    }
    if((l<=cur->left)&&(cur->right<=r))
    {
        cur->en=true;
        cur->data=num;
    }
    else
    {
        if(l<=(cur->left+cur->right)/2)
            update(lc,l,r,num);
        if(r>(cur->left+cur->right))
            update(rc,l,r,num);
        cur->sum=calcsum(lc)+calcsum(rc);
    }
}

int querysum(Node *cur,int l,int r)
{
    Node *lc=cur->leftchild,*rc=cur->rightchild;
    int ret=0;
    if((l<=cur->left)&&(cur->right<=r))\
        ret+=clacsum(cur);
    else
    {
        if(cur->en)
        {
            lc->data=cur->data;
            lc->en=true;
            rc->data=cur->data;
            rc->en=true;
            cur->en=false;
        }
        if(l<=(cur->left+cur->right)/2)
            ret+=querysum(lc,l,r);
        if(r>(cur->left+cur->right)/2)
            ret+=querysum(rc,l,r);
        cur->sum=lc->sum+lc->delta*(lc->right-lc->left+1);
        cur->sum+=rc->sum+rc->delta*(rc->right-rc->left+1);
    }
    return ret;
}

浅谈ST算法在RMQ问题中的应用

题目大意

给你一个序列,叫你找出该序列中的一个最长连续子序列[left,right]使得a[left]为这段序列的最小值,a[right]为这段序列的最大值。

问题分析

首先假设当前存在区间[l,r],那么如果我们能用O(1)的时间返回这个区间的最大值所处位置a,以及最小值所处位置b,如果ab,则对三段分别进行递归调用即可解决问题。那么,我们需要怎么样事先处理好区间[l,r]的最大值呢?

RMQ问题的ST算法

这就是一个经典的RMQ问题(Range Minimum/Maximum Query),我们采用ST算法也就是倍增来解决。用f[i][j]表示从i开始长度为2^j的区间的最小值,那么很容易得出状态转移方程:$f[i][j]=min{f[i][j-1],f[i+(1<<(j-1))][j-1]}​$,这样一来只需要O(nlogn)的时间就可以求出一个区间的最值了。接下来就是查询,我们令k为满足2^k<=R-L+1的最大整数,则以L为开头,以R为结尾的两个长度为2^k的区间合并起来即覆盖了查询区间[L,R],$k=trunc(log(R-L+1))​$,最后的查询结果即为$min{f[L][k],f[R-(1<<k)+1][k]}​$.

预处理代码

void RMQ_init()
{
    for(int i=1;i<=n;i++)
        f[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

查询代码

int find(int L,int R)
{
    int k=trunc(log2(R-L+1));
    return min(f[L][k],f[R-(1<<k)+1][k]);
}

Hexo的简易部署

Hexo的简易部署

由于机房电脑重启自动还原,每次都得重新部署一次,因此来写篇文章谈谈Hexo的简易部署方法

首先在电脑中装好gitnode.js

接着在U盘的Hexo目录打开git命令行,输入以下命令

全局安装Hexo

npm install hexo -g

安装必要组件

npm install

接着就是在电脑上生成SSHkey

设置git的user name和email:

git config --global user.name "laphets"
git config --global user.email "768066323@qq.com"

检查目录是否存在

ls -al ~/.ssh

生成SSHkey

ssh-keygen -t rsa -b 4096 -C "768066323@qq.com"

在GitHub上加入SSHkey

检测是否成功连接到GitHub

ssh -T git@github.com



dashboard