Day nn 指第 nn 个讲课日，模拟赛过屎，不放了。

Day1

单调队列优化 DP

一般形如 dpi=max⁡j∈[li,ri](f(j))+g(j)dp_i=\max_{j\in[l_i,r_i]}(f(j))+g(j) 的形式可以进行单调队列优化，其中 f(i)f(i) 是一个关于 jj 的函数，[li,ri][l_i,r_i] 是滑动窗口。

宝物筛选

多重背包优化。O(nWlog⁡m)O(nW\log m) 的二进制拆分优化就不讲了。
考虑朴素的 O(nWm)O(nWm) 转移：

dpj=max⁡k=0mi(dpj−k×wi+k×vi)dp_{j}=\max_{k=0}^{m_i}(dp_{j-k\times w_i}+k\times v_i)

尝试改写成适合单调队列优化的形式，按余数分组：
设当前 r=j mod wir=j\bmod w_i，t=⌊j/wi⌋t=\lfloor j/w_i\rfloor，状态转移方程改写为：

dpj=max⁡k=0min⁡(mi,t)(dpr+(t−k)⋅wi+k⋅vi)dp_j=\max_{k=0}^{\min(m_i,t)}(dp_{r+(t-k)\cdot w_i}+k\cdot v_i)

令 t′=t−kt'=t-k，则 k=t−t′k=t-t'：

dpj=max⁡(dpr+t′⋅wi+(t−t′)⋅vi)=max⁡(dpr+t′⋅wi+t′⋅vi)+t⋅vi\begin{aligned} dp_j&=\max(dp_{r+t'\cdot w_i}+(t-t')\cdot v_i)\\ &=\max(dp_{r+t'\cdot w_i}+t'\cdot v_i)+t\cdot v_i \end{aligned}

t′∈[max⁡(0,t−mi),t]t'\in[\max(0,t-m_i),t]，构成一个滑动窗口。
时间复杂度 O(nW)O(nW)。

code 
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=4e4+10;
struct Queue{
    int val,t;
    Queue(){}
    Queue(int val,int t):val(val),t(t){}
}q[N];
int n,W,v,w,m,dp[N],l,r,tag,ans;
int main(){
    read(n,W);
    memset(dp,0xcf,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        read(v,w,m);
        if(w==0){
            tag+=v*m;
            continue;
        }
        for(int d=0;d<w;d++){
            l=1,r=0;
            for(int t=0;d+t*w<=W;t++){
                int j=t*w+d,val=dp[j]-t*v;
                while(l<=r&&q[r].val<=val) --r;
                q[++r]=Queue(val,t);
                while(l<=r&&q[l].t<t-m) ++l;
                dp[j]=max(q[l].val+t*v,dp[j]);
            }
        }
    }
    for(int i=0;i<=W;i++) ans=max(ans,dp[i]+tag);
    printf("%d\n",ans);
    return 0;
}

[NOI2005] 瑰丽华尔兹

单调队列优化 DP。
容易想到 O(nmT)O(nmT) 的方程：设 dpt,i,jdp_{t,i,j} 表示在 (i,j)(i,j) 位置经过 tt 时间的答案，容易写出转移：

dpt,i,j=max⁡(dpt−1,i,j,dpt−1,i′,j′+1)dp_{t,i,j}=\max(dp_{t-1,i,j},dp_{t-1,i',j'}+1)

考虑优化成 O(nmk)O(nmk)，则我们首先将状态优化为 dpk,i,jdp_{k,i,j} 表示第 kk 个区间，在 (i,j)(i,j) 位置的答案。转移变为

dpk,i,j=max⁡(dpk−1,i′,j′+dis)dp_{k,i,j}=\max(dp_{k-1,i',j'}+dis)

具体地，假设当前在向 ii 的正方向滑行，我们可以写出：

dpk,i,j=max⁡pos=i−lenki(dpk−1,pos,j−pos)+idp_{k,i,j}=\max_{pos=i-len_k}^i(dp_{k-1,pos,j}-pos)+i

其余三个方向同理，这就可以单调队列优化了。
可以滚动数组去掉 kk 这一维。

code 
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
#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
template<typename T>
inline T Abs(const T &x){return x<0?~x+1:x;}
template<typename T>
inline T Max(const T &a,const T &b){return a<b?b:a;}
constexpr int N=210,fx[]={0,-1,1,0,0},fy[]={0,0,0,-1,1};
struct Queue{
    int val,x,y;
    Queue(){}
    Queue(int val,int x,int y):val(val),x(x),y(y){}
}q[N];
inline int dis(const int &ax,const int &ay,const int &bx,const int &by){
    return Abs(ax-bx)+Abs(ay-by);
}
int n,m,sx,sy,k,dp[N][N],op,l,r,ans;
char s[N][N];
void dfs(int x,int y,int len){
    l=1,r=0;
    while(x>=1&&y>=1&&x<=n&&y<=m){
        if(s[x][y]=='x'){
            l=1,r=0;
            x+=fx[op],y+=fy[op];
            continue;
        }
        while(l<=r&&dp[x][y]>q[r].val+dis(x,y,q[r].x,q[r].y)) --r;
        q[++r]=Queue(dp[x][y],x,y);
        while(l<=r&&(Abs(x-q[l].x)>len||Abs(y-q[l].y)>len)) ++l;
        dp[x][y]=Max(dp[x][y],q[l].val+dis(x,y,q[l].x,q[l].y));
        ans=Max(ans,dp[x][y]);
        x+=fx[op],y+=fy[op];
    }
}
int main(){
    read(n,m,sx,sy,k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&s[i][j]);
    memset(dp,0xcf,sizeof(dp));
    dp[sx][sy]=0;
    for(int i=1,s,t;i<=k;i++){
        read(s,t,op);
        if(op==1) for(int j=1;j<=m;j++) dfs(n,j,t-s+1);
        else if(op==2) for(int j=1;j<=m;j++) dfs(1,j,t-s+1);
        else if(op==3) for(int j=1;j<=n;j++) dfs(j,m,t-s+1);
        else for(int j=1;j<=n;j++) dfs(j,1,t-s+1);
    }
    printf("%d\n",ans);
    return 0;
}

闲话：《海上钢琴师》真的非常好看！

[SCOI2010] 股票交易

设 dpi,jdp_{i,j} 表示 ii 天结束时手上有 jj 个股票时的最大收益。转移：

  • 什么也不做：

dpi,j=dpi−1,jdp_{i,j}=dp_{i-1,j}

  • 买入：

dpi,j=max⁡(dpi−W−1,j−k−k×APi)dp_{i,j}=\max(dp_{i-W-1,j-k}-k\times AP_i)

  • 卖出：

dpi,j=max⁡(dpi−W−1,j+k+k×BPi)dp_{i,j}=\max(dp_{i-W-1,j+k}+k\times BP_i)

第一个式子没有研究价值，我们看后两个。将式子转化，用 k′k' 分别代替 j−kj-k 和 j+kj+k：

dpi,j=max⁡(dpi−W−1,k′+k′×APi)−j×APij−k′≤ASidp_{i,j}=\max(dp_{i-W-1,k'}+k'\times AP_i)-j\times AP_i\quad j-k'\le AS_i

dpi,j=max⁡(dpi−W−1,k′+k′×BPi)−j×BPik′−j≤BSidp_{i,j}=\max(dp_{i-W-1,k'}+k'\times BP_i)-j\times BP_i\quad k'-j\le BS_i

显然可以单调队列。

code 
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=2010;
int t,maxp,w,l,r,ap[N],dp[N][N],bp[N],as[N],bs[N],ans; 
struct Queue{
    int val;
    ll k;
    Queue(){}
    Queue(int val,int k):val(val),k(k){}
}q[N];
int main(){
    read(t,maxp,w);
    memset(dp,0xcf,sizeof(dp));
    for(int i=1;i<=t;i++) read(ap[i],bp[i],as[i],bs[i]);
    for(int i=1;i<=t;i++)
        for(int j=0;j<=as[i];j++) dp[i][j]=-ap[i]*j;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=maxp;j++)
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        l=1,r=0;
        int pre=i-w-1;
        if(pre<=0) continue;
        for(int j=0;j<=maxp;j++){
            while(l<=r&&q[r].val<=dp[pre][j]+j*ap[i]) --r;
            q[++r]=Queue(dp[pre][j]+j*ap[i],j);
            while(l<=r&&j-q[l].k>as[i]) ++l;
            dp[i][j]=max(dp[i][j],q[l].val-j*ap[i]);
        }
        l=1,r=0;
        for(int j=maxp;j>=0;j--){
            while(l<=r&&q[r].val<=dp[pre][j]+j*bp[i]) --r;
            q[++r]=Queue(dp[pre][j]+j*bp[i],j);
            while(l<=r&&q[l].k-j>bs[i]) ++l;
            dp[i][j]=max(dp[i][j],q[l].val-j*bp[i]);
        }
    }
    for(int i=0;i<=maxp;i++) ans=max(ans,dp[t][i]);
    printf("%d\n",ans);
    return 0;
}

玉蟾宫

插一个单调栈典题。
我们考虑枚举行数，对于一行内，维护每一列向上延伸最多的 F 数量（类似直方图）。例如，对于样例

1
2
3
4
5
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

假设我们枚举到最后一行，那么应该向上延伸最多的 F 数量应当是：

1
2
3
4
5
6
      F F F
      F F F
      F F F
F F F F F F
F F F F F F
2 2 2 5 5 5

此时枚举列，同时对向上延伸最多 F 数量维护单调栈。
时间复杂度 O(nm)O(nm)。

code 
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
#include<iostream>
using namespace std;
constexpr int N=1010;
struct Stack{
    int h,len;
    Stack(){}
    Stack(int h,int len):h(h),len(len){}
}st[N];
int n,m,top,h[N][N],ans;
char c;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c;
            h[i][j]=(c=='F')?h[i-1][j]+1:0;
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int temp=0;
            while(top&&st[top].h>h[i][j]){
                temp+=st[top].len;
                ans=max(ans,st[top].h*temp);
                --top;
            }
            st[++top]=Stack(h[i][j],temp+1);
        }
        int temp=0;
        while(top){
            temp+=st[top].len;
            ans=max(ans,st[top].h*temp);
            --top;
        }
    }
    cout<<ans*3<<'\n';
    return 0;
}

