Posted on | In

序列自动机其实就是一个数组，记录了每个位置后第一次出现字符c是哪个位置，用于解决一些子序列的问题，它共有n+1个状态，即位置0-n，每个状态都是子序列的接受状态。这个数组在On内完成构建

CF1303E：给字符串s、t问能不能从s中抽取两个不重复的子序列拼接成t。由于长度最大400，考虑枚举两个子序列的分界点，然后两个指针指向两个序列已满足的位置。最初考虑的算法是，直接看这两个指针之后的字符哪个能被较近的字符满足，就先让那个指针增1，这种算法整体是n^2的但有问题就是如果两个指针后需求的字符相同，就没法判断了，所以最后我们还是要用dp。

dp的话依然先枚举分界位置，然后设置dp[i][j]表示两个子序列分别匹配了i个和j个字符时，已使用的s的最短长度，注意对于每个分界位置i，dp范围是i*(|t|-i)的小矩形，最终整体复杂度是n^3/6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

const int maxn=401;
int T,n,m;
char s[maxn],t[maxn];
int to[maxn][26],lst[26];
inline void init(){
    for(int i=0;i<26;i++)
        lst[i]=to[n][i]=n+1;
    for(int i=n-1;i>=0;i--){
        lst[s[i+1]-'a']=i+1;
        for(int j=0;j<26;j++){
            to[i][j]=lst[j];
        }
    }
}

int dp[maxn][maxn]; //dp[i][j]表示两段分别匹配长度i和j时最低消耗的原字符串长
int main(){
    cin>>T;
    while(T--){
        cin>>(s+1)>>(t+1);
        n=strlen(s+1),m=strlen(t+1);
        init();
        bool f=false;
        for(int l=1;l<=m;l++){
            //l是第一段子序列的长度
            for(int i=0;i<=l;i++)
                for(int j=0;j<=m-l;j++)
                    dp[i][j]=n+1;
            dp[0][0]=0;
            for(int cl=1;cl<=m;cl++){   //cl是当前枚举的解决的总长度
                int i=max(0,cl-m+l);
                for(;i<=min(cl,l);i++){
                    if(i>0&&dp[i-1][cl-i]<n)
                        dp[i][cl-i]=min(dp[i][cl-i],to[dp[i-1][cl-i]][t[i]-'a']);
                    if(cl-i>0&&dp[i][cl-i-1]<n)
                        dp[i][cl-i]=min(dp[i][cl-i],to[dp[i][cl-i-1]][t[l+cl-i]-'a']);
                }
            }
            if(dp[l][m-l]<=n){
                f=true;
                break;
            }
        }
        cout<<(f?"YES":"NO")<<endl;
    }
}

/*
aacab
cacab
*/

Posted on | In

https://ac.nowcoder.com/acm/contest/4862/E

给n（<=20）头牛，每头牛有自己的身高、重量、承重，要让它们叠罗汉并高度至少是h，并要求剩余的载重量最大（说明最稳），求这个最大剩余载重量。

这题初看直接暴搜剪枝，，仔细一想才发现复杂度不对，是20！的。然后就没辙了，直到看了这篇博客，果然还是有藏着很隐蔽的关系约束的hh，核心思路是想到对于每种方案就是求si-sum{wi+1..wn}的最小值。然后对于所有方案再找最大。

代码就直接按二进制遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

struct d{
    int h,w,s;
    friend bool operator<(d x,d y){
        return x.s+x.w>y.s+y.w;
    }
}ds[21];
int n,h;

int chs[21],p;
int solve(int x){
    int i=1;p=0;
    int xh=0;
    while(x){
        if(x&1){
            chs[++p]=i;
            xh+=ds[i].h;
        }
        i++;x>>=1;
    }
    if(xh<h)
        return -1;
    int xs=ds[chs[p]].s;
    int xw=ds[chs[p]].w;
    for(int i=p-1;i;i--){
        xs=min(xs,ds[chs[i]].s-xw);
        xw+=ds[chs[i]].w;
    }
    return (xs>=0?xs:-1);
}

int main(){
    cin>>n>>h;
    for(int i=1;i<=n;i++)
        cin>>ds[i].h>>ds[i].w>>ds[i].s;
    sort(ds+1,ds+1+n);
    int ans=-1;
    for(int i=1;i<=(1<<n);i++){
        ans=max(ans,solve(i));
    }
    if(ans>=0)
        cout<<ans<<endl;
    else
        cout<<"Mark is too tall"<<endl;
}

