- 题解
GESP测试题B-E题解
- 2024-5-11 21:25:42 @
本题解仅供参考,严禁抄袭模仿
T1 字母求和
考虑模拟。
没有什么坑点,主要考查基础知识。
int n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
char x;
cin >> x;
if (x >= 'a' && x <= 'z') sum += x - 'a' + 1;
else sum += -1 * (int)x; //字符转整数
}
cout << sum;
return 0;
}
T2 完全平方数
,并不是很大,考虑暴力枚举。
暴力枚举每一对 组合,检验是否为完全平方数即可。
也没什么难度喵(^_−)☆。
int n, a[100005], ans = 0;
cin >> n;
for (int i = 1; i <= n;i ++) cin >> a[i];
for (int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
{
int y = a[i] + a[j];
if ((int)sqrt(y) * (int)sqrt(y) == y) ans++; //完全平方数判定
}
cout << ans;
return 0;
}
T3 相似字符串
终于开始上难度了
因为操作比较多情况,考虑动态规划dp。
表示将 的前 个字符转换为 的前 个字符的最小操作次数。由题可得状态转移方程:
显然,如果 与 的长度差大于 ,那么必然不相似。
bool f(string A, string B) {
int m = A.size(), n = B.size();
if (abs(m - n) > 1) return false; //判断无解
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; ++i) { //dp
for (int j = 0; j <= n; ++j) {
if (i == 0 || j == 0) {
dp[i][j] = i + j;
} else if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
}
}
}
return dp[m][n] <= 1; //只要少于1次操作就相似
}
T4 做题
。考虑贪心。
将题单从小到大排序。用 遍历, 表示最多做题天数,若 就将 。
最后输出做题天数 即可。主要难度在贪心策略。
sort(a + 1, a + n + 1);
int i = 1, cnt = 0; //cnt为做题天数
while (i <= n)
{
if (a[i] >= cnt + 1) cnt++;
i++;
}