2022年HNUCM信息科学与工程学院第五届新生赛——正式赛

2022年HNUCM信息科学与工程学院第五届新生赛——正式赛

A

打卡题，向下取整即可

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

B

统计数量，注意要是不能整除需要向上取整的问题

#include
using namespace std;
int main()
{
	char ch;
	int a = 0, b = 0;
	while (scanf("%c",&ch)!=EOF)
	{
		if (ch == 'M')
			a++;
		else
			b++;
	}
	cout << (a - 1) / 5 + 1 << " " << (b - 1) / 4 + 1 << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C

按照题意来就行了

#include
using namespace std;
int main()
{
	int ans = 0, a, b, c;
	int n;
	cin >> n;
	while (n--)
	{
		cin >> a >> b >> c;
		if (a >= 6 && b >= 6 && c >= 6 || a / 10 + b / 10 + c / 10)
			ans++;
	}
	cout << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

D

这题最重要的是看懂题意，注意一个坑就是必须要两个人都到终点后其中有个人才能返回

看图就行，两种方案取最大值

#include
#include
using namespace std;
int main()
{
	int a[4];
	for (int i = 0; i < 4; i++)
		cin >> a[i];
	sort(a, a + 4);
	cout << min(a[0] + 3 * a[1] + a[3], 2 * a[0] + a[1] + a[2] + a[3]) << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

E

从前往后依次出现“HNUCM”，出现一次完整的记录一次，原因自行领悟

#include
#include
#include
using namespace std;
int main()
{
    string s;
    string s1 = "HNUCM";
    while (cin >> s)
    {
        int cnt = 0, ans = 0;
        for (char c : s)
        {
            if (c == s1[cnt])
                cnt++;
            if (cnt == 5)
                cnt = 0, ans++;
        }
        cout << ans << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

F

数据量很小，直接可以暴力枚举每种价格选多少种菜，然后运用排列组合知识，就可以知道同一价值的n个菜选m个有多少种，接着分类相加，分布相乘即可

#include
using namespace std;
int C(int m, int n)
{
	int ans = 1;
	for (int i = 1; i <= m; i++)
		ans = ans * (n - m + i) / i;
	return ans;
}
int main()
{
	int a, b, c;
	int ans = 0;
	cin >> a >> b >> c;
	for(int i=0;i<=a;i++)
		for(int j=0;j<=b;j++)
			for (int k = 0; k <= c; k++)
			{
				if (i + 2 * j + 3 * k == 10)
					ans += C(i, a) * C(j, b) * C(k, c);
			}
	cout << ans << endl;
	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

G

动态规划题，和D题有点像的地方就是要找到合适的式子，且要分类讨论一下，加上里面的一些细节，在新生赛应该也算一个比较难的题了。这次的新生赛和蓝桥杯dp没有像往年考背包，倒都是考了线性dp。

令f[i] [j]为第i天选第j种外卖的总数，例如第i天选0的话，第i-1天选1,2加上第i-1天选0且i-2天不选0，这里需要注意的地方有两个，其中一个我在其中摔了个跟头。

1. 第i-1天选0且i-2天不选0不能写成dp[i-1] [0]-dp[i-2] [0]，因为dp[i-1] [j]!=dp[i-1] [0]+dp[i-1] [1]+dp[i-1] [2]
2. 第二个就是取模的需要注意，int相加会超过范围，所以dp数组用longlong

#include
#include
using namespace std;
typedef long long ll;
const int maxn = 100010, mod = 1e9 + 7;
long long f[maxn][3] = { {0,0,0},{1,1,1},{3,3,3} };
int main()
{
    int t, n;
    cin >> t;
    for (int i = 3; i <= maxn-10; ++i) {
        f[i][0] = (f[i - 2][1] + f[i - 2][2] + f[i - 1][1] + f[i - 1][2]) % mod;
        f[i][1] = (f[i - 2][0] + f[i - 2][2] + f[i - 1][0] + f[i - 1][2]) % mod;
        f[i][2] = (f[i - 2][1] + f[i - 2][0] + f[i - 1][1] + f[i - 1][0]) % mod;
    }
    /*
    for (int i = 3; i <= maxn - 10; i++)
        for (int j = 0; j < 3; j++)
            dp[i][j] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + mod - dp[i - 2][j])%
            mod;
            错误写法，因为dp[i-1][j]!=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
    */
    while (t--)
    {
        cin >> n;
        cout << (f[n][0] + f[n][1] + f[n][2])%mod << endl;
    }
    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

H

这题难的地方在于对于边界的讨论，但是我们可以将边界和其他点划分为一类，只要预处理一下矩阵就行

首先将问题拆分为两个子问题，1周围全是0的1的个数，0周围全是1的0的个数。

对于第一种，我们可以输入矩阵时行下标和列下标都从1开始，然后将第0，m+1行全部变为0，第0，n+1列全部变为0，这样我们就只需要判断每个1周围是否全部是0

对于第二种我们类似的将矩阵其全部预处理为1就行了

还有个问题就是输入老问题，回车问题，这里其实我们可以不需要用字符存储，我们用整型，可是怎么解决数字是连续输入的问题呢？我们只需要格式化输入%1d就行了

#include
#include
using namespace std;
int mp1[1005][1005], mp2[1005][1005];
int m, n;
int dir[8][2] = { -1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1 };
void init()
{
	for (int i = 0; i <= m + 1; i++)
		for (int j = 0; j <= n + 1; j++)
			mp1[i][j] = 0, mp2[i][j] = 1;
}
int main()
{
	cin >> m >> n;
	int ans = 0;
	init();
	for(int i=1;i<=m;i++)
		for (int j = 1; j <= n; j++)
		{
			scanf("%1d", &mp1[i][j]);
			mp2[i][j] = mp1[i][j];
		}
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
		{
			if (mp1[i][j] == 1)
			{
				bool flag = true;
				for (int k=0;k<8;k++)
					if (mp1[i + dir[k][0]][j + dir[k][1]] != 0)
					{
						flag = false;
						break;
					}
				ans+=flag;
			}
		}
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
		{
			if (mp2[i][j] == 0)
			{
				bool flag = true;
				for (int k = 0; k < 8; k++)
					if (mp2[i + dir[k][0]][j + dir[k][1]] != 1)
					{
						flag = false;
						break;
					}
				ans += flag;
			}
		}
	cout << ans << endl;
	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
43
44
45
46
47
48
49
50
51
52
53
54
55
56

I

按照题目来模拟，输入老师评分和学生评分时分别记录他们的最大最小值和总分，最后平均值就是和减去最大最小除以8，再分别乘以0.6和0.4相加就行了

#include
#include
using namespace std;
int main()
{
	double maxx = -1, minx =111, sum = 0, x,ans=0;
	for (int i = 0; i < 10; i++)
	{
		cin >>x;
		maxx = max(x, maxx);
		minx = min(x, minx);
		sum += x;
	}
	ans += (sum - maxx - minx) / 8*0.6;
	sum = 0, maxx = -1, minx =111;
	for (int i = 0; i < 10; i++)
	{
		cin >> x;
		maxx = max(x, maxx);
		minx = min(x, minx);
		sum += x;
	}
	ans += (sum - maxx - minx) / 8*0.4;
	printf("%.2lf\n", 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

J

又是一道和素数有关的题目

先写一个判断素数的函数备用，然后查找m到n之间为2 ^p-1且是素数的个数

#include
#include
using namespace std;
bool is_prime(long long n)
{
	if (n == 1)
		return false;
	if (n == 2)
		return true;
	for (long long i = 2; i * i <= n; i++)
		if (n % i == 0)
			return false;
	return true;
}
int main()
{
	int n, m,ans=0;
	cin >> m >> n;
	long long i;
	for (i = 1; i-1 < m; i *= 2)
	{ }
	for (; i-1 <= n; i *= 2)
		if (is_prime(i - 1))
			ans++;
	cout << ans << endl;
	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

K

照着题目模拟

不想写了，写了一下，看到那个表，无论写ifelse还是Switch都贼多，各位自己实现吧