Posted on | In

单哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef unsigned long long ull;
const int N = 100000 + 5;
const ull base = 163;
char s[N];
ull hash[N];
 
void init(){//处理hash值
    p[0] = 1;
    hash[0] = 0;
    int n = strlen(s + 1);
   for(int i = 1; i <=100000; i ++)p[i] =p[i-1] * base;
   for(int i = 1; i <= n; i ++)hash[i] = hash[i - 1] * base + (s[i] - 'a');
}
 
ull get(int l, int r, ull g[]){//取出g里l - r里面的字符串的hash值
    return g[r] - g[l - 1] * p[r - l + 1];
}

和自然溢出法不同的是，这种方法需要取模，并且是两套base mod。每次做哈希操作时，需要两套哈希值都一致，这就大大降低了冲突概率。但是据说常数比较大，并且写起来麻烦一些。

CF1320D

对于一个01串（2e5），给出两种操作：110<->011，可以执行任意多次，q（2e5）个提问，问这个串中某两个子串能否通过这两种操作互相转化。

分析可知，这种操作实际上就是把0左移或右移2位，也就是偶数次，那么如果这两个串中0出现的奇偶序列相同（比如第一个0都是奇数位上，第二个0都是偶数位上）那么就一定能互相转化成功，如果奇偶不同例如某两个0相邻，那是无法彼此转化的。所以问题就变成了，这两个子串中0出现的奇偶序列是否相同，这里是按照奇偶位置分别取1或2，不明白为啥0或1就会wa，，关于hash还有好多不懂的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

const int base1=131;
const int base2=13331;
const int mod1=998244353;
const int mod2=1e9+7;
const int maxn=2e5+2;
int pos[maxn],p;
int hsh1[maxn][2],hsh2[maxn][2];
int pow1[maxn],pow2[maxn];
void init_hsh(){
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=p;i++){
        hsh1[i][0]=(1ll*hsh1[i-1][0]*base1+pos[i]%2+1)%mod1;
        hsh1[i][1]=(1ll*hsh1[i-1][1]*base1+!(pos[i]%2)+1)%mod1;
        pow1[i]=1ll*base1*pow1[i-1]%mod1;
        hsh2[i][0]=(1ll*hsh2[i-1][0]*base2+pos[i]%2+1)%mod2;
        hsh2[i][1]=(1ll*hsh2[i-1][1]*base2+!(pos[i]%2)+1)%mod2;
        pow2[i]=1ll*base2*pow2[i-1]%mod2;
    }
}

typedef pair<int,int> pr;
pr gethsh(int l,int r,int st){
    if(st%2){
        return pr((hsh1[r][0]-1ll*pow1[r-l+1]*hsh1[l-1][0]%mod1+mod1)%mod1,(hsh2[r][0]-1ll*hsh2[l-1][0]*pow2[r-l+1]%mod2+mod2)%mod2);
    }else{
        return pr((hsh1[r][1]-1ll*pow1[r-l+1]*hsh1[l-1][1]%mod1+mod1)%mod1,(hsh2[r][1]-1ll*hsh2[l-1][1]*pow2[r-l+1]%mod2+mod2)%mod2);
    }
}
int n;
char s[maxn];
int main(){
    cin>>n;
    cin>>(s+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='0')
            pos[++p]=i;
    init_hsh();
    int q;
    cin>>q;
    int x,y,l;
    while(q--){
        cin>>x>>y>>l;
        int xl=lower_bound(pos,pos+p+1,x)-pos;
        int xr=upper_bound(pos,pos+p+1,x+l-1)-pos-1;
        int yl=lower_bound(pos,pos+p+1,y)-pos;
        int yr=upper_bound(pos,pos+p+1,y+l-1)-pos-1;
        pr px=gethsh(xl,xr,x);
        pr py=gethsh(yl,yr,y);
        cout<<(px==py?"Yes":"No")<<endl;
    }
    return 0;
}
/*
10
0100001001
1
2 9 2
*/

Posted on | In

再整理一遍板子

后缀数组

例题cf432D：问对字符串s，对于所有的前缀，当它等于同长度后缀时，这个子串一共在s中出现多少次。

