Kyooma's Blog

2023杭电多校01

  • ~17.26K 字

题目来自: 2023“钉耙编程”中国大学生算法设计超级联赛（1）

Solved Rank A B C D E F G H I J K L
6 / 12 70 / 1200 Ø O - - O - - O O O - O

  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

A - Hide-And-Seek Game

SOLUTION

对于每次询问，可以 $O(n)$ 找出两人都可以到达的点并记录下到达的时刻 (记作 $t1$ 和 $t2$ ) 以及两人路径的长度 $len1$ 和 $len2$。

设 $x$ 为两人同时到达该点的时刻，则有

这是经典的excrt式子，使用exgcd求解即可。

若对每个情况都是用exgcd求解，这样的复杂度是 $O(mnlog(n))$的（虽然也能通过）。不过注意到对于同一组询问来说，$len1$ 和 $len2$ 是保持不变的，因此在最开始只需要求一次 exgcd 即可，这样的复杂度是 $O(mn + mlog(n))$。

undefined

ps.赛中把某个减号写成加号了一直没发现(

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
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10, Log = 12, inf = 0x3f3f3f3f;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
    for(n=0;(c=gc())<'0'||c>'9';);
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
    for(n=0;(c=gc())<'0'||c>'9';);
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return g;
}

vector<int> e[N];
int anc[N][Log + 5], depth[N];

