周测总结6-12

5k_sync_closer · 2021-06-14 19:59:49 · 个人记录

IOI boom again

T1 受欢迎度调查

计数排序板子题,sort 也能过

#include <iostream>
using namespace std;
int cnt[1001], n, m, t;
int main()
{
    cin >> n >> m;
    for(int i = 0;i < m;++i)
        cin >> t, ++cnt[t];
    for(int i = 0;i < 1000;++i)
        for(int j = 0;j < cnt[i];++j)
            cout << i << " ";
    return 0;
}

T2 序列

这道题的板子题是个黄的。

但这里数据给的较小,只有 1000。

所以我们可以用O(n ^ 2)的dp。

首先,记 dp[i] = 从 a[0] 到 a[i] 最长上升子序列的长度。

那么 dp[n] 就是从 a[0] 到 a[n] 最长上升子序列的长度,也就是 ans。

初始状态,dp[0] = 1,只有一个数。

然后就可以推 dp[i] 了。

我们借助可以与dp[i]连接的最长上升子序列的长度。

当然,还要判断连接后是否最优,得到方程 dp[i] = max(dp[i], dp[j])。

因为算的是可以与 dp[i] 连接的最长上升子序列的长度,所以最后要加上 1。

#include <iostream>
using namespace std;
int n, a[1001], dp[1001], ans;
int main()
{
    cin >> n;
    for(int i = 0;i < n;++i) cin >> a[i];
    dp[0] = 1;
    for(int i = 1;i < n;++i)
    {
        for(int j = 0;j < i;++j)
            if(a[i] > a[j]) dp[i] = max(dp[i], dp[j]);
        ++dp[i];ans = max(dp[i], ans);
    }
    cout << ans;
    return 0;
}

T3 验证码识别

模拟题,直接看code

#include <iostream>
#include <string>
using namespace std;
string s, t;int n;long long ans = 1;
int main()
{
    cin >> s;cin >> n;
    for(int i = 0;i < n;++i)
    {
        cin >> t;
        for(int j = 0;j < s.length();++j) //枚举原序列,找易混淆字符
            if(t.find(s[j]) != string::npos) //找到了
                ans *= t.length(), ans %= 1000000007; //更新答案,记!得!取!模!!!
    }
    cout << ans % 1000000007;
    return 0;
}

考场没取模,0pts

T4 木板覆盖2

横着放

前提是i ≥ m

方程为dp[i] = dp[i - 1] + dp[i - m]

记得取模和特判

#include <iostream>
using namespace std;
int n, m;long long dp[1000001];
int main()
{
    cin >> n >> m;
    if(m == 1) {cout << 1;return 0;}
    dp[0] = 1;
    for(int i = 1;i <= n;++i)
    {
        dp[i] = dp[i - 1];
        if(i >= m) dp[i] += dp[i - m];
        dp[i] %= 1000000007;
    }
    cout << dp[n] % 1000000007;
    return 0;
}