后缀数组求lcp是logn，显然直接二分即可。复杂度nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,sa[N],rnk[N],height[N];
char s[N];
int st[N][20];
//sa数组表示字典序为i的后缀是谁，rnk数组表示某个后缀的排名(1~n)
void buildSA(int m=128){
    int cnt[N],rnk1[N],rnk2[N],tmpSA[N];    //cnt[i]用来记录rnk小于等于i的子串已经有多少个了，这样可以直接用cnt[rnk[i]]更新sa
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;++i)
        cnt[(int)s[i]]++;
    for(int i=1;i<=m;i++)
        cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++)
        rnk[i]=cnt[(int)s[i]];

    for(int l=1;l<n;l<<=1){
        for(int i=1;i<=n;++i){
            rnk1[i]=rnk[i];
            rnk2[i]=(i+l<=n?rnk[i+l]:0); //如有缺失，名次按0算，即较短的占优势，它和较长的比较时缺失部分的优先级按最高算
        }
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
            cnt[rnk2[i]]++;
        for(int i=1;i<=n;++i)    //小于等于当前rnk的共有几个后缀
            cnt[i]+=cnt[i-1];
        for(int i=n;i;--i)         //tmpSA这里按rnk2名次记录的后缀
            tmpSA[cnt[rnk2[i]]--]=i;    //--是为了区分rnk相同的串，后访问的排序靠前一些
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
            cnt[rnk1[i]]++;
        for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
        for(int i=n;i;--i)
            sa[cnt[rnk1[tmpSA[i]]]--]=tmpSA[i];    //是按照tmpSA的逆序计算，也就是rnk2较大的对应的cnt值会大一些，排在rnk1相同而rnk2较小的后面
        //cnt代表每个桶的大小
        bool uniq=true;     //如果构建完rnk数组还是true，说明所有后缀的大小已经区分出来了，没有排名相同的后缀了，可以退出
        rnk[sa[1]]=1;       //构建新的rank数组
        for(int i=2;i<=n;++i){
            rnk[sa[i]]=rnk[sa[i-1]];
            if(rnk1[sa[i]]==rnk1[sa[i-1]]&&rnk2[sa[i]]==rnk2[sa[i-1]])
                uniq=false;     //这里不能break，因为还要继续把当前rank数组算完
            else
                rnk[sa[i]]++;
        }
        if(uniq)
            break;
    }
}
//height[i]表示位于sa[i-1]和sa[i]的两个后缀的最长前缀
//有性质height[rnk[i]]>=height[rnk[i-1]]-1，即字符串向后推一位，height值最多减小1
void getHeight() {
    for(int i=1,k=0;i<=n;++i){
        if(k) --k;        //新的长度不会比k-1小，是结论
        int j=sa[rnk[i]-1]; //j是排序刚好比i小1的后缀
        while(s[i+k]==s[j+k])
            k++;
        height[rnk[i]]=k;
    }
}

//满足lcp(l,r)=min{height[i+1],...height[r]}，故是RMQ问题
//st[i][j]表示[i,i+(1<<j)-1]的最小height，[i,i+(1<<j)]的lcp，这一点注意一下
void initST(){    //用ST表进行RMQ
    for(int i=1;i<n;i++)
        st[i][0]=height[i+1];
    for(int l=1;(1<<l)<=n-1;l++){
        for(int i=1;i+(1<<l)-1<=n;i++)
            st[i][l]=min(st[i][l-1],st[i+(1<<(l-1))][l-1]);
    }
}

//lcp：最长公共前缀，此处指sa[l]和sa[r]的最长公共前缀
int lcp(int l,int r){
    if(l==r)
        return n-sa[l]+1;
    if(l>r)
        swap(l,r);
    int k=0;
    while((1<<(k+1))+1<=r-l+1) ++k;
    return min(st[l][k],st[r-(1<<k)][k]);
}
vector<pair<int,int>> ans;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    buildSA();
    getHeight();
    initST();
    for(int len=1;len<=n;len++){
        int a=rnk[1],b=rnk[n-len+1];
        if(lcp(a,b)<len)
            continue;
        if(a>b) swap(a,b);
        int res=b-a+1;
        int l=1,r=a;
        while(l<=r){
            int mid=(l+r)/2;
            if(lcp(mid,a)>=len)
                r=mid-1;
            else
                l=mid+1;
        }
        res+=max(a-l,0);
        l=b,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(lcp(mid,b)>=len)
                l=mid+1;
            else
                r=mid-1;
        }
        res+=max(r-b,0);
        ans.push_back(make_pair(len,res));
        //printf("%d %d\n",len,res);
    }
    cout<<ans.size()<<endl;
    for(auto p:ans)
        cout<<p.first<<' '<<p.second<<endl;
    return 0;
}

