2022 年杭电多校第七场补题记录

A Bowling

题意：给定平面上一 $n$ 顶点凸多边形，和 $m$ 个点，$q$ 次询问，每次给定一个方向向量 $\vec{v}$，问该凸多边形以该方向向量移动会碰到几个点。$n,m,q\le 1\times 10^5$。

解法：不妨考虑点向凸包移动。则一个点会撞击到凸包等效于该方向向量处于该点看凸包的视角范围内。因而对每个点以 $\mathcal{O}(\log n)$ 的复杂度求出它到凸多边形的切线，记录每个点的视角范围（必然为至多两个连续区间，可以根据 $x$ 轴负向为分界点），则变成一区间问题——查询对应的方向向量被多少个区间覆盖。使用前缀和即可。总复杂度 $\mathcal{O}(m\log n+q)$。

vector<int> solve(const Convex &ball, const vector<Point> &pins, const vector<Point> &ques)
{
    auto dirs=ques; dirs.reserve(ques.size()+pins.size()+pins.size());
    vector<pair<size_t,size_t>> tans; tans.reserve(pins.size());
    for (const auto &pin:pins)
    {
        const auto t=ball.tangent(pin);
        const auto i=t.first,j=t.second;
        tans.push_back(t);
        dirs.push_back(pin-ball.p[j]);
        dirs.push_back(pin-ball.p[i]);
    }
    sort(dirs.begin(),dirs.end(),argcmp());
    const auto eq=[&](const Point &u,const Point &v){return u*v>eps && abs(u^v)<=eps;};
    dirs.erase(unique(dirs.begin(),dirs.end(),eq),dirs.end());
    const int siz=dirs.size();
    vector<int> diff(siz),sum(siz);
    for (size_t i=0;i<pins.size();i++)
    {
        const auto pin=pins[i];
        const auto t=tans[i];
        const Point u=pin-ball.p[t.second],v=pin-ball.p[t.first];
        const int l=lower_bound(dirs.begin(),dirs.end(),u,argcmp())-dirs.begin();
        const int r=lower_bound(dirs.begin(),dirs.end(),v,argcmp())-dirs.begin();
        if (l<=r)
        {
            diff[l]++;
            if (r+1<siz) diff[r+1]--;
        }
        else
        {
            diff[l]++; diff[0]++;
            if (r+1<siz) diff[r+1]--;
        }
    }
    partial_sum(diff.begin(),diff.end(),sum.begin());
    vector<int> ans; ans.reserve(ques.size());
    for (const auto &que:ques)
    {
        const int i=lower_bound(dirs.begin(),dirs.end(),que,argcmp())-dirs.begin();
        ans.push_back(sum[i]);
    }
    return ans;
}
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

B Independent Feedback Vertex Set

题意：通过如下方式构造一个 $n$ 个点的图：首先有三点 $1,2,3$，互相相连；此外再依次加入 $n-3$ 个点，每个点 $i$ 恰与之前已经直接连通的两点 $u,v$ 构成三元环——即每加入一个点新增两条边 $(u,i),(v,i)$。在这个图上，每个点有一个权值 $a_i$，要求从该图中选出一个点的子集 $V$，使得 $V$ 中任意两点没有直接的边相连，且 $U/V$ 为一个森林，最大化 $V$ 中点权值和。$n\le 5\times 10^5$。

解法：容易注意到，$V$ 集合必然包含每个三元环中恰好一个点，因而 $1,2,3$ 中恰好只能选一个，这时对图做三染色（让每个三元环三个点颜色均不相同）即可。总时间复杂度 $\mathcal{O}(n)$。

#include 
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<vector<int>> vis(n, vector<int>(3, 0));
        vector<long long> a(n), f(3, 0);
        for (int i = 0; i < n;i++)
            scanf("%lld", &a[i]);
        for (int i = 0; i < 3;i++)
        {
            vis[i][i] = 1;
            f[i] = a[i];
        }
        for (int i = 3, u, v; i < n; i++)
        {
            scanf("%d%d", &u, &v);
            u--;
            v--;
            for (int j = 0; j < 3; j++)
                if (!vis[u][j] && !vis[v][j])
                {
                    vis[i][j] = 1;
                    f[j] += a[i];
                }
        }
        printf("%lld\n", max({f[0], f[1], f[2]}));
    }
    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
