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

A

打卡题,向下取整即可

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	cout << n / 7 << endl;
	return 0;
}

B

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

#include<iostream>
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;
}

C

按照题意来就行了

#include<iostream>
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;
}

D

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

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

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

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

E

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

#include<iostream>
#include<string>
#include<unordered_map>
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;
}

F

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

#include<iostream>
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;
}

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

H

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

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

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

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

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

#include<iostream>
#include<cstring>
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;
}

I

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

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

J

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

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

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

K

照着题目模拟

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

12-06 08:04