Posted on | In ,

cf704D

给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。

上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点缺少的从源点补充。合法要求：源点s发出的必须能跑满，否则原有的平衡条件就打破了，无可行流。

对于原本就有源的情况如下图，先确立一个可行流，取t-s边的流量，再把t-s边去掉，跑最大流加上即可。

20180406145614611

先明确建图方案。对某一行列的属性做文章的时候考虑裂点，我们用所有的xy坐标作点，原有的（x，y）点变成x->y边，表示由x选中它的同时会对y造成影响。这样形成了一个二分图，我们令某条边选便宜颜色的时候取流1，否则取0，这样原优化问题就变成了最大流问题，流量越大选取的便宜颜色越多。我们同时建立源点s汇点t，从s向每个x连边，容量表示每行能允许的某种颜色的数量（如果无限制则是该行上的点数，有限制则出现上下界），y同理连向t。这里我们发现出现了上下界网络流问题。套用上面算法解决即可。

在dinic的bfs中，如果把两个&&改成||会超时，按理说是完全等价的写法……这里卡了半天找原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;
#define ll long long
#define inf 0x3f3f3f3f
map<int,int> name[2];   //x,y的离散化映射
int cntx,cnty;  //用每个坐标值出现的顺序代表这个点

struct edge{
    int to,next;
    ll cap;     //cap是剩余可用流量
}es[maxn<<3];//最多可能有两倍的附加边，6*maxn
int st,ed,s,t,ss,tt;
int cnt=1,head[maxn<<1];
int cur[maxn<<1];
int forbid[maxn<<1];
inline void add(int u,int v,ll d){
    es[++cnt]=(edge){ v,head[u],d};
    head[u]=cnt;
}
inline void add1(int u,int v,ll d){
    add(u,v,d);
    add(v,u,0);
}
inline void add2(int u,int v,ll least,ll most){
    add1(u,v,most-least);
    add1(ss,v,least);
    add1(u,tt,least);
}

int tot[2][maxn],limit[2][maxn],p[maxn][2],num[maxn<<1];    //tot record the degree of a point,limit the min difference,num record the addr of origin edge of a point
int n,m,r,b;
int flag=1;
int total=0;    //点的总数
int level[maxn<<1]; //bfs中确认的层数
bool bfs(){
    memset(level,0,sizeof(level));
    queue<int> q;
    q.push(st);level[st]=1;	//这里必须写！！否则会无限回退到第一个点
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(!level[v]&&es[i].cap>0&&forbid[v]==0){
                level[v]=level[u]+1;
                q.push(v);
            }
        }
    }
    return level[ed];
}

ll dfs(int x,ll f){
    if(x==ed||f==0)
        return f;
    ll res=0,tmp;
    for(int &i=cur[x];i;i=es[i].next){
        int v=es[i].to;
        if(level[v]==level[x]+1&&es[i].cap>0&&res<f){
            tmp=dfs(v,min(f-res,es[i].cap));
            es[i].cap-=tmp;es[i^1].cap+=tmp;
            res+=tmp;
        }
        if(res>=f)
            break;
    }
    if(!res)
        level[x]=0; //x点已经没用了
    return res;
}

