2024年蓝桥杯省赛C/C++大学A组代码

发表于 更新于 分类于 阅读次数： 本文字数： 7.3k 阅读时长 ≈ 26 分钟

[蓝桥杯 2024 省 A] 艺术与篮球

题目描述

小蓝出生在一个艺术与运动并重的家庭中。
妈妈是位书法家，她希望小蓝能通过练习书法，继承她的艺术天赋，并练就一手好字。爸爸是一名篮球教练，他希望小蓝能通过篮球锻炼身体，培养运
动的激情和团队合作的精神。
为了既满足妈妈的期望，又不辜负爸爸的心意，小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 YYYYMMDD 的格式
转换成一个 位数，然后将这 位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过 ，他就去练习篮球；如果总笔画数不超过 ，他就去练习书法。
例如，在 年 月 日这天，日期可表示为一个 位数字 ，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 ，因此在这天，小蓝会去练习书法。
以下是汉字的笔画数对照表：

汉字 笔画数 汉字 笔画数
零 五
一 六
二 七
三 八
四 九

现在，请你帮助小蓝统计一下，在 年 月 日到 年 月 日
这段时间内，小蓝有多少天是在练习篮球？

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解法

模拟

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<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int bh[]={13,1,2,3,5,4,4,2,2,2};
int bihua[32]={0};
int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int res=0;
int main() {
    int ans=0;
    for(int i=0;i<=31;i++){
        bihua[i]=bh[i/10]+bh[i%10];
    }
    int y;
    for(y=2000;y<=2023;y++){
        int year_days=bihua[y/100]+bihua[y%100];
        if(y%4==0)
            month[2]=29;
        else
            month[2]=28;
        for(int m=1;m<=12;m++){
            int mon_days=year_days+bihua[m];
            for(int d=1;d<=month[m];d++){
                if(mon_days+bihua[d]>50)
                    ans++;
            }
        }
    }
    month[2]=29;
    month[4]=13;
    int year_days=bihua[y/100]+bihua[y%100];
    for(int m=1;m<=4;m++){
        int mon_days=year_days+bihua[m];
        for(int d=1;d<=month[m];d++){
            if(mon_days+bihua[d]>50)
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//3228

[蓝桥杯 2024 省 A] 五子棋对弈

题目描述

“在五子棋的对弈中，友谊的小船说翻就翻？” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着 “友谊第一，比赛第二” 的宗旨，决定在一块 的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局） 作为彼此友谊的见证。
比赛遵循以下规则：

  1. 棋盘规模：比赛在一个 的方格棋盘上进行，共有 个格子供下棋使用。
  2. 棋子类型：两种棋子，黑棋与白棋，代表双方。小蓝持白棋，小桥持黑棋。
  3. 先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
  4. 轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
  5. 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
  6. 平局条件：当所有 个棋盘格都被下满棋子，而未决出胜负时，游戏以平局告终。

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况（终局不同看成不同情况，终局相同而落子顺序不同看成同一种情况），既确保棋盘下满又保证比赛结果为平局。

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解法

dfs，模拟

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
#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
using ll=unsigned long long;
int arr[26];
/*
 * 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
 */
ll ans=0;
void dfs(int d,int b){
    if(b>13||d-b>13)
        return;
    if(d==26){
        bool ok=false;
        for(int i=7;i<=25;i+=6)
            if(arr[1]!=arr[i]){
                ok=true;
                break;
            }
        if(ok)
            ans++;
        return;
    }
    for(int i=0;i<=1;i++){
        arr[d]=i;
        if(d%5==0){
            bool ok=false;
            for(int j=1;j<=4;j++){//0,1,2,3,4
                if(arr[d]!=arr[d-j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        if(d==21){
            bool ok=false;
            for(int j=9;j<=21;j+=4){//5,9,13,17,21
                if(arr[5]!=arr[j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        if(d>=21){
            bool ok=false;
            for(int j=5;j<=20;j+=5){
                if(arr[d]!=arr[d-j]){
                    ok=true;
                    break;
                }
            }
            if(!ok)
                continue;
        }
        dfs(d+1,b+i);
    }
}
int main() {
    dfs(1,0);
    cout<<ans<<endl;
}
//3126376

[蓝桥杯 2024 省 A] 训练士兵

题目描述

在蓝桥王国中，有 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 名士兵来说，进行一次训练所需的成本为 枚金币，而要想成为顶尖战士，他至少需要进行 次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

输入格式

输入的第一行包含两个整数 和 ，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。
接下来的 行，每行包含两个整数 和 ，用一个空格分隔，表示第 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出格式

输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

样例 #1

样例输入 #1

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

样例输出 #1

1
16

提示

花费金币最少的训练方式为：进行 次组团训练，花费 枚金币，此时士兵 已成为顶尖战士；再花费 枚金币，让士兵 进行两次训练，成为顶尖战士。总花费为 。

对于 的评测用例，，，。

对于所有评测用例，，，。

解法

按照需要训练数，从多往少贪心

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
#include <bits/stdc++.h>
#define pay second
#define num first
using namespace std;
using ll = long long;
#define int long long // 十年oi一场空，不开 long long见祖宗
typedef pair<int, int> pp;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr); // 正式比赛不要用这两行，用scanf和printf
    int n, s;
    cin >> n >> s;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].pay >> arr[i].num;
    }
    sort(arr.begin(), arr.end());
    int single_paid = 0, sum = 0, i;
    for (i = n - 1; i >= 0; i--)
    {
        single_paid += arr[i].pay;
        if (single_paid >= s) // 从第i个开始往前，集体训练更便宜，使用集体训练
        {
            break;
        }
    }
    int c;
    if (i == -1) // 全都是单独训练便宜
    {
        i = 0;
        c = 0;
    }
    else
    {
        c = arr[i].num;
    }
    sum = c * s;
    for (int j = i; j < n; j++)
    {
        sum += arr[j].pay * (arr[j].num - c);
    }
    cout << sum << endl;
    return 0;
}

[蓝桥杯 2024 省 A] 团建

题目描述

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为 和 的树，树上的每个结点上有一个正整数权值。
两个人需要从各自树的根结点 出发走向某个叶结点，从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列，两人的序列的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少。

输入格式

输入的第一行包含两个正整数 ，用一个空格分隔。
第二行包含 个正整数 ，相邻整数之间使用一个空格分隔，其中 表示第一棵树结点 上的权值。
第三行包含 个正整数 ，相邻整数之间使用一个空格分隔，其中 di 表示第二棵树结点 上的权值。
接下来 行，每行包含两个正整数 表示第一棵树中包含一条 和
之间的边。
接下来 行，每行包含两个正整数 表示第二棵树中包含一条
和 之间的边。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
2 2
10 20
10 30
1 2
2 1

样例输出 #1

1
1

样例 #2

样例输入 #2

1
2
3
4
5
6
7
8
9
10
5 4
10 20 30 40 50
10 40 20 30
1 2
1 3
2 4
3 5
1 2
1 3
3 4

样例输出 #2

1
2

提示

对于 的评测用例，；
对于所有评测用例，，，，，对于任意结点，其儿子结点的权重互不相同。

解法

对两个树进行dfs

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
#include <bits/stdc++.h>
#define N 200005
using namespace std;
using ll = long long;

int n[2], res = 0;

vector<vector<int>> node(2);
vector<vector<vector<int>>> g(2);
vector<vector<bool>> vis(2, vector<bool>(N));

void dfs(int u, int v, int d)
{
    res = max(res, d);
    map<int, int> mp; // tree2 value in tree1 value?不用map，只用双重循环过不了
    for (int i = 0, l = g[0][u].size(); i < l; i++)
    {
        int uu = g[0][u][i];
        if (vis[0][uu])
            continue;
        mp[node[0][uu]] = uu;
    }
    for (int j = 0, s = g[1][v].size(); j < s; j++)
    {
        int vv = g[1][v][j];
        if (vis[1][vv])
            continue;
        if (mp.count(node[1][vv]) > 0)
        {
            int uu = mp[node[1][vv]];
            vis[0][uu] = vis[1][vv] = true;
            dfs(uu, vv, d + 1);
        }
    }
}
signed main()
{
    for (int i = 0; i < 2; i++)
        scanf("%d", &n[i]);
    for (int i = 0; i < 2; i++)
    {
        node[i].resize(n[i] + 1);
        for (int j = 1; j <= n[i]; j++)
            scanf("%d", &node[i][j]);
    }
    int u, v;
    for (int i = 0; i < 2; i++)
    {
        g[i].resize(n[i] + 1);
        for (int j = 1; j < n[i]; j++)
        {
            scanf("%d%d", &u, &v);
            g[i][u].push_back(v);
            g[i][v].push_back(u);
        }
    }
    vis[0][1] = vis[1][1] = true;
    if (node[0][1] == node[1][1])
        dfs(1, 1, 1);
    printf("%d\n", res);
    return 0;
}

[蓝桥杯 2024 省 A] 成绩统计

题目描述

小蓝的班上有 个人，一次考试之后小蓝想统计同学们的成绩，第 名同学的成绩为 。当小蓝统计完前 名同学的成绩后，他可以从 中选出任意 名同学的成绩，计算出这 个成绩的方差。小蓝至少要检查多少个人的成
绩，才有可能选出 名同学，他们的方差小于一个给定的值 ？
提示： 个数 的方差 定义为：，其中 表示
的平均值，。

输入格式

输入的第一行包含三个正整数 ，相邻整数之间使用一个空格分隔。

第二行包含 个正整数 ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不能满足条件，输出 。

样例 #1

样例输入 #1

1
2
5 3 1
3 2 5 2 3

样例输出 #1

1
4

提示

检查完前三名同学的成绩后，只能选出 ，方差为 ；

检查完前四名同学的成绩后，可以选出 ，方差为 ，所以答案为 。

对于 的评测用例，保证 ；
对于 的评测用例，保证 ；
对于所有评测用例，保证 ，，。

解法

前缀和, 二分

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
#include <bits/stdc++.h>
#define N 100005
using namespace std;
using ll = long long;
ll n, k, t, kt;
ll a[N], v[N];
ll sum[N], sum2[N];
inline ll pow2(ll x)
{
    return x * x;
}
bool check(int x)
{
    memcpy(v + 1, a + 1, x * sizeof(ll));
    sort(v + 1, v + 1 + x);
    for (int i = 1; i <= x; i++)
    {
        sum[i] = sum[i - 1] + v[i];
        sum2[i] = sum2[i - 1] + pow2(v[i]);
    }
    for (int i = k; i <= x; i++)
    {
        double ds = 1.0 * sum[i] - sum[i - k];
        if ((1.0 * sum2[i] - sum2[i - k]) - (ds / k) * ds < kt)
        {
            return true;
        }
    }
    return false;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &k, &t);
    kt = k * t;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    int l = k, r = n, res = -1;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (check(mid))
        {
            res = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}

[蓝桥杯 2024 省 A] 因数计数

题目描述

小蓝随手写出了含有 个正整数的数组 ，他发现可以轻松地算出有多少个有序二元组 满足 是 的一个因数。因此他定义一个整数对 是一个整数对 的“因数”当且仅当 和 分别是 和 的因数。他想知道有多少个有序四元组 满足 是 的因数，其中 互不相等。

输入格式

输入的第一行包含一个正整数 。
第二行包含 个正整数 ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

1
2
5
3 6 2 2 7

样例输出 #1

1
4

提示

四元组 ： 为 的因子；
四元组 ： 为 的因子；
四元组 ： 为 的因子；
四元组 ： 为 的因子。

对于 的评测用例，；
对于 的评测用例，；
对于所有评测用例，，。

解法

样例输入：
找到不同的两对因数

1
2
5
3 6 2 2 7

能找到(1,2), (3,2), (4,2), (3,4), (4,3)五对因数（对于(i,j), i≤j)
四元组，满足四个元素不重叠的两组因数，有{(1,2),(3,4)}, {(1,2),(4,3)},{(3,4),(1,2)},{(4,3),(1,2)}

先写了个直接按题意的代码void baoli()，造出测试例。
再尝试写了一个复杂度的代码，会有一半的测试例TLE

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
/*尝试的笨代码*/
#include <bits/stdc++.h>
#define N 100005
using namespace std;
using ll = long long;
ll res = 0ll;
int n;              // 数据数量
int a[N];           // 数据
ll e_sum, e_same;   // 边的总数量,端点对应数值相同的边的总数量（双向边总数量）
ll e[N];            // 连接边的数量
void baoli();       // 暴力验证
inline ll c2(int a) // 组合数,n*(n+1)/2，因为最后结果要*2就抵消了
{
    return a * (a - 1);
}
signed main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    // baoli();
    // return 0;
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] % a[i] == 0)
            {

                if (a[i] == a[j])
                {
                    e[i] += 2;
                    e[j] += 2;
                    e_sum += 2;
                    e_same += 2;
                }
                else
                {
                    e[i]++;
                    e[j]++;
                    e_sum++;
                }
            }
        }
    }
    res = c2(e_sum) + e_same;
    for (int i = 0; i < n; i++)
    {
        // cout << e[i] << ' ';
        res -= c2(e[i]);
    }
    printf("%lld\n", res);
    return 0;
}
// 以下是纯暴力验证
int baoli_ans = 0;
int t[4];
void baoli_dfs(int d)
{
    if (d == 4)
    {
        for (int i = 0; i < 4; i++)
            for (int j = i + 1; j < 4; j++)
                if (t[i] == t[j])
                    return;
        if (a[t[1]] % a[t[0]] == 0 && a[t[3]] % a[t[2]] == 0)
        {
            baoli_ans++;
        }
        return;
    }
    for (int i = 0; i < n; i++)
    {
        t[d] = i;
        baoli_dfs(d + 1);
    }
}
void baoli()
{
    baoli_dfs(0);
    cout << baoli_ans << endl;
}
/*
input:
10
1 2 2 3 3 3 4 5 6 6
//ouput: 564
*/

说明至少思路是对的，只是爆时间了👉👈。换一种方式找它们之间的因数关系。
设点输入的数量为，最大的因子为，是点和多少个点有因数关系。把两个端点是因数关系的称作一条边。两条样的边称为一对边。
对每一个因子，乘以倍数，获得它的倍数，直到超过为止。这样，，点x和y之间连边，它们增加边的数量均为。
时间复杂度：，比好。

一个答案：

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
#include <bits/stdc++.h>
#define N 100005
#define M 100000
using namespace std;
using ll = unsigned long long;

ll n, m;           // 数据数量,不重复的数据的数量
ll num[N];         // 不重复数据排列
ll cnt[N];         // 桶
ll e[N];           // 连接到的值不一样的边
ll res;            // 结果
inline ll c2(ll a) // 组合数,n*(n+1)/2，因为最后结果要*2就抵消了
{
    return a * (a - 1);
}
signed main()
{
    scanf("%d", &n);
    ll a;
    for (register ll i = 0; i < n; i++)
    {
        scanf("%d", &a);
        cnt[a]++;
    }
    for (register ll i = 1; i <= M; i++)
    {
        if (cnt[i] == 0)
            continue;
        num[m++] = i;
        res += c2(cnt[i]);
        for (register ll j = i * 2; j <= M; j += i)
        {
            e[i] += cnt[j];
            e[j] += cnt[i];
            res += cnt[i] * cnt[j];
        }
    }
    res = c2(res);
    for (register ll i = 0; i < m; i++)
    {
        res -= c2(e[num[i]] + 2 * (cnt[num[i]] - 1)) * cnt[num[i]];
        res += c2(cnt[num[i]]);
    }
    cout << res<< endl;
    return 0;
}

[蓝桥杯 2024 省 A] 零食采购

题目描述

小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 颗星球，由 条航路连接为连通图，第 颗星球卖第 种零食特产。小蓝想出了 个采购方案，第 个方案的起点为星球 ，终点为星球 ，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。

输入格式

输入的第一行包含两个正整数 ，，用一个空格分隔。
第二行包含 个整数 ，相邻整数之间使用一个空格分隔。
接下来 行，第 行包含两个整数 ，用一个空格分隔，表示一条
航路将星球 与 相连。
接下来 行，第 行包含两个整数 ，用一个空格分隔，表示一个采购方案。

输出格式

输出 行，每行包含一个整数，依次表示每个采购方案的答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4

样例输出 #1

1
2
3
2

提示

第一个方案路线为 ，可以买到第 种零食；
第二个方案路线为 ，可以买到第 种零食。

对于 20% 的评测用例，；
对于所有评测用例，，，，。

解法

使用最近公共祖先LCA板子，在其中加上状态压缩DP
我博客里的lca: https://misaka-xxw.github.io/2025/02/01/lca/

首先，注意审题，题目里说n个节点，n-1条边，连通图，所以这是一个树。任意选中一个根节点，那么点s到点e的最短路径，就是从s往上走到根节点，再往下走到点e。

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
#include<bits/stdc++.h>
using namespace std;
const int N=(5e5)+5;

int n,s,e;//结点数，起点，终点
vector<int> g[N];//树
int lg[N];//对数表
int c[N];//每个结点对应的食物
int depth[N],father[N][31],dp[N][31];//深度，第i结点的2^j个祖先，以及这条链路对应相应的食物购买情况
void init_lg() {
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i>>1] + 1;
    }
}
//利用补码的性质，找二进制里最后一个1
inline int lastof1(int x){
    return x & -x;
}
//统计二进制里有多少1
inline int numof1(int x){
    int a=0;
    while(x){
        x-= lastof1(x);
        a++;
    }
    return a;
}
// 深度优先搜索，计算每个节点的父节点倍增表
void dfs(int me,int fa) {
    for (int i = 1; i <= lg[depth[me]]; ++i){
        dp[me][i]=dp[father[me][i - 1]][i - 1]|dp[me][i - 1];
        father[me][i] = father[father[me][i - 1]][i - 1];
    }
    for (int son : g[me])
        if (son!=fa){
            depth[son] = depth[me] + 1;
            father[son][0] = me;
            dp[son][0]=c[son]|c[me];
            dfs(son,me);
        }
}
// 查询x和y的最低公共祖先用lca算法，改变
int lca(int x,int y){
    int res=c[x]|c[y];
    if(depth[x]<depth[y])
        swap(x,y);
    while(depth[x]>depth[y]){
        int delta=lg[depth[x]-depth[y]];
        res|=dp[x][delta];
        x=father[x][delta];
    }
    if(x!=y){
        for(int i=lg[depth[x]];i>=0;--i){
            if(father[x][i]!=father[y][i]){
                res|=(dp[x][i]|dp[y][i]);
                x=father[x][i];
                y=father[y][i];
            }
        }
        res|=dp[x][0];
    }
    return numof1(res);
}
int main() {
    int u,v,q;
    scanf("%d%d",&n,&q);
    init_lg();
    for(int i=1;i<=n;i++){
        scanf("%d",&u);
        c[i]=(1<<u);
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,1);
    while(q--){
        scanf("%d%d",&s,&e);
        printf("%d\n",lca(s,e));
    }
    return 0;
}

