BzhH

1. 基本概念 1.1 流网络，不考虑反向边 1.2 可行流，不考虑反向边 1.2.1 两个条件：容量限制、流量守恒 1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量 1.2.3 最大流是指最大可行流 1.3 残留网络，考虑反向边，残留网络的可行流f' + 原图的可行流f = 原题的另一个可行流 (1) |f' + f| = |f'| + |f| (2) |f'| 可能是负数 1.4 增广路径 1.5 割 1.5.1 割的定义 1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。 1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T) 1.5.4 对于任意可行流f，任意割[S, T]，|f| = f(S, T) 1.5.5 对于任意可行流f，任意割[S, T]，|f| <= c(S, T) 1.5.6 最大流最小 ...

这道题和P4008 【[NOI2003] 文本编辑器】其实是差不多的,只是tm的有一些坑 比如样例 10Insert 13Balanced eertMove 2Delete 5NextInsert 7editorMove 0GetMove 11Rotate 4Get 其实是 editor\n 还有输出字符的时候可能是\n,这时就不需要再输出换行符 真的有毒这道题

一道简单的数据结构题,直接用splay做即可 对于每一个操作 Move:直接修改光标位置 Insert:将光标所指的位置旋到根,再将它的后继旋到它下面,直接将序列插入为它的左儿子 Dlete:将光标所指的位置旋到根,再将光标加n所指的位置旋到它下面,并将它的左儿子直接赋值为0 Get:将光标所指的位置旋到根,再将光标加n所指的位置旋到它下面,输出它的左儿子 Prev:光标位置减1 Next:光标位置加1 代码 #include<iostream>#include<cstdio>using namespace std;const int N = 2e6 + 50005;struct tree{ int s[2], v, p, siz; void init(int _v, int _p) { s[0] = s[1] = 0; v = _v, p = _p, siz = 1; }//初始化} tr[N];int root, nodes[N], tot, poi;//nodes用 ...

P3165 [CQOI2014]排序机械臂 一道Splay模板题,只不过需要注意一些细节 直接上代码 #include<iostream>#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int N = 1e5 + 5, INF = 0x3f3f3f3f;typedef pair<int, int> PII;struct tree{ int s[2], v, p, siz, lz; void init(int _v, int _p) { v = _v, p = _p, siz = 1; }} tr[N];int root, idx, hi[N];PII poi[N];bool cmp(PII a, PII b){ if (a.first == b.first) return a.second < b.second; ...

一道简单分块题，题目要求的是逆序对数量，那么对于每一次交换位置l,r(l≤r)l,r(l \le r)l,r(l≤r)的操作,我们只需要判断区间(L,R)(L,R)(L,R)中大于与小于两个端点的数字个数即可,可以考虑将每个块中进行排序再二分达到快速查询,时间复杂度为O(nnlog⁡n)O(n\sqrt{n}\log{n})O(nn​logn) 具体见代码 #include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N = 2e5 + 500;int len, num[N], block[N], gt[N], L[N], R[N];long long ans = 0;long long work(int x, int k){ int l = L[k], r = R[k], res = R[k] + 1; while (l <= r) { int m ...

P2596 [ZJOI2006]书架 一道简单的数据结构题 对于每一个操作 Top:将s转到根节点，并将s的左子树移给s的后继 Bottom:将s转到根节点，并将s的右子树移给s的前驱 Insert:与前驱/后继交换信息 Ask:询问s的前驱的排名 Query:询问排名为s的编号 用Splay实现 代码 #include<iostream>#include<cstdio>using namespace std;const int N = 1e5 + 5;struct tr{ int s[2], id, p, siz; void init(int _id, int _p) { id = _id, p = _p, siz = 1; }} tree[N];int root, idx, id[N], poi[N];void pushup(int p){ tree[p].siz = tree[tree[p].s[0]].siz + tree[tree[p].s[1]].siz + ...