并查集

[APIO2008] 免费道路

题意：一个边权为 00 或 11 的图，求边权和为 n−kn-k 的生成树。
首先 Kruskal 求最大生成树，求得必须要加入的 00 边。
再 Kruskal 一遍，先将 00 边加至 kk 条，然后一直加 11 边直到求出生成树。

code 
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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=2e4+10,M=1e5+10;
int n,m,k,fa[N],tot,cnt,ans[N];
struct edge{int u,v,w;}e[M];
bool l(const edge &x,const edge &y){return x.w<y.w;}
bool g(const edge &x,const edge &y){return x.w>y.w;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
    read(n,m,k);
    for(int i=1;i<=m;i++)
        read(e[i].u,e[i].v,e[i].w);
    sort(e+1,e+1+m,g);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        fa[u]=v;
        ++tot;
        if(e[i].w==0) ++cnt,e[i].w=-1;
        if(tot==n-1) break;
    }
    if(cnt>k){
        printf("no solution\n");
        return 0;
    }
    sort(e+1,e+1+m,l);
    for(int i=1;i<=n;i++) fa[i]=i;
    tot=0;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        if(e[i].w==-1){
            fa[u]=v;
            e[i].w=0;
            ans[++tot]=i;
        }
        else if(tot<k&&e[i].w==0){
            fa[u]=v;
            ans[++tot]=i;
        }
        else if(tot>=k&&e[i].w==1){
            fa[u]=v;
            ans[++tot]=i;
        }
        if(tot==n-1) break;
    }
    if(tot!=n-1){
        printf("no solution\n");
        return 0;
    }
    for(int i=1;i<=tot;i++){
        int j=ans[i];
        printf("%d %d %d\n",e[j].u,e[j].v,e[j].w);
    }
    return 0;
}

[AHOI2013] 连通图

线段树分治+可撤销并查集。
在时间轴上开线段树，每个节点维护 std::vector 表示当前区间需要加的边，使用可撤销并查集在回溯时撤销当前节点添加的边。

code 
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
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=2e5+10;
int n,m,fa[N],siz[N],k,last[M];
struct Edge{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
}edge[M];
vector<Edge> tree[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
void modify(int u,int l,int r,int x,int y,Edge t){
    if(x<=l&&y>=r){
        tree[u].push_back(t);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,t);
    if(y>mid) modify(rs,mid+1,r,x,y,t);
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
stack<Edge> st;
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    if(siz[x]>siz[y]) swap(x,y);
    fa[x]=y;
    siz[y]+=siz[x];
    st.push(Edge(x,y));
}
void get_ans(int u,int l,int r){
    int temp=st.size();
    for(Edge x:tree[u]) merge(x.u,x.v);
    if(l==r){
        if(siz[find(1)]==n) printf("Connected\n");
        else printf("Disconnected\n");
    }
    else{
        int mid=(l+r)>>1;
        get_ans(ls,l,mid);
        get_ans(rs,mid+1,r);
    }
    while((int)st.size()>temp){
        Edge x=st.top();
        int u=x.u,v=x.v;
        st.pop();
        siz[v]-=siz[u];
        fa[u]=u;
    }
}
int main(){
    read(n,m);
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++) read(edge[i].u,edge[i].v);
    read(k);
    for(int i=1,c,x;i<=k;i++){
        read(c);
        while(c--){
            read(x);
            if(last[x]+1<=i-1) modify(1,1,k,last[x]+1,i-1,edge[x]);
            last[x]=i;
        }
    }
    for(int i=1;i<=m;i++) modify(1,1,k,last[i]+1,k,edge[i]);
    get_ans(1,1,k);
    return 0;
}