void dfs(int u, int fa){
    anc[u][0] = fa;
    depth[u] = depth[fa] + 1;
    for(int v : e[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
}

void init(int root, int n){
    depth[0] = 0;
    dfs(root, 0);
    for(int j = 1; j <= Log; j++){
        for(int i = 1; i <= n; i++){
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int rush(int u, int h){
    for(int i = 0; i < Log; i++){
        if(h >> i & 1) u = anc[u][i];
    }
    return u;
}

int qry(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    u = rush(u, depth[u] - depth[v]);
    if(u == v) return u;
    for(int i = Log; i >= 0; i--){
        if(anc[u][i] != anc[v][i]){
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int dfn_a[N], dfn_b[N];

void gao(int u, int fa, int l, int step, int t[]){
    while(u != fa){
        t[u] = l;
        l += step;
        u = anc[u][0];
    }
    t[u] = l;
}

int upper(int m, int n){
    if(m <= 0) return m / n;
    return (m - 1) / n + 1;
}

int lcmp;

int calc(int x1, int a, int y1, int b, int g, int x, int y, int now){
    // x*a - y*b = y1 - x1
    int cx = y1 - x1;
    if(cx % g) return -1;
    cx /= g;
    x *= cx;
    int t = upper(now - x1 - x * a, lcmp);
    int ans = x1 + x * a + t * lcmp;
//    dbg(ans);
    return ans;
}

void get_dfn(int u, int v, int dfn[], int &len){
    int lca = qry(u, v);
    len = depth[u] + depth[v] - depth[lca] * 2 + 1;
    gao(u, lca, 1, 1, dfn);
    gao(v, lca, len, -1, dfn);
}

int run(int len1, int len2, int n){
    int x, y, a = (len1 - 1) * 2, b = (len2 - 1) * 2;
    int g = exgcd(a, b, x, y);
    // dbg(a, b, x, y, g);
    lcmp = a * b / g;
    int now = 1, ans = inf, location = -1;
    for(int i = 1; i <= n; i++){
        if(!dfn_a[i] || !dfn_b[i]) continue;
        vector<int> tx{dfn_a[i], dfn_a[i] + (len1 - dfn_a[i]) * 2};
        vector<int> ty{dfn_b[i], dfn_b[i] + (len2 - dfn_b[i]) * 2};
        for(int x1 : tx){
            for(int y1 : ty){
                // x*a - y*b = y1 - x1
                int res = calc(x1, a, y1, b, g, x, y, max(x1, y1));
                if(res != -1){
                    if(res < ans){
                        ans = res;
                        location = i;
                    }
                }
            }
        }
    }
    return location;
}

void kaibai() {
    int n, m;
    read(n);
    read(m);
    for(int i = 1, u, v; i < n; i++){
        read(u);
        read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    init(1, n);
    while(m--){
        for(int i = 1; i <= n; i++) dfn_a[i] = dfn_b[i] = 0;
        int sa, ta, sb, tb, len1, len2;
        read(sa);read(ta);
        read(sb);read(tb);
        get_dfn(sa, ta, dfn_a, len1);
        get_dfn(sb, tb, dfn_b, len2);
        int ans = run(len1, len2, n);
        cout << ans << '\n';
    }
    for(int i = 1; i <= n; i++){
        e[i].clear();
    }
}

int main(void) {
    int T = 1;
    read(T);
    while (T--) {
        kaibai();
    }
}

B - City Upgrading

SOLUTION

树形dp

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>e[N];
int a[N];
ll dp[N][3];
void dfs(int x,int f){
    dp[x][0]=0;
    dp[x][1]=0;
    dp[x][2]=a[x];
    int fl=0;
    for(auto i:e[x]){
        if(i==f) continue;
        dfs(i,x);
        dp[x][0]+=min(dp[i][1],dp[i][2]);
        dp[x][2]+=min(dp[i][0],min(dp[i][1],dp[i][2]));
        if(dp[i][2]<=dp[i][1]) fl=1;
    }
    if(fl){
        for(auto i:e[x]){
            if(i==f) continue;
            dp[x][1]+=min(dp[i][2],dp[i][1]);
        }
    }
    else{
        vector<ll>v;
        for(auto i:e[x]){
            if(i==f) continue;
            dp[x][1]+=dp[i][1];
            v.push_back(dp[i][2]-dp[i][1]);
        }
        if(v.size()==0){
            dp[x][1]=1e18;
            return;
        }
        sort(v.begin(),v.end());
        dp[x][1]+=v[0];
    }
}
void kaibai(){
    int d,n,m,i,j,x,y,l,r,mid,ans=0;
    cin>>n;
    for(i=1;i<=n;i++){
        cin >> a[i];
        e[i].clear();
    }
    for(i=1;i<n;i++){
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0);
    cout<<min(dp[1][2],dp[1][1])<<'\n';
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        kaibai();
    }
}

E - Cyclically Isomorphic

SOLUTION

板子题，求字符串环的最小表示

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<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10;
const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251};
pll hashs[N];

pll operator * (pll a, pll b){
    return {a.first * b.first % mod.first, a.second * b.second % mod.second};
}

pll operator + (pll a, pll b){
    return {(a.first + b.first) % mod.first, (a.second + b.second) % mod.second};
}

void minrep(int x, string s){
    int n = s.size();
    for(int i = 0; i < n; i++) s += s[i];
    int i = 0, j = 1, k = 0, t;
    while(i < n && j < n && k < n) if(t = s[(i + k) % n] - s[(j + k) % n]){
        if(t > 0) i += k + 1; else j += k + 1;
        if(i == j) j++;
        k = 0;
    }else k++;
    int l = i < j ? i : j;
    pll res = {0, 0};
    for(i = 0; i < n; i++){
        res = res * base + pll{s[i + l] - 'a' + 1, s[i + l] - 'a' + 1};
    }
    hashs[x] = res;
}

void kaibai() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        minrep(i, s);
    }
    int q;
    cin >> q;
    while(q--){
        int u, v;
        cin >> u >> v;
        if(hashs[u] == hashs[v]){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
    }
}

int main(void) {
    int T = 1;
    ios::sync_with_stdio(0);
    cin >> T;
    while (T--) {
        kaibai();
    }
}

H - Umamusume

SOLUTION

骗骗题，仔细分析一下就会发现商店中很多道具是多余的（bugaibaibugai秒了）。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1000000007;
int quick_pow(int x,int n) {
    int res=1;
    while (n) {
        if (n&1) res=res*x%p;
        n>>=1;
        x=x*x%p;
    }
    return res;
}
int n,k,ans;
void kaibai(){
    cin >> n >> k;
    if (n<=2) {
        cout << n*15 << endl;
        return;
    }
    if (n%2==0) {
        cout << (n/2*15+15)%p << endl;
        return;
    }
    if (n<6) {
        cout << (n/2*15+15)%p << endl;
        return;
    }
    int x=n/6;
    ans=n/2*15+15;
    int a=(p+1-quick_pow(1-k,x)%p)%p;
    int b=(p+p+1-quick_pow(1-k,x)-quick_pow(1-k,x-1)*k%p*x%p)%p;
    int c=(1-(1-a+p)*(1-b)%p+p)%p;
    int d=a;//if and only if exist
    int e=b*(1-d+p)%p;
    int f=(p+1-d)*quick_pow((1+p-k),x-1)%p*x%p*k%p;
    ans+=c*((d*7+e*6+f*3)%p)%p;
    ans%=p;
    ans+=p;
    ans%=p;
    cout << ans << endl;
}
signed main(){
    int T=1;
    cin>>T;
    while(T--){
        kaibai();
    }
}

I - Assertion

SOLUTION

签到题

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
void kaibai(){
    int d,n,m,i,j,x,y,l,r,mid,ans=0;
    cin>>m>>n>>d;
    if((n+m-1)/m>=d) cout<<"Yes\n";
    else cout<<"No\n";
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        kaibai();
    }
}

J - Easy problem I

SOLUTION

关键在于题目中询问的 ，也就是说一旦某次操作是 ，那么之后每次都是 。

那么就可以用势能线段树维护这个东西。具体来说，需要把要维护的东西分为两部分，一部分是未做过取负操作的 $a$，另一部分是已经做过至少一次取负操作的 $a$。

对于第一部分，可以维护最小值、区间中处于该部分的个数、区间和以及减法的懒标记。

对于第二部分，可以维护区间和、区间中处于该部分的个数、以及加法和乘法的懒标记（将取负视作乘上 $-1$）。

那么在对某个区间操作时，若第一部分的最小值比 $x$ 大，则可以直接计算贡献（因为此次操作不会造成第一部分的个数减少），无需往下递归；否则则说明第一部分中的个数需要减少了，则需要递归到叶子将这个点从第一部分转化成第二部分，然而这个操作最多只会进行 $n$ 次，因此这么维护对于单次询问的时间复杂度是 $O(log(n))$。

因此总时间复杂度为 $O(mlog(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
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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10;
const ll inf = 1e18;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
    for(n=0;(c=gc())<'0'||c>'9';);
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
    for(n=0;(c=gc())<'0'||c>'9';);
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

int a[N];

struct Seg{
    ll sum0[N << 2], sub[N << 2], mn[N << 2], cnt0[N << 2];
    //
    ll sum1[N << 2], add[N << 2], cnt1[N << 2], mul[N << 2];

    void clearTag(int k){
        sub[k] = 0;
        add[k] = 0;
        mul[k] = 1;
    }

    void apply(int k){
        int fa = k / 2;
        sum0[k] -= sub[fa] * cnt0[k];
        mn[k] -= sub[fa];
        sub[k] += sub[fa];

        sum1[k] *= mul[fa];
        sum1[k] += add[fa] * cnt1[k];
        mul[k] *= mul[fa];
        add[k] *= mul[fa];
        add[k] += add[fa];
    }

    void pd(int k){
        apply(k << 1);
        apply(k << 1 | 1);
        clearTag(k);
    }

    void pu(int k){
        sum0[k] = sum0[k << 1] + sum0[k << 1 | 1];
        cnt0[k] = cnt0[k << 1] + cnt0[k << 1 | 1];
        mn[k] = min(mn[k << 1], mn[k << 1 | 1]);

        sum1[k] = sum1[k << 1] + sum1[k << 1 | 1];
        cnt1[k] = cnt1[k << 1] + cnt1[k << 1 | 1];
    }

    void build(int k, int l, int r){
        clearTag(k);
        if(l == r){
            sum0[k] = mn[k] = a[l];
            cnt0[k] = 1;
            cnt1[k] = 0;
            sum1[k] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        pu(k);
    }

    void upd(int k, int l, int r, int ql, int qr, int x){
        if(ql > r || qr < l) return;
        int mid = (l + r) >> 1;
        if(ql <= l && r <= qr){
            if(mn[k] > x){
                sum0[k] -= 1ll * x * cnt0[k];
                mn[k] -= x;
                sub[k] += x;

                sum1[k] *= -1;
                mul[k] *= -1;
                add[k] *= -1;
                sum1[k] += 1ll * cnt1[k] * x;
                add[k] += x;
                return;
            }
            //mn[k] = sum0[k] = a[l] <= x
            if(l == r){
                sum1[k] = x - sum0[k];
                sum0[k] = cnt0[k] = 0;
                cnt1[k] = 1;
                mn[k] = inf;
                return;
            }
        }
        pd(k);
        upd(k << 1, l, mid, ql, qr, x);
        upd(k << 1 | 1, mid + 1, r, ql, qr, x);
        pu(k);
    }

    ll qry(int k, int l, int r, int ql, int qr){
        if(ql > r || qr < l) return 0;
        if(ql <= l && r <= qr){
            return sum0[k] + sum1[k];
        }
        pd(k);
        int mid = (l + r) >> 1;
        return qry(k << 1, l, mid, ql, qr) + qry(k << 1 | 1, mid + 1, r, ql, qr);
    }
}seg;

void kaibai() {
    int n, m;
    read(n);
    read(m);
    for(int i = 1; i <= n; i++){
        read(a[i]);
    }
    seg.build(1, 1, n);
    while(m--){
        int op, l, r, x;
        read(op);
        read(l);
        read(r);
        if(op == 1){
            read(x);
            seg.upd(1, 1, n, l, r, x);
        }else{
            cout << seg.qry(1, 1, n, l, r) << '\n';
        }
    }
}

int main(void) {
    int T = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    read(T);
    while (T--) {
        kaibai();
    }
}

L - Play on Tree

SOLUTION

树上博弈结论题，再套了个简单换根dp

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>e[N];
int sg[N];
const int p=1e9+7;
ll po(ll x,ll y){
    ll b=1;
    while(y){
        if(y&1) b=b*x%p;
        y>>=1;
        x=x*x%p;
    }
    return b;
}
void dfs(int x,int f){
    sg[x]=0;
    for(auto i:e[x]){
        if(i==f) continue;
        dfs(i,x);
        sg[x]^=(sg[i]+1);
    }
}
int cnt;
void dfs2(int x,int f){
    if(sg[x]) cnt++;
    int l,r;
    for(auto i:e[x]){
        if(i==f) continue;
        l=sg[x];
        r=sg[i];
        sg[x]^=(r+1);
        sg[i]^=(sg[x]+1);
        dfs2(i,x);
        sg[x]=l;
        sg[i]=r;
    }
}
void kaibai(){
    int d,n,m,i,j,x,y,l,r,mid,ans=0;
    cin>>n;
    for(i=1;i<=n;i++) e[i].clear();
    for(i=1;i<n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    cnt=0;
    dfs(1,0);
    dfs2(1,0);
    cout<<cnt*po(n,p-2)%p<<'\n';
}
int main(void){
    int T=1;
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        kaibai();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可