7
1007 创作乐曲 （hdu7511）
妙妙dp题，赛时wyq一眼丁真、发现可以线段树优化dp，可惜我们没推出关键性质，最后TLE遗憾离场。
在每个最优子乐曲中，音符 \(i\) 的后继音符只有两种可能：\(a[p] - a[i] \leq k\) 中距离 \(i\) 最近的 \(p\)，或者 \(a[i] - a[q] \leq k\) 中距离 \(i\) 最近的 \(q\). 采用反证法，若 \(i\) 的后继是其他音符 \(j\)，由 \(\mid a[j] - a[i]\mid\space\leq k\)，\(a[p]\) 与 \(a[q]\) 中至少其一可放在 \(i\) 与 \(j\) 间，即其他情况不是最优解。
查询距 \(i\) 最近的合法后继结点 \(p,q,\) 可使用线段树优化时间复杂度。建立 \(1\) 至 \(m\) 的权值线段树，维护每个音符的下标，加入新的音符 \(i\) 即 \(a[i]\) 位置赋值为 \(i\)，查询 \(p,q\) 即查询 \(l = a[i] - k,\space r = a[i]\) 或 \(l = a[i],\space r = a[i] + k\) 的区间最小值；注意由于权值范围过大，线段树需要动态开点。预处理所有 \(p,q,\) 询问时即可 \(O(n)\) 计算最优子乐曲。
线段树代码：
int num[M], ls[M] = {0}, rs[M] = {0}, cnt;
void update(int i, ll l, ll r, ll q, int x) {
num[i] = x;
if(l == r) return;
ll mid = (l + r) / 2;
if(q <= mid) {
if(!ls[i]) ls[i] = ++cnt;
update(ls[i], l, mid, q, x);
} else {
if(!rs[i]) rs[i] = ++cnt;
update(rs[i], mid + 1, r, q, x);
}
}
int query(int i, ll l, ll r, ll ql, ll qr) {
if(ql <= l && qr >= r) return num[i];
ll mid = (l + r) / 2;
int ans = n + 1;
if(ql <= mid) ans = min(ans, query(ls[i], l, mid, ql, qr));
if(qr > mid) ans = min(ans, query(rs[i], mid + 1, r, ql, qr));
return ans;
}
main函数内主要代码：
cnt = 1;
num[0] = num[1] = n + 1; // num[0] = n + 1，防止查询时最小值取为0
for(int i = n; i; i--) {
nex1[i] = query(1, 1, m, max(1ll, a[i] - k), a[i]);
nex2[i] = query(1, 1, m, a[i], min(a[i] + k, m));
update(1, 1, m, a[i], i); // 先查询再加点
}
int q;
scanf("%d", &q);
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
for(int i = l; i <= r; i++) {
dp[i] = i - l;
}
for(int i = l; i <= r; i++) {
dp[nex1[i]] = min(dp[nex1[i]], dp[i] + nex1[i] - i - 1);
dp[nex2[i]] = min(dp[nex2[i]], dp[i] + nex2[i] - i - 1);
}
int ans = n + 1;
for(int i = l; i <= r; i++) {
ans = min(ans, dp[i] + r - i);
}
printf("%d\n", ans);
}
1008 循环图 （hdu7512）
计数题，考虑dp递推计算，发现dp方程已确定的情况下需要最多 \(10^{18}\) 次转移，且 \(n\leq 100\)，可使用矩阵快速幂优化dp，分别对区间左右端点计数，最终答案即 \(ans[r] - ans[l - 1]\). 设计转移矩阵，对于 \(x\) 指向 \(y\) 的一条边，\(y\leq n\) 时在本周期内转移、可以与其他路径累计，\(y > n\) 时则只能计算一次，按节点编号依次处理可避免遗漏；\(ans[x]\) 为节点 \(1\) 至 \(x\) 方案数之和，因此在转移矩阵中添加第 \(n + 1\) 维，对前 \(n\) 维的结果求和，再令 \(a[n + 1][n + 1] = 1\)，即可在快速幂过程中维护答案。初值行向量即节点 \(1\) 至 \(n\) 的方案数，与转移矩阵同理计算；对于最后不足 \(n\) 个节点的答案可暴力统计。
主要代码：
// 转移矩阵
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(y[j] == i + n) {
b[x[j]][i] += w[j];
if(b[x[j]][i] >= mo) b[x[j]][i] -= mo;
} else if(y[j] == i) {
for(int k = 1; k <= n; k++) {
b[k][i] += b[k][x[j]] * w[j] % mo;
if(b[k][i] >= mo) b[k][i] -= mo;
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
b[i][n + 1] += b[i][j];
if(b[i][n + 1] >= mo) b[i][n + 1] -= mo;
}
}
b[n + 1][n + 1] = 1;
equal(qwq, b); // equal用于赋值，似乎库函数里有赋值函数但我忘了）
fpm(b, (l - 1) / n); // 快速幂
fpm(qwq, (r - 1) / n);
// 初始向量
for(int i = 1; i <= n + 1; i++) sl[i] = 0;
sl[1] = sr[1] = 1;
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(y[j] == i) {
sl[i] += sl[x[j]] * w[j] % mo;
if(sl[i] >= mo) sl[i] -= mo;
}
}
sr[i] = sl[i];
}
for(int i = 1; i <= n; i++) {
sl[n + 1] += sl[i];
if(sl[n + 1] >= mo) sl[n + 1] -= mo;
}
sr[n + 1] = sl[n + 1];
mul(sl, b); // 矩阵乘
mul(sr, qwq);
// 统计答案，暴力处理边界
ll ans = (sr[n + 1] - sl[n + 1] + mo) % mo;
int cur = (l - 1) % n + 1;
for(int i = cur; i <= n; i++) {
ans += sl[i];
if(ans >= mo) ans -= mo;
}
cur = (r - 1) % n + 1;
for(int i = cur + 1; i <= n; i++) {
ans += mo - sr[i];
if(ans >= mo) ans -= mo;
}
printf("%lld\n", ans);
另有：一开始转移矩阵似乎写错了，想参考std却发现它自己都过不了样例，不好评价（）最后找xht要了代码才AC，感谢大佬队友orz
标签：杭电多校,int,mo,mid,2024,num,ans,ll From： https://www.cnblogs.com/meowqwq/p/18352516