比赛传送门

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


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

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

暴力枚举每一对 <i,j><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]dp[i][j] 表示将 AA 的前 ii 个字符转换为 BB 的前 jj 个字符的最小操作次数。由题可得状态转移方程:

{dp[i][j]=i+j,i=0j=0dp[i][j]=dp[i1][j1],A[i1]=B[j1]dp[i][j]=min(dp[i1][j],dp[i][j1],dp[i1][j1])+1,无特殊情况\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}

显然,如果 AABB 的长度差大于 11,那么必然不相似。

参考代码参考代码

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

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

将题单从小到大排序。用 ii 遍历,dayday 表示最多做题天数,若 aidaya_i ≥ day 就将 day++day++

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

参考代码参考代码

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

0 comments

No comments so far...