Day2

Trie

[JSOI2009] 电子字典

Trie 题怎么能用 Trie 做呢？
由于串长极小，直接字符串哈希，实现时需要注意以下几个点：

  • 使用自然溢出哈希；
  • 记得去重，去重一定不要用 std::set，会 T 飞。
code 
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
#include<cstdio>
#include<cstring>
#include<set>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
int n,m;
ull base[25],h[25];
gp_hash_table<ull,int> word;
char s[25];
int main(){
    base[0]=1;
    for(int i=1;i<=22;i++) base[i]=base[i-1]*131;
    scanf("%d%d",&n,&m);
    while(n--){
        memset(s,0,sizeof(s));
        memset(h,0,sizeof(h));
        scanf("%s",s+1);
        h[0]=0;
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*131+s[i];
        word[h[len]]=m+1;
    }
    while(m--){
        memset(s,0,sizeof(s));
        memset(h,0,sizeof(h));
        h[0]=0;
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*131+s[i];
        if(word.find(h[len])!=word.end()){
            printf("-1\n");
            continue;
        }
        int res=0;
        for(int i=1;i<=len;i++){
            ull hash1=h[i-1]*base[len-i]+(h[len]-h[i]*base[len-i]);
            auto it=word.find(hash1);
            if(it!=word.end()&&it->second!=m)
                it->second=m,++res;
        }
        for(int i=1;i<=len;i++)
            for(char j='a';j<='z';j++){
                if(j==s[i]) continue;
                ull hash1=h[len]-s[i]*base[len-i]+j*base[len-i];
                auto it=word.find(hash1);
                if(it!=word.end()&&it->second!=m)
                    it->second=m,++res;
            }
        for(int i=0;i<=len;i++)
            for(char j='a';j<='z';j++){
                ull hash1=h[i]*base[len-i+1]+j*base[len-i]+(h[len]-h[i]*base[len-i]);
                auto it=word.find(hash1);
                if(it!=word.end()&&it->second!=m)
                    it->second=m,++res;
            }
        printf("%d\n",res);
    }
    return 0;
}

[USACO12DEC] First! G

建 Trie，在 Trie 上查找时对字母连边，拓扑排序判环。

code 
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
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
constexpr int N=3e5+10;
int n,nxt[N][26],tot,e[26][26],indegree[26],cnt,ans[N];
bool ed[N];
string s[N];
inline void insert(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        if(!nxt[p][k]) nxt[p][k]=++tot;
        p=nxt[p][k];
    }
    ed[p]=1;
}
bool find(string s){
    int p=0;
    memset(e,0,sizeof(e));
    memset(indegree,0,sizeof(indegree));
    for(char c:s){
        if(ed[p]) return 0;
        int k=c-'a';
        for(int i=0;i<26;i++)
            if(k!=i&&nxt[p][i]&&!e[k][i]){
                e[k][i]=1;
                ++indegree[i];
            }
        p=nxt[p][k];
    }
    queue<int> q;
    for(int i=0;i<26;i++)
        if(!indegree[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v=0;v<26;v++)
            if(e[u][v]&&!--indegree[v]) q.push(v);
    }
    for(int i=0;i<26;i++)
        if(indegree[i]) return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        insert(s[i]);
    }
    for(int i=1;i<=n;i++)
        if(find(s[i]))
            ans[++cnt]=i;
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
        cout<<s[ans[i]]<<'\n';
    return 0;
}

[IOI 2008] Type Printer

显然先建出 Trie，考虑怎样的遍历顺序更优。
发现这不是老熟人吗？

code 
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
#include<iostream>
using namespace std;
constexpr int N=25010;
int n,nxt[N*20][26],tot;
bool ed[N*20],flag[N*20],f;
string maxlen,ans;
void insert(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        if(!nxt[p][k]) nxt[p][k]=++tot;
        p=nxt[p][k];
    }
    ed[p]=1;
}
void query(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        p=nxt[p][k];
        flag[p]=1;
    }
}
void dfs(int u){
    if(ed[u]) ans.push_back('P');
    int maxk=-1;
    for(int i=0;i<26;i++){
        int v=nxt[u][i];
        if(!v) continue;
        if(flag[v]) maxk=i;
        else{
            ans.push_back(i+'a');
            dfs(v);
        }
    }
    if(~maxk){
        ans.push_back(maxk+'a');
        dfs(nxt[u][maxk]);
    }
    if(flag[u]&&!~maxk){
        cout<<ans.length()<<'\n';
        for(char c:ans)
            cout<<c<<'\n';
        exit(0);
    }
    ans.push_back('-');
}
int main(){
    f=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        insert(s);
        if(s.length()>maxlen.length()) maxlen=s;
    }
    query(maxlen);
    dfs(0);
    return 0;
}

笛卡尔树

[TJOI2011] 树的序

考虑 BST 每个节点记录权值 kk 和插入的时间 tt，则 kk 满足 BST 的性质，tt 满足小根堆的性质，这样构建的 BST 是一棵 Treap。
题意转化为：重新分配 tt，使得生成序列最小。
既然 tt 维度是小根堆，那么满足父亲小于后代。贪心地想，较小的 tt 分配顺序为：父亲 >> 左子树 >> 右子树，也就是 BST 的前序遍历。
笛卡尔树同样满足 Treap 的性质。它的 kk 与 tt 正好与本题的 BST 相反。则我们只需交换 kk 和 tt 并 O(n)O(n) 构建笛卡尔树即可。

code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10;
int n,a[N],st[N],top,son[N][2];
bool vis[N];
void dfs(int u){
    printf("%d ",u);
    if(son[u][0]) dfs(son[u][0]);
    if(son[u][1]) dfs(son[u][1]);
}
int main(){
    read(n);
    for(int i=1,x;i<=n;i++) read(x),a[x]=i;
    for(int i=1;i<=n;i++){
        int last=0;
        while(top&&a[st[top]]>a[i]) last=st[top--];
        if(top) son[st[top]][1]=i;
        son[i][0]=last;
        st[++top]=i;
    }
    for(int i=1;i<=n;i++)
        vis[son[i][0]]=vis[son[i][1]]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            dfs(i);
            break;
        }
    return 0;
}

数据结构

最大异或和

可持久化 01 trie 模板题。
操作与主席树类似，对于查询，设我们已经维护了所有的前缀异或和 sumi=⊕j=1iajsum_i=\oplus_{j=1}^ia_j，则只需最大化 sump−1⊕sumn⊕xsum_{p-1}\oplus sum_n\oplus x。后两项是给定的，则我们只需贪心求出答案即可。

