算法练习专栏——牛客练习——牛客round38内测

A：小红的正整数自增

链接

题目描述

小红拿到了一个正整数，她每次操作可以使得这个正整数加1。
小红想知道，使得该数的末尾为0至少需要操作多少次？

输入描述:

1
2
一个正整数x。
1≤x≤10^9

输出描述:

1
一个整数，代表小红的最小操作次数。

示例1

输入

复制

1
16

输出

复制

1
4

说明

1
操作4次后，x变成20，末尾为0。

示例2

输入

复制

1
20

输出

复制

1
0

说明

1
小红并不需要任何操作。

代码

1

B：小红的抛弃后缀

链接

题目描述

小红拿到了一个正整数，她准备切掉一个后缀并抛弃，使得剩余部分是9的倍数。小红想知道有多少种不同的操作方案？

输入描述:

一个正整数x
$1\leq x \leq 10^{100000}$

输出描述:

1
一个整数，代表合法的方案数。

示例1

输入

复制

1
1989

输出

复制

1
2

说明

1
2
方案1：什么都不切（即切一个长度为0的后缀）。
方案2：切掉最后一个9（即切一个长度为1的后缀）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int ans;

int main()
{
    long long res = 0;
    string s;
    cin >> s;
    int len = s.length();
    for (int i = 0; i < len; i++) {
        res += s[i] - '0';
        if (res % 9 == 0) ans++;
    }
    
    cout << ans;
    
    
    return 0;
}

C：小红的字符串构造

链接

题目描述

小红希望你构造一个长度为n的、仅包含小写字母的字符串，其中恰好有k个长度大于1的回文子串。你能帮帮她吗？

输入描述:

1
2
3
两个整数n,kn,kn,k，用空格隔开。
1≤n≤105
0≤k≤n/2

输出描述:

1
2
一个字符串。如果有多解输出任意即可。
可以证明，一定存在至少一个合法解。

示例1

输入

复制

1
6 3

输出

复制

1
woooca

说明

1
长度大于1的回文子串有2个"oo"和一个"ooo"

示例2

输入

复制

1
4 0

输出

复制

1
ruby

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        char c = 'a' + (i % 26);
        cout << c << c;
    }
    n -= 2 * k;
    int kk = k % 26;
    for (int i = 0; i < n; i++) {
        char c = 'a' + (kk + i) % 26;
        cout << c;
    }
    
    return 0;
}

D：小红的平滑值插值

链接

题目描述

小红定义一个数组的“平滑值”为：相邻两数差的绝对值的最大值。
具体的，数组a的平滑值定义为$f(a)=max_{i=1}^{n-1}|a_{i+1}-a_i|$
现在小红拿到了一个数组。她每次操作可以在两个元素之间添加一个元素（不能添加在第一项前面或者最后一项后面）。小红希望最终数组的平滑值恰好等于k，你能帮小红求出最小的操作次数吗？

输入描述:

1
2
3
4
第一行输入两个正整数n,k，代表数组的大小、以及最终希望达到的平滑值。
第二行输入n个正整数ai。代表小红拿到的数组。
2≤n≤105
1≤k,ai≤109

输出描述:

1
一个整数，代表小红最少的操作次数。

示例1

输入

复制

1
2
5 2
1 4 5 1 3

输出

复制

1
2

说明

1
小红首先在1和4之间插入一个3，然后在5和1之间插入一个3即可。

代码

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

using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N];
long long res = 0;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    
    for (int i = 1; i < n; i++) {
        int kk = abs(a[i + 1] - a[i]);
        if (kk > k) continue;
        if (kk == 0) continue;
        res += ceil(1.0 * kk / k) - 1;
    }
    
    cout << res;
    return 0;
}

// #include<bits/stdc++.h>
// using ll = long long;
// using namespace std;

// int main()
// {
//     ll n,k,mx = 0;
//     cin >> n >> k;
//     vector<ll> a(n + 1,0);
//     for(int i = 1;i <= n;i ++){
//         cin >> a[i];
//         if(i > 1) mx = max(mx,abs(a[i] - a[i - 1]));
//     }
//     if(mx == k) cout << 0 << endl;
//     else if(mx < k) cout << 1 << endl;
//     else{
//         ll cnt = 0;
//         for(int i = 2;i <= n;i ++){
//             if (a[i] - a[i - 1] == 0) continue;
//             cnt += (abs(a[i] - a[i - 1]) - 1) / k;
//         }
//         cout << cnt << endl;
//     }
//     return 0;
// }

E：小苯的等比数列

链接

题目描述

​ 小苯非常喜欢等比数列。有一天他得到了一个长为 nnn 的数组 aaa，他想从里面选一些数字使得被选中的数字构成一个等比数列，请问他最多可以选择多少个数字呢？

​ 注意：小苯选择的等比数列公比需要是正整数。

输入描述:

1
2
3
输入包含两行。
第一行一个正整数 n (1≤n≤2×105)n\ (1\leq n \leq 2 \times 10^5)n (1≤n≤2×105)，表示数组 aaa 的长度。
第二行 nnn 个正整数 ai (1≤ai≤2×105)a_i \ (1 \leq a_i \leq 2 \times 10^5)ai (1≤ai≤2×105)，表示数组 aaa 的元素。

