预估难度：

Very easy：A、I

Easy：D、C

Mid：F、G

Mid hard：B、J

Hard：E、H

A

有三种情况：

1. ：没有交集，共同痕迹为。
2. ：只有上下的方块有交集，共同痕迹为左右两块。
3. ：上下左右都有交集，共同痕迹为一个十字。

计算对应的图形面积即可。

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    LL w, l, r;
    cin >> w >> l >> r;
    if(r * 2 <= w){ // 没有交集
        cout << 0 << endl;
        return 0;
    }
    if(r * 2 <= l){ // 只有上下有交集
        cout << r * (r * 2 - w) * 2 << endl;
        return 0;
    }
    cout << (r * 2 - w) * l + (r * 2 - l) * w - (r * 2 - w) * (r * 2 - l) << endl; // 上下左右都有交集
    return 0;
}

B

由点经过任意次传送到点可以用从点直接传送到点来代替，因此最优方案传送操作只会传送一次。

因此到任意一个终点的最小代价的路径可以分为两种：

• 不使用传送门，直接走到该终点
• 先走到一个离起点最近的传送门，传送到离该终点最近的传送门，然后走到该终点。

转移和数字三角形类似，使用两个数组，表示从起点开始向右/下走的最短路，表示从任意一个终点开始向左/上走的最短路。

遍历所有的格子，第一种路径的最小花费即为所有终点的的最小值。

对于第二种路径，对于一个传送门，前半段（从起点走到并使用传送门）最小花费即为，后半段（从另一个传送门传送到后从走到最近的终点）最小花费即，遍历所有的传送门，分别取两段花费的最小值，将两段的最小值加在一起和第一种路径取即最终的答案。

由于此题的数据定在，用求最短路也可通过，只需要将二维的状态压到一维，每个格子分别向右、向下连边，对于传送门，建立一个虚拟源点，将各个传送门和虚拟源点之间连双向边，跑单源最短路即可。

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
using LL = long long;

int cost(int x){
    return x > 0 ? x : 0;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int> (m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    vector<vector<LL>> dp1(n, vector<LL> (m, 1e18));
    dp1[0][0] = cost(a[0][0]); // 从起点开始走
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(i > 0) dp1[i][j] = min(dp1[i][j], dp1[i - 1][j] + cost(a[i][j])); // 下
            if(j > 0) dp1[i][j] = min(dp1[i][j], dp1[i][j - 1] + cost(a[i][j])); // 右
        }
    }
    vector<vector<LL>> dp2(n, vector<LL> (m, 1e18));
    for(int i = n - 1; i >= 0; i--){
        for(int j = m - 1; j >= 0; j--){
            if(a[i][j] == 0) dp2[i][j] = 0; // 从终点开始走
            else{
                if(i + 1 < n) dp2[i][j] = min(dp2[i][j], dp2[i + 1][j] + cost(a[i][j])); // 上
                if(j + 1 < m) dp2[i][j] = min(dp2[i][j], dp2[i][j + 1] + cost(a[i][j])); // 左
            }
        }
    }
    LL res = 1e18;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!a[i][j]) res = min(res, dp1[i][j]); // 第一种路径最小代价
        }
    }
    LL res1 = 1e18, res2 = 1e18;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] < 0){
                res1 = min(res1, dp1[i][j] - a[i][j]); // 起点到传送门并使用传送门最小代价
                res2 = min(res2, dp2[i][j]); // 传送门到终点最小代价
            }
        }
    }
    res = min(res, res1 + res2);
    if(res > k || res == 1e18) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
using LL = long long;
typedef pair<LL, int> PII;

int n, m, k;

