感谢验题同学对本套题目提出的反馈。

题解中的复杂度默认为单组测试的时间复杂度。

A.小A的文化节

签到题，按照题意模拟即可。

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
#define endl "\n"

void solve()
{
    int n, m; cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        ans += a[x];
    }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}

B.小A的游戏

由于每局游戏结果可能有胜平负三种，因此小A和小B的得分差值应该是 的倍数，因为每局游戏胜者得到 分，败者不得分，若打平则双方都得 分。这意味着他们的得分差值只能是 等值。

因此只需要判断 是否为零即可。

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
#define endl "\n"

void solve() 
{
    int x, y; cin >> x >> y;
    cout << ((x - y) % 3 ? "No" : "Yes") << endl;
}
int main() 
{
    int _ = 1;
    cin >> _;
    while(_--) solve();
    return 0;
}

C.小A的数字

由于需要最小化答案，我们可以贪心地构造答案，当 在某位上为 时，我们可以令答案在该位为 ，其余情况可以令答案在该位为 。

这种构造方案可以得到一个各数位均与 不同的最小整数 。

因此在得到的答案为 时，我们需要进行特判，如果 的最后一位数字为 ，答案则为 ，否则答案为 。

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
#define endl "\n"

void solve() 
{
    string s; cin >> s;
    int res = 0;
    string ans;
    for(auto x : s) {
        if(x == '0') ans += '1';
        else ans += '0';
    }
    res = stoi(ans);
    if(!res) res = 1 + (s.back() == '1');
    cout << res << endl;
}
int main() 
{
    int _ = 1;
    cin >> _;
    while(_--) solve();
    return 0;
}

D.小A的线段（easy version）

观察到 非常小，因此可以考虑二进制枚举线段的选择方案。

在处理线段覆盖的时候可以使用差分优化（不用差分的代码因为与正解仅有常数差距且牛子的机器太快了所以也能通过）

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
#define endl "\n"

void solve()
{
    int n, m; cin >> n >> m;
    vector<pii> a(m);
    vector<int> d(n + 10);
    for(int i = 0; i < m; i++) cin >> a[i].first >> a[i].second;
    int ans = 0;
    for(int mask = 1; mask < 1 << m; mask++) {
        for(int i = 0; i < m; i++) {
            if((mask >> i) & 1) {
                d[a[i].first]++, d[a[i].second + 1]--;
            }
        }
        bool f = 1;
        for(int i = 1; i <= n; i++) {
            d[i] += d[i - 1];
            f &= d[i] >= 2;
            if(!f) break;
        }
        ans += f;
        for(int i = 1; i <= n; i++) d[i] = 0;
    }
    cout << ans << endl;
}
int main() 
{
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}

E.小A的任务

不难发现答案由两部分组成，分别是 类任务的时间和 类任务的时间。

记完成前 个 类任务的时间为 ，完成前 个任务 类任务中前 小的时间为 。可以通过优先队列动态维护，答案为 。

ps：用 multiset 实现疑似常数巨大。

pps：由于出题人水平有限，不知道此题的询问内容为 时是否是可做题，欢迎大家讨论做法

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl "\n"

void solve()
{
    int n, q; cin >> n >> q;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int _ = 1; _ <= q; _++) {
        int k; cin >> k;
        i64 sum1 = 0, sum2 = 0, ans = 1e18;
        priority_queue<int> q;
        for(int i = 1; i <= n; i++) {
            sum1 += a[i];
            if(q.size() < k) {
                sum2 += b[i];
                q.push(b[i]);
            }
            else if(q.size() == k) {
                int now = q.top();
                if(b[i] < now) {
                    sum2 -= now;
                    sum2 += b[i];
                    q.pop(); q.push(b[i]);
                }
            }
            if(q.size() == k) ans = min(ans, sum1 + sum2);
        }
        cout << ans << endl;
    }
}
int main() 
{
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}

F.小A的线段（hard version）

由于至多只有 条线段，因此至多只有 的有效点，可以通过离散化降低复杂度。

在离散化之后将线段按照左端点为第一关键字，右端点为第二关键字双升序排序，在考虑放置线段 后的某状态 需满足以下条件：

1. 至少被覆盖两次
2. 恰好被覆盖一次
3. 恰好未被覆盖

记状态 为只考虑前 个线段，至少被覆盖两次的点最大编号为 ，恰好被覆盖一次的点最大编号为 的方案数量。

当 转移至状态 时，需进行分类讨论：

1. 若当前枚举的线段的左端点 小于等于当前枚举区间左端点 ，有转移方程：

   

2. 否则仅有转移：

   

时间复杂度：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int 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]);
    }
    v.push_back(n), v.push_back(0);
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    n = v.size();
    vector<pii> a(m + 1);
    for (int i = 1; i <= m; i++) {
        s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
        t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
        a[i] = {s[i], t[i]};
    }
    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] << endl;
}
int main()
{
    solve();
    return 0;
}