code 
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<cstdio>
#include<algorithm>
using std::max;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=6e5+10;
int n,m,nxt[N*25][2],siz[N*25],tot,root[N],sum;
inline void insert(int u,int old,int x){
    root[u]=++tot;
    int p=root[u],q=root[old];
    siz[p]=siz[q]+1;
    for(int i=24;i>=0;i--){
        int c=(x>>i)&1;
        nxt[p][0]=nxt[q][0],nxt[p][1]=nxt[q][1];
        nxt[p][c]=++tot;
        p=nxt[p][c],q=nxt[q][c];
        siz[p]=siz[q]+1;
    }
}
inline int query(int x,int a,int b){
    int p=root[a],q=root[b],res=0;
    for(int i=24;i>=0;i--){
        int c=(x>>i)&1;
        if(siz[nxt[q][c^1]]>siz[nxt[p][c^1]]){
            res|=1<<i;
            p=nxt[p][c^1];
            q=nxt[q][c^1];
        }
        else{
            p=nxt[p][c];
            q=nxt[q][c];
        }
    }
    return res;
}
int main(){
    read(n,m);
    insert(0,0,0);
    for(int i=1,a;i<=n;i++){
        read(a);
        insert(i,i-1,sum^=a);
    }
    char op;
    int x,l,r;
    while(m--){
        op=getchar();
        while(op!='A'&&op!='Q') op=getchar();
        if(op=='A'){
            read(x);
            ++n;
            insert(n,n-1,sum^=x);
        }
        else{
            read(l,r,x);
            int ans;
            if(l==1) ans=max(query(sum^x,0,r-1),sum^x);
            else ans=query(sum^x,l-2,r-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

[十二省联考 2019] 异或粽子

类似[NOI2010] 超级钢琴的贪心，由于 ai⊕aj=aj⊕aia_i\oplus a_j=a_j\oplus a_i，只需使用堆查询最大的 2k2k 个，再令答案除以 22。可以用 Trie 查询全局第 kk 大，方法类似线段树上二分。

code 
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
#include<cstdio>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=5e5+10;
int n,k,nxt[N<<5][2],siz[N<<5],tot=1;
ll a[N],ans;
void insert(ll x){
    int p=1;
    ++siz[p];
    for(int i=32;i>=0;i--){
        int c=(x>>i)&1;
        if(!nxt[p][c]) nxt[p][c]=++tot;
        p=nxt[p][c];
        ++siz[p];
    }
}
ll query(ll x,int rnk){
    int p=1;
    ll res=0;
    for(int i=32;i>=0;i--){
        int c=(x>>i)&1;
        if(siz[nxt[p][c]]>=rnk) p=nxt[p][c];
        else{
            rnk-=siz[nxt[p][c]];
            p=nxt[p][c^1];
            res|=1ll<<i;
        }
    }
    return res;
}
struct node{
    int id,rnk;
    ll val;
    node(int id,int rnk,ll val):id(id),rnk(rnk),val(val){}
    bool operator<(const node &x)const{return val<x.val;}
};
priority_queue<node> q;
int main(){
    read(n,k);k<<=1;
    insert(0);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i]^=a[i-1];
        insert(a[i]);
    }
    for(int i=0;i<=n;i++)
        q.push(node(i,n+1,query(a[i],n+1)));
    while(k--){
        node u=q.top();
        q.pop();
        ans+=u.val;
        if(u.rnk) q.push(node(u.id,u.rnk-1,query(a[u.id],u.rnk-1)));
    }
    printf("%lld\n",ans>>1);
    return 0;
}

Day3

字符串哈希

[POI 2006] PAL-Palindromes

容易发现，两个回文串 AA，BB 组合成新回文串当且仅当 ABAB 等于 BABA。设 AA 的哈希值为 aa，BB 的哈希值为 bb，有

a×base∣B∣+b=b×base∣A∣+aa\times base^{|B|}+b=b\times base^{|A|}+a

简单移项

abase∣A∣−1=bbase∣B∣−1\frac{a}{base^{|A|}-1}=\frac{b}{base^{|B|}-1}

开哈希桶维护即可。

code 
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
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<utility>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
constexpr int mod1=998244353,mod2=1e9+7;
int n;
ll ans;
int qpow(ll a,int b,int p){
    a%=p;
    int res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
struct pair_hash{
    size_t operator()(const pair<int,int> &x)const{
        size_t seed=0;
        seed^=hash<int>{}(x.first)+0x9e3779b9+(seed<<6)+(seed>>2);
        seed^=hash<int>{}(x.second)+0x9e3779b9+(seed<<6)+(seed>>2);
        return seed;
    }
};
gp_hash_table<pair<int,int>,int,pair_hash> cnt;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    string s;
    for(int i=1,temp;i<=n;i++){
        cin>>temp>>s;
        ll h1=0,h2=0,base1=1,base2=1;
        for(char c:s){
            h1=(h1*131+c)%mod1;
            base1=base1*131%mod1;
            h2=(h2*131+c)%mod2;
            base2=base2*131%mod2;
        }
        ll x=h1*qpow(base1-1,mod1-2,mod1)%mod1;
        ll y=h2*qpow(base2-1,mod2-2,mod2)%mod2;
        ans+=cnt[make_pair(x,y)];
        ++cnt[make_pair(x,y)];
    }
    cout<<ans*2+n;
    return 0;
}

[POI 2012] OKR-A Horrible Poem

AA 的一个子串 BB 能成为 AA 的一个完整周期，当且仅当其长度为 AA 长度的因数。直接枚举因数。判断是否是完整周期的方法：设 hl,rh_{l,r} 表示 [l,r][l,r] 的哈希值，则当一个长为 lenlen 的子串满足 hl,r−len=hl+len,rh_{l,r-len}=h_{l+len,r} 时，其为一个完整周期。先跑一遍线性筛降低枚举因数的时间复杂度。

code 
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
#include<cstdio>
typedef unsigned long long ull;
constexpr int N=5e5+10;
int n,q,e[N],p[N],tot;
ull h[N],base[N];
char s[N];
ull gethash(int l,int r){return h[r]-h[l-1]*base[r-l+1];}
int main(){
    scanf("%d %s %d",&n,s+1,&q);
    base[0]=1;
    for(int i=1;i<=n;i++){
        base[i]=base[i-1]*131;
        h[i]=h[i-1]*131+s[i];
    }
    for(int i=2;i<=n;i++){
        if(!e[i]) p[e[i]=++tot]=i;
        for(int j=1;j<=e[i]&&p[j]<=n/i;j++)
            e[p[j]*i]=j;
    }
    int a,b,len,ans;
    while(q--){
        scanf("%d %d",&a,&b);
        len=ans=b-a+1;
        while(len>1){
            int prime=p[e[len]];
            if(gethash(a+ans/prime,b)==gethash(a,b-ans/prime))
                ans/=prime;
            len/=prime;
        }
        printf("%d\n",ans);
    }
    return 0;
}

[ONTAK2015] Tasowanie

双指针+二分+哈希。

code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef unsigned long long ull;
constexpr int N=2e5+10;
int n,m,a[N],b[N],len,p1,p2;
ull h1[N],h2[N],base[N];
inline ull gethash1(int l,int r){return h1[r]-h1[l-1]*base[r-l+1];}
inline ull gethash2(int l,int r){return h2[r]-h2[l-1]*base[r-l+1];}
inline bool check(int x){return gethash1(p1,p1+x-1)==gethash2(p2,p2+x-1);}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    read(m);
    for(int i=1;i<=m;i++) read(b[i]);
    if(n<m) for(int i=n+1;i<=m;i++) a[i]=1e3+1;
    if(n>m) for(int i=m+1;i<=n;i++) b[i]=1e3+1;
    base[0]=1;
    len=max(n,m);
    a[len+1]=b[len+1]=1e3+1;
    for(int i=1;i<=len;i++) base[i]=base[i-1]*13331;
    for(int i=1;i<=len;i++)
        h1[i]=h1[i-1]*13331+a[i];
    for(int i=1;i<=len;i++)
        h2[i]=h2[i-1]*13331+b[i];
    p1=1,p2=1;
    for(int i=1;i<=n+m;i++){
        if(a[p1]<b[p2]) printf("%d ",a[p1++]);
        else if(a[p1]>b[p2]) printf("%d ",b[p2++]);
        else{
            int l=1,r=min(len-p1+1,len-p2+1);
            while(l<=r){
                int mid=(l+r)>>1;
                if(check(mid)) l=mid+1;
                else r=mid-1;
            }
            if(a[p1+r]<b[p2+r]) printf("%d ",a[p1++]);
            else printf("%d ",b[p2++]);
        }
    }
    return 0;
}

KMP

[HNOI2008] GT考试

设 fi,jf_{i,j} 表示长串匹配前 ii 个字符，短串匹配前 jj 个字符的方案数。答案为：

ans=∑i=0m−1fn,ians=\sum_{i=0}^{m-1} f_{n,i}

设 gi,jg_{i,j} 表示匹配到第 ii 位时加入一个数字后匹配到第 jj 位的方案数，可以用 KMP 求出。

fi,j=∑k=0m−1fi−1,k×gk,jf_{i,j}=\sum_{k=0}^{m-1}f_{i-1,k}\times g_{k,j}

注意到这是矩阵乘法的形式，矩阵快速幂 O(m3log⁡n)O(m^3\log n)。
在转化成矩阵的过程中，fi,jf_{i,j} 被转化为一个一行 m−1m-1 列的矩阵。

code 
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
#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
int n,m,mod,nxt[25],ans;
struct Matrix{
    int a[20][20];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator*(const Matrix &x)const{
        Matrix res;
        for(int k=0;k<m;k++)
            for(int i=0;i<m;i++)
                for(int j=0;j<m;j++)
                    res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;
        return res;
    }
}base,f,g;
Matrix qpow(Matrix a,int b){
    Matrix res=base;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
char s[25];
int main(){
    read(n,m,mod);
    for(int i=0;i<m;i++) base.a[i][i]=1;
    scanf("%s",s+1);
    int j=0;
    for(int i=2;i<=m;i++){
        while(j&&s[j+1]!=s[i]) j=nxt[j];
        if(s[j+1]==s[i]) j++;
        nxt[i]=j;
    }
    for(int i=0;i<m;i++)
        for(char c='0';c<='9';c++){
            j=i;
            while(j&&s[j+1]!=c) j=nxt[j];
            if(s[j+1]==c) j++;
            g.a[i][j]=(g.a[i][j]+1)%mod;
        }
    f.a[0][0]=1;
    f=f*qpow(g,n);
    for(int i=0;i<m;i++) ans=(ans+f.a[0][i])%mod;
    printf("%d\n",ans);
    return 0;
}

Manacher

感觉自己没理解 Manacher 啊，改天重学一次。

[国家集训队] 拉拉队排练

由于只需要找长度为奇数的回文串，无需在字符间插入 #，直接跑 Manacher，开差分数组 sumsum，表示当前长度的回文串数量。当位置 ii 的最长回文半径为 pip_i 时，容易想到半径长度小于等于 pip_i 的都是回文串，则我们只需在差分数组 sum1sum_1 处加 11，sumpi×2sum_{p_i\times 2} 处减 11 就行了。最后统计答案时要用快速幂。

code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
constexpr int N=1e6+10,mod=19930726;
int qpow(ll a,int b){
    a%=mod;
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int n,p[N];
ll k,sum[N],ans;
char s[N];
int main(){
    scanf("%d %lld",&n,&k);
    scanf("%s",s+1);
    s[0]='#';
    for(int i=1,r=0,mid=0;i<=n;i++){
        if(i<=r) p[i]=min(p[mid*2-i],r-i+1);
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(p[i]+i>r) r=p[i]+i-1,mid=i;
        ++sum[1],--sum[p[i]*2];
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    int tot=n;
    ans=1;
    if(tot%2==0) --tot;
    while(k&&tot>0){
        ans=ans*qpow(tot,min(sum[tot],k))%mod;
        k=max(k-sum[tot],0ll);
        tot-=2;
    }
    if(k) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

[国家集训队] 最长双回文串

在跑 Manacher 同时维护以每个点开头和结尾的最长回文串长度。仅 Manacher 求解的答案不完全，需要再递推地扫一遍，最后枚举中点即可。

code 
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
constexpr int N=1e5+10;
char t[N],s[N<<1];
int len0,len,p[N<<1],a[N<<1],b[N<<1],ans;
int main(){
    scanf("%s",t+1);
    len0=strlen(t+1);
    s[0]=s[1]='#';
    len=1;
    for(int i=1;i<=len0;i++){
        s[++len]=t[i];
        s[++len]='#';
    }
    for(int i=1,r=0,mid=0;i<=len;i++){
        int j=2*mid-i;
        if(i<=r) p[i]=min(r-i+1,p[j]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]-1>r){
            r=i+p[i]-1;
            mid=i;
        }
        a[i+p[i]-1]=max(a[i+p[i]-1],p[i]-1);
        b[i-p[i]+1]=max(b[i-p[i]+1],p[i]-1);
    }
    for(int i=len;i>=1;i-=2) a[i]=max(a[i],a[i+2]-2);
    for(int i=1;i<=len;i+=2) b[i]=max(b[i],b[i-2]-2);
    for(int i=1;i<=len;i+=2)
        if(a[i]&&b[i]) ans=max(ans,a[i]+b[i]);
    printf("%d\n",ans);
    return 0;
}

Day4

搜索

搜索题真是无聊死了，就少放几道吧……

[CSP-S 2022] 假期计划

nn 遍 BFS 求全源最短路，之后考虑枚举。将 55 个点记作 1,2,3,4,51,2,3,4,5，则枚举 3,43,4 点，判断 2,52,5 是否与已选的点重复。可以预处理出每个能同时到达 11 点和另一个点的前三大点，因为它最多只有可能与 3,43,4 中的一个和 2,52,5 中的一个重合。总体时间复杂度 O(nm+n2)O(nm+n^2)。

code 
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
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=2510;
int n,m,k,dis[N][N];
ll ans,val[N];
vector<int> e[N];
queue<int> q;
struct node{
    int id;
    node(int id):id(id){}
    bool operator<(const node &x)const{
        return val[id]!=val[x.id]?val[id]<val[x.id]:id<x.id;
    }
};
set<node> st[N];
int main(){
    read(n,m,k);++k;
    for(int i=2;i<=n;i++) read(val[i]);
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++){
        dis[i][i]=0;
        q.push(i);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v:e[u])
                if(dis[i][u]+1<dis[i][v]&&dis[i][u]+1<=k){
                    dis[i][v]=dis[i][u]+1;
                    q.push(v);
                }
        }
    }
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++){
            if(i==j) continue;
            if(dis[i][j]<=k&&dis[1][j]<=k)
                st[i].insert(node(j));
            if(st[i].size()>3) st[i].erase(st[i].begin());
        }
    for(int b=2;b<=n;b++)
        for(int c=2;c<=n;c++){
            if(b==c||dis[b][c]>k) continue;
            for(auto temp1:st[b]){
                int a=temp1.id;
                if(a==b||a==c) continue;
                for(auto temp2:st[c]){
                    int d=temp2.id;
                    if(d==b||d==c||a==d) continue;
                    ans=max(ans,val[a]+val[b]+val[c]+val[d]);
                }
            }
        }
    printf("%lld\n",ans);
    return 0;
}

