算法练习专栏——牛客练习——牛客周赛 Round 44

A.唐龙守则

链接

题目描述

众所周知，牛客小白月赛q群有一条特殊规则：
不能连续发三张及以上的奶龙表情包。
但是，发多了也没关系，好心的管理员会对表情包序列进行处理。
只要每三张撤回一张，炸鸡块就没办法禁言了！
给定 表情包序列 的长度 n ，请问管理员需要撤回几张表情包。

输入描述:

1
第一行有一个正整数 n ( 1≤n≤105 ) 。

输出描述:

1
输出一个整数，代表需要撤回的表情包的数量。

示例1

输入

复制

1
7

输出

复制

1
2

说明

1

代码

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    cout << n / 3;
}

B.最大公约

链接

题目描述

Silencer76 定义一个序列是 好序列 ，当且仅当序列中所有元素的 最大值 和 最大公约数 相等。
给定一个长度为 n 的正整数序列 a ，请找出最长的符合好序列定义的子序列，输出它的长度。

输入描述:

1
2
第一行有一个正整数 n ( 1≤n≤105 ) 。
第二行有 n 个正整数 ai ( 1≤ai≤109 )。

输出描述:

1
输出一个整数，代表子序列的长度。

示例1

输入

复制

1
2
5
1 2 3 2 1

输出

复制

1
2

思路

​

代码

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

using namespace std;
const int N = 1e5 + 10;
int a[N];
map<int, int> mp;
int maxn;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]]++;
    for (auto [k, x] : mp) maxn = max(maxn, x);
    cout << maxn;
    return 0;
}

C.连锁进位

链接

题目描述

给定 t 组询问，每组询问给出一个正整数 n ，你可以对其施加任意次以下操作：
选择一个 10 的非负整数次幂 x ，令 n=n+x 。
如果要使这个正整数 n 只有一个数位不为 0，最少要操作几次？

输入描述:

1
2
3
第一行一个整数 t ( 1≤t≤105 ) 。
随后 t 行，每行有一个正整数 n ( 1≤n≤10^100000 ) 。
保证 ∑len(n)≤106。

输出描述:

1
输出 t 行，每行一个整数，代表最少的操作次数。

示例1

输入

复制

1
2
3
4
3
114514
10000
999

输出

复制

1
2
3
31
0
1

思路

​

代码

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

using namespace std;

int eval(string s) {
    int ans = 0;
    int tt = 0;
    for (int i = s.length() - 1; i >= 1; i--) {
        int t = s[i] - '0' + tt;
        if (t != 0) ans += (10 - t), tt = 1;
        
    }
    
    return ans;
}
int main()
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        string s;
        cin >> s;
        cout << eval(s) << '\n';
    }
}

D.因子区间

原题

题目描述

Silencer76 定义一个二元组 (ai,aj) 是漂亮二元组，当且仅当 i< j且 ai 和 aj 的因子数量相等。
给定一个长度为 n 的正整数序列 a ，以及 q次询问。
每次询问给出一个区间[l,r] ，请输出区间中漂亮二元组的数量。

输入描述:

1
2
3
第一行有两个正整数 n ( 1≤n≤105 )。
第二行有 n 个正整数 ai ( 1≤ai≤105 ) 。
随后 q 行，每行两个整数 l,r ( 1≤l≤r≤n ) 。

输出描述:

1
输出 q 行，每行一个整数，代表漂亮二元组的数量。

示例1

输入

复制

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

输出

复制

1
2
3
4
5
3
1
0
3
1

说明

1
1,2,3,4,5 的因子数量分别为 1,2,2,3,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
56
57
58
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
int n, q;

