首页 题解

# A. Garland

简单分讨。

考虑一段 0 的两端奇偶性不同，那么不管怎么放代价只会加 1.

所以只考虑连段奇偶性相同的。

如果数字数量足够填满当前段，那么没有代价，否则代价是 2（自己手模一下）。

所以把两端奇偶性相同的空段按长度从小到大排序，能填满就填满即可。

还有一些奇奇怪怪的小细节，自己写代码的时候慢慢调吧。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 110;
int n, ans;
int a[N], vis[N];
int pos, pre[N];
struct node{
    int len, typ, t;
    inline bool operator < (const node &b) const{
        return t != b.t ? t > b.t : len > b.len;
    }
};
priority_queue <node> q;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i], vis[a[i]] = 1;
    if(n == 1) return cout << "0\n", 0;
    for(int i = 1; i <= n; ++i)
        if(a[i]) pre[i] = pos, pos = i;
    a[n + 1] = a[pos] + 2, pre[n + 1] = pos;
    int c0 = 0, c1 = 0;
    for(int i = 1; i <= n; ++i)
        if(!vis[i]){
            if(i & 1) c1++;
            else c0++;
        }
    for(int i = 2; i <= n + 1; ++i)
        if(a[i] && a[i - 1] && (a[i] & 1) != (a[i - 1] & 1)) ans++;
    for(int i = 1; i <= n + 1; ++i){
        int t = (pre[i] > 0) ? (a[pre[i]] & 1) != (a[i] & 1) : 0;
        if(a[i] && pre[i] < i - 1){
            if(!t) q.push((node){i - pre[i] - 1, a[i] & 1, (pre[i] == 0 || i > n)});
            else ans++;
        }
    }
    while(!q.empty()){
        int len = q.top().len, typ = q.top().typ, t = q.top().t; q.pop();
        if(!typ){
            if(c0 >= len) c0 -= len;
            else ans += 2 - t;
        }else{
            if(c1 >= len) c1 -= len;
            else ans += 2 - t;
        }
    }
    cout << ans << '\n';
    return 0;
}
# B. Numbers on Tree
这道题似乎没有那么复杂。
大致思路是无脑 dfs\text{dfs} 一遍求出每个点之间的相对大小关系，然后依次赋值即可。
首先如果出现 cic_i 大于等于 ii 的子树大小，就无解。
然后 dfs 回溯过程暴力合并序列，最后把 xx 移动到 cx+1c_x + 1 的位置即可。
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
namespace IO{
    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 << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 2010;
int n, rt;
int fa[N], c[N], a[N];
vector <int> G[N], seq[N];
int siz[N];
inline void dfs(int x){
    siz[x] = 1;
    for(auto y : G[x]){
        dfs(y), siz[x] += siz[y];
        for(auto v : seq[y]) seq[x].pb(v);
    }
    if(siz[x] <= c[x]) puts("NO"), exit(0);
    seq[x].pb(x);
    for(int i = siz[x] - 1; i > c[x]; --i) swap(seq[x][i], seq[x][i - 1]);
}
int ans[N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i){
        G[fa[i] = read()].pb(i), c[i] = read();
        if(!fa[i]) rt = i;
    }
    dfs(rt);
    for(int i = 0; i < n; ++i) ans[seq[rt][i]] = i + 1;
    puts("YES");
    for(int i = 1; i <= n; ++i) write(ans[i]), putchar(' ');
    return 0;
}
# C1. Madhouse (Easy version)
C1\text{C1} 较简单，你只有 3 次询问机会，不管怎么试都能试出来吧……
那么正确的询问方法是先问 [1,n][1, n] 再问 [2,n][2, n]。
然后你的第一次询问比第二次询问子串数多 nn 个。
开个 map\text{map} 记一下依次推出每一个字符即可。
总询问字符串数为 n(n+1)2+n(n−1)2\frac {n(n + 1)}{2} + \frac {n(n - 1)}{2}。
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 110;
int n;
string s, str[N], ans;
multiset <string> s1[N], s2;
map <string, int> mp;
signed main(){
    cin >> n;
    if(n == 1){
        cout << "? 1 1\n";
        cin >> s[0];
        cout << "! " << s[0] << endl;
        fflush(stdout);
        return 0;
    }
    cout << "? 1 " << n << '\n';
    for(int i = 1; i <= n * (n + 1) / 2; ++i){
        cin >> s; sort(s.begin(), s.end());
        s1[s.length()].insert(s);
    }
    cout << "? 2 " << n << '\n';
    for(int i = 1; i <= (n - 1) * n / 2; ++i){
        cin >> s; sort(s.begin(), s.end());
        s2.insert(s), mp[s]++;
    }
    for(int i = 1; i <= n; ++i){
        for(auto s : s1[i]){
            if(!mp[s]){
                for(int j = 0; j <= i; ++j)
                    if(str[i - 1][j] != s[j]) {ans += s[j]; break;}
                str[i] = s; break;
            }else mp[s]--;
        }
    }
    cout << "! " << ans << '\n';
    fflush(stdout);
    return 0;
}
# C2. Madhouse (Hard version)
现在你总询问子串数不能超过 0.777(n+1)20.777(n + 1)^2 了。怎么办呢？
假设你的字符串为 ss，现在你询问 [1,n][1, n]。
然后你考虑 ss 中的每一位 sis_i 在不同长度子串中出现的次数。
经过一番观察不难发现，在所有不同长度的子串中出现次数全部相同的字符个数最多两个。（出现一次的是奇数长度时最中间的字符）
比如与 sxs_x 在所有长度子串出现次数完全相同的是 s2⌊n2⌋−xs_{2\lfloor\frac n2\rfloor - x}（总之就是轴对称）。
所以我们先询问 [1,n2][1, \frac n2] 和 [2,n2][2, \frac n2] 得到 1∼n21 \sim \frac n2 的答案。
然后询问 [1,n][1, n]，再根据上面说的对称性求出 [n2+1,n][\frac n2 + 1, n] 的答案。
总子串个数 2n2(n2+1)2+n(n+1)2≈0.75n22\frac {\frac n2(\frac n2 + 1)}{2} + \frac {n(n + 1)}{2} \approx 0.75n^2。
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 150;
int n, a[N], b[N], c[N];
string s;
char ans[N];
inline void qry(int l, int r, int b[N]){
    cout << "? " << l << " " << r << '\n';
    for(int i = l; i <= r; ++i)
        for(int j = i; j <= r; ++j){
            cin >> s;
            for(int k = 0; k < (int)s.length(); ++k) b[s.length()] += s[k];
        }
}
signed main(){
    ios :: sync_with_stdio(false);
    cin >> n;
    
    if(n <= 3){
        for(int i = 1; i <= n; ++i)
            qry(i, i, a), ans[i] = a[1], a[1] = 0;
        cout << "! " << (ans + 1) << '\n';
        return 0;
    }
    qry(1, (n + 1) / 2, a);
    qry(2, (n + 1) / 2, b);
    qry(1, n, c);
    for(int i = 1; i <= (n + 1) / 2; ++i)
        ans[i] = (a[i] -= b[i]) - a[i - 1];
    for(int i = n / 2, j = ans[n / 2 + 1]; i >= 1; --i){
        ans[n + 1 - i] = c[i] - c[i - 1] - j - ans[i];
        j = c[i] - c[i - 1];
    }
    cout << "! " << (ans + 1) << '\n';
    return 0;
}
# D. LCC
首先一个比较显然的结论是肯定是相邻两个点相撞，不解释了。
一共有三种碰撞情况：都向左，相向，都向右。
不难想到去枚举哪两个点相撞，假设是 ii 和 i+1i + 1 相撞。
设 limi,j,klim_{i, j, k} 表示 ii 向 jj 方向走，i+1i + 1 向 kk 方向走是被禁止的。
记 fi,0/1f_{i, 0/1} 表示考虑了前 ii 个点，当前点是向左 / 右走，且与 i+1i + 1 的碰撞是最早的概率。
pip_i 是往左走的概率，qiq_i 反之。
转移方程:
fi,0=pi×(fi−1,0×[limi−1,0,0=0]+fi−1,1×[limi−1,1,0=0])fi,1=qi×(fi−1,0×[limi−1,0,1=0]+fi−1,1×[limi−1,1,1=0])f_{i, 0} = p_i \times (f_{i - 1, 0} \times [lim_{i - 1, 0, 0} = 0] + f_{i - 1, 1} \times [lim_{i - 1, 1, 0} = 0])\\ f_{i, 1} = q_i \times (f_{i - 1, 0} \times [lim_{i - 1, 0, 1} = 0] + f_{i - 1, 1} \times [lim_{i - 1, 1, 1} = 0])
每次修改 limlim 后都要把后缀再做一遍，复杂度是 O(n2)O(n^2) 的，过不了。
如何优化呢？考虑线段树。
线段树上存 valrt,j,kval_{rt, j, k} 表示 rtrt 对应区间 [l,r][l, r] 的 ll 向 jj 走，rr 向 kk 走且当前枚举的 ii 和 i+1i + 1 最先相撞的概率。
更新的话从当前点暴力往上跳暴力修改。
答案就是根节点 4 个值加起来。
ii 和 i+1i + 1 碰撞的概率是前 i−1i - 1 个不碰撞减去前 ii 个不碰撞。
具体见代码吧。
#include <bits/stdc++.h>
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int n;
int a[N], b[N], p[N], q[N];
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}
inline int Inv(int x) {return qpow(x, mod - 2);}
struct node{
    int x, d1, d2, l, v;
    inline bool operator < (const node &b) const{
        return 1ll * l * b.v < 1ll * b.l * v;
    }
}c[N << 2];
int tot;
int val[N << 2][2][2], Mid[N << 2], id[N << 2]; //val [rt][j][k] rt 对应区间 [l, r] 的 l 向 j，r 向 k 走的概率
bool lim[N][2][2]; //lim [i][j][k]: i 向 j 且 i + 1 向 k 走是被禁止的
inline void pushup(int rt){
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j){
            val[rt][i][j] = 0;
            for(int x = 0; x < 2; ++x)
                for(int y = 0; y < 2; ++y)
                    if(!lim[Mid[rt]][x][y])
                        val[rt][i][j] = add(val[rt][i][j] + mul(val[ls][i][x], val[rs][y][j]));
        }
}
inline void build(int l, int r, int rt){
    if(l == r) return val[rt][0][0] = p[l], val[rt][1][1] = q[l], void();
    build(l, mid, ls), build(mid + 1, r, rs);
    Mid[rt] = mid, id[mid] = rt;
    pushup(rt);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    int inv = Inv(100);
    for(int i = 1; i <= n; ++i){
        cin >> a[i] >> b[i] >> q[i];
        q[i] = mul(q[i], inv), p[i] = sub(1 - q[i]);
    }
    build(1, n, 1);
    for(int i = 2; i <= n; ++i){
        c[++tot] = (node){i - 1, 1, 0, a[i] - a[i - 1], b[i] + b[i - 1]};
        if(b[i - 1] > b[i]) c[++tot] = (node){i - 1, 1, 1, a[i] - a[i - 1], b[i - 1] - b[i]};
        if(b[i - 1] < b[i]) c[++tot] = (node){i - 1, 0, 0, a[i] - a[i - 1], b[i] - b[i - 1]};
    }
    sort(c + 1, c + 1 + tot);
    int ans = 0, lst = 1;
    for(int i = 1; i <= tot; ++i){
        lim[c[i].x][c[i].d1][c[i].d2] = 1;
        for(int x = id[c[i].x]; x; x >>= 1) pushup(x);
        int res = (1ll * val[1][0][0] + val[1][0][1] + val[1][1][0] + val[1][1][1]) % mod;
        ans = add(ans + mul(mul(c[i].l, Inv(c[i].v)), sub(lst - res)));
        lst = res;
    }
    cout << ans << '\n';
    return 0;
}
# E. Fedya the Potter Strikes Back
首先这个条件就是 Border\text{Border}，我们只需要维护 Border\text{Border} 集合来计算答案增量即可。
考虑每次新加进来一个字符 sis_i 对 Border\text{Border} 的影响。
  • 新加一个 Border\text{Border}，即 s1=sis_1 = s_i.
  • 原本的 Border\text{Border} 依旧是 Border\text{Border}，但是权值要取 min⁡\min.
  • 删除原本的 Border\text{Border}.