24
25
26
27
28
29
30
31
32
33
34

C Counting Stickmen

题意：给定一棵 $n$ 个点以 $1$ 为根的树，问树上节点能构成火柴人的有多少个。$n\le 5\times 10^5$。火柴人如下图红色点所示：

解法：枚举图中 $3$ 号点（脖子）的情况。从该点开始，任意与之相连的点均可做头，与之相连的度数大于等于 $2$ 的可以做手，度数大于等于 $3$ 的可以做身体。因而总的方案为选一个做头，选两个做手，选一个做身体。但是存在一个情况：翻花手，即两条手臂相同，只是手不同，例如以 $3-5-7$ 和 $3-5-8$ 做手，这是不允许的。那么这种情况容易注意到其实就是身体，扣除这种情况即可。

在实际的操作中，维护一个 $\mathrm{head}$ 数组表示以 $i$ 节点为脖子，头有几个，$\mathrm{body}$ 表示以 $i$ 为脖子，身体有几种。枚举每个度大于等于 $4$ 的节点作为脖子进行计算即可。

#include 
using namespace std;
const int N = 500000;
const long long mod = 998244353, inv2 = (mod + 1) / 2;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[2 * N + 5];
int cnt, headers[N + 5];
void add(int from, int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
long long C(long long x)
{
    return x * (x - 1) % mod * inv2 % mod;
}
int deg[N + 5];
long long ans, body[N + 5], hand[N + 5];
void dfs(int place, int father)
{
    long long b = 0, h = 0;//当前点连出的所有的头、手方案和
    for (int i = headers[place]; i; i = que[i].next)
    {
        b = (b + body[que[i].to]) % mod;
        h = (h + hand[que[i].to]) % mod;
        if (que[i].to != father)
            dfs(que[i].to, place);
    }
    if (deg[place] < 4)
        return;
    for (int i = headers[place]; i; i = que[i].next)
        ans = (ans + body[que[i].to] * (C(h - hand[que[i].to]) - (b - body[que[i].to]) + mod) % mod * (deg[place] - 3) % mod) % mod;
        //身体*手*头，手的表示为(所有的手方案 - 翻花手的方案)
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for (int i = 1, u, v; i < n;i++)
        {
            scanf("%d%d", &u, &v);
            deg[u]++;
            deg[v]++;
            add(u, v);
            add(v, u);
        }
        for (int i = 1; i <= n;i++)
        {
            hand[i] = deg[i] - 1;
            if (deg[i] > 2)
                body[i] = C(deg[i] - 1);
        }
        dfs(1, 1);
        printf("%lld\n", ans);
        cnt = ans = 0;
        for (int i = 1; i <= n;i++)
            deg[i] = headers[i] = hand[i] = body[i] = 0;
    }
    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
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

D Black Magic

题意：有 $E$ 种两面全白的方块，$L$ 种左黑右白的方块，$R$ 种左白右黑的方块，$B$ 种两侧都黑的方块。现在将他们重新排列，相邻两侧（左侧方块的右侧和右侧方块的左侧）若均为黑色和两方块合并变成一个。方块不能旋转，问最多和最少能变成几个方块。

解法：注意到 $B+L=L$，$R+B=R$，$L+R=E$。对于最少方块数目，则必然是 $L,R$ 成对变成一个 $E$。因而答案为 $\min (L,R)+E$。若无 $L,R$，则所有 $B$ 合成为一个，答案为 $E+[B]$。

对于最多方块数目，必然是左侧全部放 $L$，右侧全部放 $R$，最后 $EBEB$ 的摆放。注意 $L,R$ 交接处有一个放 $B$ 而不会合并的机会。

#include 
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        long long e, l, r, b;
        scanf("%lld%lld%lld%lld", &e, &l, &r, &b);
        if(l + r == 0)
            printf("%lld ", e + (b != 0));
        else
            printf("%lld ", max(l, r) + e);
        if(b < e)
            printf("%lld\n", l + r + e + b);
        else if(b == e)
            printf("%lld\n", l + r + 2 * e);
        else
            printf("%lld\n", l + r + 2 * e + 1);
    }
    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

F Sumire

