前几天vp subregional看到这样一个题，写了写发现和正解不一样，也不会证自己的做法的正确性

听说是错的

题目大意

给一个 $W\times H$ 的矩形，划分成尽量少的整边长正方形，输出方案

$1\leq W,H \leq 60$

错误做法

猜想一定存在一条分割线贯穿矩形，使得矩形分成两半，并且两半的最优解拼起来就是整个矩形的最优解，然后随便dp

Hack

AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
AAAAAAAABBBBBBBBBBB      AAAAAAAAABBBBBBBBBB
BBBBBCCCBBBBBBBBBBB  vs  AAAAAAAAABBBBBBBBBB
BBBBBCCCBBBBBBBBBBB      CCCCCCCCCBBBBBBBBBB
BBBBBCCCBBBBBBBBBBB      CCCCCCCCCAAAAAAAACC
BBBBBAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
BBBBBAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAACC
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
CCCCCAAAAAAACCCCCCC      CCCCCCCCCAAAAAAAABB
      total=7                  total=8

这两个平面图的色数都是3，很有趣（被打

乱搞做法

根据以上反例猜想dp的每一个状态要么是一个矩形，要么是一个矩形抠掉一个角上的另一个矩形（称为L形）

矩形状态枚举抠掉哪个正方形转移，共$O(n)$种转移，$O(n^2)$种状态

L形状态共有5对关于$y=x$对称的转移共10种，共$O(1)$种转移，$O(n^4)$种状态

1.贴小矩形的右边界 （X是抠掉的位置，O是新放置的正方形，下同）

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOO.....
OOOO.....
OOOO.....
OOOO.....
.........
.........

2.贴大矩形的左边界，右边界不到小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOO......
OOO......
OOO......

3.贴大矩形的左边界，同时右边界贴小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOO.....
OOOO.....
OOOO.....
OOOO.....

4.贴大矩形的左边界，右边界超出小矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOOO....
OOOOO....
OOOOO....
OOOOO....
OOOOO....

（此时转移到整个矩形上下翻转后的情况）

5.贴大矩形的左边界，同时右边界贴大矩形右边界

XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
XXXX.....
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO
OOOOOOOOO

6~10是对称的，略

可以发现每种情况要么大矩形边界缩小，要么小矩形边界扩大，所以可以 $O(n^4)$ dp

代码在此，可以下载下来hack

std

看不懂俄文，机翻了一下好像是说什么枚举杨表然后本地打表，反正看起来就不怎么多项式

之前做魔法森林,提交了一个看起来错误的代码，发现通过了就没再管

后来再做别的LCT题时发现新写的代码和之前的代码不一样

唯一不同的函数——cut函数分别为

inline void cut(node *x,node *y)
{
    mkr(x);
    access(y);
    x->pa->rson=0;//老代码
    x->pa=0;
}

和

inline void cut(node *x,node *y)
{
    mkr(x);
    access(y);
    x->pa->lson=0;//新代码
    x->pa=0;
}

提交记录如下

1.老代码

2.新代码

后来我又尝试把这行不同的代码去掉

还是过了

3.修改后的代码

有没有路过的好心人帮忙解释一下这个代码为什么对，或者为什么错吗？

如果能hack掉那当然是坠吼的

upd1:相同方式修改cut函数后去交动态图连通性仍然是三种都能过

upd2:已解决，感谢各位神犇

题目描述

一个 $ n $ 个点构成的竞赛图中最多能有多少条哈密顿路径？

$ n $ 最多能做到多大？

样例输入

 4

样例输出

 5

样例解释

 边的朝向分别为
 1->2
 2->3
 3->4
 4->1
 1->3
 2->4
 时

 哈密顿路径分别为
 1->2->3->4
 2->3->4->1
 3->4->1->2
 4->1->2->3
 2->4->1->3

 共5条

 P.S.经过爆搜发现n=1~9时答案分别为1,1,3,5,15,45,189,661,3357

大家好我是oscar..这可能是我第一次发博客诶..

由于我比较弱，所以可能讲了一些大家都会的东西...求不D...

好了不说太多，先步入正题...

今天我们的挑战是：不建后缀数组完成任务（网上的做法好像都是建出后缀数组再用后缀数组的性质算出height数组）

假装大家都会后缀自动机啦（我这种蒟蒻花了约一个星期才搞懂）

首先将 从last到root用suffix link连接的路径上的节点 标上结束标记（

inline void update()
{
    node *p=last;
    while(p!=root)
    {
        p->isend=1;
        p=p->link;
    }
}

