The 16th Heilongjiang Provincial Collegiate Programming Contest

Catalog

D - Doin’ Time

Topic ideas

It can be used as an exercise interval dp The revised template question of . So hard! , I am so rubbish . The general idea is similar to merging stones , The difference is that prefixes and are not preprocessed , But from i To j Multiply .

Title code

#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

Topic ideas

Because the title has been given to M The scope of is Less than or equal to 2 * n - 3, So we can conclude that there must be no such thing as

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

Data like this , So it can be concluded that as long as it is not A It matches n individual B You must be able to pair them all .

Title code

#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 //  If you don't, it will time out 
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

K. Keep Eating

Topic ideas

We can put all the weight together first sum, Then eat it once 1 weight , In the end k individual , Just eat it k / 2 That's all right. , Pay attention to the special judgment sum Is it greater than k.

Title code

#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;
}