[蓝桥杯 2024 省 A] 封印宝石

题目描述

在一次探险中，勇者小蓝发现了 颗闪烁着奇异光芒的宝石，每颗宝石都蕴含着魔法能量，分别记作 。小蓝计划用 个特制的魔法盒子来封
印这些宝石，防止其魔法能量被滥用。
封印宝石会消耗小蓝的体力，具体地，将第 颗宝石放入第 个盒子会消耗小蓝 点体力（注：需满足 才能将第 颗宝石放入第 个盒子进行有效的封印）。小蓝也可以选择将魔法盒留空，以保存体力供后续使用。
此外，为了避免魔力相冲，每个盒子最多存放一颗宝石（每个宝石也只能放进一个盒子），且任意两个相邻盒子不能存放魔力值相同的宝石，相邻的盒子允许同时为空。
小蓝初始的体力值为 。在不超出体力限制的条件下，小蓝希望找出一种宝石的放置方法，使得宝石的魔力值在这 个盒子中的排列顺序具有最大的字典序（注：未放置宝石的盒子在此序列中记为 ）。
作为勇者小蓝的追随者，请你帮他找出这一放置宝石的方法。

字典序的解释： 在本题中，字典序的大小是按照宝石的魔力值进行比较的。对于两个长度同为 的魔力值序列 和 ，如果存在一个位置 ，使得 对所有 成立，但是 ，则序列 在字典序上小于序列 。
反之，如果 ，则序列 在字典序上大于序列 。如果不存在这样的 ，则序列 和序列 的字典序相等。