int get(int x, int y){ // 二维压一维
    return (x - 1) * m + y;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    int N = n * m;
    vector<int> a(N + 1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x;
            cin >> x;
            a[get(i, j)] = x;
        }
    }
    vector<vector<PII>> g(N + 1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int u = get(i, j);
            if(i + 1 <= n){ // 向下连边
                int v = get(i + 1, j);
                int w = max(0, a[v]);
                g[u].emplace_back(v, w);
            }
            if(j + 1 <= m){ // 向右连边
                int v = get(i, j + 1);
                int w = max(0, a[v]);
                g[u].emplace_back(v, w);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int u = get(i, j);
            if(a[u] < 0){ // 传送门和超级源点连边
                int w = -a[u];
                g[u].emplace_back(0, w);
                g[0].emplace_back(u, 0);
            }
        }
    }
    vector<LL> dist(N + 1, 1e18);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    vector<bool> st(N + 1, false);
    int s = get(1, 1);
    dist[s] = max(0, a[s]);
    q.emplace(dist[s], s);
    LL res = 1e18;
    while(!q.empty()){
        auto [dis, u] = q.top();
        q.pop();
        if(st[u]) continue;
        st[u] = true;
        if(u && a[u] == 0){ // 第一次到终点就是最小代价
            res = dis;
            break;
        }
        for(auto [v, w] : g[u]){
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                q.emplace(dist[v], v);
            }
        }
    }
    if(res > k) cout << -1 << endl;
    else cout << res << endl; 
    return 0;
}

C

从前向后依次考虑每个位置，每次贪心地放所有可放字母中剩余数量最多的一个即可。

可以用优先队列维护当前所有剩余字母及其剩余数量，对于每个位置：

• 在剩余字母中选择一个剩余数量最多的一个，尝试将其放到末尾（看其和最后一位或倒数第二位是否冲突）：
  • 如果剩余数量最多的字母能放到末尾，就将其放到末尾，若该字母放完后仍有剩余，则继续保留在优先队列中。
  • 如果剩余数量最多的字母不能放到末尾，跳过这个字母（将其弹出并存到一个临时的队列中，该位置处理完后再放回队列），继续看下一个剩余数量最多的字母。
• 如果尝试过所有剩余字母都不能放（都与最后一位或倒数第二位冲突），则无解，输出 。

也可以每次循环遍历，找到数量最多的字母来尝试放到末尾。

或者每次排序，找到数量最多的字母来尝试放到末尾。

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int sum = 0;
    priority_queue<pair<int, char>> pq; // 第一维纯数量，第二维存字母
    for(int i = 0; i < 26; i++){
        int x;
        cin >> x;
        if(x > 0) pq.emplace(x, 'a' + i);
        sum += x;
    }
    string res;
    queue<pair<int, char>> tmp; // 临时队列，用来临时存因为构成回文而在该位置放不了的字母
    while(!pq.empty()){ // 循环判断每个位置
        auto [cnt, ch] = pq.top(); // 剩余数量最多的字母
        pq.pop();
        if(res.size() >= 1 && ch == res[res.size() - 1]){ // 在该位置放不了
            tmp.emplace(cnt, ch); // 存到临时队列里
            continue;
        }  
        if(res.size() >= 2 && ch == res[res.size() - 2]){ // 在该位置放不了
            tmp.emplace(cnt, ch); // 存到临时队列里
            continue;
        }
        res += ch; // 能放就放
        cnt--; // 剩余数量-1
        if(cnt > 0) pq.emplace(cnt, ch); // 如果还有剩余，放回队列继续判断下一个位置
        while(!tmp.empty()){ // 将临时数组中的字母放回队列，继续判断下一个位置
            pq.emplace(tmp.front());
            tmp.pop();
        }
    }
    if(res.size() == sum) cout << res << endl; 
    else cout << -1 << endl;
    return 0;
}

D

题意其实就是，有段区间，把所有有公共部分的区间两两合并（比如），在合并后的区间中，判断是否存在一个长度大于的区间。

只需将所有区间按左端点从小到大排序，依次遍历进行区间合并：

