爱飞鱼的blog

c题jls的代码，拿过来仔细研究了一番，终于弄明白了。 https://codeforces.com/contest/1859/problem/C jls代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include <bits/stdc++.h>using i64 = long long;struct DSU { std::vector<int> f, siz; DSU() {} DSU(int n) { init(n); } void init(int n) { f.resize(n); ...

hh的项链：不带修改维护区间种类数 https://www.luogu.com.cn/problem/P1972#submit 山东理工大学系列赛 https://acm.sdut.edu.cn/onlinejudge3/contests/4125/problems/D Description 给定一个长度为 nnn 的序列 aaa 和 mmm 次询问，对于第 iii 次询问给定两个正整数 [l,r][l, r][l,r]，判断 al∼ara_l \sim a_ral​∼ar​ 是否为合法序列。 定义：若区间 [l,r][l, r][l,r] 中存在一个数 aia_iai​ (l≤i≤r)(l \le i \le r)(l≤i≤r) 出现在 [1,l−1][1, l - 1][1,l−1] 或 [r+1,n][r + 1, n][r+1,n] 中则为不合法序列。 Input 输入的第一行包含两个正整数 n,mn, mn,m (1≤n,m≤105)(1 \le n, m \le 10 ^ 5)(1≤n,m≤105) 输入的第二行包含 nnn 个数 a1,a2,⋯ ,ana_1,...

stl的妙用 关于mutiset的应用的几个题 G - Minimum Xor Pair Query 题意：你可以进行以下操作 加入一个数 删除一个数 输出任意两个数异或最小值 思路：首先我们要知道一个性质(重要!)：两个数差值越小，异或值也越小。 那么我们要求异或最小值，那么答案一定在排序后相邻两个数中产生。 为了便于写，防止在set里面找不到的情况出现，我们手动插入下界和上界。 考虑我们的操作： 对于加入一个数，我们的答案有什么影响呢？ 假设我们插入的值是x。 假设我们的情况是：l x r 首先如果l和r都存在，那么显然此时l和r的异或值不可能成为答案，我们把它删去 然后在答案里面加入x^l和 x^r(前提是l，r存在) 12345678910111213void add(ll x){ s.insert(x); multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x); it1--, it2++; if(*it1 != -1 && *it2 != up) ...

SDUT 校赛题目 Description 给定正整数 nnn，计算 nnn 个元素的集合 {1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n}，所有非空子集和的乘积取模 998 244 353998 \, 244 \, 353998244353 后的结果。 Input 一个正整数 nnn (1≤n≤200)(1\le n\le200)(1≤n≤200)，代表集合大小。 例如 333 个元素的集合有 777 个非空子集，分别为...

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]步到达终点。这种状态的转移是刷表法 还可以拓扑排序，直接很数学地倒着算一遍。（待完成 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667// Problem: 绿豆蛙的归宿//...

https://codeforces.com/contest/1950/problem/G 在非连通图上找到一条包含点最多的路径，dp数组维护可达性 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293// Problem: G. Shuffling Songs// Contest: Codeforces - Codeforces Round 937 (Div. 4)// URL: https://codeforces.com/contest/1950/problem/G// Memory Limit: 256 MB// Time Limit: 3000 ms// // Powered by CP Editor (https://cpeditor.org)#include...

https://www.luogu.com.cn/problem/P5752 https://codeforces.com/contest/598/problem/E cf这个题考虑dp预处理，状态是三维的，转移是分割方案和所分块需要获得的巧克力数量。最后题目多次询问可以o（1）快速查询的 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273// Problem: E. Chocolate Bar// Contest: Codeforces - Educational Codeforces Round 1// URL: https://codeforces.com/contest/598/problem/E// Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor...

无限制最长连续的子序列和 题目链接 动态规划转移方程 1dp[i] = max(dp[i-1] + a[i], a[i]); 最终结果在 dp 数组中线性扫描找出最大值： 12int pos = max_element(dp + 1, dp + 1 + n) - dp;cout << dp[pos] << " "; dp[i] 表示以序列中第 i 个数字结尾的最大子段和。 转移方程分析： 如果选择第 i-1 个数，则由 dp[i-1] 转移而来。 如果不选择第 i-1 个数，则只能自己作为一个子段存在，因为必须以第 i 个数结尾。 优化：记录子段端点 在题目中，还需要给出具体是哪段子段和最大（即左端点和右端点）。 初始方法：先求出最大值，再排序所有符合最大值的子段，按题目要求取左端和右端尽可能小的子段。 优化方法：在线性扫描时维护最大值，同时更新左右端点。 有长度限制最长连续的子序列和 类型：单调队列优化 DP 题目描述 给定一个长度为 n 的序列 a，找出其中元素总和最大且长度不超过 m...

最长上升子序列 我们讨论的是严格单调递增的LIS，然后考虑基本状态dp[i]dp[i]dp[i]表示以i结尾的LIS长度。状态转移是dpi=max⁡j<i,aj<aidpj+1dp_i=\max\limits_{j<i, a_j<a_i} dp_j+1dpi​=j<i,aj​<ai​max​dpj​+1 朴素O(n2)O(n^2)O(n2) 12345678910111213141516void solve() { int n; cin >> n; vector<int> dp(n + 1); vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = 1; j <= i - 1; j++) { ...

给出一组包含 mmm 个不等式，有 nnn 个未知数的形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​xc1​​−xc1′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​ 的不等式组，求任意一组满足这个不等式组的解。 输入格式 第一行为两个正整数 n,mn,mn,m，代表未知数的数量和不等式的数量。 接下来 mmm 行，每行包含三个整数 c,c′,yc,c',yc,c′,y，代表一个不等式 xc−xc′≤yx_c-x_{c'}\leq yxc​−xc′​≤y。 数据范围 对于 100%100\%100% 的数据，1≤n,m≤5×1031\leq n,m \leq 5\times...