算法练习系列——2024牛客五一集训派对day2

2024牛客五一集训派对day2

A：The Crime-solving Plan of Groundhog

链接

题目描述

Groundhog took a math class. In this class, his math teacher said:

Any positive integer can be represented by the power of 2. For example:137=2^7^+2^3^+2^0^

And powers are expressed in parentheses.That is ,a(b){a(b)}a(b) stands for ab{a^b}ab.Therefore,137 can be expressed as 137=2(7)+2(3)+2(0).

Further more,for 7=2^2^+2+2^0^（2^1^is expressed with 2），3=2+2^0^,137 can be finally expressed as 137=2(2(2)+2+2(0))+2(2+2(0))+2(0).

Another example:1315=2^10^+2^8^+2^5^+2+1=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0).

Groundhog feels amazing and wants you to write a program to simulate the above content.You need to read in an expression that is a power of 2 and calculate its value.

输入描述:

1
Given a string, indicating the power representation.

输出描述:

1
Output the original number.

示例1

输入

复制

1
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输出

复制

1
1315

备注:

1
The range of answers :[10,10^180]，and the length of the input data shall not exceed 20000.

思路

​ 这道题目的综合性还是很强的，先介绍一下这道题目的使用算法和思想：递归 + 快速幂 + 高精度乘法（超高精度） + 高精度加法

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int len; // 最终答案的位数
int ans[1010]; // 存最终结果的
int p; 
int b[1010];
string s;

void add(int b[], int Len) {
    len = max(len, Len);
    int t = 0;
    for (int i = 1; i <= len; i++){
        ans[i] += b[i] + t;
        t = ans[i] / 10;
        ans[i] %= 10;
    }
    if (t) {
        ans[len + 1] = t;
        ++len;
    }
}

// 高精度乘法plus+,还有一个精度计算plus++可以更上一层楼的办法还没有
// 学会。因此没有写
void pow(LL x) {
    memset(b, 0,sizeof b);
    b[1] = 1;
    int k = 1;
    for (int i = 1; i <= x; i++) {
        int t = 0;
        for (int j = 1; j <= k; j++) {
            b[j] = b[j] * 2 + t;
            t = b[j] / 10;
            b[j] %= 10;
            if (t && j == k) k++;
        }
    }
    add(b, k);
}

