T1 IOI 2009 小熊
没有在实现中注意题目里的条件（蜂蜜不能经过喜欢吃蜜蜂的小熊的家）。

T2 IOI 2010 生活品质
这就比较尴尬了：没想到怎么写=。=
这个 DZY Love Sorting里用过的套路没想起来非常尴尬。
简单地说就是用01序列代替复杂的排列简化判定条件。
具体二分的时候感觉到是在二分一个可行范围。

T3 IOI 2009 旅行商
常规线段树优化dp。
不过还是切分提示的好。
bblss123神犇可以用spfa虐个15分。

FastInput by bblss123

char buf[M*8],*p;
inline void rd(int &a){
    for(++p;*p<=32;++p);
    for(a=0;47<*p;++p)a=a*10+(*p^48);
}
int main(){
    p=buf-1;
    fread(buf,1,M*M*8,stdin);
      ....
}

Templet by ShinFeb

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cctype>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <set>
#include <bitset>
#include <stack>

//long long,memory,freopen
using namespace std;

#define rep(i,s,t) for(register int i=s,t_=t;i<t_;i++)
#define per(i,s,t) for(register int i=(t)-1,s_=s;i>=s_;i--)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define shut assert(0)
#define when printf("%.2f\n",1.0*clock()/CLOCKS_PER_SEC)
#define sqr(x) ((x)*(x))
#define inf (1<<30)
#define INF (1ll<<62)

typedef long long ll;
typedef double db;
struct ii
{
    int x,y;
    ii(int x=0,int y=0):x(x),y(y){}
    inline bool operator<(const ii &a)const{return (x==a.x&&y<a.y)||x<a.x;}
    ii operator+(const ii &a)const{return ii(x+a.x,y+a.y);}
};