• 如果下一个区间的左端点 当前区间的右端点，就可以合并，更新右端点。
• 否则不能合并，新开一段。

在合并过程中，维护最大区间长度 。

若最大区间长度大于，输出；否则输出。

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, x;
    cin >> n >> x;
    vector<PII> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end()); // 优先按左端点从小到大排序
    int l = a[0].first, r = a[0].second; // 第一个区间
    int res = r - l + 1; // 第一个区间的长度
    for(int i = 1; i < n; i++){ 
        if(a[i].first <= r) r = max(r, a[i].second); // 和前一个区间有交集，就合并
        else{ // 没有交集就另开一个区间
            l = a[i].first; 
            r = a[i].second;
        }
        res = max(res, r - l + 1);
    }
    if(res > x) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

E

按题意模拟，如果暴力枚举所有的释放技能情况，复杂度为指数级别，难以接受，但实际状态数很少，考虑用记忆化搜索优化。

对于每轮出招，需要考虑的信息只有：Alice和Bob的当前血量、Alice各技能的冷却时间、Bob技能2的冷却时间、该轮该谁出招，可以用一个五维的数组来进行记忆化。对于Alice各技能的冷却时间，只有三种，可以将其用三进制转十进制的方法将其转化成一个十进制数来表示，最多个技能，数组预留的位置即可。

用递归模拟游戏的每个回合，暴力枚举每个技能，求出释放该技能后两人的状态（血量、技能冷却时间、下一轮该谁出招），如果有人血量降到，直接回溯返回该分支的结果，否则继续用新的状态向下递归，递归结束后用记忆化数组记录该状态的结果，如果下次遇到完全相同的状态，直接返回数组的值。

需要注意：在的回合中，不能直接用两个回血技能的回血量来比较，要比较实际的回血量，因为在一些情况下，虽然技能比技能回血多，但两个技能都只能给恢复到满血状态，这时显然释放无冷却的技能肯定比释放技能要优。比如在初始血量较低时第一回合轮到使用技能，但现在为满血状态，释放两个技能的实际回血量都为，这时要优先选择释放技能。

#include <iostream>
#include <cstring>
#include <vector>
#define endl '\n'
using namespace std;

int dp[201][201][81][3][2];
int n, k, limb;
vector<int> dmg, cd;

int ceil8(int x){ // x * 0.8 向上取整
    return (8 * x + 9) / 10;
}

int get(vector<int> alice_cd){ // 用三进制转十进制将Alice各技能的cd转化成一个数字
    int res = 0;
    int p = 1;
    for(int i = 0; i < n; i++){
        res += p * alice_cd[i];
        p *= 3;
    }
    return res;
}

int dfs(int a, int b, vector<int> &alice_cd, int bob_cd, int is_alice){
    if(a <= 0) return false; // 如果该状态Alice或Bob死亡，回溯向上返回结果
    if(b <= 0) return true;
    int mask = get(alice_cd);
    auto &res = dp[a][b][mask][bob_cd][is_alice]; // 记忆化
    if(~res) return res; // 如果已经处理过这个状态了，直接返回
    if(is_alice){ // Alice 回合
        for(int i = 0; i < n; i++){ // 遍历Alice的每个技能，尝试释放，向下递归
            if(alice_cd[i] == 0){ // 如果不在冷却
                int newb = max(0, b - dmg[i]); // 释放后Bob的血量
                int newa = max(0, a - ceil8(dmg[i])); // 释放后Alice的血量
                vector<int> nxt_alice_cd = alice_cd;
                for(int j = 0; j < n; j++){
                    if(j != i) nxt_alice_cd[j] = max(0, alice_cd[j] - 1); // 其他技能cd-1
                    else nxt_alice_cd[j] = cd[j]; // 该技能cd恢复到初始值
                }
                int nxt_bob_cd = max(0, bob_cd - 1); // Bob的技能2的cd-1
                res = dfs(newa, newb, nxt_alice_cd, nxt_bob_cd, 0); // 继续向下递归，同时更新dp数组
                if(res == 1) return true; // 向上回溯
            }
        }
    }
    else{ // Bob 回合
        int max_blood = k; // 优先使用没有冷却的技能1
        int nxt_bob_cd = max(0, bob_cd - 1); // 使用技能1的话，技能2的cd-1
        if(bob_cd == 0){
            int real1 = min(b + max_blood, limb) - b; // 使用技能1实际能回复的血量
            int real2 = min(b + a / 2, limb) - b; // 使用技能2实际能回复的血量
            if(real2 > real1){ // 如果技能2回血回的多，用技能2
                max_blood = a / 2;
                nxt_bob_cd = 2; // 技能2的cd恢复到初始值
            }
        }
        vector<int> nxt_alice_cd = alice_cd;
        for(int i = 0; i < n; i++){
            nxt_alice_cd[i] = max(0, nxt_alice_cd[i] - 1); // Alice的每个技能的cd-1
        }
        res = dfs(a, min(b + max_blood, limb), nxt_alice_cd, nxt_bob_cd, 1); // 继续向下递归，同时更新dp数组
        if(res == 1) return true; // 向上回溯
    }
    res = 0;
    return false;
}