输入格式

输入的第一行包含两个整数 和 ，用一个空格分隔，分别表示宝石的数量和小蓝的初始体力值。
第二行包含 个整数 ，相邻整数之间使用一个空格分隔，分别表示每颗宝石的魔法能量值。

输出格式

输出一行包含 个整数，相邻整数之间使用一个空格分隔，表示每个魔法盒中宝石的魔法能量值。如果某个魔法盒为空，则对应位置输出 。

样例 #1

样例输入 #1

1
2
3 3
1 3 2

样例输出 #1

1
3 2 -1

提示

在开始放置宝石之前，体力为 ，宝石在盒子中的排列为 。

  1. 将第 个宝石放进第 个盒子，得到 ，体力剩余 。
  2. 将第 个宝石放进第 个盒子，得到 ，体力剩余 。

最后宝石在盒子中的排列为 。显然，没有比这更优的放置方法。

对于 的评测用例，，，。
对于所有评测用例，，，。

解法

贪心+线段树
我博客里的线段树:https://misaka-xxw.github.io/2025/02/02/segment-tree/

解释

给定个数放到个位置上，放到位置上消耗个代价，合理放置这些数，让它们在代价范围内有最大的字典序。
要求：

  • 数可以放在的位置区间
  • 位置可以放置区间的数
  • 可以有空的位置，相邻位置不能有相同的数。
  • 字典序的解释：两个排列方法，对于最靠前的放置了不相等的数的位置，放更大的数的那个字典序更大。没有放数就是-1。如：[5,4,3,…]比[5,4,2,…]大