假设我们能找到所有依旧是 Border\text{Border} 的位置，和被删除的 Border\text{Border} 的位置。
我们只需要开一个线段树来找区间最小值，然后再开一个 map\text{map} 来存每个权值出现过多少次用于更新答案。
现在的问题是找到被删除的 Border\text{Border} 的位置。
我们只需要在 kmp\text{kmp} 的失配树上跑即可，具体可以先枚举 sborder+1≠sis_{border + 1} \neq s_i 的 sborder+1s_{border + 1} 是什么，然后暴力跳。
具体看代码。
#include <bits/stdc++.h>
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
#define int long long
#define fi first
#define se second
using namespace std;
namespace IO{
    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 << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 6e5 + 10;
const int inf = 1e18;
const int mod = 1e18;
typedef pair<int, int> P;
int n, sum, s[N], w[N];
__int128 ans;
char c[4];
map <int, int> mp;
int nxt[N], col[N], fa[N][27];
int mn[N << 2];
inline void upd(int x, int v, int l = 1, int r = n, int rt = 1){
    if(l == r) return mn[rt] = v, void();;
    if(x <= mid) upd(x, v, l, mid, ls);
    else upd(x, v, mid + 1, r, rs);
    mn[rt] = min(mn[ls], mn[rs]);
}
inline int qry(int L, int R, int l = 1, int r = n, int rt = 1){
    if(L > r || R < l) return inf;
    if(L <= l && r <= R) return mn[rt];
    return min(qry(L, R, l, mid, ls), qry(L, R, mid + 1, r, rs));
}
inline void add(int x, int v){
    mp[x] += v, sum += x * v;
}
int stk[N];
inline int calc(int w){
    int cnt = 0, top = 0;
    for(auto it = mp.upper_bound(w); it != mp.end(); ++it)
        stk[++top] = it->first, cnt += it->second, sum -= it->first * it->second;
    while(top) mp.erase(stk[top--]);
    return cnt;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), scanf("%s", c), w[1] = read();
    s[1] = c[0] - 'a', ans = ans + w[1], upd(1, w[1]);
    write(ans), puts("");
    for(int i = 2; i <= n; ++i){
        scanf("%s", c), w[i] = read();
        s[i] = (c[0] - 'a' + ans % 26) % 26, w[i] ^= (ans % (1 << 30));
        if(s[1] == s[i]) add(w[i], 1); // 新加 border
        upd(i, w[i]), ans = ans + qry(1, i); // 往线段树里插入 w [i]
        int pos = nxt[i - 1]; // 更新 nxt
        while(pos && s[pos + 1] != s[i]) pos = nxt[pos];
        nxt[i] = (s[pos + 1] == s[i]) ? pos + 1 : pos, col[i - 1] = s[i];
        for(int j = 0; j < 26; ++j) fa[i][j] = fa[nxt[i]][j]; // 更新失配树
        fa[i][col[nxt[i]]] = nxt[i];
        for(int c = 0; c < 26; ++c){ // 枚举被删除的 border 后一位是什么
            if(c == s[i]) continue;
            for(int j = fa[i - 1][c]; j; j = fa[j][c]) add(qry(i - j, i - 1), -1); // 修改
        }
        add(w[i], calc(w[i]));
        write(ans = ans + sum), puts("");
    }
    return 0;
}
# F. Harry The Potter
感觉这个比上面两道题稍微简单一点。
我们假设对 (i,j)(i, j) 进行二操作，那么在 (i,j)(i, j) 之间连一条边。
不难证明，最后形成的一定是森林，设连通块个数为 CC，答案就是 n−Cn - C，问题变成了如何最大化 CC。
我们再把这个问题分成两部分。
  • 判断一个点集 SS 是可以由二操作连成一棵树的。
  • 跑一个枚举子集 dp\text{dp} 的东西来求值。
