MX Day 6

· · 生活·游记

T1：

这道题没什么好说的，就是很简单的区间DP，因为我们可以发现这就是一道区间合并类问题，我们定义dp[i][j][k]，表示这一段的可以用句法k表示，相当于一种bool数组，之后，就是三层循环暴力查找可能性。

code：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int p[309], q[309], r[309];
int n, a[209], m;
bool dp[109][109][309];
vector<pair<int, int>> mp[309];
signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    m = read();
    for (int i = 1; i <= m; i++)
    {
        p[i] = read();
        q[i] = read();
        r[i] = read();
        mp[p[i]].push_back(make_pair(q[i], r[i]));
        // mp[q[i]][r[i]][++mpl[q[i]][r[i]]] = p[i];
    }
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        dp[i][i][a[i]] = 1;
    }
    // cout << "m=" << m << " n=" << n << endl;
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i <= n - len + 1; i++)
        {
            int j = i + len - 1;
            for (int k = i + 1; k <= j; k++)
            {
                for (int p = 1; p <= m; p++)
                {
                    for (auto [x, y] : mp[p])
                    {
                        dp[i][j][p] |= dp[i][k - 1][x] & dp[k][j][y];
                    }
                }
            }
        }
    }
    bool gg = 0;
    for (int i = 1; i <= m; i++)
    {
        if (dp[1][n][i])
        {
            cout << i << ' ';
            gg = 1;
        }
    }
    if (!gg)
    {
        cout << -1;
    }
    return 0;
}

T2：

大致解法：

T3：

分类讨论：

1、我们可以发现这道题就是一道建立在基环树之上的题目；我们可以分三种情况讨论，分别是：环上没有‘-’，有一条‘-’，以及有多条。

2、关键点：我们要以环上最后一条被连上的边为分界线；

3、贪心大体思路：先连‘+’，再连‘-’；

4、当为情况二时，我们要考虑到，我们首先要要连的是树上的边，因为我们先连环上的边会导致在倒数第二条边连上时会使代价不变，因为环上最后一条‘-’会不满意，所以顺序是：树上‘+’--->环上‘+’--->‘-’边

5、为情况一或三时，我们其实不用管那么多，反正不管树上环上，先连‘+’，之后，我们先连树上的‘-’，再连环上的‘-’。

6、完结撒花！！！