输出描述:

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

示例1

输入

复制

1
2
5
3 4 2 1 4

输出

复制

1
3

说明

1
可以选择 a4=1,a3=2,a2=4a_4 = 1, a_3 = 2, a_2=4a4=1,a3=2,a2=4，构成一个首项为 111 ，公比为 222，长度为 333 的等比数列，可以证明不存在更长的等比数列。

示例2

输入

复制

1
2
1
114514

输出

复制

1
1

代码一（最原始的暴力解法,O(n^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
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;
const int N = 2e5 + 10;
int a[N];
long long st[N];

int ma;
long long ans;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++) {
        cin >> a[i];
        ma = max(ma, a[i]);
        st[a[i]]++;
    }
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= ma; i++) {
        ans = max(ans, st[i]);
    }
    for (int i = 1; i <= n;i++) {
        long long res = a[i];
        long long k = 0;
        for (int j = 2; j <= ma / 2; j++) {
            while (res <= ma && st[res]) {
                res *= j;
                k++;
            }
            ans = max(ans, k);
        }
    }    
    cout << ans;
    
    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
#include<bits/stdc++.h>
typedef long long ll;
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    map<int,int> mp;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for (auto i : mp) {     //q为1的情况
        ans = max(ans,i.second);
    }
    for (int i = 2;  pow(i,ans) <= 4e5; ++i) { //枚举公比
        for (int j = 1; j <= n; ++j) {    //枚举元素
            int tmp = a[j];
            int cnt = 0;     //统计次数
            while (tmp <= 2e5 && mp[tmp] > 0){
                cnt++;
                tmp *= i;
            }
            ans = max(cnt,ans);
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}

F：小苯的回文询问

链接

题目描述

小苯有一个长度为 n 的数组 a，他定义一个数组是好数组，当且仅当该数组是一个回文数组，且长度严格大于 2。

他现在进行了 q 次询问，每次询问都给出一段区间 [l,r]，他想知道 a 在这一段区间中是否存在一个子序列是一个好数组，请你帮帮他吧。

输入描述:

1
2
3
4
输入包含 q+2 行。
第一行两个正整数 n,q (1≤n≤105), (1≤q≤2×105)，以空格分隔，分别表示小苯拥有的数组的长度，以及他的询问次数。
第二行 n 个正整数 ai (1≤ai≤109)，表示数组 a 的元素。
接下来 q 行，每行两个正整数 [l,r] (1≤l≤r≤n)，以空格分隔，表示小苯每次询问的区间。

输出描述:

1
输出包含 q 行，如果对于当前询问的区间，存在一个好子序列是一个好数组，则输出 "YES"，否则输出 "NO"。（不含双引号）

示例1

输入

复制

1
2
3
4
5
9 3
1 1 2 1 1 3 1 1 2
1 4
2 7
1 2

输出

复制

1
2
3
YES
YES
NO

说明

1
[1, 4] 可以选择子序列：(a1,a3,a4) 即：{1, 2, 1}，满足是一个好数组。（注意：子序列可以不连续）

代码一（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
71
72
73
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
int tr[N << 4],a[N],lst[N];
void build(int u,int l,int r){
    if(l == r){
        tr[u] = lst[l];
        return;
    }
    int mid = l + r >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
int ask(int u, int l,int r,int L,int R){
    if(l >= L && r <= R){
        return tr[u];
    }
    int mid = l + r >> 1;
    int res = 0;
    if(L <= mid){
        res = max(res, ask(u << 1,l, mid, L,R));
    }
    if(R >= mid + 1){
        res = max(res, ask(u << 1 | 1,mid + 1,r, L,R));
    }
    return res;
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)cin >> a[i];
    map<int,int>mp;
    for(int i = 1 ;i <= n; i++){
        if(mp.count(a[i])){
            lst[i] = mp[a[i]];
        }
        else lst[i] = lst[mp[a[i]]];
        mp[a[i - 1]] = i - 1;
    }
    //0 0 0 2 2 2 5 5 5 
    //0 0 0 2 2 2 5 5 3 
    //0 0 0 2 2 0 5 5 3 
    //0 0 0 2 2 0 5 5 3 
//     for(int i=1; i<=n; i++) {
//         if(mp.count(a[i])) lst[i] = mp[a[i]];
// //         lst[i] = max(lst[i], lst[i-1]);
//         if(i >= 2) mp[a[i-1]] = i-1;
//     }
//     for(int i = 1; i <= n; i++){
//         cout << lst[i] << ' ';
//     }
//     puts("");
    build(1,1, n);
    while(q--){
        int l, r;
        cin >> l >> r;
        if(ask(1,1,n,l,r) >= l){
            cout << "YES" << endl;
        }
        else cout << "NO" <<endl;
    }
}

signed main(){
    int _(1);
    while(_ --){
        solve();
    }
    return 0;
}

代码二