由于后缀自动机上所有路径能表示出原串的所有子串，所有以 一个有标记节点 结束的路径能表示出原串的所有后缀

于是可以从根节点DFS一遍，每次有分岔时优先走字典序比较小的转移，途中遇到有结束标记的节点则输出（原串总长度-DFS到当前节点经过长度+1），这样就完成了第一部分的任务（？）

第二部分的任务是找出排序后相邻两个后缀的最长公共前缀...我们发现在第一部分的DFS中正好排序后位置相邻的后缀访问顺序也是连着的，只需要求相邻两个访问的后缀的“LCA”就可以啦

贴代码走人

鬼故事，进度条

int lcp[MAXN],minn,cnt;
void dfs(node *u,int len=0)
{
    if(u->isend)
    {
        printf("%d ",totlen-len+1);//totlen为字符串总长
        lcp[++cnt]=minn;            //更新LCP信息
        minn=len;
    }
    for(int x=0;x<sigma;x++)
    {
        if(u->next[x])
        {
            if(len<minn)minn=len;//用来记录LCP长度
            dfs(u->next[x],len+1);
        }
    }
}

呃...等等...为什么我TLE了？

貌似这样搜索会做好多重复工作诶...（应该是 $ O(n^2) $ 的）

我们来想办法优化一下

由于不需要输出路径上的所有字符，所以只需要考虑路径长度

那么只有一种走法的路径就可以被压缩成一条边

也就是说这样的路径↓

$ \Huge \bigcirc ---1--> \bigcirc ---1--> \bigcirc ---1--> \bigcirc $

可以压缩成这样↓

$ \Huge \bigcirc ---3--> \bigcirc $

而不改变拓扑结构DFS结果

这...就是...传说中的...路径压缩？

typedef pair<node*,int> pni;
pni find(node *u)
{
    if(!u->fast)return make_pair(u,0);
    pni _=find(u->fast);
    u->fast=_.first;
    u->fastlen+=_.second;
    return make_pair(u->fast,u->fastlen);
}

对比一下并查集的路径压缩（大雾）

typedef pair<int,int> pii;
pii find(int x)
{
    if(!pa[x])return make_pair(x,shift[x]);
    pii _=find(pa[x]);
    pa[x]=_.first;
    shift[x]^=_.second;
    return make_pair(pa[x],shift[x]);
}

好像没啥区别（大雾）

还需要预处理一下哪些边可以被压缩掉（动态求好像是错的，我不太明白为什么，可能是我写挂了），

把代码扔进一开始的update函数里

inline void update()
{
    node *p=last;
    while(p!=root)
    {
        p->isend=1;
        p=p->link;
    }
   //更新部分↓
    for(int i=1;i<=top;i++)
    {
        node *t=&pool[i],*q=0;
        if(t->isend)continue;
        int c=0;
        for(int ch=0;ch<sigma;ch++)
        {
            if(t->next[ch])
                ++c,q=t->next[ch];
        }
        if(c==1)
        {
            t->fast=q;
            t->fastlen=1;
        }
    }
   //更新部分↑
}

最后在搜索的时候判一下能不能走被压缩的路径就好啦

int lcp[MAXN],minn,cnt;
void dfs(node *u,int len=0)
{
    if(u->isend)
    {
        printf("%d ",totlen-len+1);
        lcp[++cnt]=minn;
        minn=len;
    }
   //更新部分↓
    if(u->fast)
    {
        find(u);
        dfs(u->fast,len+u->fastlen);
    }
   //更新部分↑
    else
        for(int x=0;x<sigma;x++)
        {
            if(u->next[x])
            {
                if(len<minn)minn=len;
                dfs(u->next[x],len+1);
            }
        }
}

这样复杂度为什么是对的呢？

我数学不好，不会证明，那就来感性理解一下

$ \bullet $ 经过“路径压缩”后的自动机构成一棵树

$ \bullet $ 叶子结点数（=原串后缀数）是 $ O(n) $ 的

$ \bullet $ 非叶子结点数（ $ \leq $ 叶子节点数-1）是 $ O(n) $ 的

$ \bullet $ 树的边数是 $ O(n) $ 的

$ \bullet $ 遍历这棵树是 $ O(n) $ 的

应该是这个意思吧QWQ反正跑得飞快QWQ

于是我就这么通过了 UOJ#35 后缀排序 通过记录

第一次写后缀自动机可能写挂了，欢迎dalao来hack

P.S.这种方法貌似在LOJ上会被卡内存...悲剧了...