2022 ICPC 沈阳站

发表于 分类于

2022ICPC沈阳站。

gym

A. Absolute Difference

一眼题，但是要分三种情况讨论一下。

算一算积分就好了。

代码有点长。

C. Clamped Sequence

显然 $r-l$ 越大越好。

然后一定是 $l,r$ 当中的某一个与某个 $a_i$ 是相等的。

枚举即可。时间复杂度 $O(n^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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5005;
int n,d;
int a[N],b[N];

inline ll check(int l,int r) {
    for(int i=1;i<=n;i++) {
        b[i] = min(r,max(a[i],l));
    }
    ll sum = 0;
    for(int i=2;i<=n;i++) {
        sum += abs(b[i]-b[i-1]);
    }
    return sum;
}

int main() {
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    ll ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans,check(a[i],a[i]+d));
    for(int i=1;i<=n;i++) ans = max(ans,check(a[i]-d,a[i]));
    printf("%lld\n",ans);
    return 0;
}

D. DRX vs. T1

简单签到题。

E. Graph Completing

VP的时候傻掉了。其实这个并不难。

先边双缩点，变成一棵树，树上有权值 $a_i$，表示第 $i$ 个边双中有 $a_i$ 个点。

然后你要在树上任意两个点连边，连边有 $a_x\times a_y$ 种方法。

为了使得整个图变成一个边双，那一次连边就会使得 $x,y$ 之间的点都捏成一个。

也就是每连两个点，树上两点的路径的边就会被覆盖。要求每条边至少覆盖一次。问方案数。

直接做不好做。考虑容斥，设至少有 $k$ 条边一定不连的方案数位 $g_k$，那么答案是 $\sum_{k} (-1)^k g_k$。

因此，可以把容斥系数扔进DP里。

设 $f_{u,i}$ 表示子树 $u$ 中，和子树根节点 $u$ 相连的连通块中 $a_x$ 之和为 $i$ 的方案数。

直接枚举转移。

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

const ll mod = 998244353;
inline ll Pow(ll x,ll y) {
    ll ans = 1;
    x %= mod;
    for(;y;y>>=1,x=x*x%mod) if(y&1) ans = ans * x % mod;
    return ans;
}
inline void Add(ll &x,ll y) {
    x+=y;
    if(x>=mod) x-=mod;
}
const int N = 5005;
ll pw[N*N];
inline void init(int n) {
    pw[0] = 1;
    ll inv = 2;
    fo(i,1,n)
        pw[i] = pw[i-1] * inv % mod;
}
namespace Tree{
    int n;
    VI adj[N];
    int a[N],b[N];
    int si[N];
    ll f[N][N],g[N];
    inline void add(int x,int y) {
        adj[x].pb(y);
        adj[y].pb(x);
    }
    void dfs(int u,int pre) {
        si[u] = a[u];
        f[u][a[u]] = 1;
        for(int v:adj[u])
            if(v!=pre) {
                dfs(v,u);
                fo(i,0,si[u]+si[v])
                    g[i] = 0;
                fo(i,0,si[u])
                    fo(j,0,si[v]) {
                        Add(g[i],mod-f[u][i]*f[v][j]%mod);
                        Add(g[i+j],f[u][i]*f[v][j]%mod*pw[i*j-1]%mod);
                    }
                fo(i,0,si[u]+si[v])
                    f[u][i] = g[i];
                si[u] += si[v];
            }
    }
    inline ll work(int k) {
        ll sum = 0, ans = 0,s = 0;
        fo(i,1,n) s += a[i]*(a[i]-1)/2;
        sum = (s - k + (n-1)) % (mod-1) + (mod-1);
        sum %= (mod-1);
        dfs(1,0);
        fo(i,1,si[1])
            Add(ans,f[1][i]);
        return ans * Pow(2,sum) % mod;
    }
}

namespace Graph{
    int n,m;
    VI adj[N];
    inline void add(int x,int y) {
        adj[x].pb(y); adj[y].pb(x);
    }
    int dfn[N],low[N],tim;
    int bel[N];
    int st[N],top;
    map<pair<int,int>,int> ma;
    void dfs(int u,int pre) {
        dfn[u] = low[u] = ++tim; st[++top] = u;
        for(int v:adj[u])
            if(!dfn[v]) {
                dfs(v,u); low[u] = min(low[u],low[v]);
                if(low[v]>dfn[u]) {
                    ma[{u,v}] = ma[{v,u}] = 1;
                }
            }
            else if(v!=pre) low[u] = min(low[u],dfn[v]);
    }
    void dfs2(int u,int pre) {
        bel[u] = Tree::n;
        Tree::a[Tree::n]++;
        for(int v:adj[u])
            if(v!=pre&&!ma.count({u,v})&&!bel[v]) {
                dfs2(v,u);
            }
    }
    inline void work() {
        read(n,m);
        fo(i,1,m) {
            int x,y;
            read(x,y);
            add(x,y);
        }
        dfs(1,0);
        fo(i,1,n)
            if(!bel[i]) {
                ++Tree::n;
                dfs2(i,0);
            }
        for(int u=1;u<=n;u++)
            for(int v:adj[u])
                if(u<v) {
                    if(bel[u] == bel[v])
                        Tree::b[bel[u]] ++;
                    else
                        Tree::add(bel[u],bel[v]);
                }
        printf("%lld\n",Tree::work(m));
    }
}

