A. 魔法序列

根据题意写出序列的前几项为 ，容易发现序列的偶数项全部是 ，奇数项是 开始公差为 的等差数列。奇偶位置分开算和，最后加起来即可。

核心部分代码：

int main() {
  cin >> n;
  ll ans = n / 2;
  n = (n + 1) / 2;
  ans += 1ll * n * (n + 1) / 2;
  cout << ans << '\n';
}

B. 赛跑

考虑假设两个人选择的向量分别是 和 ，则两人的曼哈顿距离为 。考虑将绝对值拆开：

扫描小 L 的所有向量，分别计算 的最大值。再扫描小 P 的向量计算即可。时间复杂度 。

核心部分代码：

int main() {
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i] >> b[i];
  rep (i, 1, m) cin >> c[i] >> d[i];
  ll mx00 = -1e18, mx01 = -1e18;
  ll mx10 = -1e18, mx11 = -1e18;
  rep (i, 1, n) chkmx(mx00, - a[i] - b[i]);
  rep (i, 1, n) chkmx(mx01, - a[i] + b[i]);
  rep (i, 1, n) chkmx(mx10, + a[i] - b[i]);
  rep (i, 1, n) chkmx(mx11, + a[i] + b[i]);
  ll ans = -1e18;
  rep (i, 1, m) chkmx(ans, mx00 + c[i] + d[i]);
  rep (i, 1, m) chkmx(ans, mx01 + c[i] - d[i]);
  rep (i, 1, m) chkmx(ans, mx10 - c[i] + d[i]);
  rep (i, 1, m) chkmx(ans, mx11 - c[i] - d[i]);
  cout << ans << '\n';
}

C. 路径

设 表示现在在平面上的第 个点，当前匹配到了方向序列的第 个位置是否可行。

若暴力找到下一个方向的所有合法位置进行转移，这个方向上可能有很多点，复杂度无法保证（例如一行 个点，方向序列全部为 R，则每次都需要枚举它右边的所有点进行转移）。

考虑我们不钦定下一步一定要匹配一个新的方向序列位置，而是可以与当前方向序列的位置相同，那么此时我们只需要让每个点向他四个方向的第一个点进行转移即可。通过预处理每个点在每个方向上的下一个点，可做到时间复杂度 。

核心部分代码：

void work() {
  cin >> n >> m >> str;
  rep (i, 1, m) {
    if (str[i - 1] == 'L') s[i] = 0;
    if (str[i - 1] == 'R') s[i] = 1;
    if (str[i - 1] == 'U') s[i] = 2;
    if (str[i - 1] == 'D') s[i] = 3;
  }
  rep (i, 1, n) cin >> a[i] >> b[i];
  rep (i, 1, n) rep (j, 0, 3) nxt[i][j] = -1;
  rep (i, 1, n) p[i] = i;
  sort(p + 1, p + n + 1, [&](int x, int y) { return a[x] < a[y]; });
  mp.clear();
  rep (i, 1, n) {
    if (mp.count(b[p[i]])) nxt[p[i]][0] = mp[b[p[i]]];
    mp[b[p[i]]] = p[i];
  }
  sort(p + 1, p + n + 1, [&](int x, int y) { return a[x] > a[y]; });
  mp.clear();
  rep (i, 1, n) {
    if (mp.count(b[p[i]])) nxt[p[i]][1] = mp[b[p[i]]];
    mp[b[p[i]]] = p[i];
  }
  sort(p + 1, p + n + 1, [&](int x, int y) { return b[x] > b[y]; });
  mp.clear();
  rep (i, 1, n) {
    if (mp.count(a[p[i]])) nxt[p[i]][2] = mp[a[p[i]]];
    mp[a[p[i]]] = p[i];
  }
  sort(p + 1, p + n + 1, [&](int x, int y) { return b[x] < b[y]; });
  mp.clear();
  rep (i, 1, n) {
    if (mp.count(a[p[i]])) nxt[p[i]][3] = mp[a[p[i]]];
    mp[a[p[i]]] = p[i];
  }
  rep (i, 1, n) rep (j, 0, m) f[i][j] = 0;
  rep (i, 1, n) f[i][0] = 1, q.emplace(i, 0);
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    if (y && nxt[x][s[y]] != -1) {
      if (!f[nxt[x][s[y]]][y]) {
        f[nxt[x][s[y]]][y] = 1;
        q.emplace(nxt[x][s[y]], y);
      }
    }
    if (y < m && nxt[x][s[y + 1]] != -1) {
      if (!f[nxt[x][s[y + 1]]][y + 1]) {
        f[nxt[x][s[y + 1]]][y + 1] = 1;
        q.emplace(nxt[x][s[y + 1]], y + 1);
      }
    }
  }
  int ok = 0;
  rep (i, 1, n) ok |= f[i][m];
  cout << (ok ? "YES" : "NO") << '\n';
}