[AHOI2012] 铁盘整理

IDA* 板题。先离散化，估价函数为相邻差不为 11 的个数。

code 
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<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=18;
int n,a[N],b[N],lim;
inline int h(){
    int res=0;
    for(int i=1;i<=n;i++) res+=(abs(a[i+1]-a[i])!=1);
    return res;
}
bool dfs(int cnt,int pre){
    int temp=h();
    if(temp==0) return 1;
    if(cnt+temp>lim) return 0;
    bool f=0;
    for(int i=1;i<=n;i++){
        if(i==pre) continue;
        reverse(a+1,a+1+i);
        f|=dfs(cnt+1,i);
        reverse(a+1,a+1+i);
    }
    return f;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    a[n+1]=n+1;
    lim=1;
    while(1){
        if(dfs(0,0)){
            printf("%d\n",lim);
            break;
        }
        ++lim;
    }
    return 0;
}

Prime Gift

容易发现，pip_i 越小，方案数越多。n=16n=16 时不可接受，考虑 Meet in the middle。最坏情况下前 88 个质数 2,3,5,7,11,13,17,192,3,5,7,11,13,17,19，在 101810^{18} 内能组成 70391937039193 种数字。实际实现时可以将数的分配得更加均匀以降低复杂度。之后二分答案+双指针求解即可。

