搜索结果
查询Tags标签： tot，共有 83条记录-
Jeffrey's ambition(Dinic板子题）
Jeffreys ambition(网络流板子题) 网路流的经典例题，会有两种需要匹配的东西，这两种东西直接可以构成一个二分图，这时候题目就会要求你求出最大匹配（水题） //要与这道Arrange the Bulls题目区分开来。两道题同样是找匹配，但是一个是问你匹配的可能总数，而且题目是一…
2022/8/29 6:23:48 人评论 次浏览 -
AcWing-4507. 子数组异或和
异或的一个性质：如果对一个数异或了两次就相当于不异或。 所以我们可以用前缀和预处理 \(a[i]\oplus =a[i-1]\) \(i\) 至 \(j\) 的异或和为 \(a[j]\oplus a[i-1]\) 该连续子数组的前一半元素的异或和等于其后一半元素的异或和。 即该连续子数组的异或和为 \(0\) 。 暴力的…
2022/8/13 23:28:40 人评论 次浏览 -
如何计算 LIS
LIS，即最长上升子序列 . 基于 DP 的做法 令 \(dp_i\) 表示以 \(i\) 结尾的 LIS 长度，则有 \[dp_i=1+\max_{\substack{j<i\cr a_j<a_i}}\{dp_j\} \]可以直接暴力转移，于是答案就是 \(\displaystyle\max_{i\in[1,n]}dp_i\) . 时间复杂度 \(O(n^2)\) . 优化方法（均…
2022/7/31 23:39:22 人评论 次浏览 -
LOJ #3534. 「NOI2021」庆典
提交记录 题目叙述 给定一个 \(n\) 个点 \(m\) 条边的有向图，满足如果 \(x\) 到 \(w\) 右边，并且 \(y\) 到 \(w\) 也有边，那么就一定有边 \(x\) 到 \(y\) 或者 \(y\) 到 \(x\) 。每次给出 \(k\) 条边 \(a_i\rightarrow b_i\) 表示这次询问新加入的边（不一定这样做之后…
2022/7/20 23:25:20 人评论 次浏览 -
【网络流】EK & Dinic 算法
这两天学习了网络流，故写点东西加深理解。 关于网络流定义证明之类，前人之述备矣，此处整理一些比较舒适的代码实现。 EK 全名是 Edmonds-Karp. 慢但是码量少一些，让人十分欢乐。 EK不需要两次搜索也不需要分层。 更欢乐的是能用EK过的数据范围都较小。这是因为算法的时…
2022/7/13 14:20:27 人评论 次浏览 -
浅谈hash
作者很蒻，在这里总结一下自己学一小点hash的经验。 hash可以用于查找，速度很快，可以近似看作为O(1)的时间复杂度，缺点是占用空间比较大，不过在竞赛中这种空间换时间的方式还是值得的。 哈希冲突是说不同的元素的关键字有可能相同，不能保证一个关键字与元素是一一对应…
2022/7/11 23:21:08 人评论 次浏览 -
「APIO2014」回文串
\(\text{Solution}\) 这是一道回文树模板题。 回文树 回文树是利用回文串的包含关系建的一个图。 首先回文树有奇根，偶根，偶根的\(fail\)指针指向奇根。 设\(fail_i\)表示标号为\(i\)的回文串失配后，他的最长后缀回文串的标号。 利用\(fail\)可以构造出回文树，考虑一个…
2022/7/5 23:23:10 人评论 次浏览 -
模拟专题
1095 Cars on Campus Link 配对要求是，如果一个车多次进入未出，取最后一个值；如果一个车多次out未进入，取第一个值。 注意：一个车可能出入校园好多次，停车的时间应该取之和 #include <iostream> #include <cstdio> #include <cstdlib> #include &…
2022/7/2 23:20:07 人评论 次浏览 -
luogu P2304 [NOI2015] 小园丁与老司机
题面传送门 非常码农的二合一题。 首先第一问看上去非常simple。因为只能往左，往右，和往上走(包括左上，上，右上)，往上走显然是没有后效性的。而往左和往右因为每一层最多1000个，所以直接枚举从上一层跑过来的地方转移即可，时间复杂度\(O(1000n)\) 然后第二问只要按…
2022/6/27 23:27:24 人评论 次浏览 -
【数据结构/分块/可持久化 Trie】AcWing 269. Fotile模拟赛L
块乐 分析 因为这题查询的是指定区间 \([l, r]\) 的最大异或子段，我们很难不想到使用可持久化 \(\texttt{trie}\) 来搞。 然而，对于每次查询，如果单纯地使用可持久化 \(\texttt{trie}\)，那么必须要枚举右端点进行查询，那么每次查询的复杂度是 \(O(n{\rm {log}} V)\)（…
2022/6/27 23:24:43 人评论 次浏览 -
golang重定向输入输出办法（算法竞赛向）
本来是想用golang，因为这是工作中的主要语言，不妨试一试打cf，结果写了一题就被劝退了，golang对于打算法竞赛极不友好 首先，golang在cf中，fmt的各种scanf和printf并不直接接收来自于标准输入输出流的内容，所以有些oj由于没有做对STD IO的支持，golang提交上去就报CE…
2022/6/8 1:21:30 人评论 次浏览 -
P3747 [六省联考 2017] 相逢是问候
Problem: 题目描述Informatik verbindet dich und mich. 信息将你我连结。B 君希望以维护一个长度为 \(n\) 的数组，这个数组的下标为从 \(1\) 到 \(n\) 的正整数。 一共有 \(m\) 个操作，可以分为两种：0 l r 表示将第 \(l\) 个到第 \(r\) 个数（ \(a_l,a_{l+1} ...a_r\)…
2022/6/3 23:23:19 人评论 次浏览 -
P4690 [Ynoi2016] 镜中的昆虫
P4690 [Ynoi2016] 镜中的昆虫 区间赋值区间数颜色，\(n \leq 10^5\)，值域 \([1,10^9]\)，要求线性空间。 sol 首先考虑经典数颜色套路，设 \(pre_i\) 表示上一个与 \(a_i\) 相同的数的位置。 对于区间赋值操作，我们发现性质：\(\forall i\in(l,r],pre_i ←i-1\)，对于 \…
2022/6/2 23:24:15 人评论 次浏览 -
手写堆（优先队列），手写hash
1 struct rec {2 int a, b; // 两个变量，其中a>=b3 int val, cnt; // 未来估价val，当前次数cnt4 rec() {}5 rec(int a_, int b_, int val_, int cnt_) {6 a = a_, b = b_, val = val_, cnt = cnt_;7 }8 };9 int n; 10 const int N = 100…
2022/4/18 6:15:12 人评论 次浏览 -
LOJ #6089. 小 Y 的背包计数问题
题面传送门 奇妙的思维(技巧?)题。 发现每个物品有\(i\)个，体积为\(i\)，对于\(i>\sqrt n\)的物品来说，这个个数的限制是相当于没有的。所以相当于完全背包。 前面\(O(\sqrt n)\)个可以暴力多重背包算方案数。 考虑后面\(n\)个最多选择\(O(\sqrt n)\)个。所以可以设…
2022/4/9 23:19:27 人评论 次浏览