void solve(){
    int a, b;
    cin >> n >> k >> a >> b;
    limb = b;
    dmg.assign(n, 0);
    cd.assign(n, 0);
    for(int i = 0; i < n; i++){
        cin >> dmg[i] >> cd[i];
    }
    memset(dp, -1, sizeof dp);
    vector<int> alice_cd(n, 0);
    int bob_cd = 0;
    int is_alice = a < b; // 血量低的先释放技能
    if(dfs(a, b, alice_cd, bob_cd, is_alice)) cout << "Alice wins!" << endl;
    else cout << "Bob wins!" << endl;
}   

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

F

对于两个国家和，如果向进谏并献上国礼，就从向连一条有向边。

遍历任意两个国家和，如果和之间有双向边，就说明他们是朋友；如果有单向边，就说明他们是敌人。

对朋友和敌人的关系，可以用拓展域并查集（反集）来处理：

• 如果和是朋友，就将、合并
• 如果和是敌人，就合并、合并，将、合并。

这样就能实现朋友的朋友是朋友、敌人的敌人是朋友。

合并完后，只需找到所有联通块中国家数量最多的一个，用带权并查集或者遍历一遍将各个节点累加到其祖先即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#define endl '\n'
using namespace std;
using LL = long long;

struct DSU{
    vector<int> fa;
    vector<int> sz;
    DSU(int n){
        fa.resize(n * 2 + 1);
        sz.resize(n * 2 + 1);
        iota(fa.begin(), fa.end(), 0);
        fill(sz.begin() + 1, sz.begin() + n + 1, 1);
    }
    int find(int x){
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unite(int a, int b){
        int pa = find(a), pb = find(b);
        if (pa == pb) return;
        sz[pb] += sz[pa];
        fa[pa] = pb;
    }
    int get_size(int x){ // x所在联通块中节点数量
        return sz[find(x)];
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1, vector<int> (n + 1, 0));
    while(m--){
        int u, v;
        cin >> u >> v;
        g[u][v] = 1;
    }
    DSU dsu(n);
    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            if(g[i][j] & g[j][i]) dsu.unite(i, j); // i, j有双向边
            if(g[i][j] ^ g[j][i]){ // i, j有单向边
                dsu.unite(i + n, j);
                dsu.unite(j + n, i);
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        res = max(res, dsu.get_size(i)); // 找所有部落中最大的
    }
    cout << res << endl;
    return 0;
}

G

首先转化一下题意：互慕团体就是环（包括自环）、单慕团体就是链、孤立团体就是孤立点、非孤立单慕团体就是节点数量大于2的链。

因为每位同学都有一个仰慕的同学，每位同学仰慕的同学互不相同，因此每个节点的入度和出度都为，因此在老师约谈之前的图一定是只有若干个环。

老师每约谈一个同学，等同于删掉所有和该同学相连的边，从而破环成链或者将一个链破坏成多个链。

对于约谈后的图，答案就等于：

我们可以直接建约谈之后的图：标记一下被老师约谈的位同学，在连边时如果该边的某一端点的同学被约谈了，就直接舍弃这条边。

对约谈后的图，依次统计环、链、孤立点的数量即可。找链和环的过程用循环即可实现。

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1); // i 仰慕 a[i]
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<bool> st(n + 1, false); // 判断同学是不是被约谈
    int k;
    cin >> k;
    for(int i = 0; i < k; i++){
        int x;
        cin >> x;
        st[x] = true; // 被约谈
    }
    vector<int> din(n + 1, 0), dout(n + 1, 0); // 约谈后的图的入度和出度
    for(int i = 1; i <= n; i++){
        if(st[i] || st[a[i]]) continue; // 如果一条边的端点有一个被约谈，就舍弃这条边
        dout[i]++, din[a[i]]++;
    }
    vector<bool> vis(n + 1, false); // 判断点遍历没遍历过
    int link = 0, ring = 0; // 链和环的数量
    for(int i = 1; i <= n; i++){ // 把所有的链和孤立点都标记出来
        if(vis[i] || st[i]) continue;
        if(!din[i]){ // 链和点的起点入度为0
            int u = i;
            int cnt = 0;
            while(!vis[u] && !st[u]){
                vis[u] = true;
                cnt++;
                u = a[u];
            }
            if(cnt == 1) k++; // 孤立点
            else link++; // 链
        }
    }
    for(int i = 1; i <= n; i++){ // 把所有的环标记出来
        if(vis[i] || st[i]) continue;
        if(din[i] && dout[i]){ // 标记完链后剩下的点都在环上
            int u = i;
            while(!vis[u]){
                vis[u] = true;
                u = a[u];
            }
            ring++; // 环
        }
    }
    int res = ring + link / 2;
    if(link & 1) res++;
    else res +=  k;
    cout << res << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