D. 不存在的玩家

考虑条件相当于给每个点一个权值 ，使得对于点 ，其连向的点的权值集合恰好为 。

直接 DP 不好维护。考虑取出权值为 的点。观察剩下的点，我们发现每个点需要连向至少一个权值为 的点，权值为 的点不能连边。我们处理好剩下的点和权值为 的点之间的边后，将权值为 的点删除，并将剩下点权值减 ，就得到了一个子问题。接下来我们对这个过程 DP。

记 表示 个点的答案，我们转移的时候枚举 的个数。但此时转移系数没有很好的形式，我们再预处理一个 DP 数组 表示总共 个点，其中 个 和 个非 的点，转移系数为多少。 可以 预处理。对 进行转移直接使用 的系数即可。

复杂度 。

核心部分代码：

int main()
{
    cin >> n >> mod;
    p[0]=1;
    rep(i,1,n) p[i]=p[i-1]*2%mod;
    g[0][0]=1;
    rep(i,1,n) rep(j,0,i)
    {
        g[i][j]=g[i-1][j]*(p[j]-1)%mod;
        if (j!=0) (g[i][j]+=g[i-1][j-1])%=mod;
    }
    dp[0]=1;
    rep(i,1,n) rep(j,0,i) (dp[i]+=g[i][j]*dp[i-j])%=mod;
    cout << dp[n];
    return 0;
}

E. 记忆

考虑路径拆分为 和 。我们希望可以整体维护询问。

注意到 trie 可以支持全局 和全局 ，因此我们可以建 trie 维护答案。对于 ，我们考虑从叶子向根维护答案。那么合并的时候只要用 trie 合并即可。再到 LCA 的时候我们取出对应编号的位置，即可知道当前的值是多少。

对于 ，我们从根向叶子维护。维护一棵 trie 表示当前每个值的答案。我们只需要 DFS 一遍即可，进入子树时 ，离开子树时回退，要用到全局 。

关于 trie 的全局 操作，这是一个经典问题。考虑按照二进制从低向高位建 trie 树，每次加一时，等价于将当前节点的 儿子互换，然后递归到 儿子进行 操作。全局 可以直接对每一位打懒标记。

复杂度 。注意容易构造使得每次异或之后让二进制最后 位全部是 ，再进行 操作，相当于走一个点答案 ，因此答案可以到 级别，所以 trie 树要开 位（这个问题场上几乎所有写的人都挂了一遍，瑟瑟发抖）。

由于本做法常数有些大，所以本题时限开的比较宽松，如果你使用树链剖分 / 点分治套 trie 树的 做法，且常数较小也可以通过此题。

核心部分代码：

const int N=300005,K=50,M=N*(K+2);
int n,q; 
ll a[N];
vector<int>t[N];
int fa[N][21],deth[N];
void dfs(int x,int f)
{
    fa[x][0]=f,deth[x]=deth[f]+1;
    rep(i,1,20) fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i:t[x])
    {
        if (i==f) continue;
        dfs(i,x);
    }
}
int LCA(int x,int y)
{
    if (deth[x]<deth[y]) swap(x,y);
    per(i,20,0) if (deth[fa[x][i]]>=deth[y]) x=fa[x][i];
    if (x==y) return x;
    per(i,20,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int rt[N],tr[M][2],tot,Fa[M],f[M];
ll s[M];
int find(int x)
{
    if (x==Fa[x]) return x;
    return Fa[x]=find(Fa[x]);
}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    Fa[x]=y;
}
inline int make_node()
{
    ++tot;
    Fa[tot]=tot,s[tot]=0;
    return tot;
}
inline void push_up(int u)
{
    if (tr[u][0]) f[tr[u][0]]=u;
    if (tr[u][1]) f[tr[u][1]]=u;
}
int insert(int &rt,ll x)
{
    if (!rt) rt=make_node();
    int u=rt;
    rep(i,0,K-1)
    {
        x^=s[u];
        bool c=x&(1ll<<i);
        if (!tr[u][c]) tr[u][c]=make_node(),f[tot]=u;
        u=tr[u][c];
    }
    return u;
}
ll query(int u)
{
    ll res=0,bas=0;
    per(i,K-1,0)
    {
        int v=f[u];
        if (tr[v][1]==u) res^=(1ll<<i);
        u=v;
        bas^=(1ll<<i);
        res^=bas&s[u];
    }
    return res;
}
int merge(int u,int v,ll w,int k)
{
    if (!v) return u;
    if (!u) 
    {
        s[v]^=w;
        return v;
    }
    if (k!=K)
    {
        w^=s[u]^s[v];
        bool c=w&(1ll<<k);
        tr[u][0]=merge(tr[u][0],tr[v][c],w,k+1);
        tr[u][1]=merge(tr[u][1],tr[v][c^1],w,k+1);  
        push_up(u);
    }
    else merge(v,u);
    return u;
}
void add(int u,ll w,int k)
{
    if (k==K) return;
    swap(tr[u][0],tr[u][1]);
    w^=s[u];
    bool c=w&(1ll<<k);
    if (tr[u][c]) add(tr[u][c],w,k+1);
}
void del(int u,ll w,int k)
{
    if (k==K) return;
    swap(tr[u][0],tr[u][1]);
    w^=s[u];
    bool c=w&(1ll<<k);
    c^=1;
    if (tr[u][c]) del(tr[u][c],w,k+1);
}
int id[N];
ll ans[N];
vector<int>A[N],B[N],C[N];
void dfs1(int x)
{
    rt[x]=0;
    for (int i:t[x])
    {
        if (i==fa[x][0]) continue;
        dfs1(i);
        add(rt[i],0,0);
        rt[x]=merge(rt[x],rt[i],0,0);
    }
    for (int i:A[x])  id[i]=insert(rt[x],ans[i]);
    if (rt[x]) s[rt[x]]^=a[x];
    for (int i:B[x]) ans[i]=query(find(id[i]));
}
void dfs2(int x)
{
    s[rt[0]]^=a[x];
    for (int i:B[x])  id[i]=insert(rt[0],ans[i]);
    for (int i:C[x]) ans[i]=query(find(id[i]));
    for (int i:t[x])
    {
        if (i==fa[x][0]) continue;
        add(rt[0],0,0);
        dfs2(i);
        del(rt[0],0,0);
    }
    s[rt[0]]^=a[x];
}
 
int main()
{
    cin >> n >> q;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n-1)
    {
        int x,y;
        cin >> x >> y;
        t[x].pb(y),t[y].pb(x);
    }
    dfs(1,0);
    rep(i,1,q)
    {
        ll x;
        int u,v;
        cin >> x >> u >> v;
        int w=LCA(u,v);
        A[u].pb(i),B[w].pb(i),C[v].pb(i);
        ans[i]=x;
    }
    dfs1(1);
    tot=0,mem(tr),mem(s),mem(f),mem(rt);
    rt[0]=make_node();
    dfs2(1);
    rep(i,1,q) cout << ans[i] << "\n";
    return 0;
}

