前言

D - 小A的线段（easy version）

思路：

  • 用暴力即可通过
  • 如——状态压缩

以下是代码部分

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5 + 10, mod = 998244353;
int vis[N];
vector<pair<int, int> > v;

bool check(int n)
{
    for(int i = 1; i <= n; i ++)
        if(vis[i] < 2)
            return false;
    return true;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    int pow_2 = 1 << m;
    for(int i = 1; i <= m; i ++)
    {
        int st, cd;
        cin >> st >> cd;
        v.emplace_back(st, cd);
    }
    int sum = 0;
    for(int i = 0; i < pow_2; i ++)
    {
        int k = i;
        for(int kl = 1; kl <= n; kl ++) vis[kl] = 0;
        for(auto it : v)
        {
            if(k % 2)
                for(int jl = it.first; jl <= it.second; jl ++)
                    vis[jl] ++;
            k /= 2;
        }
        if(check(n))
            sum ++, sum %= mod;
    }
    cout << sum << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

E - 小A的任务

思路：

  • 优先队列即可

以下是代码部分

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5 + 10;
ll a[N], b[N];

void solve()
{
  //输入
    int n, q, k;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];

    while(q --)
    {
        cin >> k;
        priority_queue<ll> prio;
        ll ans = 1e17, sum = 0, n_sum = 0;
      //找到数量为k的时候的b的最小状态
        for(int i = 1; i <= n; i ++)
        {
            sum += a[i];
            prio.push(b[i]);
            n_sum += b[i];
            if(prio.size() > k)
                n_sum -= prio.top(), prio.pop();
            if(prio.size() == k)
                ans = min(ans, sum + n_sum);
        }
        cout << ans << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

F - 小A的线段（hard version）

移步——出题人题解

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5 + 10, mod = 998244353;

int dp[401][401][401];

void add(int& ret, int x)
{
    ret += x;
    if(ret >= mod) ret -= mod;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> v;
    vector<int> s(m + 1), t(m + 1);
  //离散化处理
    for(int i = 1; i <= m; i ++)
    {
        cin >> s[i] >> t[i];
      //统一下标
        s[i] --;
      //存储左端点
        v.push_back(s[i]);
      //存储右端点
        v.push_back(t[i]);
    }
  //存储断点0， n
    v.push_back(n), v.push_back(0);
  //从小到大排序
    sort(v.begin(), v.end());
    //去重
    v.resize(unique(v.begin(), v.end()) - v.begin());
    n = (int)v.size();
    vector<pair<int, int> > a(m + 1);
    for(int i = 1; i <= m; i ++)
    {
      //二分查找第一个小于等于s[i], 并存入位置
        s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
      //二分查找第一个小于等于t[i], 并存入位置
        t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
      //存入到a[i]当中
        a[i] = {s[i], t[i]};
    }
//从小到大排序，并跳过下标为1的时候
    sort(a.begin() + 1, a.end());
//初始化
    dp[0][0][0] = 1;
    for(int k = 1; k <= m; k ++)
        for(int i = 0; i < n; i ++)
            for(int j = i; j < n; j ++)
            {
                if(dp[k - 1][i][j] == 0) continue;
                add(dp[k][i][j], dp[k - 1][i][j]);
                if(a[k].first <= i)
                    add(dp[k][max(i, min(j, a[k].second))][max(j, a[k].second)], dp[k - 1][i][j]);
            }
    cout << dp[m][n - 1][n - 1] << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}