code 
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
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr ll lim=1e18,N=7039192+10;
int n,p[20],k,tota,totb;
ll a[N],b[N];
void dfs1(int x,ll num){
    if(x>n) return;
    dfs1(x+2,num);
    for(ll i=p[x];;i*=p[x]){
        if(lim/i<num) break;
        a[++tota]=num*i;
        dfs1(x+2,num*i);
    }
}
void dfs2(int x,ll num){
    if(x>n) return;
    dfs2(x+2,num);
    for(ll i=p[x];;i*=p[x]){
        if(lim/i<num) break;
        b[++totb]=num*i;
        dfs2(x+2,num*i);
    }
}
inline bool check(ll x){
    ll cnt=0;
    for(int i=1,j=totb;i<=tota;i++){
        while(j&&x/a[i]<b[j]) --j;
        cnt+=j;
        if(j==0) break;
    }
    return cnt<k;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(p[i]);
    sort(p+1,p+1+n);
    a[++tota]=b[++totb]=1;
    dfs1(1,1);
    dfs2(2,1);
    sort(a+1,a+1+tota);
    sort(b+1,b+1+totb);
    read(k);
    ll l=1,r=1e18;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",l);
    return 0;
}

[USACO09NOV] Lights G

Meet in the middle，开一个 std::map 记录状态对应的最小操作次数，按照补集相加。

code 
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
#include<cstdio>
#include<map>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=40;
int n,m,ans;
ll a[N];
map<ll,int> mp;
int main(){
    read(n,m);
    for(int i=0;i<n;i++) a[i]=1ll<<i;
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        --u,--v;
        a[u]|=1ll<<v;
        a[v]|=1ll<<u;
    }
    ans=n+1;
    for(int i=0;i<(1<<(n>>1));i++){
        ll temp=0;
        for(int j=0;j<(n>>1);j++)
            if((i>>j)&1)
                temp^=a[j];
        if(!mp.count(temp)) mp[temp]=__builtin_popcount(i);
        else mp[temp]=min(mp[temp],__builtin_popcount(i));
    }
    for(int i=0;i<(1<<(n-(n>>1)));i++){
        ll temp=0;
        for(int j=0;j<n-(n>>1);j++)
            if((i>>j)&1)
                temp^=a[(n>>1)+j];
        if(mp.count(((1ll<<n)-1)^temp))
            ans=min(ans,__builtin_popcount(i)+mp[((1ll<<n)-1)^temp]);
    }
    printf("%d\n",ans);
    return 0;
}

机关

坏题。
考虑 A*。容易想到 44 进制状压，则状态 xx 的估价 h(x)h(x) 应为当前已经旋转的次数与所有不为 11 的旋钮旋到 11 所需总步数除以 22 的和。因为最好情况是旋一个按钮时另一个正好也到了 11。每个状态记录一个 prepre 表示是从哪个状态转移过来的以输出方案。