int main(){
    cin>>n>>m>>r>>b;
    if(r>b){
        swap(r,b);flag=0;
    }
    for(int x,y,i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        if(!name[0][x])
            name[0][x]=++cntx;
        if(!name[1][y])
            name[1][y]=++cnty;
        p[i][0]=name[0][x];
        p[i][1]=name[1][y];
        tot[0][p[i][0]]++;
        tot[1][p[i][1]]++;
    }
    memset(limit,inf,sizeof(limit));
    for(int i=1,t,l,d;i<=m;i++){
        scanf("%d%d%d",&t,&l,&d);
        if(t==1){
            int x=name[0][l];
            limit[0][x]=min(limit[0][x],d);   //the smaller the d,the more restrictive it is
        }else{
            int y=name[1][l];
            limit[1][y]=min(limit[1][y],d);
        }
    }
    total=cntx+cnty;
    s=++total;t=++total;
    ss=++total;tt=++total;
    for(int x,y,i=1;i<=n;i++){  //添加边
        x=p[i][0],y=p[i][1];
        add1(x,y+cntx,1);
        num[i]=cnt;
    }
    for(int i=1;i<=cntx;i++){
        if(limit[0][i]==inf){
            add1(s,i,tot[0][i]);
        }else{
            ll least=(tot[0][i]-limit[0][i]+1)/2;
            ll most=(tot[0][i]+limit[0][i])/2;
            if(least>most) return puts("-1");   //这种情况说明总数奇数且要求两者差为0，要求无法满足
            add2(s,i,least,most);
        }
    }
    for(int i=1;i<=cnty;i++){
        if(limit[1][i]==inf){
            add1(i+cntx,t,tot[1][i]);
        }else{
            ll least=(tot[1][i]-limit[1][i]+1)/2;
            ll most=(tot[1][i]+limit[1][i])/2;
            if(least>most) return puts("-1");
            add2(i+cntx,t,least,most);
        }
    }
    add1(t,s,inf);
    st=ss,ed=tt;
    ll tmp=0;

    while(bfs()){
        for(int i=1;i<=total;++i) cur[i]=head[i];
        dfs(st,inf);
    }
    tmp=es[cnt].cap;    //选取t->s的流量（反向边的cap），不能直接取ss->tt的最大流，因为有的没经过t->s边
    ll judge=0;
    for(int i=head[ss];i;i=es[i].next){
        judge+=es[i].cap;
    }
    if(judge>0){    //if extra edges aren't used up, then invalid
        puts("-1");
        return 0;
    }
    st=s,ed=t;
    es[cnt].cap=es[cnt^1].cap=0;    //这一步是把s到t的连边正反都取消
    forbid[ss]=forbid[tt]=1;
    while(bfs()){
        for(int i=1;i<=total;++i) cur[i]=head[i];
        tmp+=dfs(st,inf);
    }
    ll ans=(ll)r*(tmp)+(ll)b*(n-tmp);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        int o=0;
        if(es[num[i]^1].cap==0){
            //如果出边用了,就说明这个点选小的
            o=1;
        }
        if(!flag)
            o^=1;
        putchar(o?'r':'b');
    }
    cout<<endl;
    return 0;
}

/*
4 1
1 2
1 1
1 2
2 1
2 2
1 1 1
*/

Posted on | In ,

长链剖分可以把维护子树中只与深度有关的信息做到线性的时间复杂度。

例题cf1009f

给一棵树，定义每个点的dom值为，以该点为根的子树重中，节点数最多的那一层的层数，即那一层距离这个根节点有几条边，如果多层节点数相同，取最小的层数。例如单独叶节点的dom值是0，一条垂直的链的dom值也是0（每层数量都是1，取最前面的）

定义dp[i][j]为i树第j层的节点数，如果暴力遍历复杂度是n^2。我们用类似启发式合并的思想，对于长链（最深而非最重的链）处理后的结果直接拿给父节点用，然后再去依次解决轻节点，并把这些轻节点向父节点暴力合并。由于所有的轻链合并到深链上之后就“失效”了，之后再也用不到，所有整体时间复杂度只有O(n)。（太nb了这个算法……

由于剖分的性质，一条链上的节点在一个区间，子树的节点也都在一个区间，所以dp数组不必为难开n^2大小，我们考虑用指针实现，这样也实现了重儿子O(1)传递dp数组给父亲，实际上就是用了同一块内存，重儿子跑完了直接父亲就顺着用（看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+4;

struct edge{
    int to,next;
}es[maxn*2];
int head[maxn],cnt;
void add(int u,int v){
    es[++cnt]=(edge){ v,head[u]};
    head[u]=cnt;
}

int h[maxn],son[maxn];
void dfs1(int x,int fa){
    h[x]=1;
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(v==fa)
            continue;
        dfs1(v,x);
        h[x]=max(h[x],h[v]+1);
        if(h[v]>h[son[x]])
            son[x]=v;
    }
}

int *dp[maxn],g[maxn],dfn[maxn];    //dp[i][j]表示和根节点i相距j条边的子孙数量（树的第j层节点个数）
void dfs2(int x,int fa){
    //先搜重儿子，这样重儿子和父节点的dp数组地址差1，刚好可以公用
    dfn[x]=++dfn[0];
    dp[x]=g+dfn[x];
    if(son[x])
        dfs2(son[x],x);
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(v==fa||v==son[x])
            continue;
        dfs2(v,x);
    }
}