贪心

  • 优先将更大的数放置到更靠前的位置
  • 对于相等的数，选更靠前的
  • 两个位置不能同时放一样的数

线段树

  • 作用：区间内最大值和次大值的查询和更新
  • 从1遍历到n，查询区间内的最大值，放在位置上。
    • 如果和上一个答案相同，选次大值。
    • 使用了宝石，就要更新线段树
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
#include<bits/stdc++.h>

using namespace std;
const int N = (1e5) + 5;

struct node {
    int num; // 数值
    int pos; // 第几个数值
    node() : num(-1), pos(0) {}

    node(int a, int b) : num(a), pos(b) {}

    bool operator>(const node &other) const {
        return num != other.num ? num > other.num : pos < other.pos;
    }
} node0;//空结点
typedef pair<node, node> maxs;//最大值和次大值,对应first和second
int n, m;//数量，代价，当前搜索
int a[N];//宝石数值
int loc[N];//判断叶子节点位置与线段树位置的对应关系
int ans[N];//答案，放置方法
maxs t[4 * N];//线段树，最大值和次大值
maxs res;//存放find_max时的最大值和次大值

// 更新某个节点的最大值和次大值，可能稍微快一点
void update_max(maxs &cur, const maxs l, const maxs r) {
    //根据l和r，更新cur的最大值和次大值
    if (l.first.num > r.first.num) {//左最大值大
        cur.first = l.first;
        if (l.second.num >= r.first.num)
            cur.second = l.second;
        else
            cur.second = r.first;
    } else if (l.first.num < r.first.num) {//右最大值大
        cur.first = r.first;
        if (l.first.num >= r.second.num)
            cur.second = l.first;
        else
            cur.second = r.second;
    } else {//左右最大值相同
        cur.first = l.first;
        if (l.second.num != cur.first.num && l.second.num >= r.second.num)
            cur.second = l.second;
        else if (r.second.num < cur.first.num)
            cur.second = r.second;
        else
            cur.second = node0;
    }
}