code 
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
#include<cstdio>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=(1<<24)+10;
int st,a[15][4],b[N],pre[N],step[N];
bool vis[N];
void write(int x){
    if(x==st) return;
    write(pre[x]);
    printf("%d ",b[x]);
}
inline int h(int x){
    int res=0;
    for(int i=0;i<12;i++){
        int temp=(x>>(i<<1))&3;
        res+=temp?4-temp:0;
    }
    return res>>1;
}
struct node{
    int x,h;
    node(int x,int h):x(x),h(h){}
    bool operator<(const node &a)const{return h>a.h;}
};
priority_queue<node> q;
int main(){
    for(int i=0,x;i<12;i++){
        read(x);
        st|=(x-1)<<(i<<1);
        for(int j=0;j<4;j++)
            read(a[i][j]),--a[i][j];
    }
    q.push(node(st,h(st)));
    vis[st]=1;
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(x==0) break;
        for(int i=0;i<12;i++){
            int pos1=i<<1,temp1=(x>>pos1)&3,j=a[i][temp1];
            int pos2=j<<1,temp2=(x>>pos2)&3,res=x;
            res&=~(3<<pos1);
            res&=~(3<<pos2);
            res|=((temp1+1)&3)<<pos1;
            res|=((temp2+1)&3)<<pos2;
            if(!vis[res]){
                vis[res]=1;
                step[res]=step[x]+1;
                pre[res]=x,b[res]=i+1;
                q.push(node(res,step[res]+h(res)));
            }
        }
    }
    printf("%d\n",step[0]);
    write(0);
    return 0;
}

Day5

最小生成树

[NOIP 2013 提高组] 货车运输

最优情况一定是走最大生成树上的边，所以先 Kruskal 求最大生成树，接下来求树上两点间路径权值最小值，可以边权下放点权上树剖+线段树或倍增。另外，图不保证连通，实际上要对森林做操作。

code 
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<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e4+10,M=5e4+10;
int n,m,q,boss[N],cnt;
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
struct Edge{
    int u,v,w;
    bool operator<(const Edge &x)const{return w>x.w;}
}edge[M];
struct Edge1{int v,w;};
vector<Edge1> e[N];
void kruskal(){
    for(int i=1;i<=n;i++) boss[i]=i;
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m&&cnt<n-1;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u==v) continue;
        boss[u]=v;
        ++cnt;
        u=edge[i].u,v=edge[i].v;
        int w=edge[i].w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
}
int dfn[N],dfncnt,son[N],fa[N],siz[N],top[N],dep[N],w[N],P,tree[N<<2];
void dfs1(int u,int f){
    siz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(auto t:e[u]){
        int v=t.v;
        if(v==f) continue;
        w[v]=t.w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int topf){
    top[u]=topf;
    dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],topf);
    for(auto t:e[u]){
        int v=t.v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void build(){
    for(int i=1;i<=n;i++)
        if(!siz[i]) w[i]=2e9,dfs1(i,0);
    for(int i=1;i<=n;i++)
        if(!dfn[i]) dfs2(i,i);
    P=1;
    while(P<=n+1) P<<=1;
    memset(tree,0x3f,sizeof(tree));
    for(int i=1;i<=n;i++)
        tree[P+dfn[i]]=w[i];
    for(int i=P-1;i;i--)
        tree[i]=min(tree[ls(i)],tree[rs(i)]);
}
int query(int l,int r){
    l+=P-1,r+=P+1;
    int res=2e9;
    while(l^1^r){
        if(~l&1) res=min(tree[l^1],res);
        if(r&1) res=min(tree[r^1],res);
        l>>=1,r>>=1;
    }
    return res;
}
int ask(int x,int y){
    if(find(x)!=find(y)) return -1;
    int res=2e9;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res=min(res,query(dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) res=min(res,query(dfn[x]+1,dfn[y]));
    return res;
}
int main(){
    read(n,m);
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        edge[i]={u,v,w};
    }
    kruskal();
    build();
    read(q);
    int x,y;
    while(q--){
        read(x,y);
        printf("%d\n",ask(x,y));
    }
    return 0;
}

[BJWC2010] 严格次小生成树

跟上一道题一个套路。考虑枚举替换边的过程，首先加一条边形成环，再从环上删去最大的一条小于加入边边权的边。线段树维护区间最大值和区间严格次大值即可。

code 
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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=1e5+10,M=3e5+10;
int n,m,boss[N],cnt;
struct node{
    int maxn,se;
    node(int maxn=-1,int se=-1):maxn(maxn),se(se){}
    node operator+(const node &x)const{
        node res;
        res.maxn=max(maxn,x.maxn);
        res.se=max(se,x.se);
        if(maxn!=x.maxn)
            res.se=max(res.se,min(maxn,x.maxn));
        return res;
    }
};
int P;
node tree[N<<2];
node query(int l,int r){
    l+=P-1,r+=P+1;
    node res;
    while(l^1^r){
        if(~l&1) res=res+tree[l^1];
        if(r&1) res=res+tree[r^1];
        l>>=1,r>>=1;
    }
    return res;
}
struct Edge{
    int u,v,w;
    bool operator<(const Edge &x)const{return w<x.w;}
}edge[M];
struct Edge1{int v,w;};
vector<Edge1> e[N];
ll ans,minval;
int dfn[N],top[N],dfncnt,dep[N],fa[N],siz[N],son[N],w[N];
bool vis[N];
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    fa[u]=f;
    siz[u]=1;
    for(auto t:e[u]){
        int v=t.v;
        if(v==f) continue;
        w[v]=t.w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int topf){
    top[u]=topf;
    dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],topf);
    for(auto t:e[u]){
        int v=t.v;
        if(v==fa[u]||v==son[u])
            continue;
        dfs2(v,v);
    }
}
node ask(int x,int y){
    node res;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res=res+query(dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) res=res+query(dfn[x]+1,dfn[y]);
    return res;
}
int main(){
    read(n,m);
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        edge[i]={u,v,w};
    }
    sort(edge+1,edge+1+m);
    for(int i=1;i<=n;i++) boss[i]=i;
    for(int i=1;i<=m&&cnt<n-1;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u==v) continue;
        boss[u]=v;
        vis[i]=1;
        u=edge[i].u,v=edge[i].v;
        int w=edge[i].w;
        minval+=w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
        if(++cnt==n-1) break;
    }
    dfs1(1,0);
    dfs2(1,1);
    P=1;
    while(P<=n+1) P<<=1;
    for(int i=1;i<=n;i++)
        tree[P+dfn[i]]=w[i];
    for(int i=P-1;i;i--)
        tree[i]=tree[i<<1]+tree[i<<1|1];
    ans=1e18;
    for(int i=1;i<=m;i++){
        if(vis[i]) continue;
        int x=edge[i].u,y=edge[i].v,w=edge[i].w;
        if(x==y) continue;
        node temp=ask(x,y);
        if(temp.maxn==w)
            ans=min(ans,minval-temp.se+w);
        else ans=min(ans,minval-temp.maxn+w);
    }
    printf("%lld\n",ans);
    return 0;
}

Peaks

Kruskal 重构树的在线做法还是太吃操作了，我们直接离线。容易想到将边权和询问的 xx 升序排序后动态加边，查询第 kk 大直接线段树上二分，加边用并查集+线段树合并维护。