template<class v>void sc(v &x)
{
    char c;x=0;int f=1;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class v>void nt(v x)
{
    if(!x)return;
    nt(x/10);putchar('0'+x%10);
}
template<class v>void pt(v x)
{
    if(x<0)putchar('-'),x=-x;
    if(!x)putchar('0');
    else nt(x);
}
template<class v>void ptn(v x)
{
    pt(x);putchar('\n');
}
template<class v>void pts(v x)
{
    pt(x);putchar(' ');
}
template<class v>void pp(v x,int f)
{
    static char ch[]={" \n    "};
    pt(x);putchar(ch[f]);
}
template<class v>inline void Max(v &x,v y){if(x<y)x=y;}
template<class v>inline void Min(v &x,v y){if(x>y)x=y;}
int main()
{
//    freopen("pro.in","r",stdin);
//    freopen("chk.out","w",stdout);
    return 0;
}

从出生到现在的种种迹象都能印证我的平凡。

我初中的时候听一个教授讲数学频频睡着。这是我放弃数学竞赛的原因。
因为类似的原因，我放弃了化学竞赛。
我写物理试卷很慢，往往临交卷还有很多题空着。这是我放弃物理竞赛的原因。

我玩游戏成绩会下滑。
我中午不午睡会崩溃。
……

因为很笨，所以当觉得眼前的生活还和谐的话，要学会珍惜。

2016.May.24th

昨晚比的很浪，提前交卷后也没有太多事做，以后应该耐着性子，对拍、骗分种种，毕竟几乎没满分过。

该有一个正能量的OIer该有的样子，机房不是浮夸的地方，与其抱着调完了想其他题目的心态，不如认认真真的把比赛题目调到最后，对已付出的时间负责。总有或多或少的坑等待着我们去填补。

估分的时候别估太高，要有自知之明，报能拿稳的分，如果碰巧多水了点分，会收获意外的喜悦。

陈题新作，我们在成长，会有更开阔的思路、更神奇的解法。

同样是盯着屏幕，认真一些会大大缩短debug的时间。每一步不要想当然，多问为什么。

胜负心不要太重，上帝把自己安排在这里，就履行好自己对上帝所给予的一切的责任。

题目还是要多靠自己，少依赖别人，多分析、猜测。

不要人云亦云，做好自己。

2016.Sept.14th

有些话是很简单的：我要打败谁，谁谁谁是我的对手，谁谁谁好强，谁谁谁弱鸡。
小孩都会说。

有些东西是要静下心才能掌握的，与用了几次无关，与笔记写了多长无关。

少说话，多做事。

以上差不多是近期的反思。

最后不恰当的引用一句很喜欢的诗句：

心事浩茫连广宇，于无声处听惊雷。

——鲁迅

根到每个节点的每一条路径对应每一种子串，无一重复，无一遗漏。

关于自动机中的一个节点的大小，就是其所能表示的最长子串的长度。

一个节点表示的子串都是后缀关系，即其中一个是另一个的后缀。他们的长度连续，并可以由一个右端点联系起来。

当节点a表示的最长子串是节点b表示的最长子串的后缀，节点a可以由节点b跳到，可以看做是对一种蕴含关系的遍历。另外，b可以把自己的右端点分享给a。

当一个节点表示的一个子串是别的点表示的子串的后缀，而该节点表示的其他子串可能不是，就得把这个节点拆开来，需要哪个就把哪个当儿子。

附一份优雅的代码

struct suffix_automaton
{
    string s;
    int son[maxn][26],pre[maxn],step[maxn],last,total;
    inline void push_back(int v)
    {
        step[++total]=v;
    }
    void Extend(char ch)
    {
        push_back(step[last]+1);
        int p=last,np=total;
        for (; !son[p][ch]; p=pre[p]) son[p][ch]=np;
        if (!p) pre[np]=1;
        else
        {
            int q=son[p][ch];
            if (step[q]!=step[p]+1)
            {
                push_back(step[p]+1);
                int nq=total;
                memcpy(son[nq],son[q],sizeof(son[q]));
                pre[nq]=pre[q];
                pre[q]=pre[np]=nq;
                for (; son[p][ch]==q; p=pre[p]) son[p][ch]=nq;
            }  else pre[np]=q;
        }
        last=np;
    }
    void Build()
    {
        cin>>s;
        total=last=1;
        memset(son,0,sizeof(son));
        memset(pre,0,sizeof(pre));
        memset(step,0,sizeof(step));
        for (int i=0,End=s.size(); i!=End; i++) Extend(s[i]-'A');
        visit(1,0);
    }
} suf;

我想具体的Kyle会讲的==。

这就是后缀自动机。

参考文献( 有图哦(:з」∠) )：
后缀自动机学习总结-functioner
后缀自动机讲解-Oyking

还有后缀自动机的性质：

后缀自动机具有两大性质，考虑转移边为自动机，考虑父亲边为逆序后缀树（后缀数组为后缀树的dfs序），如果忽略字符集大小的常数，构造复杂度为o（n）
很好很强大，更深的性质呢？
对于一个节点i，根s
1、整个自动机可以接受字符串的所有子串，且自动机为一个有向拓扑图
2、一条到i的路径唯一对应一个子串
3、所有i可以接受的状态互相成后缀关系，且长度连续
4、对于i的父亲rt[i],rt[i]所能接受的所有子串都是i所能接受的所有子串的后缀
构造后缀自动机的时候有一步是判断l[a]+1==l[b],为的是防止多余状态被自动机接受，如果l[a]+1==l[b]，那么b所能接受的最长子串是合法的，根据3,4可知所有其他状态也都是合法的，否则l[a]+1!=l[b]可能会出现不合法状态,那么新建节点使l[c]=l[a]+1就可以筛出合法状态，而rt指针的修改可以看作是逆序后缀树的压缩边被解压缩出一个节点并添加一个新的叶子节点（即新逆序后缀）
5、统计方式的理解。从后续题目来看有两种统计方法，一是根据转移边dp，二是根据父亲边dp，其实是统计两个不同东西，转移边dp可以统计出有多少子串以此节点接受的状态为前缀，根据父亲边dp可以统计出以该节点接受的最长子串为后缀的子串有多少（逆序后缀树i所代表的是i所接受最长子串）
6、其实字典树也可以建立后缀自动机，考虑我们对于串建的时候，记last是为了找出最后一个的最长子串，而在字典树上就是字典树的父亲，所以按dfs序及父亲就可以建出字典树的后缀自动机
7、（逆序后缀树i所代表的是i所接受最长子串）这句话的意思是，将该串所有的逆序后缀建立一棵后缀树，而自动机中的每个节点i，它在后缀树中一直沿父亲边走向根\所代表的逆序后缀==节点i在自动机中接受到的最长子串
总而言之，后缀自动机兼有两种特性，如果想知道后缀的公共前缀之类，或子串重复次数等等与后缀联系的上的，可以用后缀树的性质，如果与所有子串相关，自动机就比较好用

转载自【字符串新武器】后缀自动机-huyuncong

习题：
后缀自动机（SAM）学习指南-电子幼体
SAM 后缀自动机-Rivendell

竞赛

刚刚参加完了一年一度的物理竞赛。只是一个市里的竞赛。

大家都没做什么准备，学校的意思也好像是大家随便考考就好(?)。

在坐满了人的大巴上，我开始想象着我是一个为这个竞赛准备了很久的一个学生。因为紧张，所以我脑子里空空的。我回忆起这一年里我的生活，一种依然混乱、怠惰的生活。如果只是为了一场竞赛，是否值得付出那么多的时间？

以前读《维特根斯坦传》时，看到维特根斯坦的一句话：

学习哲学还有什么用，如果哲学只是让你看上去有道理的谈论某些逻辑问题，如果哲学不能改变你对生活中重大问题的思考……

放在竞赛上也同样适用吧

物理

依然没有掌握好物理。掌握了就该自信的面对自己写过的每道题。

有的时候说这什么的太难了，留着以后再去填吧。

她看起来很冷，但熟悉之后就会发现她热的一面。

时间很多的不是么，如果不接触一些陌生的东西消磨一些，就难免在熟悉的地方无所适从。

不过可能是因为太久没考物理了，写物理题的方式和以前大有不同，感觉物理比以前亲切了许多，但从效率来说是很糟糕的革新。

等以后一切结束了就去学好物理吧。期待着Ginger请教。

title

subtitle

latex: $O(n^2)$

$$
k^{k^{k^{k^{k^{k^{k^{k^{k^{k^{k^{k}}}}}}}}}}}
$$

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}

template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

int main()
{
//    freopen("pro.in","r",stdin);
//    freopen("chk.out","w",stdout);

    return 0;
}

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

$ hexo new "My New Post"

More info: Writing

Run server

$ hexo server

More info: Server

Generate static files

$ hexo generate

More info: Generating

Deploy to remote sites

$ hexo deploy

More info: Deployment