//效果一样的函数，似乎稍微慢一点点
void update_max2(maxs &cur, const maxs l, const maxs r) {
    //根据l和r，更新cur的最大值和次大值
    node tmp[] = {l.first, l.second, r.first, r.second};
    sort(tmp, tmp + 4, greater<>());//从大到小排
    cur.first = tmp[0];
    for (int i = 1; i < 4; i++) {
        if (cur.first.num != tmp[i].num) {
            cur.second = tmp[i];
            return;
        }
    }
    cur.second = node0;
}

//建立线段树
void build(int l, int r, int p) {
    if (l == r) {
        t[p].first = node(a[l], l);
        t[p].second = node0;
        loc[l] = p;
        return;
    }
    int mid = l + ((r - l) >> 1), lc = p << 1, rc = lc | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    update_max(t[p], t[lc], t[rc]);
}

//查找最大值
void find_max(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) {//找到了合适的区间
        update_max(res, res, t[p]);
        return;
    }
    int lc = p << 1, rc = lc | 1;
    int mid = i + ((j - i) >> 1);
    if (l <= mid) find_max(l, r, i, mid, lc);
    if (mid < r) find_max(l, r, mid + 1, j, rc);
}
// 自底而上，修改被影响节点的最大值和次大值
void modify(int pos) {
    int p = loc[pos];
    t[p].first = node0;
    t[p].second = node0;
    for (p >>= 1; p >= 1; p >>= 1) {
        update_max(t[p], t[p << 1], t[(p << 1) | 1]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    memset(ans, -1, sizeof(ans));//初始化为-1，盒子为空
    build(1, n, 1);//建立线段树
    for (int i = 1; i <= n; i++) {
        res = {node0, node0};
        find_max(i, min(i + m, n), 1, n, 1);
        int pos;
        if (res.first.pos == 0)//最大值是一个空节点
            continue;
        else if (res.first.num == ans[i - 1]) {//最大值跟前一个盒子相同撞了，找次大值
            if (res.second.pos == 0)//次大值是一个空节点
                continue;
            ans[i] = res.second.num;//选次大值
            pos = res.second.pos;
        } else {
            ans[i] = res.first.num;//选最大值
            pos = res.first.pos;
        }
        m -= (pos - i);
        modify(pos);
    }
    for (int i = 1; i < n; i++) {
        printf("%d ", ans[i]);
    }
    printf("%d\n", ans[n]);
    return 0;
}