期望dp——用记忆化搜索
title: 期望dp——用记忆化搜索categories: - ICPCtags: - nullabbrlink: 1e8ca1bdate: 2024-08-07 00:00:00https://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: - ICPCtags: - nullabbrlink: 2e8656b4date: 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) continue; ...
回文自动机PAM
title: 回文自动机PAMcategories: - ICPCtags: - nullabbrlink: e5a7c7ecdate: 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; struct...
离散化
title: 离散化categories: - ICPCtags: - nullabbrlink: 515818b4date: 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: - ICPCtags: - nullabbrlink: 9e993aa5date: 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 <=max_log;...
第 132 场周赛——质数小结论，并查集配Floyd
title: 第 132 场周赛——质数小结论，并查集配Floydcategories: - ICPCtags: - nullabbrlink: b614dbf4date: 2024-08-01 00:00:00https://www.acwing.com/activity/content/competition/problem_list/3648/ B题收获：1.利用题目告诉的结论：1e9范围质数之差小于3002.一个数不被2-a的任何数整除 等价于他的最小质因子需要大于a c题：初步宏观思路：不难想到用并查集维护类别，只需将每一个类缩成一个点，由于最多只有500个类别，跑一个floyd就可以了部分细节处理：我的思路是类别用并查集维护，开了一个哈希表去存每个类别对应的根节点是最终floyd的第几个点，in...
5157
title: 5157categories: - ICPCtags: - nullabbrlink: d9943f91date: 2024-07-25 00:00:00https://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: - ICPCtags: - nullabbrlink: edd265aadate: 2024-07-18 00:00:00Codeforces Round 923 (Div. 3)F：给定一张一般图，不保证连通，定义一个简单环的权值是环中最小边的权值，求图中最小环的权值和具体由哪些点组成。 Sol：首先需要思考的是怎么求出最大权值？我们考虑用克鲁斯卡尔算法的思想对边权排序，考虑逐步加入图中，一旦合并失败就说明当前边构成了这个环的最小边，我们维护答案，同时记录左右端点。第二阶段我们需要利用最小边的两个点把目标环的所有点找出来。我们用标记数组保证点不走回头路，用flag保证函数递归栈退出，不再执行循环。从L开始dfs，遇到R的时候就统计答案。 实现的地方还有一个困难就是对于不在环上的点可能需要加入再删除，这样比较啰嗦，提供一种jly用bool返回值的写法。当更深的递归函数返回结果时，当前的点才加入path中 //为了给小的边机会，我们当然应该将边权从大到小加进图中 struct...
牛客小白月赛86
title: 牛客小白月赛86categories: - ICPCtags: - nullabbrlink: 9be380b5date: 2024-07-17 00:00:00B 水平考试====== 等价于两个集合 $S, T$ 判断 $S$ 中是否存在 $T$ 中所不包含的元素。 若存在则输出 0； 否则输出 10。 时间复杂度：$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...
IEEE备战
title: IEEE备战categories: - ICPCtags: - nullabbrlink: 712f0cc1date: 2024-07-14 00:00:00IEEE评测题解链接10.0以前提交链接：IEEE ENSIAS Student Branch (github.com) 11.0-17.0评测：https://csacademy.com/ieeextreme-practice/task/ IEEEXtreme 10.0 极限编程大赛题解 - meelo - 博客园 https://www.cnblogs.com/meelo/p/6059749.html 13.0 https://www.cnblogs.com/izcat/p/11707465.html 代码参考：https://github.com/ducthienbui97/IEEExtreme13...