比赛传送门

本题解仅供参考，严禁抄袭模仿

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 完全平方数

$1 ≤ n ≤ 1000$，并不是很大，考虑暴力枚举。

暴力枚举每一对 $<i,j>$ 组合，检验是否为完全平方数即可。

也没什么难度喵(^_−)☆。

$参考代码$

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。

$dp[i][j]$ 表示将 $A$ 的前 $i$ 个字符转换为 $B$ 的前 $j$ 个字符的最小操作次数。由题可得状态转移方程：

$$\begin{cases} dp[i][j] = i+j, & i=0或j=0 \\ dp[i][j]=dp[i-1][j-1], & A[i - 1] = B[j - 1] \\ dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) +1, & 无特殊情况 \end{cases}$$

显然，如果 $A$ 与 $B$ 的长度差大于 $1$，那么必然不相似。

$参考代码$

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 做题

$1≤n≤10^6,1≤a_i≤10^9$。考虑贪心。

将题单从小到大排序。用 $i$ 遍历，$day$ 表示最多做题天数，若 $a_i ≥ day$ 就将 $day++$。

最后输出做题天数 $day$ 即可。主要难度在贪心策略。

$参考代码$

sort(a + 1, a + n + 1);
int i = 1, cnt = 0; //cnt为做题天数
while (i <= n)
{
	if (a[i] >= cnt + 1) cnt++;
	i++;
}

$$完$$