Splay是一个功能强大的数据结构，可以实现一些平衡树无法完成的操作 例题P3391 【模板】文艺平衡树 和平衡树一样，Splay同样也有左旋右旋的操作。 并且Splay中还有一个核心操作，那就是将一个节点移到另一个节点下面，并保证整棵树的中序遍历不变。 那么很多操作就可以通过这两个函数得出 比如在x后面插入一段序列，那么只需要让x移到根节点，让x的后继y成为x的儿子，那么只需要将这个序列转化为树接到y的左儿子上即可。 下面是这两个函数 左旋右旋函数 void rotate(int x)//左右旋合并过后的函数,可自行画图理解{ int y = tree[x].p, z = tree[y].p; int k = tree[y].s[1] == x; tree[z].s[tree[z].s[1] == y] = x, tree[x].p = z; tree[y].s[k] = tree[x].s[k ^ 1], tree[tree[x].s[k ^ 1]].p = y; tree[x].s[k ^ 1] = y, tree[y].p = x; ...

这道题一眼看去好像不能用什么数据结构做出，所以就只有打分块暴力了，刚开始想的时候没有想到用前缀和，所以写出来的时间复杂度就达到了O(nnlog⁡n)O(n\sqrt{n}\log{n})O(nn​logn),交上去不仅T了还WA了。后面加上了前缀和时间复杂度就可以过了 思路 假设将整个序列分为T块，那么考虑预处理一个数组timi,jtim_{i,j}timi,j​表示前i个块中,字符j出现的次数,这样就可以快速求出每一段块中各数字出现的次数了,然后再预处理一个数组numi,jnum_{i,j}numi,j​表示第iii个块到第jjj个块中出现了正偶数次的数字的个数,那么对于查询的区间[L,R][L,R][L,R],分为两种情况 [L,R][L,R][L,R]在同一个块中,这种情况就直接暴力枚举每个数字即可 [L,R][L,R][L,R]不在同一个块中,考虑分为三段[L,r),[l,r],(r,R][L,r),[l,r],(r,R][L,r),[l,r],(r,R],其中[l,r]为完整的块,那么只需要在枚举的时候判断一下加上当前这个字符对答案是否有影响,详细解释见代码 #inclu ...

首先看到这到题，很容易想到AC自动机，但这个题它求的是方案，并且没有告诉我们母串，所以这个时候我就们可以尝试用搜索枚举每一种方案 部分代码 void dfs(int now, int j, bool flag)//now代表枚举了的文章长度，j代表AC自动机的下标，flag代表当前的文章是否合法{ if (now == m) { ans = (ans + flag) % MOD; return; } for (int i = 0; i < 26; i++) { int t = tr[j][i]; bool is = true; while (t) { if (cnt[t]) { dfs(now + 1, tr[j][i], true); is = false; break; ...

这到题一眼看去，似乎就是个AC自动机，然后迅速的打出了AC自动机的板子。 最开始思路 最开始我想的是，不就判断一下长度就行了吗，把每一个单词的长度求出来，在AC自动机的时候每次用当前位置的下标减去单词长度，如果小于等于目前的前缀长度，就更新答案，然后迅速地打出代码，发现只有70分，仔细思考了一下，发现是因为我没有读清题目，单词不能有重复，比如如果单词是she element 的话，那么shelement的前缀应该是3，照我这个思路的话算出来是9，所以这个思路还有一些问题。 正确的思路 刚才的思路其实大致方向是没有什么问题的，只需要在多考虑一种情况就是了，接下来该如何考虑这种情况，对于一个最长前缀，我们可以把它划分为许多种不同的单词组成的一个字符串，那么就会有很多种方案，我们只需要将每种方案记录一下即可，那么如何记录？考虑再开一个数组vis，表示是否存在长度为i的合法前缀， 那么这个问题就迎刃而解了。 具体结合代码理解 #include<iostream>#include<queue>#include<cstdio>#include<cstrin ...