当前位置: 首页 > news >正文

数据结构思维题选做(长期更新)

到处乱找的. 用到的数据结构在 NOIP 考纲内,主要是学习、锻炼各种处理思路. 代码的实现都不算困难.

倍增思想

P10198 [USACO24FEB] Infinite Adventure P

Hint:跳的步数明显提示倍增. 根据 \(\sum T_i\) 的限制直接预处理是三只 \(\log\) 的,考虑怎样优化到两只 \(\log\).

的确是非常深刻的倍增题.

\(f_{u,k,t}\) 表示在日期 \(\bmod T_u=t\)\(u\) 开始\(2^k\) 步到达的节点. 但是这样直接做正确性无法保证,因为可能跳到 $ T_v>T_u$ 的节点 \(v\),这时我们就无法继续倍增了. 根据 \(\sum T_i\le10^5\) 以及 \(T_i\)\(2\) 的幂,令 \(V=\sum T_i\),所以只存在 \(O(\log V)\) 种不同的 \(T_i\). 于是我们令出现上述情况时 \(u\) 停在 \(v\) 不再继续跳,回答单次询问就是 \(O(\log V\log\Delta)\) 的. 由于预处理要对每种 \(T_i\) 都做一遍,所以总复杂度是 \(O(V\log^2V\log \Delta+q\log V\log\Delta)\) 的.

上述的预处理方法实际上有大量冗余的部分,如果跳到一个 \(T_v<T_u\) 的节点那么我们会丢失 \(u\) 的信息,之后再扩大 \(T_u\) 范围时间复杂度很劣. 因为 \(T_u\) 本身其实可以记录所有 \(\le T_u\) 的状态,所以我们可以通过修改倍增状态 \(f_{u,k,t}\) 的定义为\(2^k\)\(T_v=T_u\) 的节点后到达的点,此时转移就需要额外记录跳的步数 \(d_{u,k,t}\). 我们仍然强制让 \(f\) 停在第一个 \(T_v>T_u\)\(v\),就可以先通过每次跳极大的步数来用 \(O(\log V)\) 的时间找到第一个 \(T_v\ge T_u\) 的点作为 \(f_{u,0,t}\),并记下当前花的步数 \(d_{u,0,t}\),就可以倍增转移了. 这样大大优化了预处理的复杂度,总时间复杂度变为 \(O(V(\log V+\log \Delta)+q\log V\log\Delta)\).

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 1e5 + 10; const ll inff = 2e18;
int n, q, a[maxn];vector<int> b[maxn], f[maxn][70];
vector<ll> d[maxn][70];void init() {for(int s = 1; s < maxn; s <<= 1) {for(int u = 1; u <= n; u++) if(a[u] == s) {for(int i = 0; i < s; i++) {int v = b[u][i]; ll t = 1;while(a[v] < s && t < inff) {ll w = f[v][60][(i + t) % a[v]];t += d[v][60][(i + t) % a[v]], v = w;}f[u][0][i] = v, d[u][0][i] = min(t, inff);}}for(int k = 1; k <= 60; k++) for(int u = 1; u <= n; u++) if(a[u] == s) {for(int i = 0; i < s; i++) {int v = f[u][k - 1][i]; ll t = d[u][k - 1][i];if(a[v] == s) {f[u][k][i] = f[v][k - 1][(i + t) % s];d[u][k][i] = min(d[v][k - 1][(i + t) % s] + t, inff);}else f[u][k][i] = v, d[u][k][i] = t;}}}
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) {b[i].resize(a[i]);for(int &p : b[i]) cin >> p;for(int k = 0; k <= 60; k++) d[i][k].resize(a[i]), f[i][k].resize(a[i]);}init();while(q--) {int u; ll cur, dis;cin >> u >> cur >> dis;while(dis) {for(int k = 60; ~k; k--) if(dis >= d[u][k][cur % a[u]]) {int v = f[u][k][cur % a[u]]; ll t = d[u][k][cur % a[u]];if(a[v] != a[u]) k = 61;dis -= t, cur += t, u = v;}if(dis) u = b[u][cur % a[u]], dis--, cur++;}cout << u << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=13756

相关文章:

  • 政治笔记/错题
  • 9.22模拟赛总结
  • 莫队 n的序列,多次查询一段区间内的数字的个数
  • 【mysql】mysql客户端中文显示乱码
  • 揭秘“牛牛透视”
  • k8s系列--控制器yml(15)
  • 学生管理系统案例初步分析报告
  • 【mysql】mysql5.6 版本修改用户的登录
  • AT_abc200_e [ABC200E] Patisserie ABC 2 题解
  • 日总结 5
  • Linux驱动开发(1)概念、环境与代码框架 - 实践
  • Diffutoon下载介绍:真人视频转动漫工具,轻松获得上千点赞
  • 9月22号
  • 0.5*8 边形 != 式
  • 题解:AT_agc052_c [AGC052C] Nondivisible Prefix Sums
  • 寻路算法
  • 2025年9月22日 - 20243867孙堃2405
  • day 1
  • [Paper Reading] METAGPT: META PROGRAMMING FOR A MULTI-AGENT COLLABORATIVE FRAMEWORK
  • 二进制 - 20243867孙堃2405
  • 学习问题日记-1
  • 记一次生产环境内存溢出记录
  • 四舍六入五成双
  • 借助 Apache Phoenix,使用标准 SQL 和 JDBC 接口来操作 HBase
  • 学生信息管理系统
  • 如何让AI生成多页面APP原型图?AI原型设计实用指南
  • 代码随想录算法训练营第五天 | leetcode 242 349 202 1
  • CF2146 Codeforces Round 1052 (Div. 2) 游记
  • 原码补码反码与位操作
  • 接口