// 快速幂板子，实际上这个可有可无，也可以选择使用上面的高精度乘法的办法计算，
// 但是为了计算方便一下，这里才写了个快速幂的板子在这里
LL qmi(LL a, LL x) {
    LL res = 1;
    while (x) {
        if (x & 1) res *= a;
        a *= a;
        x >>= 1;
    }
    return res;
}
LL check(LL x, LL h) {
    LL q = 0; // q是指数
    p = 0;
    for (int i = x; i < s.length(); i++) {
        p = max(p, i);
        if (s[i] == '(') h++;
        else if (s[i] == ')') h--;
        
        // 表示这一项的次幂结束了结束，这个时候我们可以得到这一项2的最终指数q
        if (!h) {
            // 求出2^q之后再将其加入到最终结果ans里面去
            pow(q);
            return 0;
        }
        
        // 表示当前的有括号并不是最终的右括号
        if (s[i] == ')') return qmi(2, q);
        else if (s[i] == '2') {
            if (s[i + 1] == '(') {
                q += check(i + 1, h);
                i = p;
            }
            // 表示只是1个2而已
            else {
                q += 2;
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        // 表示这个时候开始对一个数进行2的次幂操作
        if (s[i] == '2') {
            if (s[i + 1] == '(') {
                check(i + 1, 0);
                i = p;
            } else { // 单纯的 + 2即可
                memset(b, 0, sizeof b);
                b[1] = 2;
                add(b, 1);
            }
        }
    }
    
    for(int i = len; i >= 1; i--) cout << ans[i];
    return 0;
}

I：The Crime-solving Plan of Groundhog

链接

题目描述

Today, ZLZX has a mysterious case: Orange lost his down jacket hanging in his dorm room. Under the expectations of everyone, detective Groundhog took his small spoon of the artifact and started the journey to solve the case.

After an in-depth investigation of the northernmost mysterious room on each floor, Groundhog discovered n{n}n mysterious numbers. As long as the clues conveyed by these numbers are deciphered, he can reveal the truth of the matter. The deciphering method is: using these numbers to generate two positive integers without leading zeros, and minimizing the product of these two positive integers is the final clue.

Then Groundhog wants to know: What is the smallest product?

As he continued to investigate in the room west of the new building, he gave you the question.

Concise meaning:Given n numbers between 0 and 9, use them to make two positive integers without leading zeros to minimize the product.

输入描述:

1
2
3
The first line of input is a single integer T,the number of test cases.
For each set of data：
Each test case begins with a single integer n , the count of numbers.The next line are  n{n}n numbers.

输出描述:

1
For each set of Case, an integer is output, representing the smallest product.

示例1

输入

复制

1
2
3
1
4
1 2 2 1

输出

复制

1
122

示例2

输入

复制

1
2
3
4
5
2
5
1 3 2 1 2
3
1 1 0

输出

复制

1
2
1223
10

备注:

1
2
3
1⩽T⩽1000,2⩽n⩽100000,1⩽∑n⩽1000000

There are at least two Numbers that are guaranteed not to be zero.The Numbers range between [0,9].

思路

​ 基本思路：比如说有这么一个排序好的数列0,0,0,0,1,2,3,4，我们想让它最大，首先取出第一个非0数字1,然后就是后面的数，也就是234，我们下面要做的就是将1x剩余数的最小数组合，很明显要越小，只需要尽可能把0往前移动，由于不可以有前导0，所以放在不是0的数的后面位置就可以了，这个例子也就是2000034，对应着一般题目来说，进行的操作就是：swap(a[1],a[res + 1]);swap(a[2],a[res + 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
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 <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int> A;
 
vector<int> mul(vector<int> A, int B) {
    vector<int> C;
    int t = 0;
    for (int i = 0 ; i < A.size() || t ; i++) {
        if (i < A.size()) t += A[i] * B;
        C.push_back(t % 10);
        t /= 10;
    }
     
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
 
void solve() {
    A.clear();
    int n, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) res++;
    }
     
    if (res == n - 1 || res == n) {
        cout << "0\n";
        return;
    }
    sort(a + 1, a + n + 1);
     
    int b = a[res + 1];
    swap(a[res + 1], a[1]);
    swap(a[res + 2], a[2]);
    for (int i = n; i >= 2; i--) A.push_back(a[i]);
    auto D = mul(A, b);
    for (int i = D.size() - 1; i >= 0; i--) cout << D[i];
    cout << '\n';
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

F:Groundhog Looking Dowdy

链接

题目描述

Groundhog finds that Apple seems to be less intimate than before.

He is very distressed for this.After pondering for a long time, Groundhog finds that he looks too dowdy.So, Groundhog decided to improve a little.

Because Groundhog is lazy, he only lists the clothes that can be worn for the next n{n}n days. On the ith{i^{th}}ith day, the jth{j^{th}}jth clothes have a dowdiness ai,ja_{i,j}ai,j.On each day,he will choose one of the clothes and wear it.

And Groundhog should choose m{m}m days from n{n}n days to go out with Apple.

Groundhog wants to know the minimum difference between the maximum dowdiness and the minimum dowdiness in m{m}m days when Groundhog’s choice is optimal.

Simplified: You should choose n clothes for each day and then choose m clothes from those n clothes, and the problem is to calculate the minimum difference between the maximum dowdiness and the minimum dowdiness.

输入描述:

1
2
3
The first line contains two integers n{n}n and m{m}m.

Then n lines follow,each line contains a integer kik_iki,represents the number of the clothes that can be worn on ith{i^{th}}ith day.Then kik_iki integers ai,j follow.

输出描述:

1
Print in one line the minimum difference.

示例1

输入

复制

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

输出

复制

1
2

说明

1
Apple will pay attention to Groundhog's clothes on day 1, 3, and 4 ,Groundhog will wear clothes with dowdiness of 3, 2, and 1 on day 1, 3, and 4,and the difference is 2.

备注:

1
1⩽ai,j⩽10^9 1⩽ai,j⩽109，1≤n⩽106，1≤m⩽n，the sum of clothes ⩽2⋅106.ki≥1

思路

​ 使用尺取法来进行维护一个含有m天数量的区间。。。。。。

代码

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
#include<iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;
 
const int N = 1e6 + 10;
 
vector<pair<int,int>>node;
 
int cnt[N];
 
int main()
{
    int n,m;
    scanf("%d%d",&n, &m);
    for(int i = 1;i <= n; i++)
    {
        int k;
        scanf("%d", &k);
        while(k --)
        {
            int num;
            scanf("%d", &num);
            node.emplace_back(num, i);
        }
    }
    sort(node.begin(),node.end());
    
    int r = 0,now = 0,ans = inf;
    for(int l = 0;l < node.size(); l++)
    {
        while(r < node.size() && now < m)
        {
            if(cnt[node[r].second]==0)
                now ++;
            cnt[node[r].second] ++;
            r ++;
        }
        if(now == m){
            ans=min(ans, node[r - 1].first - node[l].first);            
        }
		cnt[node[l].second] --;
		if(cnt[node[l].second] == 0)
			now --;
	}
	cout << ans;
    return 0;
}

K：The Flee Plan of Groundhog

链接

题目描述

Groundhog was especially careful after the outbreak,so he put on his mask in the 1st bedroom early,and then walked on the way to the nth dormitory to play with Orange. There are n dormitories in ZLZX, which are connected by n−1 corridors. Each dormitory can be reached to each other.The length of each corridor is 1.The walking speed of Groundhog is 1 m/s.

At that moment the bad news came: After Groundhog set out for t{t}t seconds,Orange took his temperature, and it turned out to be 41℃ !!! In addition to grief and indignation, Orange decided to run to Groundhog, to tell him the news at the speed of 2 m/s.

Groundhog had to run, of course, but he was running too slow at 1 m/s . As he ran, he had an idea: if he ran with the best strategy, how soon would Orange catch up with him? Define that every second Groundhog moves and then Orange moves again. Groundhog can choose to stay put.
Groundhog would have solved that, of course, but he is running away now, so he give it to you, the smartest one.

输入描述:

1
2
The first line contains two integers n,t。
The next n−1 lines，each line contains two integers x,y, indicating there is a corridor between the  xth dormitory and the yth dormitory.

输出描述:

1
An integer, indicating the latest time for Orange to catch Groundhog.

示例1

输入

复制

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

输出

复制

1
1

说明

1
After t seconds, Groundhog is in the 5th dormitory and Orange is in the 7th dormitory.At this point, the best way for Groundhog is to goto the 2nd dormitory or the 6th6^{th}6th dormitory.But wherever he goes, he will be immediately caught by Orange.

备注:

1
1≤n≤105,1≤t≤n−1,1≤x,y≤n

思路

​ 首先分析一下題目：有一棵树，A在1，B在2，A的移动速度是1边/s，B的是2边/s（可以选择走1边），前 t s A 在不断走向B，B不动。前 t s A在不断走向B，B是不动的，之后B就要开始移动逃离 A 了，求A最晚被追到的时间。

​ 一棵树的两个结点之间的路径的基本是唯一的。所以可以把 B 为根，用LCA的ST倍增板子求A最后到达的位置。随后我们就要开始逃离，考虑A,B到达每一个点的情况，考虑A到达每个点所需要的时间,对于这个点，取两个时间中的较小值，取 A 和 B第 1 次到这个点的时间。然后从 A 出发寻找最大的二者到达时间相等的点。

代码（LCA的DFS递增版本 + BFS）

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, t;
vector<int> P[N];
int fa[N][21];
bool st[N];
int ans = 0;
int dist1[N], dist2[N];

void dfs(int root, int place) {
    fa[root][0] = place;
    for (int i = 1; i <= 20; i++) fa[root][i] = fa[fa[root][i - 1]][i - 1];
    for (auto &v : P[root]) {
        if (v != place) dfs(v, root);
    }
}

int LCA(int u, int k) {
    int bit = 0;
    while (k) {
        if (k & 1) u = fa[u][bit];
        k >>= 1;
        bit++;
    }
    return u;
}

// 被基本的东西搞死，需要非常注意这个st[k] = true; 是要写在for循环的外面的，否则肯定是不对的。
void bfs1(int kk,int dist[]) {
    memset(st, false, sizeof st);
    queue<PII> q;
    q.push({kk, 0});
    
    while (q.size()) {
        auto tt = q.front();
        q.pop();
        int k = tt.first, distance = tt.second;
        st[k] = true;
        for (int kkk: P[k]) {
            if (st[kkk]) continue;
            dist[kkk] = distance + 1;
            q.push({kkk, distance + 1});
        }
    }
}

void bfs2(int kk) {
    memset(st, false, sizeof st);
    queue<int> q;
    q.push(kk);
    while (q.size()) {
        int k = q.front();
        q.pop();
        st[k] = true;
        ans = max(ans, max((dist2[k] + 1) / 2, dist1[k]));
        if ((dist2[k] + 1) / 2 <= dist1[k]) continue;
        for (int kkk : P[k]) {                        
            if (st[kkk]) continue;            
            q.push(kkk);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> t;
    for (int i = 0; i < n - 1; i++) {
        int a, b; 
        cin >> a >> b;
        P[a].push_back(b);
        P[b].push_back(a);
    }
    // 1、下面利用LCA的DFS写法寻找到我们最终到达的结点位置
    dfs(n, 0);
    
    int kf = LCA(1, t);
    if (kf == 0) kf = n;
       
    // 2、下面我们通过BFS的方法分别求出 kf 和 n 到树上各节点位置的到达时间
    bfs1(kf, dist1);
    bfs1(n, dist2);
    bfs2(kf);
    
    cout << ans;
    return 0;
}