B. Marbles
题解
- 显然如果存在棋子位于\((x,x)\)，那么一定先手必胜
- 容易发现必败态位于\((1, 2)\)和\((2,1)\)，那么我们可以通过\(sg\)函数暴力打表得到
- 并且玩家一定不会将棋子移动至\((0,i),(i,0),(i,i)\)这三种情况上，因为谁移动到这些位置，对手一定处于必胜态
int n, f[N][N];
pair<int, int> p[M];
int sg(int x, int y)
{
if (f[x][y] != -1)
return f[x][y];
unordered_map<int, int> mp;
for (int i = x - 1; i >= 1; --i)
{
if (i != y)
mp[sg(i, y)]++;
}
for (int j = y - 1; j >= 1; --j)
if (x != j)
mp[sg(x, j)]++;
for (int i = 1; i <= min(x - 1, y - 1); ++i)
mp[sg(x - i, y - i)]++;
for (int i = 0;; ++i)
if (!mp.count(i))
return f[x][y] = i;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> p[i].first >> p[i].second;
memset(f, -1, sizeof f);
f[1][2] = f[2][1] = 0;
int ans = 0;
for (int i = 1; i <= n; ++i)
{
auto [x, y] = p[i];
ans ^= sg(x, y);
if (x == y)
{
cout << "Y" << endl;
return;
}
}
if (ans > 0)
cout << "Y" << endl;
else
cout << "N" << endl;
}
F. Music Festival
有\(n\)个舞台，每个舞台上都有节目，所有节目个数之和不超过\(1000\)，每个节目都有开始时间和结束时间以及喜爱程度，要求你挑选一些节目观看，使得节目之间时间不冲突，并且在所有舞台上都看了节目的条件下，能够得到的最多喜爱程度
\(1 \leq n \leq 10\)
题解：状压\(DP\)
\[dp[i][r] = dp[i \oplus (1 \ll id) ][l] + v,id是节目[l,r]的舞台编号\\ dp[i][r] = dp[i][l] + v \]
我们设计状态\(dp[i][j]\)代表舞台状态为\(i\)时，在时间点的\(j\)的时刻下，能够得到的最多喜爱程度
这是一个经典的转移问题，一个节目的右端点肯定是通过其左端点转移过来的，所以我们考虑将左端点挂在右端点的\(vector\)上
考虑状态转移：
- 初始状态：\(dp[i][j] = -INF,dp[0][0] = 0\)
int n;
int dp[(1ll << 11)][N];
vector<array<int, 3>> seg[N];
void solve()
{
cin >> n;
int mx = 0;
for (int i = 0; i < n; ++i)
{
int k;
cin >> k;
for (int j = 1; j <= k; ++j)
{
int l, r, v;
cin >> l >> r >> v;
mx = max(mx, r);
seg[r].push_back({l, v, i});
}
}
for (int i = 0; i < (1ll << n); ++i)
for (int j = 0; j <= mx; ++j)
dp[i][j] = -inf;
for (int j = 0; j <= mx; ++j)
dp[0][j] = 0;
for (int i = 0; i < (1ll << n); ++i)
{
for (int j = 1; j <= mx; ++j)
{
dp[i][j] = dp[i][j - 1];
for (auto [l, v, id] : seg[j])
{
if (i >> id & 1)
{
dp[i][j] = max(dp[i][j], dp[i][l] + v);
dp[i][j] = max(dp[i][j], dp[i ^ (1ll << id)][l] + v);
}
}
}
}
int ans = -inf;
for (int j = 0; j <= mx; ++j)
ans = max(ans, dp[(1ll << n) - 1][j]);
if (ans <= 0)
cout << -1 << endl;
else
cout << ans << endl;
}
H. Police Hypothesis
给定一颗树，树上每个节点都有字母，给定模式串\(P\)，存在两个操作：
- \(1 , u, v\)：询问从\(u\)到\(v\)的路径中\(P\)出现的次数
- \(2, u, ch\)：将\(u\)上的字母改成\(ch\)
\(1 \leq |P| \leq 100\)
题解：树链剖分 + 线段树维护字符串哈希
由于\(P\)的长度比较小，我们可以在线段树上维护答案\(ans\)，区间长度\(len\)，以及长度为\(100\)的字符串哈希前后缀数组\(pre[],suf[]\)
考虑区间合并：
\(ans:=lson.ans+rson.ans + (lson.suf[]和rson.pre[]之间产生的贡献)\)
\(pre[] := lson.pre[] + rson.pre[]\)，通过字符串哈希合并
\(suf[]:=rson.suf[] + lson.suf[]\)，通过字符串哈希合并，注意应该倒着合并
\(len:=lson.len + rson.len\)
但是询问存在方向性，所以我们需要再开一颗线段树维护反串，合并时右儿子合并左儿子即可
对于一次询问来说，因为存在方向性，所以我们可以维护\(u\)和\(v\)的\(lca\)的左侧和右侧两部分的串，最后将这两部分合并
复杂度：\(O(100nlog^2n)\)
int n, m, q, sz[N], hson[N], dep[N], fa[N], l[N], mp[N], idx, top[N], pw[N], base = 131, hash_P;
string P;
char a[N];
vector<int> g[N];
void dfs1(int u, int par)
{
sz[u] = 1;
hson[u] = -1;
fa[u] = par;
dep[u] = dep[par] + 1;
for (auto v : g[u])
{
if (v == par)
continue;
dfs1(v, u);
sz[u] += sz[v];
if (hson[u] == -1 || sz[v] > sz[hson[u]])
hson[u] = v;
}
}
void dfs2(int u, int head)
{
top[u] = head;
l[u] = ++idx;
mp[idx] = u;
if (hson[u] != -1)
dfs2(hson[u], head);
for (auto v : g[u])
{
if (v != fa[u] && v != hson[u])
dfs2(v, v);
}
}
struct info
{
int ans, len, pre[101], suf[101];
friend info operator+(const info &a, const info &b)
{
if (a.len == 0)
return b;
if (b.len == 0)
return a;
info c;
c.len = a.len + b.len;
c.ans = a.ans + b.ans;
c.pre[0] = 0;
for (int i = 1; i <= min(100ll, c.len); ++i)
{
if (i <= a.len)
c.pre[i] = a.pre[i];
else
c.pre[i] = (a.pre[a.len] * pw[i - a.len] % mod + b.pre[i - a.len]) % mod;
if (i <= b.len)
c.suf[i] = b.suf[i];
else
c.suf[i] = (a.suf[i - b.len] * pw[b.len] % mod + b.suf[b.len]) % mod;
}
for (int i = max(1ll, m - b.len); i <= a.len && m - i >= 1; ++i)
if ((a.suf[i] * pw[m - i] % mod + b.pre[m - i]) % mod == hash_P)
++c.ans;
return c;
}
};
struct SEG
{
info val;
} seg[2][N << 2];
void up(int id)
{
seg[0][id].val = seg[0][lson].val + seg[0][rson].val;
seg[1][id].val = seg[1][rson].val + seg[1][lson].val;
}
void build(int id, int l, int r)
{
if (l == r)
{
if (m == 1 && a[mp[l]] == P[0])
{
seg[0][id].val.ans = 1;
seg[1][id].val.ans = 1;
}
else
{
seg[0][id].val.ans = 0;
seg[1][id].val.ans = 0;
}
seg[0][id].val.len = seg[1][id].val.len = 1;
seg[0][id].val.pre[1] = seg[1][id].val.pre[1] = a[mp[l]];
seg[0][id].val.suf[1] = seg[1][id].val.suf[1] = a[mp[l]];
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
up(id);
}
void change(int id, int l, int r, int x, char val)
{
if (l == r)
{
a[mp[l]] = val;
if (m == 1 && a[mp[l]] == P[0])
{
seg[0][id].val.ans = 1;
seg[1][id].val.ans = 1;
}
else
{
seg[0][id].val.ans = 0;
seg[1][id].val.ans = 0;
}
seg[0][id].val.pre[1] = seg[1][id].val.pre[1] = a[mp[l]];
seg[0][id].val.suf[1] = seg[1][id].val.suf[1] = a[mp[l]];
return;
}
int mid = l + r >> 1;
if (x <= mid)
change(lson, l, mid, x, val);
else
change(rson, mid + 1, r, x, val);
up(id);
}
info query(int id, int l, int r, int ql, int qr, int op)
{
if (ql <= l && r <= qr)
return seg[op][id].val;
int mid = l + r >> 1;
if (qr <= mid)
return query(lson, l, mid, ql, qr, op);
else if (ql > mid)
return query(rson, mid + 1, r, ql, qr, op);
else if (op == 0)
return query(lson, l, mid, ql, qr, op) + query(rson, mid + 1, r, ql, qr, op);
else
return query(rson, mid + 1, r, ql, qr, op) + query(lson, l, mid, ql, qr, op);
}
// u --> v
int query(int u, int v)
{
info L, R, M;
L.ans = L.len = R.ans = R.len = M.ans = M.len = 0;
while (top[u] != top[v])
{
if (dep[top[u]] > dep[top[v]])
{
L = L + query(1, 1, n, l[top[u]], l[u], 1);
u = fa[top[u]];
}
else
{
R = query(1, 1, n, l[top[v]], l[v], 0) + R;
v = fa[top[v]];
}
}
if (dep[u] < dep[v])
M = query(1, 1, n, l[u], l[v], 0);
else
M = query(1, 1, n, l[v], l[u], 1);
return (L + M + R).ans;
}
void solve()
{
cin >> n >> q >> P;
m = (int)P.size();
for (auto ch : P)
hash_P = (hash_P * base % mod + ch) % mod;
pw[0] = 1ll;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
pw[i] = pw[i - 1] * base % mod;
}
for (int i = 1, u, v; i < n; ++i)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
while (q--)
{
int op, u, v;
char c;
cin >> op;
if (op == 1)
{
cin >> u >> v;
cout << query(u, v) << endl;
}
else
{
cin >> u >> c;
change(1, 1, n, l[u], c);
}
}
}