Eclipse's Blog
0%

20250313携程笔试题练习

发表于 分类于

做题地址：https://oj.niumacode.com/training/41/problems

20250313_1_诗

签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstring>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    string ans;
    int j = 0;
    for(int i = 1; i < 1000; i ++ ) {
        ans += s[j];
        if(j + i < n) {
            j += i;
        }else {
            break;
        }
    } 
    cout << ans;
    return 0;
}

20250313_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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 200010;
int a[N];

int main() {
	int T;
    cin >> T;
    while(T --) {
		int n;
        cin >> n;
        for(int i = 0; i < n; i ++ ) {
            cin >> a[i];
        }
        sort(a, a + n);
        int ans = 0;
        for(int i = 0; i < n; i ++ ) {
            ans = max(ans, a[i] + n - i);
        }
        cout << ans << endl;
    }
    return 0;
}

20250313_3_小牛的数组询问

计算质因子、滑动窗口求长度为k最小的子数组和
计算质因子：
计算整数x能被多少个质数整除
通过逐步除尽x的因子，来计算质因子的个数。12=2^2+3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int calc(int x) {
    if(x == 1) return 0;
    int sum = 0;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) {
            sum ++;
            while(x % i == 0) {
                x /= i;
            }
        }
    }
    if(x > 1) sum++;
    return sum;
}
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<iostream>
#include<climits>
using namespace std;

const int N = 100010;
int a[N];

int calc(int x) {
    if(x == 1) return 0;
    int sum = 0;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) {
            sum ++;
            while(x % i == 0) {
                x /= i;
            }
        }
        
    }
    if(x > 1) sum++;
    return sum;
}

int main() {
    int n, k;
    cin >> n >> k;
    int sum = 0;
    for(int i = 0; i < n; i ++ ) {
        cin >> a[i];
        a[i] = calc(a[i]);
        sum += a[i];
    }
    int l = 0, r = 0;
    
    int mink = INT_MAX;
    int cnt = 0;
    while(r < n) {
       	cnt += a[r];
        if(r - l + 1 == k) {
            mink = min(mink, cnt);
            cnt -= a[l];
            l ++;
        }
        r ++;
    }
    cout << sum - mink << endl;
    
    return 0;
}

20250313_4_偶数路径2.0

还没做出来，样例通过了，提交通过一个样例
建图，dfs遍历整棵树
结论：一组数中包含奇数，那么这组数gcd不可能是偶数；如果一组数全是偶数，那么这组数gcd是偶数。