The 16th Heilongjiang Provincial Collegiate Programming Contest

目录

D - Doin’ Time

题目思路

可以作为练习区间dp的改后的模板题。 好难啊，我好垃圾啊。 大体的思路和合并石子差不多，区别就是预处理的不是前缀和，而是从i到j相乘。

题目代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 310;
const int mod = 1000003;

int n;
LL p[N];
LL s[N][N], f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> p[i];
        
    for (int i = 1; i <= n; i ++)
    {
        LL t = 1;
        for (int j = i; j <= n; j ++)
            t = (t * p[j]) % mod, s[i][j] = t;
    }
        
    for (int len = 2; len <= n; len ++)
    {
        for (int i = 1; i + len - 1 <= n; i ++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = -1;
            
            for (int k = l; k < r; k ++)
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + (s[i][k] - s[k + 1][r]) * (s[i][k] - s[k + 1][r]));
            }
        }
    }
    
    cout << f[1][n] << '\n';
    return 0;
}

J - JOJO’s Factory

题目思路

因为题目已经给了M的范围即 小于等于2 * n - 3，所以我们可以得出一定不会有像

4 6
1 1
1 2
1 3
2 1
2 2
2 3

这样的数据，所以就可以得出只要不是A里面匹配了n个B就一定可以全部配对。

题目代码

#include <bits/stdc++.h>

using namespace std;

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
const int N = 5e5 + 10;

int ma[N], mb[N], n, m;

void solve()
{
    cin >> n >> m;

    int a = n, b = n;
    while (m -- )
    {
        int x, y;
        cin >> x >> y;

        ma[x] ++;
        mb[y] ++;

        if (ma[x] >= n)
            a --;
        if (mb[y] >= n)
            b --;
    }

    cout << min(a, b) << '\n';
}   

int main()
{
    IOS // 不加会超时
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

K. Keep Eating

题目思路

我们可以先将全部的重量合起来 sum，然后一次就吃1重量，最后剩下k个，就直接吃 k / 2 就可以了，注意特判一下 sum 是否大于 k。

题目代码

#include <bits/stdc++.h>

using namespace std;

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

void solve()
{
    LL n, k;
    cin >> n >> k;

    LL res1 = 0, res2 = 0;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;

        res1 += x;
    }

    if (res1 < k)
    {
        cout << 0 << '\n';
        return;
    }
    
    res2 += res1 - k + k / 2;

    cout << res2 << '\n';
}

int main()
{
    IOS int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}