第二个部分是简单的，O(3n)O(3^n) 即可。
下面只讨论第一个部分。
观察到二操作是对 ii 减 xx，对 jj 减 x+1x + 1。这个 +1+1 有点恶心，我们先不考虑它。即对 i,ji, j 都减去 xx。
那么一个点集能否由二操作连起来的条件即为：把这个点集 SS 分成两部分 S1,S2S1, S2，使得这两部分的和 sums1=sums2sum_{s1} = sum_{s2}。
现在把 +1+1 的条件考虑进去。
条件就变为了：∣sums1−sums2∣≤∣S∣−1|sum_{s1} - sum_{s2}| \leq |S| - 1.（∣S∣|S| 是点集大小）
所以折半搜一下所有的和，然后双指针跑一跑就行。
还有一个小问题。
设有两个数分别为 8,−98, -9，它们分成两部分后差的绝对值最小为 ∣8+(−9)∣=1|8 + (-9)| = 1.
1 是小于 2 的，符合条件。
但是我们真的可以一步把它们两个都变成 0 吗？显然不行。
所以遇到这种所有数都在同一部分还符合条件的情况，要特判掉。
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N = (1 << 20) + 10;
int n, m;
int a[25], lg[N], sum[N];
int f[N];
int b[25], v1[N], v2[N];
int s1[N], s2[N];
inline void dfs(int l, int r, int *v){
    v[1] = 0;
    if(l > r) return;
    for(int i = l, m = 1; i <= r; ++i, m <<= 1){
        for(int j = 1; j <= m; ++j) s1[j] = v[j] + b[i], s2[j] = v[j] - b[i];
        for(int p = 1, q = 1, k = 1; k <= (m << 1); ++k){
            if(p > m) v[k] = s2[q++];
            else if(q > m) v[k] = s1[p++];
            else if(s1[p] < s2[q]) v[k] = s1[p++];
            else v[k] = s2[q++];
        }
    }
}
inline bool chk(int s){
    int cnt = 0, sum = 0;
    for(int i = 1; i <= n; ++i)
        if((s >> (i - 1)) & 1) b[++cnt] = a[i], sum += a[i];
    if((sum - cnt + 1) & 1) return 0;
    dfs(1, cnt / 2, v1), dfs(cnt / 2 + 1, cnt, v2);
    int L = 1 << (cnt / 2), R = 1 << (cnt - cnt / 2), tmp = 1 + (abs(sum) < cnt) * 2;
    for(int i = R, j = 1; i >= 1; --i){
        while(j <= L && v1[j] + v2[i] <= -cnt) j++;
        for(int k = j; k <= L && tmp && v1[k] + v2[i] < cnt; ++k) tmp--;
    }
    return !tmp;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(a[i]) a[++m] = a[i];
    }
    n = m; int all = (1 << n) - 1;
    for(int s = 1; s <= all; ++s) if(!f[s] && chk(s)){
        int res = all ^ s; f[s] = 1;
        for(int t = res; t; t = (t - 1) & res) f[s | t] = max(f[s | t], f[t] + 1);
    }
    cout << n - f[all] << '\n';
    return 0;
}