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

A

打卡题，向下取整即可

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

B

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

#include
using namespace std;
int main()
{char ch;int a = 0, b = 0;while (scanf("%c",&ch)!=EOF){if (ch == 'M')a++;elseb++;}cout << (a - 1) / 5 + 1 << " " << (b - 1) / 4 + 1 << endl;return 0;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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;
}

K

照着题目模拟

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