11.25 NOIP模拟赛2 题解

T1 数对（pair）

给定 $n$ 个正整数，求满足 $a_i$ 是 $a_j$ 倍数的数对数量。

题目分析

$(O(n\sqrt n))$ 做法

对于每个数 $a_i$ 求出它的因数，用桶来存储每个数作为因数的出现次数，循环统计答案即可。

$O(n\log n)$做法

对于每个数 $a_i$ 求出其不大于 $\max_{i=1}^{n}a_i$ 的所有倍数，同样用桶存储每个数作为其余数倍数的出现次数，统计答案即可。复杂度为调和 $O(n\log n)$。

Code

// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
// #define ONLINEJUDGE
// #define MULTI_CASES
const int MaxN = 2e5 + 100;
const int MaXN = 5e5 + 100;
const int INF = 1e9;
int T = 1, N, M;
int a[MaxN];
int vis[MaXN];
int ans[MaXN];
inline void Solve()
{
    cin >> N;
    int maxn = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
        // vis[a[i]]=1;
        vis[a[i]]++;
        maxn = max(maxn, a[i]);
    }
    for (int i = 1; i <= N; i++)
    {
        if (ans[a[i]])
        {
            // ans[a[i]]++;
            continue;
        }
        for (int j = 1; j * a[i] <= maxn; j++)
        {
            ans[a[i]] += vis[a[i] * j];
            if (j == 1)
            {
                ans[a[i]]--;
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= N; i++)
    {
        sum += ans[a[i]];
    }
    cout << sum << endl;
}
signed main()
{
#ifndef ONLINEJUDGE
    freopen("pair.in", "r", stdin);
    freopen("pair.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

T2 运货（transport）

题目分析

首先，对于每个货物，最优的小车出发时间应为其到达卸货口的时间减去小车到货架的时间，所以我们可以将所有的小车出发时间存储下来，对其从小到大排序，可以得到一个序列 $a_i$。显然通过贪心的思想，每辆小车在这个序列中的时间出发才是最优的。

题目要求最少花费的时间，那么显然可以发现，所有小车走了最远的那辆车所花费的时间就是最短时间。我们对于 $a_i$，运送它的小车编号应为 $i\mod M$，这辆小车运输完 $a_i$ 后的花费时间应该为 $\max(max_{i\mod M},a_i)$，那么对于 $M$ 个小车分别求出其最多花费的时间，统计答案即可。

Code

// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
// #define ONLINEJUDGE
// #define MULTI_CASES
const int MaxN = 2e5 + 100;
const int INF = 1e9;
int T = 1, N, M;
int a[MaxN];
int ans[2010];
inline void Solve()
{
    cin >> N >> M;
    // for (int i = 1; i <= M; i++)
    // {
    //     q.push(0);
    // }
    // int ans = 0;
    vector<int> f;
    for (int i = 0; i < N; i++)
    {
        int len;
        cin >> len;
        for (int j = 1; j <= len; j++)
        {
            int x;
            cin >> x;
            f.push_back(x - i - 1);
        }
    }
    sort(f.begin(), f.end());
    for (int i = 0; i < (int)f.size(); i++)
    {
        ans[i % M] = max(ans[i % M], f[i]) + N + 1;
    }
    int sum = 0;
    for (int i = 0; i < M; i++)
    {
        sum = max(sum, ans[i]);
    }
    cout << sum << endl;
}
signed main()
{
#ifndef ONLINEJUDGE
    freopen("transport.in", "r", stdin);
    freopen("transport.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

T3 找爸爸（daddy）

题目分析

题目要求DNA序列的最大相似程度，考虑 $dp$ 做法，可以得出 $dp_{i,j,k}$ 表示 a序列长度为 $i$，b序列长度为 $j$ ，末尾有/无空格（$k=0$ 无空格，$k=1$ 表示a序列有空格，$k=2$ 表示b序列末尾有空格）时的最大相似程度。

关于空格，对于每段连续空格，相似程度为 $-A-B\times (k-1)$ 因为 $A,B$ 都是正整数，所以其相似程度一定为负数。对于一个空格，会减少 $A$ 点相似度，如果在后面多添加一个空格，则会进一步减少 $B$ 点相似度。

状态转移方程如下：

$$dp_{i,j,0}=\max(dp_{i-1,j-1,0},dp_{i-1,j-1,1},dp_{i-1,j-1,2})+a_{s1_i,s2_j}$$

$$dp_{i,j,1}=\max(dp_{i-1,j,0}-A,dp_{i-1,j,1}-B,dp_{i-1,j,2}-A)$$

$$dp_{i,j,2}=\max(dp_{i,j-1,0}-A,dp_{i,j-1,1}-A,dp_{i,j-1,2}-B)$$

Code

// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
// #define ONLINEJUDGE
// #define MULTI_CASES
const int MaxN = 2e3 + 100;
const int INF = 1e18;
int T = 1, N, M;
int a[10][10];
int dp[MaxN][MaxN][4];
int A, B;

int g(int k)
{
    return -A - B * (k - 1);
}
inline void Solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    map<char, int> mp;
    mp['A'] = 1;
    mp['T'] = 2;
    mp['G'] = 3;
    mp['C'] = 4;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> A >> B;
    for (int i = max(s1.size(), s2.size()); i >= 1; i--)
    {
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = dp[0][i][1] = dp[i][0][2] = -INF;
        dp[0][i][1] = dp[i][0][2] = g(i);
    }
    for (int i = 1; i < s1.size(); i++)
    {
        for (int j = 1; j < s2.size(); j++)
        {
            dp[i][j][0] = max({dp[i - 1][j - 1][0], dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]}) + a[mp[s1[i]]][mp[s2[j]]];
            dp[i][j][1] = max({dp[i - 1][j][0] - A, dp[i - 1][j][1] - B, dp[i - 1][j][2] - A});
            dp[i][j][2] = max({dp[i][j - 1][0] - A, dp[i][j - 1][1] - A, dp[i][j - 1][2] - B});
        }
    }
    cout << max({dp[s1.size() - 1][s2.size() - 1][0], dp[s1.size() - 1][s2.size() - 1][1], dp[s1.size() - 1][s2.size() - 1][2]}) << endl;
}
signed main()
{
#ifndef ONLINEJUDGE
    freopen("daddy.in", "r", stdin);
    freopen("daddy.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}