2022“杭电杯” 中国大学生算法设计超级联赛（7）2 3 6 8 题解

1002-Independent Feedback Vertex Set

题目大意：
有一个图，初始时是三个点，并且三个点形成一个环。之后每加入一个点，新的点会和原来的两个点各连一条边，也就是每加入一个点，图中就会多一个三元环。每个点都有一个权值。
现在要把所有的点分成两个集合，一个集合满足独立集，另一个集合能够形成一个森林。要求独立集的点权之和最大。

思路：
这个问题的原型是一个NP难问题，但是这个问题的图有点特殊，每个点都在一个三元环中，因此每个三元环里一定且只有一个点被划分到独立集中，否则森林的条件无法满足，而选两个点的话独立集的条件则无法满足。
那么可以对点进行染色，当一个三元环的两个点颜色确定后第三个点的颜色也能确定了。
最后答案就是选取一种颜色的点加入到独立集中，比较三种答案取最大值即可。
首先将初始的三个点分别染成1、2、3。之后每加入一个点，都可以直接确定其颜色。

AC代码：

#include 
const int N = 1e5 + 5;
using namespace std;

int color[N], w[N];

void solve()
{
    int n, u, v;
    long long ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    color[1] = 1;
    color[2] = 2;
    color[3] = 3;
    for (int i = 4; i <= n; i++)
    {
        cin >> u >> v;
        switch (color[u] + color[v])
        {
        case 3: // 1+2
            color[i] = 3;
            break;
        case 4: // 1+3
            color[i] = 2;
            break;
        case 5: // 2+3
            color[i] = 1;
            break;
        default:
            break;
        }
    }
    for (int c = 1; c <= 3; c++)
    {
        long long tmp = 0;
        for (int i = 1; i <= n; i++)
            if (color[i] == c) tmp += w[i];
        ans = max(tmp, ans);
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> 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
45
46
47
48
49
50
51
52

1003-Counting Stickmen

题目大意：
火柴人的组成如图红色部分所示

头是2
身体是3-5
两个手臂是4-6、9-10
脚是7、8
给定一个图，问图中能组成多少个火柴人。

思路：
很容易能想到枚举身体的那条边，然后计算每条边作为身体时的火柴人数量。
假设靠近头部的点为x，靠近脚部的点为y。每个点的度数为deg[i]。
头的组成方案有deg[x]-3种，也就是去掉了两个手臂的点和y点。
脚的组成方案有(deg[y] - 1) * (deg[y] - 2) / 2种，也就是在y连接的点中（除x外）选取两个点。
手臂的组成方案需要首先求得与x距离为2的点数量（和x之间隔了一个点，记为deg2[x]），再去掉作为脚的点，然后从这些点里面选取两个点作为手。但是手不能位于同一个"臂"下面，因此还要减去这种不符合的情况才是手臂的方案数。
那么这条边作为身体时的方案数就是头、脚、手臂的方案数相乘。
deg2可以O(n)预处理，在处理deg2的同时还能计算每个点作为靠近头部那个点时，两个手位于同一个臂下的情况数，记为s。
预处理完这些后枚举每条边计算即可。复杂度为O(n+m)

AC代码：

#include 
const int N = 5e5 + 5;
const int mod = 998244353;
using namespace std;

vector<int> g[N];
long long deg2[N], s[N];
long long cal(long long x)
{
    if (x <= 1) return 0;
    return x * (x - 1) / 2 % mod;
}

void solve()
{
    int n, u, v;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        g[i].clear();
        deg2[i] = s[i] = 0;
    }
    for (int i = 2; i <= n; i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) //预处理
    {
        for (auto y : g[i])
        {
            deg2[i] += g[y].size() - 1;
            s[i] += cal(g[y].size() - 1);
        }
        s[i] %= mod;
    }
    long long ans = 0, head, arm, foot;
    for (int x = 1; x <= n; x++)
    {
        if (g[x].size() < 4) continue;
        head = g[x].size() - 3;
        for (auto y : g[x])
        {
            if (g[y].size() < 3) continue;
            foot = cal(g[y].size() - 1);
            arm = (cal(deg2[x] - g[y].size() + 1) + foot - s[x] + mod) % mod;
            ans += head * arm % mod * foot % mod;
        }
    }
    cout << ans % mod << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

1006-Sumire

题目大意：
f(x, B, d)表示在B进制下的数字x中d在所有位上出现的次数。
给定K、B、d、l、r，求下面这个式子的值，对结果模1e9+7（在本题中0⁰=0）

思路：
很显然是一道数位dp的题目，并且这题要对f取k次方，但是f的取值范围是很小的，大概在0~63之间，因此我们可以把f值相同的情况都找出来，然后一起进行幂的计算。
以往的数位dp在状态表示上会引入当前位，但是这道题的进制很大，这么做显然不太现实。
不过，这道题对于每次输入，只要求一个区间即可，所以在状态的表示上可以将当前位替换成当前位是否到达上限，这样就只有两种状态需要表示了。
同时为了找出f值相同的所有情况，还要再引入d出现的次数。
为了处理前导0，再引入是否有前导0的状态。
最后就可以用dp[i][j][0/1][0/1]来表示已经统计了前i位有j位是d且当前位有/无限制，有/无前导0的方案数
代码参考了一下这篇博客

AC代码：

#include 
using namespace std;
long long k, b, d;
const int N = 65, mod = 1e9 + 7;
long long dp[N][N][2][2]; // dp[i][j][1/0][1/0]表示已经统计了前i位有j位是d且当前位有/无限制，有/无前导0的方案数
long long digit[N];
long long ksm(long long base, long long power)
{
    if (base == 0) return 0; //题目要求0^0=0
    long long result = 1;
    base %= mod;
    while (power)
    {
        if (power & 1)
            result = (result * base) % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}
long long dfs(int pos, int cnt, int limit, int lead)
{
    if (!pos) return ksm(cnt, k);
    if (dp[pos][cnt][limit][lead] != -1) return dp[pos][cnt][limit][lead];
    int up = limit ? digit[pos] : (b - 1);
    long long res = 0;
    if (d == up)
    {
        res += dfs(pos - 1, cnt + 1, limit, 0); //填d
        if (lead)
        {
            res += dfs(pos - 1, cnt, 0, 1);                  //填0
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //不填up和0
        }
        else
            res += up * dfs(pos - 1, cnt, 0, 0) % mod; //不填d
    }
    else if (d == 0)
    {
        res += dfs(pos - 1, cnt, limit, 0);              //填up
        res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //填up和d
        if (lead)
            res += dfs(pos - 1, cnt, 0, 1); //填0
        else
            res += dfs(pos - 1, cnt + 1, 0, 0); //填d
    }
    else if (up > d)
    {
        res += dfs(pos - 1, cnt + 1, 0, 0) + dfs(pos - 1, cnt, limit, 0); //填d和up
        if (lead)
        {
            res += dfs(pos - 1, cnt, 0, 1);                  //填0
            res += (up - 2) * dfs(pos - 1, cnt, 0, 0) % mod; //不填up和d和0
        }
        else
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //不填up和d
    }
    else // up
    {
        res += dfs(pos - 1, cnt, limit, 0); //填up
        if (lead)
        {
            res += dfs(pos - 1, cnt, 0, 1);                  //填0
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //不填0和up
        }
        else
            res += up * dfs(pos - 1, cnt, 0, 0) % mod; //不填up
    }
    return dp[pos][cnt][limit][lead] = (res % mod);
}
long long cal(long long x)
{
    memset(dp, -1, sizeof dp);
    int pos = 0;
    while (x)
    {
        digit[++pos] = x % b;
        x /= b;
    }
    return dfs(pos, 0, 1, 1);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    long long l, r;
    while (T--)
    {
        cin >> k >> b >> d >> l >> r;
        cout << (cal(r) - cal(l - 1) + mod) % mod << "\n";
    }
    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

1008-Triangle Game

题目大意：
有一个三角形，两个人每次可以选择一条边减去不少于1的长度，当谁操作后使得三角形构不成就输了。现在给出三条边的长度，问哪个人会获胜。

思路：
做多了这种类似取石子的题目变种，发现大部分都和异或是否为0有关。
那么大胆地猜测：

• 当(a-1)⊕(b-1)⊕(c-1) = 0时为必败态
• 当(a-1)⊕(b-1)⊕(c-1) != 0时为必胜态

下面给出证明：
位于必败态时有两种情况：

• 一条边为1，另外两条边相等，此时操作后必构不成三角形
• 三条边都不为1，此时改变一条边之后必会使得(a-1)⊕(b-1)⊕(c-1) != 0

因此当必败态还能操作时，一定会转移到必胜态。

位于必胜态时：
设r=(a-1)⊕(b-1)⊕(c-1) ，下面三个式子一定有一个能成立

• r⊕(a-1)<(a-1)
• r⊕(b-1)<(b-1)
• r⊕(c-1)<(c-1)

对于符合的式子，操作对应的边就能使异或和为0

不过这种题目大多数还是猜一个结论然后代入几组数据验证比较快，在赛场上推不太现实。

AC代码：

#include 
using namespace std;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int a, b, c, T;
    cin >> T;
    while (T--)
    {
        cin >> a >> b >> c;
        if ((a - 1) ^ (b - 1) ^ (c - 1))
            cout << "Win\n";
        else
            cout << "Lose\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18