杂题合集 I
不是自己想出来的题打了星号。
* P13525 [KOI 2025 #2] 新的情缘
容斥好题，感觉思路很像 NOIP2024 T3。想的时候被 Sub3 的错排做法误导了一直没想到容斥。
区间不交的性质是很好的，这使得我们可以将区间包含的关系利用树形结构刻画。于是可以先建树，即如果 \(u\) 包含了 \(v\)，那么连边 \(u\to v\)。
首先有一个结论：不同弱连通块的点不能互相选。证明可以考虑最右边的弱连通块，如果左边的男的选了右边的一个女的，那么右边必然存在一个男的找不到女朋友。
因此最后的答案是每个弱连通块的乘积。
下文中，我们规定配对是指给左端点（男）找右端点（女）。
考虑弱化限制，如果两个人能复合时该怎么做。手模样例后能够发现一个男的能配对的女的个数一定是这个节点的深度。于是此时的答案是 \(\prod_{u\in T} \text{dep}_u\)。
加入了不能复合的限制后，考虑容斥原理。
假设我们当前钦定复合的点集为 \(S\)，那么其容斥系数为 \((-1)^{|S|}\)。如何计算其方案数呢？参考之前弱化限制的公式，可以想到答案是 \(\prod_{u\in T} a_u\)。其中 \(a_u\) 表示 \(\text{root}\to u\) 的路径上不在 \(S\) 中的点的个数。如果 \(u\) 在 \(S\) 中则将 \(a_u\) 赋值为 \(-1\)。
容易发现此时一种方案的容斥结果就是 \(\prod_{u\in T}a_u\)。我们考虑设计树形 DP 来维护这个式子。
因为一个节点 \(a_u\) 的值与其到根链在 \(S\) 中的个数有关，于是可以设计 DP：\(dp_{u, i}\) 表示 \(\text{root}\to u\) 的路径上（不包含 \(u\) 自己）有 \(i - 1\) 个点不在 \(S\) 里的情况下，\(\prod_{v\in \text{Subtree}_u}a_v\) 的值。转移可以进行分类讨论：
- 若 \(u\) 在 \(S\) 里，则 \(dp_{u, i}\xleftarrow{+} -1\times \prod_{v \in \text{son}_u}dp_{v, i}\)。
- 若 \(u\) 不在 \(S\) 里，则 \(dp_{u, i}\xleftarrow{+} (i - 1 + 1)\times \prod_{v \in \text{son}_u}dp_{v, i+1}\)。其中 \((i - 1 + 1)\) 的原因是 \(u\) 依然能和自己配对。
转移即可。时间复杂度 \(O(n^2)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 6005;
const ll mod = 1e9 + 7;
int n, rd[N], dep[N];
ll dp[N][N], f[N];
pi seg[N];
vector<int> g[N];
void dfs(int u)
{
if(g[u].size() == 0)
{
for(int i = 1; i <= dep[u]; i++) dp[u][i] = i - 1;
return;
}
for(auto v : g[u])
{
dep[v] = dep[u] + 1;
dfs(v);
}
for(int i = 1; i <= dep[u] + 1; i++) f[i] = 1;
for(auto v : g[u])
for(int i = 1; i <= dep[v]; i++)
f[i] = (f[i] * dp[v][i]) % mod;
for(int i = 1; i <= dep[u]; i++)
dp[u][i] = ((f[i + 1] * i % mod - f[i]) % mod + mod) % mod;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> seg[i].fi >> seg[i].se;
g[i].clear();
rd[i] = 0;
}
if(n == 1)
{
cout << "0\n";
return;
}
sort(seg + 1, seg + n + 1);
for(int i = 1; i <= n; i++)
{
int nowl = i;
for(int j = i + 1; j <= n; j++)
{
if(seg[j].se > seg[i].se) break;
if(seg[j].fi > nowl)
{
g[i].push_back(j);
rd[j]++;
nowl = seg[j].se;
}
}
}
ll ans = 1;
for(int i = 1; i <= n; i++)
{
if(rd[i]) continue;
dep[i] = 1;
dfs(i);
ans = (ans * dp[i][1]) % mod;
}
cout << ans << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P8252 [NOI Online 2022 提高组] 讨论
先考虑如何判断无解。显然我们把有交集的人进行连边，如果形成的是一个森林则一定无解。
具体实现上，可以用并查集维护连通块。然后对于每个连通块里的人，按照会的题的数目从大到小排序后，让每个人检查自己会的题上的标记是否都是同一个人的，最后让他给自己会的题打上标记（之前的标记会被覆盖掉）。
一旦一个人检查到不合法，那么必然存在另一个人会和他进行讨论。证明可以进行分类讨论，比较繁琐此处略去。
于是我们暴力 check 每一个人，找到其同伙即可。
时间复杂度 \(O(n\log n + m)\)，如果使用桶排序可以做到线性。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 2000005;
int n, tot[N], vis[N];
vector<int> g[N], gt[N];
struct DSU{
int fa[N];
void init()
{
for(int i = 1; i <= 2 * n; i++) fa[i] = i;
}
int findf(int x)
{
if(fa[x] != x) fa[x] = findf(fa[x]);
return fa[x];
}
void combine(int x, int y)
{
int fx = findf(x), fy = findf(y);
fa[fx] = fy;
}
} dsu;
bool cmp(int x, int y)
{
return (tot[x] > tot[y]);
}
void brute(int u)
{
cout << "YES\n";
memset(vis, 0, sizeof(vis));
for(auto v : g[u]) vis[v] = 1;
int anc = dsu.findf(u);
for(auto us : gt[anc])
{
if(us == u) continue;
bool legal1 = 0, legal2 = 0, legal3 = 0;
int nowtot = 0;
for(auto v : g[us])
{
if(vis[v] == 0) legal1 = 1;
if(vis[v] == 1) legal2 = 1, nowtot++;
}
legal3 = (nowtot != tot[u]);
if(legal1 && legal2 && legal3)
{
cout << u << " " << us << "\n";
return;
}
}
}
void solve()
{
cin >> n;
dsu.init();
for(int i = 1; i <= 2 * n; i++)
{
g[i].clear();
gt[i].clear();
vis[i] = 0;
}
for(int i = 1; i <= n; i++)
{
cin >> tot[i];
for(int j = 1; j <= tot[i]; j++)
{
int x;
cin >> x;
g[i].push_back(x);
dsu.combine(i, n + x);
}
}
for(int i = 1; i <= n; i++)
{
int anc = dsu.findf(i);
gt[anc].push_back(i);
}
for(int i = 1; i <= 2 * n; i++)
{
if(gt[i].size() == 0) continue;
sort(gt[i].begin(), gt[i].end(), cmp);
int mxu = gt[i][0], tid = 1;
for(auto v : g[mxu])
vis[v] = 1;
for(auto u : gt[i])
{
if(u == mxu) continue;
++tid;
int lst = -1;
for(auto v : g[u])
{
if(lst == -1) lst = vis[v];
if(vis[v] != lst)
{
brute(u);
return;
}
vis[v] = tid;
}
}
}
cout << "NO\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
* P8256 [NOI Online 2022 入门组] 字符串
这题的题解都在叽里咕噜说什么呢，感觉没有提到倒序操作的都没什么道理啊。
正做着是不好考虑的，因为不仅会删 \(R\) 的头还会删 \(R\) 的尾，根本无法快速求出当前 \(R\) 与 \(T\) 匹配的部分。
我们考虑倒着做，初始时 \(R=T\)。那么操作就会变为：
- \(S_i=\texttt{-}\) 时，在 \(R\) 前面或者后面加一个通配符 \(\texttt{*}\)。因为这个字符是被删掉的，所以它是什么都不会影响答案，起到的只是一个占位的作用。
- \(S_i=\texttt{0/1}\) 时，必须要保证 \(R\) 的末尾能匹配上 \(S_i\)，因为此时 \(R\) 的末尾会被删除。
在这个过程中我们不难发现：倒着操作的过程中，\(R\) 匹配上 \(T\) 的部分一定是一段 \(T\) 的前缀。因为我们无法在前面删数，只能在后面删。
于是可以定义状态 \(dp_{i, j, k, l}\) 表示从后往前考虑，已经执行了第 \(i\) 次操作，前面的通配符有 \(j\) 个，中间匹配上 \(T\) 的有 \(k\) 个，后面的通配符有 \(l\) 个的方案数。但是注意到 \(l = L - j - k\)，所以可以将 \(l\) 这一维度省略。其中 \(L\) 表示当前时间下字符串应有的长度。
转移即可。时间复杂度 \(O(tmn^2)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 405;
const int mod = 1e9 + 7;
int n, m, L[N];
char s[N], t[N];
int dp[N][N][N];
void add(int &x, int y)
{
x += y;
if(x >= mod) x -= mod;
}
void solve()
{
cin >> n >> m >> s + 1 >> t + 1;
for(int i = 1; i <= n; i++)
{
if(s[i] == '-') L[i] = L[i - 1] - 1;
else L[i] = L[i - 1] + 1;
}
memset(dp, 0, sizeof(dp));
dp[n][0][m] = 1;
for(int i = n; i >= 1; i--)
{
for(int j = 0; j <= n; j++)
{
for(int k = 0; k <= n; k++)
{
int l = L[i] - j - k;
if(l < 0 || l > n) continue;
if(s[i] == '-')
{
add(dp[i - 1][j + 1][k], dp[i][j][k]);
add(dp[i - 1][j][k], dp[i][j][k]);
}
else
{
if(l == 0 && k > 0 && t[k] != s[i]) continue;
if(l > 0) add(dp[i - 1][j][k], dp[i][j][k]);
else if(k > 0) add(dp[i - 1][j][k - 1], dp[i][j][k]);
else add(dp[i - 1][j - 1][k], dp[i][j][k]);
}
}
}
}
cout << dp[0][0][0] << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P6570 [NOI Online #3 提高组] 优秀子序列
\(\varphi\) 和位运算显然没啥优美的性质，所以我们只能考虑对每个 \(\varphi\) 求出其贡献系数，即组成它的方案数。
于是考虑状压 DP：\(dp_{S}\) 表示当前和为 \(S\) 的方案数。转移可以考虑枚举子集：
其中 \(f_T\) 表示初始时有多少个 \(T\)。转移时要保证 \(S \oplus T > T\) 的原因是，需要强制要求新加进来的一个数是最大的，否则把数字加进来的顺序也会影响答案。
最后需要特判 \(0\)，因为可以放任意多个 \(0\) 到子序列里。
时间复杂度是经典的子集和复杂度 \(O(3^{\log V})\)。使用 FWT 可以做到更优的复杂度，但是我不会。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1000005, V = 300005;
const ll mod = 1e9 + 7;
ll n, dp[V], a[N], ans, phi[N], cnt, prm[N], f[V];
bitset<N> vis;
ll qpow(ll a, ll b)
{
ll res = 1;
while(b)
{
if(b & 1) res = (res * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return res;
}
void init()
{
phi[1] = 1;
for(int i = 2; i < N; i++)
{
if(!vis[i])
{
prm[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * prm[j] < N; j++)
{
int v = i * prm[j];
vis[v] = 1;
if(i % prm[j] == 0)
{
phi[v] = phi[i] * prm[j];
break;
}
phi[v] = phi[i] * (prm[j] - 1);
}
}
}
int main()
{
// freopen("P6570.in", "r", stdin);
// freopen("P6570.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
f[a[i]]++;
}
dp[0] = 1;
for(int i = 1; i < (1 << 18); i++)
for(int j = i; j > 0; j = ((j - 1) & i))
if(j > (i ^ j))
dp[i] = (dp[i] + dp[i ^ j] * f[j] % mod) % mod;
dp[0] = qpow(2, f[0]);
for(int i = 0; i < (1 << 18); i++)
{
if(i > 0) dp[i] = (dp[i] * dp[0]) % mod;
ans = (ans + dp[i] * phi[1 + i] % mod) % mod;
}
cout << ans;
return 0;
}
P4600 [HEOI2012] 旅行问题
好久没写串串题了。可惜遇到了道没啥思维含量的典题。
题意可以转化为：给你一颗字典树，多次询问，每次询问给定两个点 \(u, v\)，问你字典树上 \(\text{root}\to u\) 和 \(\text{root}\to v\) 路径上的字符串 \(S, T\) 的最长公共后缀的哈希值。
最长公共后缀容易想到 ACAM，因为其 fail 树具有良好的性质：节点 \(u\) 的父亲为字典树上到根链的最长后缀对应的节点。
建出 fail 树后就是简单的了，直接求 \(u, v\) 的 LCA，输出 LCA 处的哈希值即可。
时间复杂度 \(O(|\sum| L + L \log L)\)。如果求 LCA 使用的是树剖，需要注意在求重儿子的时候特判 \(\text{son}_u = 0\) 的情况。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1000005;
const ll mod = 1e9 + 7;
int n, q;
vector<string> ts;
vector<int> ys[N];
vector<int> g[N];
ll tw[N];
struct ACAM{
int ch[N][26], ne[N], idx;
void insert(string s, int id)
{
int p = 0, fa = 0;
for(int i = 0; i < s.length(); i++)
{
fa = p;
int c = s[i] - 'a';
if(ch[p][c] == 0) ch[p][c] = ++idx;
p = ch[p][c];
tw[p] = (tw[fa] * 26 + c) % mod;
ys[id].push_back(p);
}
}
void build()
{
queue<int> q;
for(int i = 0; i < 26; i++)
if(ch[0][i])
q.push(ch[0][i]);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0; i < 26; i++)
{
int v = ch[u][i];
if(v)
{
q.push(v);
ne[v] = ch[ne[u]][i];
}
else ch[u][i] = ch[ne[u]][i];
}
}
for(int i = 1; i <= idx; i++) g[ne[i]].push_back(i);
}
} acam;
int fa[N], top[N], sz[N], dep[N], son[N];
void dfs1(int u, int father)
{
fa[u] = father; sz[u] = 1; dep[u] = dep[father] + 1;
for(auto v : g[u])
{
dfs1(v, u);
sz[u] += sz[v];
if(son[u] == 0 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
if(son[u] == 0) return;
dfs2(son[u], tp);
for(auto v : g[u])
{
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int getlca(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]]) swap(u, v);
v = fa[top[v]];
}
if(dep[u] > dep[v]) swap(u, v);
return u;
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
ts.push_back(s);
acam.insert(s, i);
}
acam.build();
dfs1(0, 0);
dfs2(0, 0);
cin >> q;
while(q--)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
b--, d--;
cout << tw[getlca(ys[a][b], ys[c][d])] << "\n";
}
return 0;
}
P5678 [GZOI2017] 河神
广义矩阵乘法。
\((\oplus, \otimes)\) 矩阵能进行矩阵乘法的充分必要条件为：
- \(\oplus, \otimes\) 都具有结合律。
- $\otimes $ 对 \(\oplus\) 具有分配律。
\((\oplus, \otimes)\) 矩阵存在单位矩阵的充分必要条件为：
- \(\oplus\) 存在零元 \(0\)。
- \(\otimes\) 存在单位元 \(1\)。
- \(\oplus\) 的零元 \(0\) 是 \(\otimes\) 的吸收元。
在本题中，因为 \(\operatorname{and},\operatorname{or}\) 操作具有结合律，且 \(\operatorname{and}\) 对 \(\operatorname{or}\) 有分配律（可以考虑韦恩图证明或者代入 \(0, 1\) 变量证明），所以该操作可以使用矩阵乘法描述。
按照题意模拟构造完转移矩阵后，使用矩阵快速幂即可。注意广义矩阵快速幂的单位矩阵构造，本题中 \(\oplus\) 的零元为 \(0\)，\(\otimes\) 的单位元为 \(2^{63} - 1\)。
PS：其实幂次 \(\ge 1\) 的矩阵快速幂并不一定要构造出单位矩阵，可以直接将幂次减 \(1\)，把转移矩阵作为初始乘积。
时间复杂度 \(O(K^3\log N)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 105;
const ll MSK = 9223372036854775807ll;
struct Matrix{
ll a[N][N];
Matrix(){ memset(a, 0, sizeof(a)); }
Matrix operator * (const Matrix & t) const{
Matrix res;
for(int i = 0; i < N; i++)
for(int k = 0; k < N; k++)
for(int j = 0; j < N; j++)
res.a[i][j] = (res.a[i][j] | (a[i][k] & t.a[k][j]));
return res;
}
};
Matrix qpow(Matrix a, ll b)
{
Matrix res;
for(int i = 0; i < N; i++) res.a[i][i] = MSK;
while(b)
{
if(b & 1) res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
ll n, k, a[N], b[N];
void construct_init(Matrix &res)
{
for(int i = 0; i < k; i++) res.a[0][i] = a[i];
}
void construct_dp(Matrix &res)
{
for(int i = 0; i < k - 1; i++) res.a[i + 1][i] = MSK;
for(int i = 0; i < k; i++) res.a[i][k - 1] = b[i];
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 0; i < k; i++) cin >> a[i];
for(int i = 0; i < k; i++) cin >> b[i];
if(n < k)
{
cout << a[n];
return 0;
}
Matrix s, dp;
construct_init(s);
construct_dp(dp);
s = s * qpow(dp, n - k + 1);
cout << s.a[0][k - 1];
return 0;
}
* P9462 「EZEC-14」终点
好题！
首先对 \(1 < i \le n\) 查询 \((1, i)\)，可以确定树的二分图染色。
考虑 A 性质怎么做。显然 \(2\) 的父亲一定是 \(1\)，于是我们可以依次确定 \(3\sim n\) 的父亲。具体而言，假设当前要确定的是 \(u\) 的父亲：
- 若 \(1, u\) 同色，则查询 \((1, u)\) 的中点 \(v\)。可知 \(u\) 一定在 \(v\) 的子树中，所以可以递归到 \(v\) 子树内的子问题。
- 若 \(1, u\) 不同色，则查询 \((2, u)\) 的中点 \(v\)。后面递归到 \(v\) 子树内也是同理。
容易发现这样的话每次 \(u, v\) 的距离会变为原来的一半，所以需要用 \(O(n+\sum_{i = 1}^n\lceil \log_2i\rceil)\) 次操作。
现在如果 A 性质不成立了，我们就要想办法将 A 性质的做法转化一下。
先是要求出一个与 \(1\) 相邻的节点，这样才能在后面处理与 \(1\) 异色的点。该如何求出这个相邻的点？结论是：我们在确定树的二分图染色后，跳跃到异色点的步数最多的一条路径上的异色点就是与 \(1\) 相邻的节点。证明可以考虑对 \(1, u\) 之间的距离做质因数分解，容易发现如果存在一个非 \(2\) 质因子，则替换为 \(2\) 是一定最优的，到最后就一定是 \(1\cdot 2^k\) 的形式，即与 \(1\) 相邻。
求出相邻点之后就是好做的了，我们仿照上文的思路，用这个类似整体二分的方法逐步确定所有点的父亲。这个可以用 BFS 实现，只要把当前局面下已确定父亲的点全部丢进队列里即可。遇到需要查询未确定父亲的节点时，直接把询问挂在那个点上，等它出队的时候再处理即可。
操作次数大概是 \(O(n+\sum_{i = 1}^n\lceil \log_2i\rceil)\) 级别。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 10005;
map<pi, int> ans;
int query(int x, int y)
{
if(ans.count({x, y})) return ans[{x, y}];
cout << "? " << x << " " << y << endl;
int res;
cin >> res;
ans[{x, y}] = res;
return res;
}
int tid, n, fa[N], col[N], dep[N];
vector<int> g[N], qs[N];
void dfs(int u)
{
for(auto v : g[u])
{
dfs(v);
dep[u] = max(dep[u], dep[v] + 1);
}
}
int main()
{
cin >> tid >> n;
col[1] = 1;
for(int i = 2; i <= n; i++)
{
col[i] = query(1, i);
if(col[i] == 0) g[1].push_back(i);
else
{
g[col[i]].push_back(i);
col[i] = 1;
}
}
dfs(1);
int m = 2;
for(int i = 3; i <= n; i++)
if(dep[i] > dep[m])
m = i;
queue<int> q;
q.push(1); q.push(m);
fa[1] = m; fa[m] = 1;
for(int i = 2; i <= n; i++)
if(i != m)
qs[1].push_back(i);
while(!q.empty())
{
int u = q.front();
q.pop();
for(auto v : qs[u])
{
if(col[u] == col[v])
qs[query(u, v)].push_back(v);
else
{
int res = query(fa[u], v);
if(res == u) fa[v] = u, q.push(v);
else qs[res].push_back(v);
}
}
}
cout << "!" << endl;
for(int i = 2; i <= n; i++) cout << i << " " << fa[i] << endl;
return 0;
}
AT_abc440_f [ABC440F] Egoism
写这题的感觉堪比吃了一斤鸵鸟史。
注意到乘积的其中一项只能是 \(1, 2\)，考虑直接把 \(2\) 的系数分配给心情值大的马。
一般情况下这些 \(2\) 是可以全部分完的，但是如果 \(2\) 的系数全在心情值最大的那几个身上，就有一个无法被分完。此时需要删掉心情值最大的那几个中，最小的心情值；然后再加上其余心情值里，最大的心情值。
可以使用权值线段树 + 线段树上二分维护。细节很多，讲了也没啥用，直接看代码吧。
时间复杂度 \(O(n\log V)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1000005, V = 1000000 + 1;
struct Node{
int l, r;
ll sm, cnt2, mx, num;
};
struct Segtree{
Node tr[4 * N];
void pushup(Node &p, Node ls, Node rs)
{
p.sm = ls.sm + rs.sm;
p.cnt2 = ls.cnt2 + rs.cnt2;
p.mx = max(ls.mx, rs.mx);
p.num = ls.num + rs.num;
}
void build(int p, int ln, int rn)
{
tr[p] = {ln, rn, 0, 0, 0, 0};
if(ln == rn) return;
int mid = (ln + rn) >> 1;
build(lc, ln, mid);
build(rc, mid + 1, rn);
pushup(tr[p], tr[lc], tr[rc]);
}
void update(int p, int pos, int typ, int x)
{
if(tr[p].l == pos && tr[p].r == pos)
{
if(typ == 1) tr[p].sm += x * pos, tr[p].num += x;
else tr[p].cnt2 += x;
if(tr[p].num == 0) tr[p].mx = 0;
else tr[p].mx = pos;
return;
}
int mid = (tr[p].l + tr[p].r) >> 1;
if(pos <= mid) update(lc, pos, typ, x);
else update(rc, pos, typ, x);
pushup(tr[p], tr[lc], tr[rc]);
}
Node query(int p, int ln, int rn)
{
if(ln <= tr[p].l && tr[p].r <= rn) return tr[p];
int mid = (tr[p].l + tr[p].r) >> 1;
if(rn <= mid) return query(lc, ln, rn);
if(ln >= mid + 1) return query(rc, ln, rn);
Node tmp;
pushup(tmp, query(lc, ln, rn), query(rc, ln, rn));
return tmp;
}
int binary(int p, int k, int &cur)
{
if(cur + tr[p].num < k)
{
cur += tr[p].num;
return -1;
}
if(tr[p].l == tr[p].r) return tr[p].l;
int res = binary(lc, k, cur);
if(res != -1) return res;
res = binary(rc, k, cur);
return res;
}
} tr1;
ll n, q, a[N], b[N], cnt2;
void solve()
{
ll lst = n - cnt2;
int tmp = 0;
int p = tr1.binary(1, lst, tmp);
int pre = tr1.query(1, 0, p).cnt2;
ll ans = tr1.tr[1].sm;
if(cnt2 == 0)
{
cout << ans << "\n";
return;
}
ans += tr1.query(1, p + 1, V).sm;
tmp = 0;
int nowp = tr1.binary(1, tr1.query(1, 0, p).num + 1, tmp);
if(!pre)
{
tmp = 0;
int nowp = tr1.binary(1, tr1.query(1, 0, p).num + 1, tmp);
ans -= nowp;
ans += tr1.query(1, 0, p).mx;
}
else
ans += (cnt2 - tr1.query(1, p + 1, V).num) * p;
cout << ans << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
tr1.build(1, 0, V);
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i];
tr1.update(1, a[i], 1, 1);
if(b[i] == 2) tr1.update(1, a[i], 2, 1), cnt2++;
}
for(int i = 1; i <= q; i++)
{
int id, x, y;
cin >> id >> x >> y;
tr1.update(1, a[id], 1, -1);
if(b[id] == 2) tr1.update(1, a[id], 2, -1), cnt2--;
a[id] = x; b[id] = y;
tr1.update(1, a[id], 1, 1);
if(b[id] == 2) tr1.update(1, a[id], 2, 1), cnt2++;
solve();
}
return 0;
}
AT_abc438_f [ABC438F] Sum of Mex
Sol.1 暴力分讨
考虑枚举 \(\text{MEX} = x\)，则 \(1\sim x - 1\) 必须构成一条链，且 \(x\) 不在链上。
为了方便讨论，钦定 \(0\) 为树根。
接下来显然可以直接暴力分类讨论，我分了两个阶段：
- 当链的某个端点为 \(0\) 时，此时右端点为 \(cur\)。根据 \(i\) 的位置：在 \(cur\) 子树里、在 \(0\) 的另一个子树里、在 \(cur\) 的到根链上、在其他位置进行分类讨论，可以利用 LCA 来判断属于哪一类。
- 否则这条链的两个端点分居 \(0\) 的两颗子树内，我们称左端点为 \(lx\)，右端点为 \(cur\)。根据 \(i\) 的位置：在 \(lx\) 子树里、在 \(cur\) 子树里、在 \(lx\to cur\) 的链上、在其他位置进行分类讨论，依然可以利用 LCA 来判断属于哪一类。
计数部分直接乘法原理算即可。
时间复杂度 \(O(n\log n)\)，如果使用一些神秘均摊求 LCA 可以做到线性。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 200005;
ll n, rd[N];
ll fa[N], dep[N], son[N], sz[N], top[N];
ll ans = 0;
vector<int> g[N];
void dfs1(int u, int father)
{
fa[u] = father; dep[u] = dep[father] + 1; sz[u] = 1;
for(auto v : g[u])
{
if(v == fa[u]) continue;
dfs1(v, u);
sz[u] += sz[v];
if(son[u] == 0 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
if(son[u] == 0) return;
dfs2(son[u], tp);
for(auto v : g[u])
{
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int getlca(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
return v;
}
int main()
{
// freopen("abc438f.in", "r", stdin);
// freopen("abc438f.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
ll mxrd = 0;
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
rd[u]++; rd[v]++;
mxrd = max(mxrd, rd[u]);
mxrd = max(mxrd, rd[v]);
}
if(n == 2)
{
cout << 3;
return 0;
}
dfs1(0, 0);
dfs2(0, 0);
int nowu = 1;
while(fa[nowu]) nowu = fa[nowu];
ans = 1;
ll pre = 1, sumu = 1;
for(auto v : g[0])
{
if(v == nowu)
{
ans += (sz[v] - sz[1]) * pre;
pre += sz[v] - sz[1];
}
else
{
ans += sz[v] * pre;
pre += sz[v];
sumu += sz[v];
}
}
int cur = 1, lx = 0;
for(int i = 2; i < n; i++)
{
if(lx == 0)
{
int lca = getlca(cur, i);
if(lca == cur)
{
ans += sumu * (sz[cur] - sz[i]) * i;
cur = i;
}
else if(lca == i)
continue;
else if(lca == 0)
{
ans += (sumu - sz[i]) * sz[cur] * i;
lx = i;
}
else
{
ans += sumu * sz[cur] * i;
break;
}
}
else
{
int lca1 = getlca(lx, i), lca2 = getlca(cur, i);
if(lca1 == lx)
{
ans += (sz[lx] - sz[i]) * sz[cur] * i;
lx = i;
}
else if(lca2 == cur)
{
ans += sz[lx] * (sz[cur] - sz[i]) * i;
cur = i;
}
else if(lca1 == i || lca2 == i)
continue;
else
{
ans += sz[lx] * sz[cur] * i;
break;
}
}
}
if(mxrd == 2) ans += n;
cout << ans;
return 0;
}
Sol.2 01 转化
将 \(\sum \text{MEX}\) 转化为 \(\sum_{i = 0}^n [\text{MEX}> i]\)。于是我们就不需要考虑被 ban 掉的那个 \(x\)，直接看 \(1\sim x - 1\) 构成的链即可。分类讨论的情况被大大减少。
* P4375 [USACO18OPEN] Out of Sorts G
首先将原序列离散化，相同的元素里位置靠前的分配较小的编号，否则无法保证轮数最少。
结论：双向冒泡排序的排序轮数为 \(\max_{i = 1}^n\{\sum_{j = 1}^i[A_j > B_i]\}\)。其中 \(A\) 为原序列，\(B\) 为排序后的序列。
现在给出两种不同角度的证明：
Pf.1 从元素交换角度
每轮冒泡排序会把左侧比 \(B_i\) 大的带到右边去，然后带回来一个右侧比 \(B_i\) 小的数。又因为左侧比 \(B_i\) 大的数的个数等于右侧比 \(B_i\) 小的数的个数，所以答案为对每个 \(B_i\)，左侧比它大的数的个数取 \(\max\) 的结果。
Pf.2 从二维平面转化角度
该思路来源于CommonAnts 的视频。
考虑 \(01\) 转化。具体而言，考虑枚举基准值 \(d\)，将 \(\ge d\) 的元素视为 \(1\)，\(< d\) 的元素视为 \(0\)。
把 \(01\) 串刻画在二维平面上。即把 \(0\) 视为向右走，\(1\) 视为向上走，则该 \(01\) 串在二维平面上构成了一段从 \((0, 0) \to (cnt_0, cnt_1)\) 的路径。当序列有序时这个路径的形态显然是 \((0, 0)\to (cnt_0, 0)\to (cnt_0, cnt_1)\)。
那么在执行一轮冒泡排序之后 \(01\) 串会变成什么样呢？在冒泡的时候，\(01\) 会变成 \(10\)，反映到二维平面上就是上右变为了右上，如图 \(1\) 所示。
假设当前 \(01\) 串刻画在二维平面上如图 \(2\) 所示。
那么在执行一次从左到右的冒泡后，会像如图 \(3\) 所示一样，所有 \(y > 0\) 的横向移动都会变低一格。
同理，在执行一次从右到左的冒泡后（不执行从左到右的冒泡），会像如图 \(4\) 所示一样，所有 \(x < cnt_0\) 的纵向移动都会靠右一格。
如果将前后两次冒泡排序的效果复合，则可以得到一轮冒泡排序的效果，如下图所示。
观察图像可以得到结论：每轮冒泡排序会使得原路径向右下移动一格，越过边界的部分会直接变为边界。
对路径上的每个点 \((x, y)\) 考虑，定义其偏移函数 \(D(x, y) = \min\{cnt_0 - x, y\}\) 为 \((x, y)\) 移动到目标路径上的最小轮数。那么基准值确定时，排序完成的轮数为 \(r = \max_{(x, y)\in \text{Path}} D(x, y)\)。最终的答案即为所有可能的 \(d\) 下，\(r\) 的最大值。
这启示我们最后的答案是每个点、在每个 \(d\) 的情况下的偏移函数 \(D(x, y)\) 的最大值。
回到序列上，如果序列里一个元素对应着二维平面上的点 \((x, y)\)，这就相当于它前面有 \(x\) 个 \(0\)，\(y\) 个 \(1\)。类比到偏移函数里，\(D(x, y)\) 的另一含义则为前缀的 \(cnt_1\) 与后缀的 \(cnt_0\) 的最小值。
若当点 \((x, y)\) 确定时，\(f(d)\) 表示 \(d\) 固定时 \(D(x, y)\) 的值。则此时有另一个结论：\(f(d)\) 为单峰函数，且 \(d = B_p\) 时取得最大值。其中 \(p\) 为点 \((x, y)\) 对应在序列里的下标。
如何证明这个结论？容易注意到 \(d\) 变大的时候，前缀里 \(1\) 的个数单调不增，后缀里 \(0\) 的个数单调不降；\(d\) 变小的时候是同理。于是单峰性质就被证明了。而注意到 \(d = B_p\) 的时候前缀的 \(cnt_1\) 与后缀的 \(cnt_0\) 相等，所以此时可以取得最大值。
由此可以知道取 \(d = B_p\) 时，\((x, y)\) 的最小轮数 \(r = \sum_{j = 1}^p[A_j > B_p]\)。最后每个位置取最大值即为答案。
得到了结论剩下的就是随便做了，我的做法是用树状数组。时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 100005;
int n;
int a[N], b[N], bn, c[N];
int lowbit(int x)
{
return (x & (-x));
}
struct BIT{
int tr[N];
void update(int p, int v)
{
while(p)
{
tr[p] += v;
p -= lowbit(p);
}
}
int query(int p)
{
int res = 0;
while(p <= bn + 1)
{
res += tr[p];
p += lowbit(p);
}
return res;
}
} tr1;
int getrk(int x)
{
return (lower_bound(b + 1, b + bn + 1, x) - b);
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
b[++bn] = a[i];
}
sort(b + 1, b + bn + 1);
bn = unique(b + 1, b + bn + 1) - b - 1;
for(int i = 1; i <= n; i++)
{
a[i] = getrk(a[i]);
c[i] = a[i];
}
sort(c + 1, c + n + 1);
int ans = 1;
for(int i = 1; i <= n; i++)
{
tr1.update(a[i], 1);
ans = max(ans, tr1.query(c[i] + 1));
}
cout << ans;
return 0;
}
P4378 [USACO18OPEN] Out of Sorts S
题意为给定一个序列，求冒泡排序轮数。
结论：序列 \(A\) 要执行的冒泡排序轮数为 \(\max_{1\le i \le n}\{\sum_{j = 1}^{i - 1}[A_j > A_i]\}\)。
证明是简单的，因为如果 \(A_i\) 前面如果有 \(k\) 个比它自己大的，就要用 \(k\) 轮冒泡排序将这些大的数移动到后面去。
也可以使用前一题的 01 转化进行分析，只是很复杂。这题的结论很容易猜所以就没写。
剩下的用离散化 + BIT 实现即可。时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 100005;
int n, a[N], b[N], bn, ans;
int getrk(int x)
{
return (lower_bound(b + 1, b + bn + 1, x) - b);
}
int lowbit(int x)
{
return (x & (-x));
}
struct BIT{
int tr[N];
void update(int p, int v)
{
while(p)
{
tr[p] += v;
p -= lowbit(p);
}
}
int query(int p)
{
int res = 0;
while(p <= bn + 1)
{
res += tr[p];
p += lowbit(p);
}
return res;
}
} tr1;
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
b[++bn] = a[i];
}
sort(b + 1, b + bn + 1);
bn = unique(b + 1, b + bn + 1) - b - 1;
for(int i = 1; i <= n; i++) a[i] = getrk(a[i]);
for(int i = 1; i <= n; i++)
{
tr1.update(a[i], 1);
ans = max(ans, tr1.query(a[i] + 1));
}
cout << ans + 1;
return 0;
}
* P4372 [USACO18OPEN] Out of Sorts P
首先把序列离散化，相同的元素位置靠前的分配更小的编号，对应着冒泡排序的稳定性。
观察此类分割序列的性质，因为一轮冒泡排序会把最大的元素带到最后面，这样 \((n - 1, n)\) 之间就存在一个分界点了，所以这个函数里的 do while 部分完全是没用的，一次递归里这东西最多只会执行一次。
从每个元素贡献答案的角度考虑，一个元素不再贡献当且仅当区间长度为 \(1\)，否则每次递归中这个元素都会提供 \(1\) 的贡献。
因此问题被转化为求每个元素变为长度为 \(1\) 的段所需的轮数之和。而“长度为 \(1\)”的条件又可以转化为 \((i - 1, i), (i, i + 1)\) 之间都存在分界点，我们只需要求出每个分界点的出现时间即可。
继续分析分界点 \((i, i + 1)\) 的性质，因为冒泡排序每次交换都会消去一个逆序对，所以不会进行无用的操作，根据题意 \(A_{1\sim i}, A_{i + 1\sim n}\) 之间不存在逆序对，所以冒泡排序一定不会影响已经形成的分界点。
由此进一步分析可以得到：若 \(A_i\) 经过若干次冒泡排序后不会再移动，那么此时 \((i, i + 1)\) 之间就存在一个分界点。当时推到这里的时候后面就不会做了，实际上这个结论对本题的做法没有用。
先说结论：\((i, i + 1)\) 之间存在分界点的最小轮数为 \(\max\{\max_{j > i, A_j < A_i} j - i, 1\}\)。
现在给出两种角度的证明：
Pf.1 从元素交换的角度
因为要向左移动的元素每轮排序后只会向左移动一格，所以如果要成为分界点，右侧比自己小的元素必然会移到自己左侧，且移动的时间为 \(pos - i\)。
在这之中，所需的最大轮数即为答案，也就是 \(\max\{\max_{j > i, A_j < A_i} j - i, 1\}\)。
结论的证明不难理解，但是比较 Ad-hoc，但是有没有不吃智力的思考方式呢？有的兄弟，有的，不吃智力的推导方式还有很多，下文给出一种排序问题的经典刻画方式。
Pf.2 从二维平面转化的角度
考虑 \(01\) 转化。具体而言，考虑枚举基准值 \(d\)，将 \(\ge d\) 的元素视为 \(1\)，\(< d\) 的元素视为 \(0\)。
把 \(01\) 串刻画在二维平面上。即把 \(0\) 视为向右走，\(1\) 视为向上走，则该 \(01\) 串在二维平面上构成了一段从 \((0, 0) \to (cnt_0, cnt_1)\) 的路径。当 \((i, i + 1)\) 存在分界点时，我们选取基准值 \(d = A_i + 1\)，此时目标路径的形态显然是 \((0, 0)\to (i, 0)\to (i, n - i)\)。因为此时有 \(i\) 个 \(0\)，\(n - i\) 个 \(1\)。
考虑一次冒泡排序的效果，依然是这张图：
一轮冒泡排序会把 \(01\to 10\)，如图 \(1\) 所示。
那么我们假设当前的路径为图 \(2\)，则进行一轮冒泡排序之后路径会像图 \(3\) 一样（这张图是从我的另一篇题解偷过来的，所以图 \(4\) 没有用）。
转化为形式语言，就是一轮冒泡排序之后路径会整体向下移动一个单位长度，越过边界的部分会直接变为边界。
那么路径变为目标路径的时间就是，右边最后一个横向路径段 \(k\) 移动到 \(x\) 轴的时间（因为最右边的是最高的）。
根据上文的分析，这个时间为 \(pos_k\) 左侧的 \(1\) 的个数。因为 \(k\) 为最后一个 \(0\)，即 \(pos_k\) 右边有 \(n - k\) 个 \(1\)，所以所需轮数为 \(n - i - (n - k) = k - i\)。
所以轮数就是 \(\max\{\max_{j > i, A_j < A_i} j - i, 1\}\)。
得到了结论之后，我们把元素从大到小加入序列里，后面就是随便做了。时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 100005;
int n, a[N], t[N];
pi b[N];
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = {a[i], i};
}
sort(b + 1, b + n + 1);
int mxpos = 0;
for(int i = 1; i <= n; i++)
{
mxpos = max(mxpos, b[i].se);
t[i] = max(1, mxpos - i);
}
t[0] = 1;
ll ans = 0;
for(int i = 1; i <= n; i++)
ans += max(t[i - 1], t[i]);
cout << ans;
return 0;
}
* P12499 「DLESS-1」Life Lies in Movement
吓哭了，喜欢我们神秘 Ad-hoc 吗。
死因：把 \(\sum \text{dis}\) 转化成了 \(\sum \text{size}\)，后面想了一车性质全都用不到正解上。
第一步，也是最关键的一步，是将 \(f(x, u, v)\) 与 \(f(x, v, u)\) 两两配对，发现 \(f(x, u, v) + f(x, v, u) = \text{dis}(u, v)\)。
然后转化计数条件：
根据 \(x\) 的位置分类讨论后发现，\(f(x, u, v) - f(x, v, u) = \text{dis}(u, x) - \text{dis}(v, x)\)。
继续往下推：
使用换根 DP 可以得到 \(\sum_{x = 1}^n \text{dis}(u, x)\)，最后我们只需要排序后使用双指针即可完成 \((u, v)\) 的计数。
时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1000005;
ll n, k, dp1[N], dp2[N], dep[N], sz[N];
vector<pi> g[N];
void dfs1(int u, int fa)
{
sz[u] = 1;
for(auto eg : g[u])
{
int v = eg.fi; ll w = eg.se;
if(v == fa) continue;
dep[v] = dep[u] + w;
dfs1(v, u);
dp1[u] += dp1[v];
sz[u] += sz[v];
}
dp1[u] += dep[u];
}
void dfs2(int u, int fa)
{
for(auto eg : g[u])
{
int v = eg.fi; ll w = eg.se;
if(v == fa) continue;
dp2[v] = dp2[u] + w * (sz[1] - 2 * sz[v]);
dfs2(v, u);
}
}
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
g[i].clear();
dp1[i] = dp2[i] = dep[i] = 0;
}
for(int i = 1; i < n; i++)
{
ll u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs1(1, 0);
dp2[1] = dp1[1];
dfs2(1, 0);
sort(dp2 + 1, dp2 + n + 1);
int p = 1;
ll ans = 0, lmt = 2 * n * k;
for(int i = 1; i <= n; i++)
{
while(p + 1 <= i && dp2[i] - dp2[p + 1] >= lmt) p++;
if(dp2[i] - dp2[p] >= lmt) ans += p;
}
cout << ans << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P12497 「DLESS-1」回文括号序列
手玩题，挺有趣的。
首先 \(n\) 为奇数的情况没有合法括号序列，一定无解。下文只考虑 \(n\) 为偶数。
手完后发现必然有 \(s_1 = \texttt{(}, s_n = \texttt{)}\)。
贪心地考虑让每一位都会对答案产生贡献。具体而言，按照如下的方式进行构造，并时刻保证所有括号都被匹配。
容易发现这样子构造能保证几乎每个位置都有贡献。且每次加 \(4\) 个括号，最后会剩下两个未匹配的同向括号。
匹配到最后的时候，需要分两种情况讨论：
- 若 \(n\bmod 4 = 0\)，说明最后会形如 \(\texttt{(())((XXXX(())()}\)，此时 \(4\) 个 \(\texttt{X}\) 里需要填 \(3\) 个 \(\texttt{)}\) 和 \(1\) 个 \(\texttt{(}\)。枚举后发现填 \(\texttt{()))}\) 是最优的。
- 否则 \(n\bmod 4 = 2\)，最后会形如 \(\texttt{(())((XX(())()}\)，只能填 \(\texttt{))}\) 了。
这样做的话没有贡献的位置只有最外面的一个，和最里面的一个，显然无法做到更优。最外面的一个怎么办都无法做出贡献，而如果最里面的要有贡献的话，形态就是唯一的了，但是我们发现这个形态不合法。于是现在的构造就是最优的方案。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 100005;
int n;
void solve()
{
cin >> n;
if(n & 1)
{
cout << "-1\n";
return;
}
if(n % 4 == 2)
{
cout << "()";
n -= 2;
while(n > 0)
{
n -= 4;
cout << "(())";
}
cout << "\n";
return;
}
if(n == 4)
{
cout << "()()\n";
return;
}
cout << "()";
for(int i = 1; i <= ((n / 4) - 2) / 2; i++) cout << "(())";
cout << "((()))";
for(int i = 1; i <= (n / 4) - ((n / 4) - 2) / 2 - 2; i++) cout << "(())";
cout << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P12500 「DLESS-1」XOR and OR
首先考虑拆位，子区间权值按位或的异或和相当于求子区间权值按位或为 \(1\) 的个数模 \(2\) 的结果。而根据容斥原理，每一位的答案就是子区间的个数减去按位或为 \(0\) 的子区间个数。
开 \(60\) 个线段树分别维护每个位里的纯 \(0\) 段是简单的，维护区间内最左侧的数字、最右侧的数字、是否为纯色段、最左侧的连续段长度、最右侧的连续段长度、纯 \(0\) 段个数的奇偶性、纯 \(1\) 段个数的奇偶性即可。
此时时间复杂度是 \(O(n\log n\log V)\)，无法通过。
考虑不建这么多线段树，而是建一颗，把其余线段树的信息利用位运算集成到一颗线段树上。容易发现这些信息的合并都能通过位运算完成，于是时间复杂度就被降为了 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 500005;
const ll FULL = (1ll << 60) - 1;
ll n, q, a[N];
struct Node{
int l, r;
ll lhave, rhave, full, lcnt, rcnt, sm0, sm1, tag;
};
struct Segtree{
Node tr[4 * N];
void pushup(Node &p, Node ls, Node rs)
{
p.lhave = ls.lhave;
p.rhave = rs.rhave;
p.full = (ls.full & rs.full & (~(ls.lhave ^ rs.rhave)));
p.lcnt = (ls.lcnt ^ (rs.lcnt & ls.full & (~(ls.rhave ^ rs.lhave))));
p.rcnt = (rs.rcnt ^ (ls.rcnt & rs.full & (~(ls.rhave ^ rs.lhave))));
p.sm0 = (ls.sm0 ^ rs.sm0 ^ ((~ls.rhave) & (~rs.lhave) & ls.rcnt & rs.lcnt));
p.sm1 = (ls.sm1 ^ rs.sm1 ^ (ls.rhave & rs.lhave & ls.rcnt & rs.lcnt));
}
void modify(Node &p, ll tag)
{
p.tag ^= tag;
p.lhave ^= tag;
p.rhave ^= tag;
ll orism0 = p.sm0, orism1 = p.sm1;
p.sm0 ^= (tag & (orism0 ^ orism1));
p.sm1 ^= (tag & (orism0 ^ orism1));
}
void pushdown(int p)
{
if(tr[p].tag)
{
modify(tr[lc], tr[p].tag);
modify(tr[rc], tr[p].tag);
}
tr[p].tag = 0;
}
void build(int p, int ln, int rn)
{
tr[p] = {ln, rn, a[ln], a[ln], FULL, FULL, FULL, (~a[ln]), a[ln], 0};
if(ln == rn) return;
int mid = (ln + rn) >> 1;
build(lc, ln, mid);
build(rc, mid + 1, rn);
pushup(tr[p], tr[lc], tr[rc]);
}
void update(int p, int ln, int rn, ll tag)
{
if(ln <= tr[p].l && tr[p].r <= rn)
{
modify(tr[p], tag);
return;
}
pushdown(p);
int mid = (tr[p].l + tr[p].r) >> 1;
if(ln <= mid) update(lc, ln, rn, tag);
if(rn >= mid + 1) update(rc, ln, rn, tag);
pushup(tr[p], tr[lc], tr[rc]);
}
Node query(int p, int ln, int rn)
{
if(ln <= tr[p].l && tr[p].r <= rn) return tr[p];
pushdown(p);
int mid = (tr[p].l + tr[p].r) >> 1;
if(rn <= mid) return query(lc, ln, rn);
if(ln >= mid + 1) return query(rc, ln, rn);
Node tmp;
pushup(tmp, query(lc, ln, rn), query(rc, ln, rn));
return tmp;
}
} tr1;
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
tr1.build(1, 1, n);
while(q--)
{
ll op, l, r, x;
cin >> op >> l >> r;
if(op == 1)
{
cin >> x;
tr1.update(1, l, r, x);
}
else
{
ll len = r - l + 1;
ll id = len * (len + 1) / 2;
id &= 1;
ll res = 0;
if(id) res = FULL;
ll tmp = (tr1.query(1, l, r).sm0) & FULL;
res ^= tmp;
cout << res << "\n";
}
}
return 0;
}
P12498 「DLESS-1」Range | Sum | Maximum
其实是套路题。
首先转化题意，\([l, r]\) 的权值为它的最大绝对值子段和，所以可以将 \(a\) 数组先做一遍前缀和，权值就被转化为选择任意两个数使得差的绝对值最大，即极差最大。于是权值被转化为区间前缀和最大值减去区间前缀和最小值。
下文以求区间前缀和最大值为例，最小值是同理的。
套路地枚举序列里的每一个元素 \(A_i\)，用单调栈求出其支配区间 \([L, R]\)。其中 \(L\) 为 \(\max_{j < i, A_j \ge A_i}j + 1\)，\(R\) 为 \(\min_{j > i, A_j > A_i}j - 1\)。
考虑这个元素的贡献，我们枚举其左端点 \(l\in [L, i]\)，那么其右端点 \(r\in[i, R]\)。
容易发现这个贡献是若干个长度相等且相邻的区间加的形式，所以可以转为差分：将连续的一段左端点 \(+ A_i\)，然后让一段连续的右端点 \(-A_i\)。如果这样暴力做依然会超时，所以再用一次差分解决差分值的区间加即可。
上述做法和观察到贡献是两端等差数列和中间一段平的形态，然后直接二维差分的做法是本质相同的。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 1000005;
ll n, a[N], tp, stk[N], prex[N], prey[N], sufx[N], sufy[N], f[N];
void solve()
{
cin >> n;
f[0] = 0;
for(int i = 1; i <= n; i++)
{
f[i] = 0;
cin >> a[i];
a[i] += a[i - 1];
}
f[n + 1] = 0;
tp = 0; stk[0] = -1;
for(int i = 0; i <= n; i++)
{
while(tp && a[stk[tp]] < a[i]) tp--;
prex[i] = stk[tp];
stk[++tp] = i;
}
tp = 0; stk[0] = -1;
for(int i = 0; i <= n; i++)
{
while(tp && a[stk[tp]] > a[i]) tp--;
prey[i] = stk[tp];
stk[++tp] = i;
}
tp = 0; stk[0] = n + 1;
for(int i = n; i >= 0; i--)
{
while(tp && a[stk[tp]] <= a[i]) tp--;
sufx[i] = stk[tp];
stk[++tp] = i;
}
tp = 0; stk[0] = n + 1;
for(int i = n; i >= 0; i--)
{
while(tp && a[stk[tp]] >= a[i]) tp--;
sufy[i] = stk[tp];
stk[++tp] = i;
}
for(int i = 0; i <= n; i++)
{
int l = prex[i] + 1, r = sufx[i] - 1;
f[1] += a[i];
f[i - l + 2] -= a[i];
f[r - i + 2] -= a[i];
f[r - l + 3] += a[i];
l = prey[i] + 1, r = sufy[i] - 1;
f[1] -= a[i];
f[i - l + 2] += a[i];
f[r - i + 2] += a[i];
f[r - l + 3] -= a[i];
}
for(int i = 1; i <= n + 1; i++) f[i] += f[i - 1];
for(int i = 1; i <= n + 1; i++) f[i] += f[i - 1];
ll ans = 0;
for(int i = 1; i <= n; i++)
ans ^= (f[i + 1] % (1ll * i * i));
cout << ans << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P14943 浅谈矩阵乘法
没啥思维含量的纯分讨题。
矩阵快速幂的一个经典应用是在图上跑走 \(k\) 步的方案数，于是原题可以转化为给定一张有向图，问任意时刻到某个点的方案数是否是有界的。
首先可以将原图缩点，然后对图的形态进行分讨：
- 如果一个 SCC 不是纯环，则方案数一定无界。
- 如果一个边数 \(>0\) 的 SCC 能到另一个边数 \(>0\) 的 SCC，则方案数一定无界。
跑拓扑排序模拟即可，时间复杂度 \(O(Tn^2)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 105;
int n, a[N][N];
vector<int> g[N], g2[N];
int dfn[N], low[N], tot, scc[N], tp, stk[N], cnt, sz[N], esz[N], tag[N];
bitset<N> instk;
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
instk[u] = 1; stk[++tp] = u;
for(auto v : g[u])
{
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instk[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
int x;
cnt++;
do{
x = stk[tp--];
instk[x] = 0;
scc[x] = cnt;
sz[cnt]++;
} while(x != u);
}
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
g[i].clear();
g2[i].clear();
dfn[i] = low[i] = scc[i] = sz[i] = esz[i] = instk[i] = tag[i] = 0;
}
tp = tot = cnt = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
if(a[i][j]) g[i].push_back(j);
}
}
for(int i = 1; i <= n; i++)
if(dfn[i] == 0)
tarjan(i);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(a[i][j] > 1 && scc[i] == scc[j])
{
cout << "NO\n";
return;
}
if(a[i][j] && scc[i] == scc[j])
esz[scc[i]]++;
if(a[i][j] && scc[i] != scc[j])
g2[scc[i]].push_back(scc[j]);
}
}
for(int i = 1; i <= cnt; i++)
{
if(sz[i] < esz[i])
{
cout << "NO\n";
return;
}
sort(g2[i].begin(), g2[i].end());
g2[i].erase(unique(g2[i].begin(), g2[i].end()), g2[i].end());
}
for(int i = cnt; i >= 1; i--)
{
if(esz[i]) tag[i]++;
if(esz[i] && tag[i] > 1)
{
cout << "NO\n";
return;
}
tag[i] = min(tag[i], 2);
for(auto v : g2[i])
tag[v] += tag[i];
}
cout << "YES\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
* P14599 CF1093F 加强版
下文称 \(\text{len}\) 为 \(m\)。
考虑一个暴力容斥：定义 \(S_i\) 表示 \(i\sim i + m - 1\) 是否相等。答案即为所有的 \(S\) 下 \((-1)^{|S|}\times \text{cnt}\) 之和。
这个暴力容斥显然无法处理大数据，于是我们考虑将部分的容斥系数合在一起计算。具体而言，将一个长度为 \(L\) 的同色区间视为一个单元，该区间的容斥系数即为：
证明：
问题转化为在 \(1\sim L\) 中选择 \(t\) 个覆盖起点，使得它们覆盖了长度为 \(L\) 的整个区间。设第 \(i\) 个起点的位置为 \(\text{pos}_i\)，两个位置的差 \(\text{pos}_{i+1} - \text{pos}_i = d_i\)，则一个合法的覆盖方案必须要满足 \(\text{pos}_1 = 1, d_i\in [1, m]\) 且 \(d_1 + d_2 + \cdots + d_{t - 1} + m = L\)。
现在只需要求出对于所有的 \(t \ge 1\)，有多少组合法的 \(d\) 满足 \(d_1 + d_2 + \cdots + d_{t - 1}= L - m\)。
这显然是个经典的生成函数问题。定义 \(H(x) = x + x^2 + x^3 + \cdots x^m\)，则 \(t\) 确定时答案为 \(H(x)^{t - 1}\) 中 \(L - m\) 次项的系数。
根据等比级数的公式 \(1 + A + A^2 + A^3 + \cdots = \dfrac{1}{1 - A}\)，考虑推式子：
然后根据等比数列求和公式来推 \(H(x)\) 的公式：
将 \(H(x)\) 代入：
注意到 \(\dfrac{1}{1 - x^{m+1}} = \sum_{i \ge 0}x^{i\times (m+1)}\)，所以有：
因此，若 \(L\bmod (m + 1) = 0\)，则容斥系数为 \(1\)；若 \(L\bmod (m + 1) = m\)，则容斥系数为 \(-1\)；否则容斥系数为 \(0\)。
最后我们只需要求出所有情况下，容斥系数之积的和。这个可以用前缀和优化 DP 来求，只需要求出当前位置 \(i\) 前面第一个已确定的位置 \(p_1\) 与前面第一个与当前段的元素不同的已确定位置 \(p_2\) 即可。
时间复杂度 \(O(n)\)。
代码实现参考了这篇题解。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const ll N = 2000005, mod = 1e9 + 7;
ll n, k, m, a[N], dp[N], f[N], p1[N], p2[N];
int getpre(int x, int y)
{
return (x - ((x - y) % m + m) % m);
}
void add(ll &x, ll y)
{
x += y;
if(x >= mod) x -= mod;
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(a[i] > 0) p1[i] = i;
else p1[i] = p1[i - 1];
if(a[p1[p1[i] - 1]] == a[p1[i]]) p2[i] = p2[p1[i] - 1];
else p2[i] = p1[p1[i] - 1];
}
dp[0] = f[0] = 1;
for(int i = 1; i <= n; i++)
{
int px = p1[i], py = p2[i];
auto solve = [&] (int pos, ll c) -> void {
int x = getpre(i - 1, pos), y = getpre(px - 1, pos), z = getpre(py - 1, pos);
ll X = (x < 0 ? 0 : f[x]), Y = (y < 0 ? 0 : f[y]), Z = (z < 0 ? 0 : f[z]);
add(dp[i], (((X - Y) * k % mod + (Y - Z) % mod) * c % mod + mod) % mod);
};
solve(i - 1, 1);
solve(i, -1);
f[i] = dp[i];
if(i - m >= 0) add(f[i], f[i - m]);
}
cout << dp[n];
return 0;
}
AT_abc405_g [ABC405G] Range Shuffle Query
值域分块板子。
考虑如何计算答案。首先在不考虑相同元素的情况下答案是 \(\text{cnt}!\)，其中 \(\text{cnt}\) 为 \(< X\) 的元素个数。
若 \(< X\) 的元素中，等于 \(Y\) 的元素有 \(k\) 个，则答案需要除以 \(k!\) 以去掉这些数重排构成的方案数。
于是问题被转化为求区间内 \(< X\) 的数的贡献之和、贡献之积。可以使用树套树或者莫队 + 值域分块维护。
我使用的是莫队 + 值域分块，时间复杂度 \(O((q+n)\sqrt n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
const int N = 250005, B = 500;
const ll mod = 998244353;
int n, q;
ll a[N], inv[N], f[N], tot[N], ans[N];
void init()
{
inv[1] = 1;
for(int i = 2; i < N; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
f[0] = 1;
for(int i = 1; i < N; i++)
f[i] = (f[i - 1] * i) % mod;
}
struct Decompose{
int L[N], R[N], bl[N], Btot;
ll Prod[N], val[N], Sm[N], vsm[N];
void build()
{
Btot = (n + B - 1) / B;
for(int i = 1; i <= Btot; i++)
{
L[i] = (i - 1) * B + 1;
R[i] = min(n, i * B);
Sm[i] = 0;
Prod[i] = 1;
for(int j = L[i]; j <= R[i]; j++)
{
val[j] = 1;
Prod[i] = (Prod[i] * val[j]) % mod;
bl[j] = i;
vsm[j] = 0;
}
}
}
void update(int pos, ll v, ll sm)
{
vsm[pos] += sm;
val[pos] = (val[pos] * v) % mod;
Sm[bl[pos]] += sm;
Prod[bl[pos]] = (Prod[bl[pos]] * v) % mod;
}
pl query(int pos)
{
if(pos == 0) return {0, 1};
ll res = 1, sm = 0;
for(int i = pos; i >= L[bl[pos]]; i--)
{
res = (res * val[i]) % mod;
sm += vsm[i];
}
for(int i = bl[pos] - 1; i >= 1; i--)
{
res = (res * Prod[i]) % mod;
sm += Sm[i];
}
return {sm, res};
}
} dc1;
struct Mo{
int l, r, x, id;
bool operator < (const Mo & t) const{
if(l / B != t.l / B) return (l < t.l);
if((l / B) & 1) return (r > t.r);
return (r < t.r);
}
} Qs[N];
void add(int pos)
{
tot[a[pos]]++;
dc1.update(a[pos], inv[tot[a[pos]]], 1);
}
void del(int pos)
{
dc1.update(a[pos], tot[a[pos]], -1);
tot[a[pos]]--;
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
cin >> n >> q;
dc1.build();
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= q; i++)
{
cin >> Qs[i].l >> Qs[i].r >> Qs[i].x;
Qs[i].id = i;
}
sort(Qs + 1, Qs + q + 1);
for(int L = 1, R = 0, i = 1; i <= q; i++)
{
int l = Qs[i].l, r = Qs[i].r, x = Qs[i].x, id = Qs[i].id;
while(L > l) add(--L);
while(R < r) add(++R);
while(L < l) del(L++);
while(R > r) del(R--);
pl res = dc1.query(x - 1);
ans[id] = f[res.fi] * res.se % mod;
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
AT_abc405_e [ABC405E] Fruit Lineup
因为当最后一个苹果确定的时候能一口气满足两个限制，于是我们考虑枚举最后一个苹果的位置 \(p\)，这样就剩下了最后一个限制。
接下来有两种做法：
- 组合意义做法。考虑 \(p + 1 \sim n\) 的部分，因为所有橘子都在葡萄左边，所以当香蕉的位置确定的时候，其余的位置全都确定了，方案数为 \(\binom{p - 1}{A - 1}\times \binom{A + B + C + D - p}{C}\)。
- 范德蒙德卷积做法。考虑 \(p + 1 \sim n\) 的部分，发现右侧以最后一个橙子作为分界线，可以分为两部分：橙子 + 香蕉、香蕉 + 葡萄。枚举“橙子 + 香蕉”部分的香蕉个数 \(x\)，且假设当前剩余橙子个数为 \(Y\)，则结果为 \(\sum_{i = 0}^x \binom{Y + x}{x}\times \binom{C - x + D}{C - x}\)。根据范德蒙德卷积，这个式子可以化简为 \(\binom{Y+C+D}{C}\)，与组合意义做法推出来的式子是等价的。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const ll mod = 998244353, N = 4000005;
ll a, b, c, d, ans, f[N], g[N], inv[N];
void init()
{
inv[1] = 1;
for(int i = 2; i < N; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
f[0] = g[0] = 1;
for(int i = 1; i < N; i++)
{
f[i] = (f[i - 1] * i) % mod;
g[i] = (g[i - 1] * inv[i]) % mod;
}
}
ll C(ll n, ll m)
{
return (f[n] * g[m] % mod * g[n - m] % mod);
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
cin >> a >> b >> c >> d;
for(int i = a; i <= a + b; i++)
{
ll lans = C(i - 1, a - 1);
ll rans = C(a + b + c + d - i, c);
ans = (ans + lans * rans % mod) % mod;
}
cout << ans;
return 0;
}
P6855 「EZEC-4.5」走方格
一种难写的思路是正反 DP 之后建出最优转移 DAG，然后判必经点，最后在修改必经点的贡献中取一个最小值。
但是实际上本题不需要建出最优转移 DAG。注意到每一种方案之中都只会恰好走到一次 \(x + y = i\) 的直线上，所以当修改 \((x, y)\) 的时候，其余 \(x+y=i\) 的直线上元素的贡献与自己的贡献取一个最大值，即为修改 \((x, y)\) 的最大答案。这个可以对 \(x+y=i\) 的直线上做一个前缀最小值、后缀最小值实现。
时间复杂度 \(O(nm)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 2005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
ll a[N][N], f[N][N], g[N][N], ans = inf, pre[2 * N], suf[2 * N];
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
memset(f, -0x3f, sizeof(f));
memset(g, -0x3f, sizeof(g));
f[1][1] = a[1][1]; g[n][m] = a[n][m];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) continue;
if(i > 1) f[i][j] = max(f[i][j], f[i - 1][j]);
if(j > 1) f[i][j] = max(f[i][j], f[i][j - 1]);
f[i][j] += a[i][j];
}
}
for(int i = n; i >= 1; i--)
{
for(int j = m; j >= 1; j--)
{
if(i == n && j == m) continue;
if(i < n) g[i][j] = max(g[i][j], g[i + 1][j]);
if(j < m) g[i][j] = max(g[i][j], g[i][j + 1]);
g[i][j] += a[i][j];
}
}
for(int i = 1; i <= n + m; i++)
{
memset(pre, -0x3f, sizeof(pre));
memset(suf, -0x3f, sizeof(suf));
for(int x = max(1, i - m); x <= n && i - x >= 1 && i - x <= m; x++)
{
int y = i - x;
pre[x] = max(pre[x - 1], f[x][y] + g[x][y] - a[x][y]);
}
for(int x = min(n, i - 1); x >= 1 && i - x >= 1 && i - x <= m; x--)
{
int y = i - x;
suf[x] = max(suf[x + 1], f[x][y] + g[x][y] - a[x][y]);
ans = min(ans, max(pre[x - 1], max(suf[x + 1], f[x][y] + g[x][y] - 2 * a[x][y])));
}
}
cout << ans;
return 0;
}
* CF1838E Count Supersequences
依然被艾德豪克击杀。
考虑贪心地从前往后匹配，只匹配整体在最前面的子序列。
于是我们可以钦定 \(n\) 个匹配项，假设这些项的位置为 \(p_1, p_2, \cdots, p_n\)，那么在 \(1\sim p_n\) 的下标里必须满足 \(b_i\ne \mathrm{next}_i\)，其中 \(\mathrm{next}_i\) 表示位置 \(i\) 的后继。所以一个位置有 \(k - 1\) 种填法。
那么对于 \(p_n + 1\sim n\) 的位置，怎么填都可以，因为这一部分不参与任何匹配。一个位置有 \(k\) 种填法。
于是问题被转化为了求 \(\sum_{i = 0}^{m - n} C_{m-i}^{n}k^i(k-1)^{m-n-i}\) 的值。后面的步骤需要用到神秘的错位相减技巧，但是我不会，于是我就这么暴毙了。
但是根据前文的分析，我们容易注意到一个事实：\(a\) 的具体取值并不会影响答案。于是我们考虑让 \(a\) 全部变为 \(1\)。那么问题就被转化为了：求至少有 \(n\) 个 \(1\) 的序列的个数。
这就很显然了，我们考虑正难则反，问题被转化为求 \(\mathrm{cnt}_1 < n\) 的序列个数。答案即为 \(k^m - \sum_{i = 0}^{n - 1}C_{m}^{i}(k-1)^{m - i}\)。其中 \(C_{m}^i\) 可以根据组合数的定义暴力计算。
时间复杂度为 \(O(n\log V)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b)
{
ll res = 1;
while(b)
{
if(b & 1) res = (res * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return res;
}
ll n, m, k, ans;
void solve()
{
cin >> n >> m >> k;
ans = qpow(k, m);
ll tmp = 1;
ans = ((ans - tmp * qpow(k - 1, m)) % mod + mod) % mod;
for(int i = 1; i <= n; i++)
{
ll a;
cin >> a;
}
for(int i = 1; i < n; i++)
{
tmp = (tmp * (m - i + 1)) % mod;
tmp = (tmp * qpow(i, mod - 2)) % mod;
ans = ((ans - tmp * qpow(k - 1, m - i)) % mod + mod) % mod;
}
cout << ans << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P15361 「WYZOI R2」拜年
注意到有单调性：若通行证 \((l, r)\) 是合法的，且 \(1\le L \le l \le r \le R \le 2n\)，那么通行证 \((L, R)\) 也是合法的。
很容易想到使用双指针在移动左端点的时候，维护最小的合法右端点。问题在于如何判定通行证是否合法。
首先可以开一个桶存对应值的对应位置，然后有如下三种处理方式：
- 根据每一列的状态，修改一列时判断相邻两列和自己的连通性，当所有列都连通的时候则合法。时间复杂度 \(O(n)\)。
- 根据每一列的状态写出转移矩阵，用线段树维护连通性。时间复杂度 \(O(B^3n\log n )\)，其中 \(B = 2\)。
- 使用 LCT 维护动态图连通性。
代码采用了复杂度最低的第一种。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 200005;
int n, a[5][N], b[N], lst;
vector<pi> tot[2 * N];
bool check(int x, int y)
{
if((!x) || (!y)) return 0;
if((x ^ y) != 3) return 1;
return 0;
}
void solve()
{
ll ans = 0;
cin >> n;
lst = n + 1;
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
tot[a[i][j]].push_back({j, (1 << (i - 1))});
b[j] = 0;
}
}
int p = 0;
for(int i = 1; i <= 2 * n; i++)
{
while(p + 1 <= 2 * n && lst)
{
p++;
for(auto itm : tot[p])
{
int pos = itm.fi, st = itm.se;
bool ilg1 = 0, ilg2 = 0;
if(pos > 1)
{
ilg1 = (!check(b[pos - 1], b[pos]));
}
else
{
ilg1 = (!(b[pos] & 1));
}
if(pos < n)
{
ilg2 = (!check(b[pos], b[pos + 1]));
}
else
{
ilg2 = (!((b[pos] >> 1) & 1));
}
b[pos] |= st;
if(pos > 1)
{
if(ilg1 && check(b[pos - 1], b[pos])) lst--;
}
else
{
if(ilg1 && (b[pos] & 1)) lst--;
}
if(pos < n)
{
if(ilg2 && check(b[pos], b[pos + 1])) lst--;
}
else
{
if(ilg2 && ((b[pos] >> 1) & 1)) lst--;
}
}
}
if(lst == 0) ans += 2 * n - p + 1;
for(auto itm : tot[i])
{
int pos = itm.fi, st = itm.se;
bool ilg1 = 0, ilg2 = 0;
if(pos > 1)
{
ilg1 = (check(b[pos - 1], b[pos]));
}
else
{
ilg1 = ((b[pos] & 1));
}
if(pos < n)
{
ilg2 = (check(b[pos], b[pos + 1]));
}
else
{
ilg2 = (((b[pos] >> 1) & 1));
}
b[pos] ^= st;
if(pos > 1)
{
if(ilg1 && !check(b[pos - 1], b[pos])) lst++;
}
else
{
if(ilg1 && !(b[pos] & 1)) lst++;
}
if(pos < n)
{
if(ilg2 && !check(b[pos], b[pos + 1])) lst++;
}
else
{
if(ilg2 && !((b[pos] >> 1) & 1)) lst++;
}
}
}
cout << ans << "\n";
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= n; j++)
{
tot[a[i][j]].clear();
}
}
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
P15369 『ICerOI Round 1』并非图论
从讨论区来的，有人觉得这题比道路修建要难。
题是好题，但是我感觉这题除了细节比较烦人以外没啥难点了啊？
首先转化条件，添加一条边 \((u, v)\) 相当于权值为 \(u+v\)，然后后面减掉了 \(u\operatorname{and} v\)，于是边权就变成了 \(u \operatorname{or} v\)。
我们对所有 \(l < i \le r\) 的点进行考虑，尝试将点 \(i\) 与点 \(j(l\le j < i)\) 进行连边，并且选择边权最小的一条边。这样选出的就一定是一个生成树。
于是题意转化为求出 \(\sum_{i = l + 1}^r \min_{l \le j < i}{i\operatorname{or}j}\) 的值。
先考虑 \(l = 1\) 的情况，此时对于每个 \(i\)，边权都至少为 \(i\)，因此 \(j\) 要尽可能成为 \(i\) 的子集。当 \(\operatorname{popcount}(i) \ge 2\) 的时候，可以令 \(j = i - \operatorname{lowbit}(i)\)；否则令 \(j = l\)。
然后当 \(l\ne 1\) 的情况时，就需要考虑 \(i - \operatorname{lowbit}(i) < l\) 的情况了。手模后发现这种情况很少出现，具体而言，令 \(x = l\)，\(f(x) = x + \operatorname{lowbit}(x)\)，那么这种情况的 \(i\) 构成的集合为 \(\{x \mid \exists k \ge 1 \text{ s.t. } f^{k}(x) \le r \}\)。这些点直接与 \(l\) 连边是最优的。注意到集合的大小为 \(O(\log n)\)，所以可以暴力枚举出来。
第二问求 \(l\) 的最小度数可以在求第一问的过程中一并实现，此处略去。
时间复杂度 \(O(T\log n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const ll mod = 1e9 + 7, inv2 = 500000004;
ll lowbit(ll x)
{
return (x & (-x));
}
void solve()
{
ll l, r, res1 = 0, res2 = 0;
cin >> l >> r;
res1 = (res1 + (l + 1 + r) % mod * ((r - l) % mod) % mod * inv2 % mod) % mod;
ll hb = 0;
for(hb = 0; (1ll << hb) <= l; hb++);
ll tmp = l;
for(int i = 0; tmp + (1ll << i) <= r && (1ll << i) < lowbit(l); i++)
res2++;
tmp = l;
tmp += lowbit(tmp);
while(tmp < min((1ll << hb), r + 1))
{
res1 = (res1 + (tmp | l) - tmp) % mod; res2++;
tmp += lowbit(tmp);
}
while((1ll << hb) <= r)
{
res2 = (res2 + 1) % mod;
res1 = (res1 + l) % mod;
hb++;
}
cout << res1 << " " << res2 << "\n";
}
int main()
{
//freopen("sample.in", "r", stdin);
//freopen("sample.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll cid, n, q;
cin >> cid >> n >> q;
while(q--) solve();
return 0;
}
浙公网安备 33010602011771号