C

计数 DP 预处理 枚举

一个长度100的01序列b，做前缀和得到a，对a做前缀和得到s。现在给m个约束p,v，表示$s[p]=v$。问满足所有约束的b序列的个数

对于俩相邻的约束$(i,v_i)(j,v_j)$，有$s_j-s_i=a_i\ast (j-i)+x=v_j-v_i$

于是可以枚举$a_i$，如果$a_i$确定了，$x$就确定了。只需要求出这个x的方案数即可计数了。

注意到对于一个位置$i$，所有$[0,100]$的$a_i$的方案数可能不同，所以我们还需要维护到达$i$位置，不同的$a_i$的方案数，再乘上上面的x的方案数，才能计数。

具体来说我们考虑一个$d{p}_x$，表示当前前缀约束都满足后，当前位置$a_i=x$的方案数。

转移时，对于俩相邻的约束$(i,v_i)(j,v_j)$，枚举所有$a_i$，可以转移到所有$a_j$。转移系数是$(i+1,j)$这区间内，b序列和为$a_j-a_i$，s增加量为$v_j-v_i$的方案数，记为f。根据我们前面的分析，这一段对前缀和的贡献是$a_i\ast (j-i)+x$，其中x就是这一段$(i+1,j)$序列单独算前缀和的结果。

f显然可以dp预处理。dp状态里维护01序列长度，一阶前缀和a，二阶前缀和s的值。dp值维度维护方案数

最后一个约束如果不为n，那么到n这一段都可以任取，乘上一个$2^x$即可

这里有一个复杂度分析，任意两个相邻约束之间的转移，需要枚举$a_i$，枚举这一段01序列中1的个数，这样的约束有$m\le 100$个，看起来是个$100^3$。