题意：给定 $l,r,k,B,d$，计算 $\sum _{i=l}^r{f}^k(i,B,d)$，其中 $f(i,B,d)$ 表示数字 $i$ 在 $B$ 进制下数码 $d$ 出现次数，不含前导零。$T$ 组测试数据，$1\le l\le r\le 1\times 10^{18}$，$0\le d<B\le 1\times 10^9$，$0\le k\le 10^9$，定义 $0^0=0$。

解法：基础数位 dp。$g_{i,j,0/1,0/1}$ 表示当前在 $B$ 进制下已经考虑到了第 $i$ 位，已经出现了 $j$ 个数码 $d$，是否有前导零，是否顶住上界，枚举当前位置应当填什么（$0,d,up$ 和其他四种情况）进行转移即可。

#include 
using namespace std;
const int N = 60;
const long long mod = 1000000007;
long long power(long long a, long long x)
{
    if(!a)
        return 0;
    long long ans = 1;
    while(x)
    {
        if (x & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long f[N + 5][N + 5][2][2];
int a[N + 5], d, b, k;
long long dfs(int place, int cnt, int zero, int lim)
{
    if(!place)
        return f[place][cnt][zero][lim] = power(cnt, k);
    if(f[place][cnt][zero][lim] != -1)
        return f[place][cnt][zero][lim];
    int up = !lim ? b - 1 : a[place];
    long long now = 0;
    if (d <= up)
    {
        if (d)
        {
            now += dfs(place - 1, cnt, zero, 0);                //填入零,此时d不为0
            now += dfs(place - 1, cnt + 1, 1, lim & (d == up)); //填入d,此时d不为0
        }
        else
            now += dfs(place - 1, cnt + zero, zero, lim & (d == up)); // 填入d,此时d=0
        if(d < up)
            now += dfs(place - 1, cnt, 1, lim);       //填入up,此时d不为up
        int ava = max({0, d - 1, up - 1 - (d != 0)}); //填入不是d、不是up、不是0的数字
        if (ava)
            now += ava * dfs(place - 1, cnt, 1, 0) % mod;
    }
    else
    {
        if (up)
            now += dfs(place - 1, cnt, zero, 0);           //填入0,此时up不为0，不顶着上界
        now += dfs(place - 1, cnt, (zero || up > 0), lim); //填入上界，顶着上界
        int ava = max(0, up - 1);
        if(ava)
            now += ava * dfs(place - 1, cnt, 1, 0) % mod;//填入非0、非up的其他数字
    }
    return f[place][cnt][zero][lim] = now % mod;
}
long long cal(long long n)
{
    if(!n)
        return 0;
    memset(f, -1, sizeof(f));
    memset(a, 0, sizeof(a));
    int pos = 0;
    while(n)
    {
        a[++pos] = n % b;
        n /= b;
    }
    return dfs(pos, 0, 0, 1);
}
int main()
{
    int t;
    long long l, r;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%lld%lld", &k, &b, &d, &l, &r);
        printf("%lld\n", (cal(r) - cal(l - 1) + mod) % mod);
    }
    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
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

G Weighted Beautiful Tree

题意：给定一个 $n$ 个点的树，树上每个点有权值 $w_i$ 和费用 $c_i$ 表示修改它的代价，即将其权值修改为 $w_i^{\prime }$ 的代价为 $c_i|w_i^{\prime }-w_i|$。树上每条边有权值 $w{e}_i$，连接了 $u_i,v_i$。现在要求树上每条边的权值 $w{e}_i$ 满足 $w{e}_i\in [\min (w_{u_i}^{\prime },w_{v_i}^{\prime }),\max (w_{u_i}^{\prime },w_{v_i}^{\prime })]$，求最小修改代价。$n\le 1\times 10^5$。

解法：考虑 $f_{u,0/1}$ 表示 $u$ 节点修改后，作为它连向父亲的边的最小值（即 $w_u^{\prime }\le w{e}_{u,f{a}_u}$，用 $0$ 记录）还是最大值（用 $1$ 记录）。考虑 $u$ 下全部的儿子 $v$，根据 $(u,v)$ 和它连向它父亲的边权值可以将 $u$ 的可选值域划分为 $c{h}_u+1$ 段，在每一段它的转移是确定的，仅在恰好为边权的时候有两种情况。因而对 $u$ 连向它儿子的边权从小到大的排序，然后从小到大的维护最小和值即可。对于边权相同的边需要一起处理。

#include 
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 100000;
struct line
{
    int to;
    long long w;
    line(int _to, long long _w)
    {
        to = _to;
        w = _w;
    }
    bool operator<(const line &b)const
    {
        return w < b.w;
    }
};
vector<line> edge[N + 5];
long long pre[N + 5], suf[N + 5];
int tofather[N + 5];
long long f[N + 5][3], wn[N + 5], c[N + 5];
int id(long long we, long long wn)
{
    if (we == wn)
        return 2;
    else
        return wn < we; //和f[place]中的定义相反，因为这是从父亲视角去观察
}
void dfs(int place, int father)
{
    f[place][0] = f[place][1] = inf;
    for (auto i : edge[place])
        if (i.to != father)
        {
            tofather[i.to] = i.w;
            dfs(i.to, place);
        }
    //以下为wn不变的情况
    if (wn[place] <= tofather[place])
    {
        f[place][0] = 0;
        for (auto i : edge[place])
            if (i.to != father)
                f[place][0] += f[i.to][id(i.w, wn[place])];
    }
    if (wn[place] >= tofather[place])
    {
        f[place][1] = 0;
        for (auto i : edge[place])
            if (i.to != father)
                f[place][1] += f[i.to][id(i.w, wn[place])];
    }
    long long base = 0;//以tofather为最终wn
    for (auto i : edge[place])
        if (i.to != father)
            base += f[i.to][id(i.w, tofather[place])];
    f[place][0] = min(f[place][0], base + abs(wn[place] - tofather[place]) * c[place]);
    f[place][1] = min(f[place][1], base + abs(wn[place] - tofather[place]) * c[place]);
    for (int i = 0; i < edge[place].size(); i++)
    {
        pre[i] = (edge[place][i].to == father ? 0 : f[edge[place][i].to][0]);
        if (i)
            pre[i] += pre[i - 1];
    }
    suf[edge[place].size()] = 0;
    for (int i = edge[place].size() - 1; i >= 0;i--)
        suf[i] = suf[i + 1] + (edge[place][i].to == father ? 0 : f[edge[place][i].to][1]);
    for (int i = 0; i < edge[place].size();)//枚举每条边（含自己的wn）作为最终wn的情况
    {
        int j = i;
        long long equ = 0;
        while (j < edge[place].size() && edge[place][i].w == edge[place][j].w)
        {
            equ += f[edge[place][j].to][2];
            j++;
        }
        if (edge[place][i].w <= tofather[place])
            f[place][0] = min(f[place][0], equ + (i ? pre[i - 1] : 0) + suf[j] + c[place] * abs(wn[place] - edge[place][i].w));
        if (edge[place][i].w >= tofather[place])
            f[place][1] = min(f[place][1], equ + (i ? pre[i - 1] : 0) + suf[j] + c[place] * abs(wn[place] - edge[place][i].w));
        i = j;
    }
    f[place][2] = min(f[place][0], f[place][1]);
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n;i++)
            scanf("%lld", &c[i]);
        for (int i = 1; i <= n;i++)
            scanf("%lld", &wn[i]);
        for (int i = 1, u, v, w; i < n; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            edge[u].emplace_back(v, w);
            edge[v].emplace_back(u, w);
        }
        for (int i = 1; i <= n;i++)
            sort(edge[i].begin(), edge[i].end());
        dfs(1, 1);
        printf("%lld\n", f[1][2]);
        for (int i = 1; i <= n;i++)
            edge[i].clear();
    }
    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
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

H Triangle Game

题意：给定三个数字 $a,b,c$，初始时它们可以围成三角形。Alice 和 Bob 二人轮流将其中一个数字减小一个正整数，使得这三个数字仍能组成三角形三边，谁不能操作谁输。问输赢。$a,b,c\le 1\times 10^9$。

解法：不妨令 $a\le b\le c$。若 $a=1$ 则先手必败。因而谁都不会让 $a,b,c$ 率先出现 $1$，同时他们可以下对称棋，因而游戏可以规约到 Nim 游戏，判定方法即是 $(a-1)\oplus (b-1)\oplus (c-1)$ 是否为 $0$。

#include 
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 2e5 + 5;
using ll = int64_t;
int a;
void Solve() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    puts((--a) ^ (--b) ^ (--c) ? "Win" : "Lose");
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

I Counting Good Arrays

题意：求出长度不超过 $n$，最大值不超过 $m$ 且满足 $a_{i-1}|a_i$ 的序列 { a n } \{a_n\} {an​} 个数。$n,m\le 1\times 10^9$。

解法：令 $f_{m,i}$ 表示最大值不超过 $m$，严格递增序列长度为 $i$ 的个数，则：
$$f_{m,i}\leftarrow \sum _{d=2}^m{f}_{\lfloor \frac{m}{d}\rfloor ,i-1}$$
其具体含义为，对于一个最大值不超过 $m$ 的长度为 $i$ 的序列，$a_i$ 必然是通过 $a_{i-1}$ 乘以一个值 $d$ 得到的，而 $a_i\le m$ 可得 $a_{i-1}\le \lfloor \frac{m}{d}\rfloor$，且这个 $d\ge 2$。不难发现，$i\le \log m$，因而总的 dp 数组仅有 $\sqrt{m}\log m$ 个状态。但是如果朴素转移，从小到大的递推，则每个状态需要 $O(m\log m)$ 的复杂度，显然是不可接受的。这时考虑使用类似于 min_25 筛第一部分的递推，并对 $\sqrt{m}$ 个状态进行 $O(1)$ 的数组映射存储，即可将本步骤优化到 $O(m^{\frac{3}{4}})$。

接下来是由严格递增序列恢复到原序列。考虑从中间插入数字，若原序列仅 $i$ 个数字，则增补到不超过 $n$ 个数字的总方案数为：
∑ k = i n ( k − 1 i − 1 ) = ∑ k = i n ( k − 1 k − i ) = ∑ k = 0 n − i ( i + k − 1 k ) = ( n i )

==​k=i∑n​(i−1k−1​)k=i∑n​(k−ik−1​)k=0∑n−i​(ki+k−1​)=(in​)​

即考虑将原序列的 $i-1$ 个数字插入到长度为 $k-1$ 的数组中（第一个数字钦定放第一位），并对 $k$ 求和，可得方案为 $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$，则答案为 $\sum _{i=1}^{\log m}{f}_{m,i}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$。

说明：下面代码中的 $f[i][m]$ 数组其实是推导过程中的 $f_{m,i}\left(\genfrac{}{}{0ex}{}{m}{i}\right)$。

#include 
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int P = 1e9 + 7, Len = 35;
using ll = int64_t;
#define inc(a, b) (((a) += (b)) >= P ? (a) -= P : 0)
#define dec(a, b) (((a) -= (b)) < 0 ? (a) += P : 0)
#define mul(a, b) (ll(a) * (b) % P)
int n, m, N, sqrtm, k, inv[Len];
int id(int x) { return x <= sqrtm ? x : k - m / x; }
vector<int> w, C, f[Len];
int dp(int l, int p) {
    if (l > N) return 0;
    if (~f[l][id(p)]) return f[l][id(p)];
    int res = C[l];
    for (int i = l ? 2 : 1, j; i <= p; i = j + 1) {
        j = p / (p / i);
        res = (res + ll(j - i + 1) * dp(l + 1, p / i)) % P;
    }
    return f[l][id(p)] = res;
}
void Solve() {
    scanf("%d%d", &n, &m);
    k = 1, sqrtm = sqrt(m) + 1;
    w.resize(2 * sqrtm);
    for (int i = 1; i <= m; ++i, ++k)
        w[k] = i = m / (m / i);
    N = min(n, __lg(m) + 1);
    fp(i, 0, N) f[i].assign(w.size(), -1);
    C.resize(N + 1), C[0] = 1;
    fp(i, 1, N) C[i] = (ll)C[i - 1] * (n - i + 1) % P * inv[i] % P;
    C[0] = 0;
    printf("%d\n", dp(0, m));
}
int main() {
    inv[1] = 1;
    for (int i = 2; i < Len; ++i) inv[i] = mul(P - P / i, inv[P % i]);
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

J Connectivity of Erdős-Rényi Graph

题意：$q$ 次询问，每次给定一个 $n$ 个点的无向完全图 $K_n$，其中每条边以 $\frac{a}{b}$ 的概率产生，问图的连通块期望个数。$q\le 1\times 10^5$，$n\le 5\times 10^5$。

解法：（待补）