H

对于限制1，可以在树上跑一遍序，和分别表示在遍历时进入和离开节点所在子树时的时间戳，对于子树上的所有节点，其序一定在内。

通过这一性质，就可以将树上的个点转化成个区间，限制1也就变成了：所有选的物品的区间没有交集。

在朴素的背包的基础上，将物品变成区间，只需要将各个物品的信息（左右端点、重量、实际价值）存到一个结构体数组中，再对其区间端点排序。在保证物品的区间有序的前提下，遍历每个物品，在他前面的物品中二分找到第一个区间与其不相交的物品，这个物品就是当前物品前面第一个能状态转移到当前物品的物品，用一个数组存下来，即可转化成普通的背包问题。

接着就是普通的背包问题求最大价值和方案数。

对于实际价值的计算，在处理序的同时将子树的欧拉函数值都累加到根节点后按公式计算即可，欧拉函数需要用筛法预处理。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <chrono>
#define endl '\n'
using namespace std;
using LL = long long;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;

struct Node{
    int l, r, w, id; // 区间端点，物品重量，物品编号，物品实际价值
    LL val;
    bool operator < (const Node &a) const{ // 从小到大排序
        if(r == a.r) return l < a.l;
        return r < a.r;
    }
};

vector<int> get_eulers(int n){ // 筛法预处理欧拉函数
    vector<int> eulers(n + 1);
    vector<int> primes;
    vector<bool> not_prime(n + 1, false);
    eulers[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!not_prime[i]){
            primes.emplace_back(i);
            eulers[i] = i - 1;
        }
        for(int p : primes){
            LL t = 1LL * i * p;
            if(t > n) break;
            not_prime[t] = true;
            if(i % p == 0){
                eulers[t] = eulers[i] * p;
                break;
            }
            else eulers[t] = eulers[i] * (p - 1);
        }
    }
    return eulers;
}