code 
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
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=5e5+10;
int n,m,q,h[N],b[N],len,tot,root[N],fa[N],now,ans[M];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct edge{
    int u,v,w;
    bool operator<(const edge &x)const{return w<x.w;}
}e[M];
struct Query{
    int v,x,k,id;
    bool operator<(const Query &a)const{return x<a.x;}
}qu[M];
struct Tree{
    int ls,rs,sum;
}tree[N<<5];
inline void push_up(int u){
    tree[u].sum=tree[tree[u].ls].sum+tree[tree[u].rs].sum;
}
void modify(int &u,int l,int r,int x){
    if(!u) u=++tot;
    if(l==r){
        ++tree[u].sum;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(tree[u].ls,l,mid,x);
    else modify(tree[u].rs,mid+1,r,x);
    push_up(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b) return a|b;
    if(l==r){
        tree[a].sum+=tree[b].sum;
        return a;
    }
    int mid=(l+r)>>1;
    tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
    tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
    push_up(a);
    return a;
}
int query(int u,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(k<=tree[tree[u].ls].sum)
        return query(tree[u].ls,l,mid,k);
    else
        return query(tree[u].rs,mid+1,r,k-tree[tree[u].ls].sum);
}
int main(){
    read(n,m,q);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        read(h[i]);
        b[i]=h[i];
    }
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+1+len,h[i])-b;
        modify(root[i],1,len,x);
    }
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        e[i]={u,v,w};
    }
    sort(e+1,e+1+m);
    for(int i=1,v,x,k;i<=q;i++){
        read(v,x,k);
        qu[i]={v,x,k,i};
    }
    sort(qu+1,qu+1+q);
    for(int i=1;i<=q;i++){
        int x=qu[i].x,k=qu[i].k,id=qu[i].id;
        while(e[now+1].w<=x&&now<m){
            ++now;
            int u=find(e[now].u),v=find(e[now].v);
            if(u==v) continue;
            fa[u]=v;
            root[v]=merge(root[v],root[u],1,len);
        }
        int v=find(qu[i].v);
        if(tree[root[v]].sum<k) ans[id]=-1;
        else ans[id]=b[query(root[v],1,len,tree[root[v]].sum-k+1)];
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

最短路

没做。

拓扑排序

[ZJOI2007] 最大半连通子图

容易发现，半连通子图就是若干相连的强连通分量，则找最大半连通子图转化为缩点后在 DAG 上找最长链+计数。注意去重。

code 
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
#include<cstdio>
#include<stack>
#include<vector>
#include<set>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=1e6+10;
int n,m,mod,head[N],tot_edge;
struct edge{int to,nxt;}e1[M];
inline void add_edge(int u,int v){
    e1[++tot_edge].to=v;
    e1[tot_edge].nxt=head[u];
    head[u]=tot_edge;
}
stack<int> st;
bool instack[N];
int dfn[N],low[N],dfncnt,scccnt,scc[N],w[N];
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    instack[u]=1;
    st.push(u);
    for(int i=head[u];i;i=e1[i].nxt){
        int v=e1[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scccnt;
        while(1){
            int v=st.top();
            st.pop();
            instack[v]=0;
            scc[v]=scccnt;
            ++w[scccnt];
            if(u==v) break;
        }
    }
}
vector<int> e2[N];
int indegree[N],dp[N],dis[N],ans1,ans2;
set<pair<int,int>> p;
queue<int> q;
int main(){
    read(n,m,mod);
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        add_edge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=e1[i].nxt){
            int v=e1[i].to;
            if(scc[u]==scc[v]) continue;
            if(p.find(make_pair(scc[u],scc[v]))!=p.end())
                continue;
            p.insert(make_pair(scc[u],scc[v]));
            e2[scc[u]].push_back(scc[v]);
            ++indegree[scc[v]];
        }
    for(int i=1;i<=scccnt;i++)
        if(!indegree[i]){
            q.push(i);
            dis[i]=w[i];
            dp[i]=1;
        }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:e2[u]){
            if(dis[v]<dis[u]+w[v]){
                dis[v]=dis[u]+w[v];
                dp[v]=dp[u];
            }
            else if(dis[v]==dis[u]+w[v])
                dp[v]=(dp[u]+dp[v])%mod;
            if(!--indegree[v]) q.push(v);
        }
    }
    for(int i=1;i<=scccnt;i++) ans1=max(ans1,dis[i]);
    for(int i=1;i<=scccnt;i++)
        if(dis[i]==ans1) ans2=(ans2+dp[i])%mod;
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

Day6

二分图

Machine Schedule

连接每个 aia_i 和 bib_i，问题变为了二分图上找最小点覆盖。直接跑二分图最大匹配即可。
Kőnig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。

code 
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<cstdio>
#include<vector>
#include<cstring>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1010;
int n,m,k,ans,match[N];
bool vis[N];
vector<int> e[N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    while(1){
        for(int i=1;i<=n;i++) e[i].clear();
        memset(match,0,sizeof(int)*(n+10));
        read(n);
        if(!n) return 0;
        read(m,k);
        for(int i=1,u,v,a;i<=k;i++){
            read(a,u,v);
            e[u].push_back(v);
        }
        ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(bool)*(n+10));
            if(dfs(i)) ++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}

[USACO05JAN] Muddy Fields G

贪心地考虑，极长地放木板一定优。将所有横着的和竖着的木板编号，相交的连边，之后二分图最大匹配。

code 
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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
constexpr int N=55;
int r,c,tota,totb,a[N][N],b[N][N],match[N*N],ans;
char mp[N][N];
bool vis[N*N];
vector<int> e[N*N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='*'){
                if(mp[i][j-1]=='*')
                    a[i][j]=a[i][j-1];
                else a[i][j]=++tota;
                if(mp[i-1][j]=='*')
                    b[i][j]=b[i-1][j];
                else b[i][j]=++totb;
                if(a[i][j]&&b[i][j])
                    e[a[i][j]].push_back(b[i][j]);
            }
        }
    for(int i=1;i<=tota;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ++ans;
    }
    cout<<ans<<'\n';
    return 0;
}

Guardian of Decency

最大独立集与最小点覆盖之和为顶点数目，这个推论适用于一般图。

code 
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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
constexpr int N=510;
int t,n,match[N],ans,cnta,cntb;
bool vis[N];
struct student{
    int h;
    char sex;
    string music,sport;
}a[N],b[N];
vector<int> e[N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++) e[i].clear();
        memset(match,0,sizeof(int)*(n+10));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].h>>a[i].sex>>a[i].music>>a[i].sport;
            for(int j=1;j<i;j++){
                if(abs(a[i].h-a[j].h)>40||a[i].sex==a[j].sex||
                    a[i].music!=a[j].music||a[i].sport==a[j].sport)
                    continue;
                if(a[i].sex=='M') e[i].push_back(j);
                else e[j].push_back(i);
            }
        }
        ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(bool)*(n+10));
            if(dfs(i)) ++ans;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

欧拉路径

没做。

连通分量

没做。

参考资料：
https://oi-wiki.org/graph/graph-matching/bigraph-match/