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
这题最重要的是看懂题意,注意一个坑就是必须要两个人都到终点后其中有个人才能返回
看图就行,两种方案取最大值
#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,这里需要注意的地方有两个,其中一个我在其中摔了个跟头。
- 第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]
- 第二个就是取模的需要注意,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都贼多,各位自己实现吧