期望dp——用记忆化搜索
title: 期望dp——用记忆化搜索 categories: ICPC tags: null abbrlink: 1e8ca1b date: 2024-08-07 00:00:00 https://www.luogu.com.cn/problem/P4316 本题暂时只写了用期望dp经典套路，套上期望DP的基本套路，设dp(u)为到达u点的期望长度。 期望dp，也叫概率dp 一般来说，期望dp找到正确的状态后，转移是比较容易想到的。 但一般情况下，状态一定是“可数”的 事实上，将问题直接作为dp的状态是最好的。 如，问**“n人做XX事的期望次数”，那么不妨设计状态为f[i]表示i个人做完事的期望**。 转移一般是递推，通常分两种，一种是从上一个状态转移得（填表法），另一种是转移向下一个状态（刷表法）。 有时期望dp需以最终状态为初始状态转移，即逆推。 如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法 还可以拓扑排序，直接很数学地倒着算一遍。（待完成 // Problem: 绿豆蛙的归宿 // Contest: AcWing // URL:...
倍增专题
title: 倍增专题 categories: ICPC tags: null abbrlink: 2e8656b4 date: 2024-08-05 00:00:00 倍增大专题 [AHOI2008] 紧急集合 / 聚会 - 洛谷 题意：给定一棵树，多次查询费马点（bushi 费马点的含义是：到三个点的距离之和最小 Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。 //考虑到让一个点走多的路程，两点走短路程 //首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同 vector<int> e[N]; int fa[N],son[N],dep[N],siz[N]; int top[N]; void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; for(int v:e[u]){ if(v==f)...
回文自动机PAM
title: 回文自动机PAM categories: ICPC tags: null abbrlink: e5a7c7ec date: 2024-08-04 00:00:00 回文自动机PAM 在线数据结构「笔记」回文自动机 - Luckyblock - 博客园 (cnblogs.com) 每个状态仅代表唯一的本质不同的回文子串字符串 。s 的本质不同回文子串的数量至多只有 |s|个，则 PAM 的状态数个数是 O(n)级别的 算法原理就是增量法构建 PAM，利用前面的回文后缀，fail指针配合转移边进行维护。 算法核心流程： 1.加入新节点的时候找到以这个点的结尾的最长回文后缀，需要跑last,last—>fail,last—>fail->fail,直到有转移边或者有奇根。目的是找到新建节点的父亲。 为新建节点找到不平凡的最长回文回文后缀(也就是不包含自身)。这一步骤爬上一步(找到的父亲)(的fail链)（不包含父亲） struct PAM { static constexpr int asz = 28; ...
离散化
title: 离散化 categories: ICPC tags: null abbrlink: 515818b4 date: 2024-08-03 00:00:00 离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。 https://oi-wiki.org/misc/discrete/ 通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。 用来离散化的可以是大整数、浮点数、字符串等等。 最常见方法：排序+去重+二分 //数据离散化_排序+去重 void discrete() { sort(lan.begin(), lan.end()); //排序 lan.erase(unique(lan.begin(), lan.end()), lan.end()); //去重 } //查询 int query(int x) { ...
ST 表
title: ST 表 categories: ICPC tags: null abbrlink: 9e993aa5 date: 2024-08-01 00:00:00 封装函数版本 template <typename T, class F = function<T(const T&, const T&)>> struct SparseTable { int n; vector<vector<T>> st; F func; SparseTable(const vector<T>& a, const F& f) : func(f) { n=(int)a.size()-1; int max_log = __lg(n) +1; st.resize(max_log+1); st[0] = a; for (int j = 1; j...
第 132 场周赛——质数小结论，并查集配Floyd
title: 第 132 场周赛——质数小结论，并查集配Floyd categories: ICPC tags: null abbrlink: b614dbf4 date: 2024-08-01 00:00:00 https://www.acwing.com/activity/content/competition/problem_list/3648/ B题收获： 1.利用题目告诉的结论：1e9范围质数之差小于300 2.一个数不被2-a的任何数整除 等价于他的最小质因子需要大于a c题：初步宏观思路：不难想到用并查集维护类别，只需将每一个类缩成一个点，由于最多只有500个类别，跑一个floyd就可以了 部分细节处理：我的思路是类别用并查集维护，开了一个哈希表去存每个类别对应的根节点是最终floyd的第几个点，in...
5157
title: 5157 categories: ICPC tags: null abbrlink: d9943f91 date: 2024-07-25 00:00:00 https://www.acwing.com/problem/content/5157/ 利用贡献思想入门的一道题，对于看起来复杂的问题，我们去考虑每一个元素在每一轮中的贡献，如果这道题不理解了可以去看视频讲解，里面说的非常明晰。 在本题实现过程中需要找到找到数组中的最大数，并且统计有几个同时最大的数，我的实现非常不好，用stl麻烦了，参考一下别人优雅的实现。 for (int i = 0; i < n; i ++ ) { int t = ++ cnt[s[i]]; if (t > mx) mx = t, ct = 1; else if (t == mx) ct ++ ; } 上面代码中不断维护最大值以及最大值的数的个数 #include <bits/stdc++.h> using...
Codeforces Round 923 (Div. 3)
title: Codeforces Round 923 (Div. 3) categories: ICPC tags: null abbrlink: edd265aa date: 2024-07-18 00:00:00 Codeforces Round 923 (Div. 3) F：给定一张一般图，不保证连通，定义一个简单环的权值是环中最小边的权值，求图中最小环的权值和具体由哪些点组成。 Sol：首先需要思考的是怎么求出最大权值？我们考虑用克鲁斯卡尔算法的思想对边权排序，考虑逐步加入图中，一旦合并失败就说明当前边构成了这个环的最小边，我们维护答案，同时记录左右端点。 ...
牛客小白月赛86
title: 牛客小白月赛86 categories: ICPC tags: null abbrlink: 9be380b5 date: 2024-07-17 00:00:00 B 水平考试 ====== 等价于两个集合 S,TS, TS,T 判断 SSS 中是否存在 TTT 中所不包含的元素。 若存在则输出 0； 否则输出 10。 时间复杂度：O(T)O(T)O(T) C题：区间查询当前区间可以被分为多少段，要求每段只有一种数字。 做法1：提前对所有段编号，查询时直接左右边界编号相减，注意边界需要特别处理 做法2：标记第i段与第i+1段之间的分界点，然后求前缀和，本质上和做法1一样 D题：给定网格，0表示障碍，1表示道路。问有多少块长方形道路？（正方形也是长方形） 对此我们首先用过bfs找到连通块，对于每个连通块我们需要维护这个连通块最大x，y坐标， 最小x，y坐标，以及连通块大小。当连通块是矩形的时候通过 统计矩形的(minX, minY) -> (maxX, maxY) 然后判断 (maxY - minY + 1) * (maxX - minX +...
IEEE备战
title: IEEE备战 categories: ICPC tags: null abbrlink: 712f0cc1 date: 2024-07-14 00:00:00 IEEE评测题解链接 10.0以前提交链接：IEEE ENSIAS Student Branch (github.com) 11.0-17.0评测：https://csacademy.com/ieeextreme-practice/task/ IEEEXtreme 10.0 极限编程大赛题解 - meelo -...