void solve() {
    cin >> n >> q;
    vector<int> f(maxn, 0); // f[i] 数i的因子数
   
    for (int i = 1; i <= maxn; i ++) {
        for (int j = i; j <= maxn; j += i) {
            f[j] += 1;
        }
    }
    
    vector<vector<int>> pos(130);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        x = f[x];
        pos[x].push_back(i); // pos[x]存的是因子个数为x的数的下标
    }
    
    while (q --) {
        int l, r;
        cin >> l >> r;
        ll res = 0;
        for (int i = 1; i <= 128; i ++) {
            // 在pos[i]里面找到在l ~ r下标的对应下标
            auto it1 = upper_bound(pos[i].begin(), pos[i].end(), r);
            auto it2 = lower_bound(pos[i].begin(), pos[i].end(), l);
            int u = it1 - it2;
            
            //最后再排列组合一下即可得到这个公式
            res += (ll)u * (u - 1) / 2;
        }
        cout << res << '\n';
    }    
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int _ = 1;
    while (_--) {
        solve();
    }
    
    return 0;
}


E.

链接
题目描述

格格对合数十分感兴趣，她希望小苯构造一个长度为 n 的排列，使得对于所有的 i 都满足：

  • pi+i是一个合数。

  • ∣pi−i∣\ 也是一个合数。（∣x∣表示 x 的绝对值。）

​

请你帮他构造一个合法的排列 ppp 吧。

输入描述:

1
输入包含一行一个正整数 n (1≤n≤2×105)，表示排列的长度。

输出描述:

1
2
输出包含一行 n 个正整数表示构造出的排列。
如果无解，输出 −1。

示例1

输入

复制

1
10

输出

复制

1
5 8 7 10 9 2 3 4 1 6

示例2

输入

复制

1
2

输出

复制

1
-1

备注:

1
2
排列：一个长度为 n 的数组，满足其中 1 到 n 的所有正整数都恰好出现一次。
合数：n 是合数，当且仅当 2 到 n−1 的正整数中存在至少一个整数 m 使得 n % m=0。（特别的，1既不是质数也不是合数。）

思路

​

代码

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
#include<bits/stdc++.h>

using namespace std; 

void solve() {
    int n;
    cin>>n;
    if(n<=7){
        cout<<-1;
        return ;
    }
    if(n%2==0){
        int t=5;
        for(int i=1;i<=n-4;i++){
            cout<<t<<" ";
            t++;
        }
        cout<<1<<" "<<2<<" "<<3<<" "<<4;
    }
    else{
        int t=5;
        for(int i=1;i<=n-4;i++){
            cout<<t<<" ";
            t++;
        }
        cout<<2<<" "<<1<<" "<<4<<" "<<3;
    }
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

F.小红的基环树删边

链接

题目描述

小红拿到了一棵基环树，她想知道，若删除第i条边，1号点到n号点的最短路是多少？
所谓基环树，指n个点、n条边组成的、不包含重边和自环的无向连通图。

输入描述:

1
2
3
4
5
第一行输入一个正整数n，代表基环树的点数。
接下来的nnn行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。
3≤n≤105
1≤u,v≤n
保证给定的图为基环树。

输出描述:

1
输出n行，第i行输出删除第i条边的答案。如果删除后1号点和n号点不连通，请输出-1；否则输出一个正整数，代表删除后1号点和n号点的最短路长度。

示例1

输入

复制

1
2
3
4
3
1 2
2 3
1 3

输出

复制

1
2
3
1
1
2

示例2

输入

复制

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

输出

复制

1
2
3
4
-1
2
3
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 200050

int i,j,k,n,m,t,vis[N+50],f[N+50];
vector<pair<int,int> > v[N];

void dfs(int x,int dep){
	int i,j,k;
	if(x==n){
		for(i=1;i<=n;i++)if(!vis[i]){
			f[i]=min(f[i],dep);
		}
		return;
	}
	for(auto [y,id]:v[x])if(!vis[id]){
		vis[id]=1; dfs(y,dep+1); vis[id]=0;
	}
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>j>>k; f[i]=1e9;
		v[j].push_back({k,i});
		v[k].push_back({j,i});
	}
	dfs(1, 0);
	for(i=1;i<=n;i++){
		if(f[i] > 1e6)f[i]=-1;
		cout<<f[i]<<'\n';
	}
}