但其实考虑m个约束，和枚举相邻两个约束之间1的个数，这两层循环，总次数只有最多100次，因此这个dp计算量只有$100^2$，对于$T=1e4$可以通过

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
const int inf = LONG_LONG_MAX;
const int mod = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int f[110][110][5500];
void pre()
{
    f[0][0][0] = 1;
    rep(i, 0, 100)
    {
        rep(j, 0, i)
        {
            rep(k, 0, 5100)
            {
                f[i + 1][j + 1][k + j + 1] += f[i][j][k];
                f[i + 1][j + 1][k + j + 1] %= mod;

                f[i + 1][j][k + j] += f[i][j][k];
                f[i + 1][j][k + j] %= mod;
            }
        }
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;

    int pre = 1, prev = 0;
    vector<int> g(2 * n + 10);
    g[0] = 1;
    rep(i, 1, m)
    {
        int p, v;
        cin >> p >> v;

        int len = p - pre;
        vector<int> ng(2 * n + 10);
        // a[pi-1]
        rep(j, 0, pre)
        {
            int V = v - prev - j * len;
            if (V < 0 || V > 5100)
            {
                continue;
            }
            // a[pi-1,pi]
            rep(k, 0, len)
            {
                // cout << j << ' ' << k << ' ' << g[j] << ' ' << V << ' ' << f[len][k][V] << '\n';
                ng[j + k] += g[j] * f[len][k][V] % mod;
            }
        }

        rep(j, 0, p)
        {
            ng[j] %= mod;
        }
        swap(ng, g);

        pre = p;
        prev = v;
    }

    int ans = 0;
    rep(i, 0, n)
    {
        ans += g[i];
    }
    // cout << ans << ' ';
    ans %= mod;
    if (pre < n)
    {
        int t = qpow(2, n - pre);
        ans = ans * t % mod;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

    pre();
    while (T--)
    {
        solve();
    }
    return 0;
}

/*
6
1 0
3 1
3 1
3 1
2 0
4 1
4 3
5 2
1 0
5 4
5 2
2 0
5 10
*/

D

签到 转化

俩人各自有个血量和攻击，每次对撞，各自的血量扣除对方的攻击。并且有4种情况，可能给扣血都乘上相同的系数1，2，4。A赢只有B死了A活着，否则都算B赢。给出初始的血量和攻击，问谁赢

注意到每个人扣得血只能是对方攻击力的倍数，于是不妨给每个的血量除以对方的攻击力，考虑到不足一次攻击的血量，也需要一次攻击打掉，这里上取整。接下来每次对撞，就是俩人血量都同时扣1，2，4了。

这是简单的，a想要稳赢，需要至少比b多4点血，最极端的情况是碰之前5,1，碰完4,0。

void solve()
{
    int a, b, ha, hb;
    cin >> a >> b >> ha >> hb;

    int x = (ha + b - 1) / b;
    int y = (hb + a - 1) / a;

    if (x - y >= 4)
    {
        cout << "yes\n";
    }
    else
    {
        cout << "no\n";
    }
}

I

通信 欧拉序

给一个森林，n个点，你可以在树上每个节点上，传输一个信息，形成一个长度n的数组a。然后通信过程中会把这个a数组随机打乱得到b。接收方收到b后，需要还原原始的森林。还原森林，每条边的顶点下标不需要一样，拓扑结构一样即可。a的值域可以在$[1,2n]$

开始的一个思路是传输每个点的父亲，然后发现[1,2n]这个条件没用完全，于是考虑森林里每棵树的根额外+n，这样接收方可以通过$>n$确定哪些是根

但这样有个解决不了的问题：一个父亲的多个儿子，他们传输的信息是一样的，再经过打乱后，我们完全区分不了这些点的顺序。但是题目的要求其实是需要区分的，于是这个编码方式宣告失败。实际上，任何可能有两个$a_i$相同的编码方式，都会有这个问题，都是不行的

从值域角度分析，$[1,2n]$可以联想到欧拉序。即使不从这个角度，从严谨的方向分析，欧拉序其实保存了一个树上dfs的操作序列，每次in操作等于往下进入一个儿子，一次out操作等于往上返回父亲。这里我们传递不了长度2n的序列，只能传递长度n。

那么考虑传递每个点第一次进入的时刻，也就是$i{n}_x$。接收端，把b排序，对于两个$b_{i-1},b_i$，记录$x=b_i-b_{i-1}$，那么每到一个$b_i$，往上跳父亲x步，再往下走一步，到一个儿子。可以记录所有$b_i$值在b数组中对应的下标，每次向下走一步，到了一个儿子，就是父亲和儿子的下标之间连一条边。

对比排序有个更简单的做法是开个$2n$的值域数组，记录哪些值出现了，然后扫一遍$[1,2n]$，如果一个位置是1则往下到一个儿子，否则往上退一步父亲。时刻维护当前在哪个点，以及已经走过的每个点的父亲（用于回退）。每次往下走时，就确定了一条边。

这第个做法其实就是利用欧拉序，在模拟dfs过程，于是自然就能还原原始森林的拓扑。欧拉序告诉了我们每一步应该往下走儿子，还是往上回父亲。虽然只能传n个往下走儿子的操作，但是只有两种操作，且一共2n个操作，那么[1,2n]里剩下的操作自然就是往上回到父亲。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
const int inf = LONG_LONG_MAX;
const int mod = 998244353;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    string s;
    cin >> s;

    int T = 1;
    cin >> T;

    while (T--)
    {
        if (s == "cat")
        {
            int n, m;
            cin >> n >> m;

            vector<vector<int>> g(n + 10);
            rep(i, 1, m)
            {
                int u, v;
                cin >> u >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }

            vector<int> in(n + 10), out(n + 10);
            int cnt = 0;
            auto &&dfs = [&](auto &&dfs, int u, int f) -> void
            {
                in[u] = ++cnt;
                for (int v : g[u])
                {
                    if (f == v)
                        continue;
                    dfs(dfs, v, u);
                }
                out[u] = ++cnt;
            };

            rep(i, 1, n)
            {
                if (!in[i])
                {
                    dfs(dfs, i, 0);
                }
            }

            rep(i, 1, n)
            {
                cout << in[i] << ' ';
            }
            cout << '\n';
        }
        else
        {
            int n;
            cin >> n;
            vector<int> b(n + 10), mp(2 * n + 10), vis(2 * n + 10), f(n + 10);
            rep(i, 1, n)
            {
                cin >> b[i];
                mp[b[i]] = i;
                vis[b[i]] = 1;
            }

            vector<pair<int, int>> ans;
            int now = 0;
            rep(i, 1, 2 * n)
            {
                int tmp = mp[i];
                if (vis[i])
                {
                    if (now != 0)
                    {
                        ans.push_back({now, tmp});
                    }
                    f[tmp] = now;
                    now = tmp;
                }
                else
                {
                    now = f[now];
                }
            }

            cout << ans.size() << '\n';
            for (auto [u, v] : ans)
            {
                cout << u << ' ' << v << '\n';
            }
        }
    }
    return 0;
}

/*
cat
4
1 0
4 3
1 2
4 3
2 3
7 2
6 4
7 1
10 7
10 9
7 9
10 5
4 8
3 7
4 10
1 2
*/

K

二分 贪心 思维

一个序列a，一个序列l。现在需要确定一个序列b，满足$|b_i-b_{i-1}|\ge l_i$，然后最小化$\max |a_i-b_i|$

最小化最大值，考虑二分，于是对于一个二分值E，约束了$b_i\in I，I=[a_i-E,a_i+E]$。然后在此基础上考虑$l_i$的约束。那么假设前一个$b_i$在一个区间$[L,R]$，那么新的$b_i$区间就是$[L+l_i,+\infty ]\cup [-\infty ,R-l_i]$，再交上$I$，

这里看起来每一轮，上一轮的一个合法区间会分裂成最多两个，那$n$轮可能会变成$O(2^n)$个？

实则不然，如果前一轮已经有俩，那么俩一定是$[L+l_i,a_i+E]\cup [a_i-E,R-l_i]$这样的，这一轮就会变成得到$[-\infty ,a_i+E-l_{i+1}]\cup [-\infty ,R-l_i-l_{i+1}]\cup [L+l_i+l_{i+1},+\infty ]\cup [a_i-E+l_{i+1},+\infty ]$

注意到这四个是两个朝左开口，两个朝右开口的，同向的可以合并，取并集一定最多只剩两个。于是只要区间有两个了，接下来最多还是只有两个。

基于此我们可以直接手动取交集，维护这两个区间。最后看合法区间是否为空，不空则check有解。也可以利用这个性质，把每轮产生的交集做个贪心的区间合并，套一下模版，也就是要对产生的区间排序一下，然后贪心合并。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
const int inf = LONG_LONG_MAX / 2;
int n;
int adj[200005];
int L[200005];
bool check(int m)
{
    // cout << "now m: " << m << "\n";
    int l1 = adj[0] - m, r1 = adj[0] + m, l2 = adj[0] - m, r2 = adj[0] + m;
    int flag = 2;
    for (int i = 1; i < n; i++)
    {
        int x1 = max(r1 - L[i], r2 - L[i]), y1 = min(l1 + L[i], l2 + L[i]);
        // cout << i << ": " << l1 << " " << r1 << " " << l2 << " " << r2 << " " << x1 << " " << y1 << " " << "\n";
        if (x1 < adj[i] - m)
        {
            flag--;
            r1 = -inf, l1 = inf;
        }
        else
        {
            r1 = min(x1, adj[i] + m);
            l1 = adj[i] - m;
        }
        if (y1 > adj[i] + m)
        {
            flag--;
            r2 = -inf, l2 = inf;
        }
        else
        {
            l2 = max(y1, adj[i] - m);
            r2 = adj[i] + m;
        }
        // cout << i << ": " << l1 << " " << r1 << " " << l2 << " " << r2 << " " << x1 << " " << y1 << " " << "\n";
        if (flag == 0)
        {
            return 0;
        }
        flag = 2;
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        int l = 0, r = 100;
        for (int i = 0; i < n; i++)
        {
            cin >> adj[i];
            r += adj[i];
        }
        for (int i = 1; i < n; i++)
        {
            cin >> L[i];
            r += L[i];
        }
        int ans = -1;
        while (r >= l)
        {
            int mid = (l + r) / 2;
            if (check(mid))
            {
                ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

M

贪心

每个$a_i$可以在$[l_i,r_i]$里选。一个$a_i$严格大于前面所有的$a_j$，则是坏位置，问坏位置最少个数。规定$a_1$一定是坏位置。

考虑贪心，想让判断一个位置是否是坏位置，可以维护前面选的位置最大值mx，当前选择大于mx则是一个坏位置。

如果当前区间lr的最小值也就是l，已经大于mx了，则这里肯定要增加一个坏位置了。贪心的想，如果必须要增加了，为了让后面的坏位置尽量少，肯定要选一个尽量大的。但这个尽量大的不一定是当前区间的r，还可能是上一次选择mx后，到这个区间之间的所有r。

因此

• 如果不是必须增加一个坏位置，维护候选的r的最大值
• 如果必须增加一个坏位置了，从候选r和当前r里选一个最大的。然后重置候选r为负无穷

void solve() {
    int n;
    cin >> n;
    
    long long l, r;
    cin >> l >> r;
    
    int ans = 1; 
    long long mx = r; 
    long long best_r = -2e9; 

    for (int i = 2; i <= n; ++i) {
        cin >> l >> r;
        
        if (l > mx) {
            ans++;
            mx = max(best_r, r);
            best_r = -2e9; 
        } else {
            best_r = max(best_r, r);
        }
    }
    
    cout << ans << "\n";
}