vector<int> phi = get_eulers(1000000);

int n, m;
vector<int> w, basev, a;
vector<vector<int>> g;
vector<LL> sum;
vector<int> in, out;
int idx;

void dfs(int u, int fa)
    in[u] = ++idx; // 进入时间戳
    sum[u] = phi[a[u]];
    for(int v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
        sum[u] += sum[v]; // 将子树的欧拉函数累加到根节点
    }
    out[u] = idx; // 离开时间戳
}

void solve(){
    cin >> n >> m;
    w.assign(n + 1, 0);
    basev.assign(n + 1, 0);
    a.assign(n + 1, 0);
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> basev[i] >> a[i];
    }    
    g.assign(n + 1, {});
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    sum.assign(n + 1, 0);
    in.assign(n + 1, 0);
    out.assign(n + 1, 0);
    idx = 0;
    dfs(1, 0);
    vector<Node> nodes(n + 1);
    for(int i = 1; i <= n; i++){
        LL val = basev[i] * sum[i];
        nodes[i] = {in[i], out[i], w[i], i, val};
    }
    sort(nodes.begin() + 1, nodes.end());
    vector<int> pre(n + 1, 0);
    vector<int> l(n + 1), r(n + 1);
    for(int i = 1; i <= n; i++){ // 用数组存一下，方便二分
        l[i] = nodes[i].l;
        r[i] = nodes[i].r;
    }
    for(int i = 1; i <= n; i++){
        auto it = upper_bound(r.begin(), r.begin() + i, l[i] - 1); // 二分找到第一个和当前区间不相交的区间的位置
        if(it != r.begin()) pre[i] = it - (r.begin() + 1); // 能找到就存到pre数组中
    }
    vector<vector<LL>> dp_val(n + 1, vector<LL> (m + 1, -1e18)); // 最大价值
    vector<vector<int>> dp_cnt(n + 1, vector<int> (m + 1, 0)); // 方案数
    dp_val[0][0] = 0;
    dp_cnt[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){ // 不选
            dp_val[i][j] = dp_val[i - 1][j];
            dp_cnt[i][j] = dp_cnt[i - 1][j];
        }
        int w = nodes[i].w;
        LL v = nodes[i].val;
        if(w <= m){ // 选
            int p = pre[i];
            for(int j = w; j <= m; j++){ // 遍历重量
                LL cand = dp_val[p][j - w] + v; // 从pre[i]转移过来
                if(cand > dp_val[i][j]){
                    dp_val[i][j] = cand;
                    dp_cnt[i][j] = dp_cnt[p][j - w];
                }
                else if(cand == dp_val[i][j]){
                    dp_cnt[i][j] = (dp_cnt[i][j] + dp_cnt[p][j - w]) % mod;
                }
            }
        }
    }
    LL res = -1e18, cnt = 0;
    for(int j = 0; j <= m; j++){ // 遍历找到最大价值及其方案数
        if(dp_val[n][j] > res){
            res = dp_val[n][j];
            cnt = dp_cnt[n][j];
        }
        else if(dp_val[n][j] == res){
            cnt = (cnt + dp_cnt[n][j]) % mod;
        }
    }
    if(res == -1e18) cout << 0 << ' ' << 1 << endl;
    else cout << res << ' ' << cnt << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

I

对字符串进行一次操作2，相当于对字符串进行一次循环移位，而对字符串进行若干次的循环移位，都可以通过对初始字符串进行一次循环移位来替代，因此操作2最多只会执行一次。

对字符串进行两次操作1后就会回到原始字符串，没有意义，因此操作1也最多只会执行一次。

因此最多只需步就可以得到任一可达字符串。