int main() {
    init(5000*5000);
    Graph::work();
    return 0;
}

F. Half Mixed

首先是 $\binom{n}{2}$ 和 $\binom{m}{2}$ 中至少有一个是偶数。

那么就可以考虑不一定是偶数的那一个，直接扔掉不管它，转换成处理 $1\times n$ 或 $n\times 1$ 的情况，使得方案数刚好是一半。

接下来就是一个背包，但是由于这题的特殊的数据，可以直接贪心就OK了。

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
#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASES int ___;for(read(___);___--;)
mt19937 rnd(random_device{}());

const int N = 1e6+5;
ll a[N];

inline void init(int n) {
    fo(i,1,n)
        a[i] = 1ll*(i+1)*i/2-i;
}

inline vector<int> get(int n,ll m) {
    if(n==0) {
        assert(m==0);
        VI ans;
        return ans;
    }
    int i = upper_bound(a+1,a+N,m-n)-a-1;
    vector<int> ans = get(n-i,m-a[i]-i);
    ans.pb(i);
    return ans;
}

inline bool check(int n) {
    return n%4==3||n%4==0;
}
int main() {
    init(1e6);
    CASES {
        int n,m;
        read(n,m);
        if(!check(n)&&!check(m)) {
            printf("No\n");
            continue;
        }
        printf("Yes\n");
        if(check(m)) {
            VI ans = get(m,1ll*m*(m+1)/4);
            assert(ans.size() > 0);
            for(int i=1;i<=n;i++) {
                int now = 0;
                for(auto x:ans) {
                    for(int j=1;j<=x;j++) printf("%d ",now);
                    now^=1;
                }
                printf("\n");
            }
        }
        else {
            VI ans = get(n,1ll*n*(n+1)/4);
            assert(ans.size() > 0);
            int now = 0;
            for(auto x:ans) {
                for(int j=1;j<=x;j++) {
                    for(int i=1;i<=m;i++) printf("%d ",now);
                    printf("\n");
                }
                now^=1;
            }
            printf("\n");
        }
    }
    return 0;
}

G. Meet in the Middle

离线，将第一棵树的贡献挂在第二棵树上，最优的位置为第二棵树的直径中的其中一个点。

变成找第二棵树（加上第一棵树贡献以后）的直径。

$a$ 点在第一棵树游走的时候不会影响子树内和子树外的直径。于是分开维护一下，然后用换根DP的套路往下合并，传递即可。

时间复杂度 $O(n\log n + q)$。

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;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASES int ___;for(read(___);___--;)
mt19937 rnd(random_device{}());

const int N = 5e5+5;
const int K = 21;
ll d1[N];
int dfn[N],_dfn[N],low[N];

struct Tree {
    vector<pair<int,int>> adj[N];
    int top,st[N<<1],dep[N],pos[N];
    ll d[N];
    int l2[N<<1];
    int f[K][N<<1];
    Tree() {}
    void dfs(int u,int pre) {
        dep[u] = dep[pre] + 1;
        st[++top] = u; pos[u] = top;
        for(auto [v,w]: adj[u])
            if(v!=pre) {
                d[v] = d[u] + w;
                dfs(v,u);
                st[++top] = u;
            }
    }
    inline int cmp(const int &x,const int &y) {
        return dep[x] < dep[y] ? x : y;
    }
    inline int lca(int x,int y) {
        x = pos[x]; y = pos[y];
        if(x > y) swap(x,y);
        int k = l2[y-x+1];
        return cmp(f[k][x],f[k][y-(1<<k)+1]);
    }
    void build(int n) {
        fo(i,2,n) {
            int x,y,z;
            read(x,y,z);
            adj[x].pb({y,z});
            adj[y].pb({x,z});
        }
        dfs(1,0);
        fo(i,1,top) f[0][i] = st[i];
        fo(i,2,top) l2[i] = l2[i>>1] + 1;
        fo(j,1,l2[top])
            fo(i,1,top) {
                f[j][i] = f[j-1][i];
                if(i + (1<<j) - 1 <= top)
                    f[j][i] = cmp(f[j][i], f[j-1][i + (1 << (j-1))]);
            }
    }
    inline ll dis(int x,int y) {
        return d[x] + d[y] - (d[lca(x,y)] << 1);
    }
};

Tree T1, T2;