F. 字符串树

考虑对所有的串建出 AC 自动机，求出 Fail 树。走一条 Trie 树上的边相当于在表式树上增加一条边，跳一条 Fail 边相当于截取现在表示树上的一段后缀，用这一段后缀继续去匹配其他字符串。

因此对于每一条 Trie 树上的边，令其边权为 ，对于 Fail 边，边权为 ，求一个最小树形图即可。点数与边数均为 ，计算最小树形图复杂度 ，足以通过本题。由于这张图只有 边权，可以用一些技巧优化到 。

考虑该算法的正确性。

考虑对于子串表示树上的任意一条边，在 ACAM 的 trie 树上都能找到对应的边，且边权为 ，因此对于任意一个合法的子串表示树，均存在一种在上述图上的树形图表示。

而对于任意一个求出的树形图，我们可以按照在 trie 树上选择的边来构造一棵子串表示树，而对于任意一个字符串 ，只需要沿着求出的树形图上的边，即可在表示树上找到一条从祖先到儿子的路径与之匹配。具体来说，我们找到树形图上 串结尾对应的点 ，向上一直跳 在树形图上的父亲直到根节点，我们提取出这条路径上的所有边构成的字符串，走一条 trie 树上的边相当于在字符串后面加一个字符，走一条 fail 边相当于截取当前字符串的一个后缀，走到 时的字符串就必然为 。因此在对应表示树上，必然存在一条从根开始的路径，使得 是这条路径的一个后缀，也就是说 在表示树上出现。

因此在这张图上求出最小树形图即为答案。

核心部分代码：

int n, tot = 1, son[maxn][26], fa[maxn], fail[maxn];
string s[maxn];
queue<int> q;
 
void build() {
  rep (i, 0, 25) {
    if (!son[1][i]) son[1][i] = 1;
    else q.emplace(son[1][i]), fail[son[1][i]] = 1;
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    rep (i, 0, 25) {
      if (!son[u][i]) son[u][i] = son[fail[u]][i];
      else q.emplace(son[u][i]), fail[son[u][i]] = son[fail[u]][i];
    }
  }
}
 
int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n;
  rep (i, 1, n) cin >> s[i];
  rep (i, 1, n) {
    int p = 1;
    for (char ch : s[i]) {
      if (!son[p][ch - 'a']) son[p][ch - 'a'] = ++tot, fa[tot] = p;
      p = son[p][ch - 'a'];
    }
  }
  build();
  rep (i, 2, tot) Edmonds::add_edge(fa[i], i, 1);
  rep (i, 2, tot) Edmonds::add_edge(i, fail[i], 0);
  cout << Edmonds::dmst(tot, 1) + 1 << '\n';
}