int ans[maxn];
void solve_dp(int x,int fa){
    if(son[x]>0){
        solve_dp(son[x],x);
        //这时son[x]的dp数组已经构建完成，地址就比x的大1，刚好深度也大1，直接就成为了x的dp数组
        ans[x]=ans[son[x]]+1;
    }
    dp[x][0]=1;
    if(dp[x][ans[x]]==dp[x][0]) //如果x只有一个子节点，且是一条垂直的链，那么它的ans可以再向前提
        ans[x]=0;
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(v==son[x]||fa==v)
            continue;
        solve_dp(v,x);
        int len=h[v];
        for(int j=0;j<len;j++){
            dp[x][j+1]+=dp[v][j];
            if(dp[x][j+1]>dp[x][ans[x]])
                ans[x]=j+1;
            if(dp[x][j+1]==dp[x][ans[x]]&&ans[x]>j+1)
                ans[x]=j+1;
        }
    }
}
int n;
int main(){
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        add(x,y);add(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    solve_dp(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

Posted on | In ,

这个算法真是研究了好久才明白……众多博客真的不是面向小白的

模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。

首先想到暴力做法，直接去挨个点算他们的子树的答案，统计子树中每种颜色的数量并维护当前主颜色的和。这种算法显然是$O(n^2)$的。同时我们注意到一个细节，每个点的访问计算中所用到的cnt数组，应该是一个公用的全局数组，因为节点和颜色值的上限都是1e5，我们没法建立一个cnt[maxn][maxcolor]的数组（如果能建就简单多了），所以每次在访问一个点后，需要清空该点的树的记录，因为后面马上要去访问它的兄弟节点。这时就需要再写一个dfs去清除记录，用dfs而不是memset去清除是因为可以精准限制访问次数。

那么优化点在哪里呢，我们发现，当你把所有的兄弟节点访问完后，接下来需要计算父亲的答案值，又需要把这些兄弟节点的贡献加起来，十分浪费时间。如果能把他们保存在一个大数组里就好了（但是空间受限不行），最多只能保存最后访问的那个兄弟，于是我们选择把重儿子放在最后，尽可能利用这一优势。

那么这样优化下来的复杂度是多少呢？oiwiki上有严格证明，是nlogn。大概是每个点的访问次数是它到根的轻边+1？而轻边最多logn条，因为轻树的size小于父树的1/2。

看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+1;

#define ll long long
vector<int> vec[maxn];
int col[maxn],cnt[maxn],vis[maxn],n,top=0;	//cnt是每种颜色的数量
ll sum[maxn],ans[maxn]; //sum[i]表示出现次数为i的颜色数量和,sum[top]是答案ans[u]

int son[maxn],siz[maxn];

void dfs1(int u,int fa){
    siz[u]=1;
    for(int i=0;i<vec[u].size();i++){
        if(fa!=vec[u][i]){
            dfs1(vec[u][i],u);
            siz[u]+=siz[vec[u][i]];
            if(siz[vec[u][i]]>siz[son[u]]){ //一开始默认siz[0]=0
                son[u]=vec[u][i];
            }
        }
    }
}

void cal(int u,int fa,int val){	//计算树u，sum[top]是答案
    sum[cnt[col[u]]]-=col[u];	
    cnt[col[u]]+=val;
    sum[cnt[col[u]]]+=col[u];

    if(cnt[col[u]]>top||sum[top]==0){
        top=cnt[col[u]];
    }
    for(int i=0;i<vec[u].size();i++){
        if(vec[u][i]==fa||vis[vec[u][i]])
            continue;
        cal(vec[u][i],u,val);
    }
}

void dfs(int u,int fa,bool keep){   //预处理得到u及其子树的答案
    for(int i=0;i<vec[u].size();i++){
        if(fa==vec[u][i]||vec[u][i]==son[u])
            continue;
        dfs(vec[u][i],u,0); //先处理轻儿子的树
    }
    if(son[u])
        dfs(son[u],u,1),vis[son[u]]=1;  //处理重儿子，保留痕迹
        
    cal(u,fa,1);	//这一步才真正是统计树u的答案，
    //它在向下计算的时候不会再对已vis标记的重儿子进行dfs，优化在这里了
    ans[u]=sum[top];
    if(son[u])
        vis[son[u]]=0;	//已经利用过了此次便利，清除标记
    if(!keep)
        cal(u,fa,-1);	//清除对数组的影响
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",col+i);
    }
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs1(1,0);
    dfs(1,0,1); //填1是为了省下最后那次遍历
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
    puts("");
    return 0;
}

再来一道cf375d

给出一棵树，m个询问（v，k）要求回答树v中有多少种颜色出现超过k次。

我们在cal函数中维护树u中各个出现次数的颜色数量，然后将询问预先存在数组中，询问同一棵树的放在一起，在dfs函数中执行完cal后去依次回答这些提问。

只贴上不同的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void cal(int u,int fa,int val){
    if(val==-1){
        res[cnt[col[u]]]--;
        cnt[col[u]]--;
    }else{
        cnt[col[u]]++;
        res[cnt[col[u]]]++;
    }

    for(int i=0;i<vec[u].size();i++){
        if(fa==vec[u][i]||vis[vec[u][i]])
            continue;
        cal(vec[u][i],u,val);
    }
}

void dfs(int u,int fa,bool keep){
    for(int i=0;i<vec[u].size();i++){
        if(fa==vec[u][i]||vec[u][i]==son[u])
            continue;
        dfs(vec[u][i],u,0);
    }
    if(son[u])
        dfs(son[u],u,1),vis[son[u]]=1;
    cal(u,fa,1);
    for(int i=0;i<q[u].size();i++){
        int id=q[u][i].first;
        int k=q[u][i].second;
        ans[id]=res[k];
    }
    if(son[u])
        vis[son[u]]=0;
    if(!keep)
        cal(u,fa,-1);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>col[i];
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    for(int i=1,v,k;i<=m;i++){
        cin>>v>>k;
        q[v].push_back(P(i,k));
    }
    dfs1(1,0);
    dfs(1,0,1);
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<endl;
    return 0;
}

Posted on | In ,

cf1131D

给出一个n*m关系表，有<>=三种关系，要求为这n+m个对象分配一个值，使得满足约束关系且最大值最小。

用差分约束，＞转化为>=x+1。=转化为>=且<=。如果y要比x至少大1，就建立边x指向y。对于这样一张图，满足所有要求其实就意味着能走的边都走（满足关系），不能满足的点就松弛（变大），类似求最长路。

bfs版spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;

const int maxn=1001;
typedef pair<int,int> e;
vector<e> es[2*maxn];  //因为有01两种边权，所以要记录权值
int n,m;
bool vis[maxn*2];
int d[2*maxn];
int cnt[maxn*2];    //由于每条路最多经过v个顶点，超过就有正圈
bool spfa(int s){
    queue<int> q;
    d[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;   //有可能再次入队
        for(int i=0;i<es[u].size();i++){
            int v=es[u][i].first;
            int c=es[u][i].second;
            if(d[u]+c>d[v]){
                d[v]=d[u]+c;
                cnt[v]++;   //松弛成功就计算次数,这里跟某个博客有出入，那个人只把入队的加次数……
                if(cnt[v]>m+n)
                    return false;
                if(!vis[v]){    //如果这个点已在队里就不用再重复添加，反正上一步已经更新过了，如果后来更新的更大就直接用了
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
char s[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>(s+1);
        memset(d,-1,sizeof(d));
        for(int j=1;j<=m;j++){
            if(s[j]=='<'){
                es[i].push_back(e(j+n,1));
            }else if(s[j]=='>'){
                es[j+n].push_back(e(i,1));
            }else{
                es[i].push_back(e(j+n,0));
                es[j+n].push_back(e(i,0));
            }
        }
    }
    for(int i=1;i<=n+m;i++)
        es[0].push_back(e(i,1));
    bool ok=spfa(0);
    if(ok){
        for(int i=1;i<=n+m;i++)
            if(d[i]==-1){
                ok=0;break;
            }
    }
    if(ok){
        puts("Yes");
        for(int i=1;i<=n;i++)
            printf("%d ",d[i]);
        puts("");
        for(int i=n+1;i<=m+n;i++)
            printf("%d ",d[i]);
        puts("");
    }else{
        puts("No");
    }
    return 0;
}

Posted on | In ,

寻找连通图的割点和桥用的也是tarjan算法，我们计算每个点不经过父亲能到达点的最小dfs序，如果是大于等于父亲的，则说明去掉父节点，该点即无法同上面连通，所以父节点是割点。桥类似，我们对于每个点标记它到父亲的那条边是否是桥。

cf1277E：

给出一个图求对于两点ab，有多少对xy使得从x到y的每一条路径都必经ab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+1;
const int maxm=5e5+1;
#define ll long long
#define fo(i,n) for(int i=0;i<=n;i++)
struct edge{
    int to,next;
}es[maxm*2];
int head[maxn];
int cnt;
void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
int dfn[maxn],low[maxn];    //low是表示不通过父节点能回到的最小节点
int ind;
int cut[maxn];

void tarjan(int x,int fa){
    dfn[x]=low[x]=++ind;
    int child=0;
    for(int i=head[x];i;i=es[i].next){
        int v=es[i].to;
        if(!dfn[v]){
            child++;
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(!cut[x]){
                if(fa!=x&&low[v]>=dfn[x]){  //子节点不能到达比父亲小的节点,
                    //相等表示另有一条路能回到父节点，如果是桥，要去掉等号
                    cut[x]=1;
                }
            }
        }else if(v!=fa){    //遇到已经到达过的且不是父亲，说明可以绕道回去
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(fa==x&&child>1&&!cut[x]){    //根节点判断方法不一样
        cut[x]=1;
    }
}
int flag[maxn];
bool vis[maxn];
void dfs(int x,int f,int stop){
    flag[x]+=f;vis[x]=1;
    for(int i=head[x],v;i;i=es[i].next){
        v=es[i].to;
        if(!vis[v]&&v!=stop)
            dfs(v,f,stop);
    }
}

int t,n,m;
int main(){
    cin>>t;
    while(t--){
        int a,b;
        cin>>n>>m>>a>>b;
        for(int i=1;i<=n;i++){
            dfn[i]=0;
            low[i]=0;
            cut[i]=0;
            head[i]=0;
        }
        for(int i=0,x,y;i<m;i++){
            cin>>x>>y;
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                cnt=0;
                tarjan(i,i);
            }
        }
        ll res=0;
        if(cut[a]&&cut[b]){
            fo(i,n) flag[i]=0;
            fo(i,n) vis[i]=0;
            dfs(a,1,b);
            fo(i,n) vis[i]=0;
            dfs(b,2,a);
            int anum=0,bnum=0;
            for(int i=1;i<=n;i++){
                if(flag[i]==1)
                    anum++;
                if(flag[i]==2)
                    bnum++;
            }
            res=((ll)anum-1)*(bnum-1);
        }
        cout<<res<<endl;
    }
    return 0;
}

桥的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++dfs_clock;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (dfn[v] < dfn[u] && v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

Posted on | In ,

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图 的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。

实现算法：两次dfs，第一次 dfs 遍历将顶点后序(post order)记录下来vs（vector），这里需要注意的是，不管从哪个点dfs，由于是后序记录，故最终得到的记录是一样的，vs中的顶点（按下标）从前至后对应在DAG中为从尾到头。第二次dfs对于vs中的元素从尾到头进行，使用反向边，故每次dfs只能访问到同一个强连通分量。因而每次dfs时给所到顶点加上一个表示第几个scc的标号，即可完成对该图的分解。

例题：poj2186

每头羊有若干崇拜对象，并且崇拜关系可传递，求出被其他所有羊崇拜的羊的个数。

即求最后一个scc所含顶点个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

int n,m;
vector<int> g[10001];
vector<int> rg[10001];
bool used[10001];
vector<int> vs;
int cmp[10001];

void dfs(int v) {
	used[v]=true;
	for(int i=0; i<g[v].size(); i++)
		if(!used[g[v][i]])
			dfs(g[v][i]);
	vs.push_back(v);
}

void rdfs(int v,int k) {
	used[v]=true;
	cmp[v]=k;
	for(int i=0; i<rg[v].size(); i++)
		if(!used[rg[v][i]])
			rdfs(rg[v][i],k);
}

int scc() {		//strongly connected component
	memset(used,0,sizeof(used));
	vs.clear();
	for(int i=0; i<n; i++)
		if(!used[i])
			dfs(i);
	int k=0;
	memset(used,0,sizeof(used));
	for(int i=vs.size()-1; i>=0; i--)
		if(!used[vs[i]])
			rdfs(vs[i],k++);        //最开始把vs[i]错写成i，把属于不同块的顶点打上了相同标号
	return k;
}

int main() {
	while(cin>>n>>m) {
		int to,from;
		for(int i=0; i<m; i++) {
			cin>>from>>to;
			g[from-1].push_back(to-1);
			rg[to-1].push_back(from-1);
		}
		int num=scc();
		int u,res=0;
		for(int i=0; i<n; i++) {
			if(cmp[i]==num-1) {
				res++;
				u=i;
			}
		}
		memset(used,0,sizeof(used));
		rdfs(u,0);
		for(int i=0; i<n; i++) {
			if(!used[i]) {
				res=0;
				break;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}