湖南工程学院2022-2023年度算法设计与编程挑战赛题解
ACMore Team Lv1
  2023-05-26 12:03:00 2023-05-26 12:03

A:序列和找数

题目链接

思路分析

前缀和打表

c代码

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
#include <stdio.h>
#include <string.h>

#define N 510           //看题目的数据范围，一般比题目给定范围多留出一些 

int a[N];

int main()
{
	int n;
	scanf("%d", &n);
	
	for (int i = 1; i <= N; i++)
	{
		a[i] = a[i - 1] + i;     //使用前缀和的方式存储 

		if (a[i] == n)
		{
			puts("YES");        //puts输出方式更快  
			return 0;          //找到了就退出 
		}
	}
	
	puts("NO");       //puts输出方式更快 
	
	return 0;	
	
}

B：最大公约数和最小公倍数问题

题目链接

思路分析

暴力枚举

c/c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
 
ll a,b,ans;
 
int main() {
    cin>>a>>b;
    for(ll i=a;i<=b;i++) if(__gcd(i,a*b/i)==a&&a*b%i==0) ans++;
    cout<<ans;
}

C:求积

题目链接

思路分析

数学问题

c/c++代码

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    cout<<(n/10000*100+n/100%10*10+n%10)*(n/1000%10*10+n/10%10);
}

D：矩阵计算

题目链接

思路分析

数学问题，求出结果后直接输出就行（线性代数）

c代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int mod=1e9+7;
 
int main() {
    ll n,a1,a2,b1,b2;
    while(cin>>n>>a1>>a2>>b1>>b2){
        ll ans=(n-1)*n*n*n*(2*n-1)/6%mod*a2%mod*b1%mod;
        ans+=(n-1)*(n-1)*n*n*n/4%mod*((a1*b1%mod+a2*b2%mod+a1*b2%mod)%mod)%mod;
        ans=(ans+mod)%mod;
        cout<<ans;
    }
    return 0;
}

E：小王爱游泳

题目链接

思路分析

输入输出问题

c/c++代码

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
 
int a,b,c,d;
 
int main(){
    cin>>a>>b>>c>>d;
    cout<<(c*60+d-a*60-b)/60<<" "<<(c*60+d-a*60-b)%60;
}

F：传染病

题目链接

思路分析

循环问题

c代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
 
typedef long long ll;
 
ll ans=1;
 
int main(){
    int n,x;
    cin>>x>>n;
    for(int i=1;i<=n;i++) ans+=ans*x;
    cout<<ans;
}

G： 序列操作

题目链接

思路分析

输入输出问题

c/c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
 
const int N=1e5+10;
 
int a[N],n,T;
 
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>T;
    for(int i=n-T;i<n;i++) cout<<a[i]<<" ";
    for(int i=0;i<n-T;i++) cout<<a[i]<<" ";
}

H: 最小整数

题目链接

思路分析

输入输出问题

c/c++代码

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

I： 零序列

题目链接

思路分析

题目根据操作条件所求最少操作数

观察可知 若数组元素有0 则最少操作数为非0元素个数

若没有0 则先将数组其中一个元素变成0

（1）有相同的元素 则最少操作数为n

（2）没有相同元素 则最小操作数为n+1（随便将两个元素变成相同的即可）

c代码

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
#include<iostream>
using namespace std;
 
typedef long long ll;
 
int t,n,a[110];
 
int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        int cnt[110]= {0};
        for(int i=1; i<=n; i++) {
            cin>>a[i];
            cnt[a[i]]++;
        }
        int flag=0;
        for(int i=1; i<=100; i++) {
            if(cnt[i]>1) {
                flag=1;
                break;
            }
        }
        if(cnt[0]) {
            cout<<n-cnt[0]<<endl;
        } else {
            if(flag+cdnb-1+cd-2) {
                cout<<n-cnt[0]<<endl;
            } else {
                cout<<n-cnt[0]+1<<endl;
            }
        }
    }
}

J：不是唯一的树

题目链接

思路分析

一棵二叉查找树任意子树的树根结点一定比其子孙结点更先插入，在左子树结点、右子树结点分别保持正确顺序的前提下，左子树任意结点在右子树任意节点之前或之后没有影响。
设 n 个结点构建一棵二叉查找树的排列个数为 f(n)，其左子树结点个数为 x， 右子树结点个数为 y，则左、右子树结点互相穿插的情况数是 x + y 中选 x 或 y 个的组合数。

f(n) = f(x) ∗ f(y) ∗ Cx，x+y
递归可求解。

c代码

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

#define x first
#define y second

typedef long long LL;
typedef pair<int, int> PII;

const int INF = 1e9;
const int N = 1e3 + 10, mod = 1e9 + 7;

int T; 
int n;
int s[N][2], e[N], idx;

void insert(int u, int x)//这里建立一棵排序二叉树
{
    if(e[0] == 0)
    {
        e[idx ++] = x;
    }
    if(x < e[u])
    {
        if(s[u][0] == -1)
        {
            e[idx] = x;
            s[u][0] = idx ++;
        }
        else insert(s[u][0], x);
    }
    if(x > e[u])
    {
        if(s[u][1] == -1)
        {
            e[idx] = x;
            s[u][1] = idx ++;
        }
        insert(s[u][1], x);
    }
}
int cnt[1020]; // 用来储存当前节点的子节点个数
int c[1020][1020];
LL dfs(int u)
{
    if(u == -1) return 1;

    LL l = dfs(s[u][0]); //遍历左子树
    LL r = dfs(s[u][1]); //遍历右子树

    cnt[u] = cnt[s[u][0]] + cnt[s[u][1]];

    LL res = (l * r) % mod * c[cnt[u]][cnt[s[u][0]]] % mod;
    
    cnt[u] ++; //加上本身
    return res;
}
void imit(){  //初始化组合数
    for(int i = 0; i < 1010; i++)
        for(int j = 0; j <= i; j++){
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
        }
}
int main() {
    imit();
    cin>>T;
    while(T--)
    {
    	cin>>n;
        memset(s, -1, sizeof s);
        memset(cnt, 0, sizeof cnt);
        memset(e, 0, sizeof e);
        idx = 0;
        for(int i = 0; i < n; i ++)
        {
            int x;
            scanf("%d", &x);
            insert(0, x);
        }
        cout << dfs(0) << endl;
    }
    return 0;
}

K: 超级大数

题目链接

思路分析

​ 题目中的n代表整数的位数，数量级达到了10^5，而int能表达的数量级只有9，longlong的能表达的数量级为19，因此这一题需要舍弃用int或longlong暴力枚举大数的方法，转而思考题目是否存在规律，用字符数组来解决。

​ 由于2，3，5，7都是质数，因此能被它们整除的数就是它们的乘积210。当n为4时，我们要从四位数中开始寻找，即从1000开始，从1000开始第一个被210整除的数为1000/210向下取整加上210，即210*4+210=1050。

​ 我们观察1000/210=4的小数，发现6位为一次循环即476190，可以知道n=4到n=9的答案为一组循环，而n=4之前的数是固定的。

c/c++代码

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<stdio.h>

int main()
{
	int t,n;
	scanf("%d",&t);
	char ans[6][4]={{"050"},{"080"},{"170"},{"020"},{"200"},{"110"}};
	while(t--)
	{
		scanf("%d",&n);
		if(n==1||n==2)
		{
			puts("-1");
			continue;
		}
		else if(n==3)
		{
			puts("210");
			continue;
		}
		printf("1");
		for(int i=0;i<n-4;i++)
			printf("0");
		printf("%s\n",ans[(n-4)%6]);
	} 
	return 0;
}