• 如果在原串中就能找到，答案就是；
• 如果对原串翻转一下，或者对原串进行一次操作2就能在中找到，答案就是；
• 如果对翻转后的字符串进行一次操作2才能在中找到，答案就是;
• 如果上述都找不到，就输出。

对于操作2的循环移位，可以通过字符串拼接来快速实现。

#include <iostream>
#include <string>
#define endl '\n'
using namespace std;

void solve(){
    int n, m;    
    string s, t;
    cin >> n >> m >> s >> t;
    string ss = s + s; // 拼接表示循环移位后的字符串
    string rs(s.rbegin(), s.rend()); // 翻转的字符串
    string rss(ss.rbegin(), ss.rend()); // 移位+翻转的字符串
    if(s.find(t) != -1){
        cout << 0 << endl;
        return;
    }
    if(rs.find(t) != -1 || ss.find(t) != -1){
        cout << 1 << endl;
        return;
    }
    if(rss.find(t) != -1){
        cout << 2 << endl;
        return;
    }
    cout << -1 << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

J

首先，对于操作1，如果每个货架都走一次的话，复杂度是，难以通过，考虑用优化这个操作。

用维护当前所有非空货架的编号，对于操作1，只需要调用的函数，每次找到当前货架右侧的第一个非空货架处理即可，如果一个货架被买空了就从中删除，空货架补货时就将其插入，复杂度。

对于操作2，需要一个能维护场上空货架，且能快速查询在当前货架之前有几个货架被买空，并支持快速动态单点修改的数据结构，可以用树状数组求前缀和的思想。

定义一个时间戳变量记录当前空货架是“被买空”的第几次，每有一个货架被买空，就给，用一个数组记录每个货架最后一次被买空时的时间戳是多少。

• 对于操作1，如果在买蛋糕时将货架买空，就让，利用树状数组给当前的位置，表示在这个时间有一个货架被买空。
• 对于操作2，如果第个货架当前是空的，只需要用树状数组求出到位置的前缀和，也就是当前场上的空货架有多少个是在买空前被买空的。
• 对于操作3，如果原来是空货架，操作后将变得不空，和操作2相反，利用树状数组给当前的位置，表示在这个时间被买空的货架现在不空了。

按顺序处理和树状数组即可。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define endl '\n'
using namespace std;

struct Fenwick{
    int n;
    vector<int> tr;
    Fenwick(int _n = 0){
        n = _n; 
        tr.assign(n + 1, 0); 
    }
    int lowbit(int x){ 
        return x & -x; 
    }
    void update(int x, int d){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += d;
    }
    int query(int x){
        int res = 0;
        for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
        return res;
    }
};

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    Fenwick fw(sum + q + 1);
    set<int> se;
    for(int i = 1; i <= n; i++) se.insert(i); // 初始每个货架都不空
    int idx = 0;
    vector<int> v(n + 1, -1);
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int l, r;
            cin >> l >> r;
            auto it = se.lower_bound(l); // [l, r]中第一个不空的货架
            while(it != se.end() && *it <= r){ // 依次遍历不空的货架
                int i = *it;
                a[i]--; // 买走一块
                if(!a[i]){ // 如果买空
                    v[i] = ++idx; // 货架i在这个时间被买空
                    fw.update(v[i], 1); // 在这个时间有一个货架被买空
                    it = se.erase(it); // 该位置空了
                }
                else it++; // 遍历下一个不空的货架
            }
        }
        else if(op == 2){
            int x;
            cin >> x;
            if(a[x] == 0) cout << fw.query(v[x]) << endl; // 查询在x被买空的时间v[x]前有多少个蛋糕被买空
            else cout << -1 << endl; // 货架不空
        }
        else{
            int x;
            cin >> x;
            if(!a[x]){ // 如果x是空货架
                se.insert(x); // 现在不空了
                fw.update(v[x], -1); // 在v[x]这个时间被买空的那个货架现在不空了
            }
            a[x]++; // 添一块蛋糕
        }
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}