int o;
inline ll F(int x,int y,int o) {
    if(!x || !y)
        return -1;
    return T1.dis(x,o) + T1.dis(y,o) + T2.dis(x,y);
}
struct node{
    int x,y;
    node() {x = y = 0;}
    node(int _x,int _y) {
        x = _x; y = _y;
    } 
    friend inline bool operator < (const node &A,const node &B) {
        if(!A.x) return 1;
        if(!B.x) return 0;
        return F(A.x,A.y,o) < F(B.x,B.y,o);
    }
    friend inline node operator + (const node &A,const node &B) {
        ll mx = -1;
        node ans;
        auto check = [&](const int &x,const int &y) -> void {
            ll z = F(x,y,o);
            if(mx < z) {
                ans = {x,y};
                mx = z;
            }
        };
        check(A.x, A.y);
        check(A.x, B.x);
        check(A.x, B.y);
        check(A.y, B.x);
        check(A.y, B.y);
        check(B.x, B.y);
        return ans;
    }
};

vector<pair<int,int>> ask[N];
ll ans[N];
int n,q;
node f[N];
void dfs1(int u,int pre) {
    f[u] = {u,u};
    o = u;
    for(auto [v,w]:T1.adj[u])   
        if(v != pre) {
            dfs1(v,u);
            o = u;
            f[u] = f[u] + f[v];
        }
}
void dfs2(int u,int pre,node A) {
    vector<int> id;
    vector<node> g,h;
    A = A + (node){u,u};
    id.pb(0); g.pb(A);
    for(auto [v,w]:T1.adj[u])   
        if(v != pre) {
            id.pb(v); g.pb(f[v]);
        }
    id.pb(0); g.pb(A);
    h = g;
    int m = id.size();
    o = u;
    ff(i,0,m-1) h[i+1] = h[i+1] + h[i];
    fd(i,m-1,1) g[i-1] = g[i-1] + g[i];
    node mx = g[1];
    for(auto [v,i]:ask[u])
        ans[i] = max(T1.dis(mx.x, u) + T2.dis(mx.x, v), T1.dis(mx.y, u) + T2.dis(mx.y, v));
    
    ff(i,0,m)
        if(id[i] && id[i] != pre) {
            int v = id[i];
            o = v;
            node B = h[i - 1] + g[i + 1];
            B = B + A;
            dfs2(v,u,B);
        }
}
int main() {
    read(n,q);
    T1.build(n);
    T2.build(n);
    fo(i,1,q) {
        int x,y;
        read(x,y);
        ask[x].pb({y,i});
    }
    dfs1(1,0);
    dfs2(1,0,{0,0});
    fo(i,1,q) printf("%lld\n",ans[i]);
    return 0;
}

H. P-P-Palindrome

若一个 $(P,Q)$ 满足条件，则 $P+Q$ 必为整周期串。$P$ 也是整周期串。由回文串的性质可以得到这个结论。

于是我们就写一个广义PAM，然后对于每个串，统计一下他的前缀有哪些是和当前串为倍数关系的，就可以了。

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
#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASES int ___;for(read(___);___--;)
mt19937 rnd(random_device{}());

const int N = 1e6+5;
const int S = 26;

namespace PAM{
    int n,s[N],num[N],p,las,ne[N][S],fail[N],len[N],sz[N];
    void init() {
        s[n=0]=len[p=2]=-1;
        fail[las=1]=fail[2]=2;
    }
    int getfail(int x) {for(;s[n-1-len[x]]!=s[n];x=fail[x]); return x;}
    void update() {
        s[n=0]=-1;
        las=1;
    }
    void add(int c) {
        s[++n] = c;
        int cur=getfail(las);
        if(!ne[cur][c]) {
            len[++p]=len[cur]+2;
            fail[p] = ne[getfail(fail[cur])][c];
            if(!fail[p]) fail[p]=1;
            ne[cur][c]=p;
        }
        las=ne[cur][c];
    }
    VI adj[N];
    int tong[N];
    int b[N];
    inline ll sqr(int x) {return 1ll*x*x;}
    void dfs(int u) {
        if(len[u]>0)
            tong[len[u]] = u;
        if(fail[u] >= 3) {
            int x = len[u]-len[fail[u]];
            if(len[u] % x == 0 && tong[x]) {
                b[u] = 0;
                b[tong[x]] = max(b[tong[x]],len[u]/x);
            }
        }
        for(int v:adj[u])
            dfs(v);
        if(len[u]>0)
            tong[len[u]] = 0;
    }
    inline ll work() {
        fo(i,1,p) b[i] = 1;
        fo(i,1,p)
            if(i!=2)
                adj[fail[i]].pb(i);
        dfs(2);
        ll ans = 0;
        fo(i,3,p)
            ans += sqr(b[i]);
        return ans;
    }
}

int n;
char s[N];
int main() {
    scanf("%d",&n);
    PAM::init();
    for(int i=1;i<=n;i++) {
        PAM::update();
        scanf("%s",s+1);
        int m = strlen(s+1);
        for(int j=1;j<=m;j++)
            PAM::add(s[j]-'a');
    }
    printf("%lld\n",PAM::work());
    return 0;
}

I. Quartz Collection

按照 $a_i-b_i$ 排序，然后按照模 $4$ 分一下类。

用线段树维护这些和即可。

L. Tavern Chess

最终状态不会很多，直接模拟即可。