分类： ACM题解

https://hihocoder.com/problemset/problem/1457

要求求出来n个串中所有子串的十进制和。

考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；

多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！

由此只需求拓扑序的过程中把有效子串个数求出来就行了。

wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。

继续阅读“[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7”

http://newoj.acmclub.cn/problems/2054

题目给了一个方块板子，每次要么给同一列所有数字加上同一个数，要么给同一行加上全一个数，然后现在给出经过若干次这种操作之后的一个局面但是把其中一个点换成了-1，要求出来这个点的值应该是多少。

一开始没什么思路，后来写了写表达式似乎发现了可以直接解出来。设ri是第i行加的总数字，ci是第i列加的总数字，row是现在的-1所在的一行的和，col是-1所在的一列的和，若-1坐标为x，y，则可以设要求的数字为t=rx+cy，这时候可以列出来两个方程：

① row+col+2t+21==nt+Σri+Σci

② n*(Σri+Σci)==t+1+Σboard[i][j]

其中第一个方程是要求的那一点的行和列的和的两种表达式，第二个方程式整个board上的所有的点的和的两种表达形式。如果把(Σri+Σci)看作一个整体消掉，可以直接求出来t的表达式t=(n*(row+col)+2*n-Σboard[i][j]-1)/(n-1)^2

继续阅读“[数学][思维] 2018camp day1 Board”

题目链接：http://newoj.acmclub.cn/problems/2053

只要能想到用最小费用最大流去做，建图还是相对好想的：左边n个点表示n根蜡烛，右边n*m个点（或者m个点但是每个点有n条边连汇点，二者是等价的），然后源点连左边n个点之间cost为0容量为1，表示每个蜡烛最多被用一次，然后从左边到右边i到ai所有的n个分点连容量为1  cost为2*k-1的边，最后右边每个点跟汇点连容量为1  cost为0的边，最后跑最小费用最大流即可。

平方费用处理的话也不难毕竟看过lrj书上的处理平方费用的方法。。。这种平方费用的话可以拆点也可以拆边，但是思路都是新弄出来的边cost都是当流量从i到i+1的时候的增量，也就是i^2-(i-1)^2，因为这个差值是随着i增大而增大的，所以最大流增加的时候一定是从小到大选择这些边的，而这些边的cost从小到大依次选择就可以累加出来x^2，也就是与原来的要求等效了。
继续阅读“[最小费用流][平方费用][拆点/边建图] 2018camp Birthday”

http://hihocoder.com/problemset/problem/1449

需要在O(n)时间内求出所有长度为k的字串中出现次数最多的字串的出现次数。这里的话首先肯定是要求出来endpos的大小了，球的方法是利用fa树上的不同的st之间的包含关系和子树之间的交集为空的性质。这样的话要想求出来某个点的endpos大小只需要知道它的子节点的endpos大小就行了，另外还有一种需要特判的情况就是当st包含S的前缀的时候需要再额外+1，因为这个前缀是后面的节点没有包含到的。

推的过程的话，首先求出来拓扑序，然后从后往前刷fa节点的cnt即可。但是如果就这样的话，要用朴素的算法求出来每个substring的长度还是需要n²的复杂度，仍然会卡住。然后这里有一个性质那就是长度短的substring中的最大值一定不会比长度长的小，然后我们只需要更新每个节点对应的maxlen的最大值就可以了，然后从后往前更新最大值。为什么这么做是对的？首先每个st里最大值那个点肯定是对的，然后每两个更新点之间的那一段一定是被某个右端点包含在内的一个st里的连续的一段，所以这些点其实和那个右端点的大小其实是一样的，刷过去肯定是对的。

#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;
typedef long long LL;
const int maxn=1000005;
const int mod=1e9+7;
const int CHAR=26;

struct sam_node
{
    sam_node * fa,*nxt[CHAR];
    int len;
    bool flag;
    //LL cnt;
    void clear()
    {
        fa=0;
        flag=0;
        memset(nxt,0,sizeof(nxt));
        //cnt=0;
    }
    int cnt()
    {
        return len-fa->len;
    }
} pool[maxn<<1];

sam_node *root,*tail;

sam_node* newnode(int len)
{
    sam_node* cur=tail++;
    cur->clear();
    cur->len=len;
    return cur;
}

void sam_init()
{
    tail=pool;
    root=newnode(0);
}

sam_node* extend(sam_node* last,int x)
{
    sam_node *p=last,*np=newnode(p->len+1);
    while(p&&!p->nxt[x])
        p->nxt[x]=np,p=p->fa;
    if(!p)
        np->fa=root;
    else
    {
        sam_node* q=p->nxt[x];
        if(q->len==p->len+1)
            np->fa=q;
        else
        {
            sam_node* nq=newnode(p->len+1);
            memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
            nq->fa=q->fa;
            q->fa=np->fa=nq;
            while(p&&p->nxt[x]==q)
                p->nxt[x]=nq,p=p->fa;
        }
    }
    np->flag=1;
    return np;
}

char ori[maxn];
sam_node *End[maxn];

LL cnt[maxn<<1];
int deg[maxn<<1];
int topsort[maxn<<1],t;
LL ans[maxn];
int Len;
void solve()
{
    sam_node* cur;
    int len=tail-pool;
    queue<int> Q;
    for (int i=1; i<len; i++)
    {
        cur=pool+i;
        deg[cur->fa-pool]++;
    }
    for (int i=1; i<len; i++)
    {
        if(!deg[i])
            Q.push(i);
    }
    t=len-1;
    int dif;
    while(!Q.empty())//topsort
    {
        cur=pool+Q.front();
        Q.pop();
        topsort[t--]=cur-pool;
        dif=cur->fa-pool;
        deg[dif]--;
        if(!deg[dif]&&dif)
            Q.push(dif);
    }
    for (int i=len-1; i; i--)
    {
        int x=topsort[i];
        cur=pool+x;
        if(cur->flag)
            cnt[x]++;
        if(cur->fa)
            cnt[cur->fa-pool]+=cnt[x];
    }
    for (int i=1; i<len; i++)
    {
        cur=pool+i;
        ans[cur->len]=max(ans[cur->len],cnt[i]);
    }
    for (int i=Len-1; i; i--)
    {
        ans[i]=max(ans[i],ans[i+1]);
    }
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //gets(ori);
    scanf("%s",ori);
    Len=strlen(ori);
    sam_init();
    End[0]=root;
    for (int i=1; i<=Len; i++)
    {
        End[i]=extend(End[i-1],ori[i-1]-'a');
    }
    solve();
    for (int i=1; i<=Len; i++)
        printf("%lld\n",ans[i]);
    return 0;
}
/*

*/