原来的做题记录

::::info[The Pilots Brothers' refrigerator]

标签： 位运算

我们发现对于同一个点进行两次反转操作相当于什么都没做

所以我们直接枚举每一个点反转还是不反转，然后直接模拟即可。

::::

::::info[P6599 「EZEC-2」异或]

标签： 位运算

由于每一个二进制位独立，考虑分开处理

对于一个二进制位，如果有x个0和y个1，则此位贡献的答案为：ans = x * y

因为 x + y = l

所以 x * y <= (x+y) * (x+y) / 4，即 x = y = l / 2 ::::

::::info[P6225 [eJOI 2019] 异或橙子]

标签： 位运算

由于异或具有交换律，所以当 l=2,r=4 时 

1
2
ans = a2^a3^a4^a2^a3^a3^a4^a2^a3^a4
    = a2^a4
我们能够发现:

  • 当 l,r 奇偶性不同， ans=0
  • 否则，取每隔一个异或。

所以直接用 树状数组 维护 ::::

::::info[P9915 「RiOI-03」3-2]

标签： 位运算

首先我们发现其中有一个重要的性质：

\[ 0\le x\lt \min(2^n, 10^{18}) \]

所以我们其实只需要特判一下 左上角那一片0:

1
2
3
4
5
6
0 0 0
1 0 0
· 1 0
1 1 0
· · 1
· · ·
其他的联通块绝对走不出: $$ (x,y) ~~ x \in [0,2^{63}],y \in [0,63] $$ 这些点，所以我们可以直接暴力到当前连通块的最右端，然后直接计算。

这里有一个函数可以计算一个点是 0 还是 1. 

1
2
3
4
5
bool ask(int x,int y){//查询 (x,y) 为 1 为 0
    int z=(1ll<<(y+1));
    if(x%z < z/2) return 0;
    else return 1;
}
::::

::::info[P4310 绝世好题]

标签： DP动态规划

我们定义 f[i] 为当连续字串最后一个第 i 位的值为1时的最大长度。

所以对于一个x=a[i]

$$ f_j=\max_{{x的第u位为1}} f_u+1 ~~~{(x的第j位为1)} $$ ::::

::::info[P1381 单词背诵]

标签： hash,双指针

我们只需要进行一下 hash 然后直接一个双指针。

但是要特判一下 ans = 0,0。

::::

::::info[P4688 [Ynoi Easy Round 2016] 掉进兔子洞]

标签： bitset

我们发现其实 ans = len1+len2+len3-3*(相同元素个数).

我们可以将每一个区间的值按下标存储到 bitset 中，然后直接进行 & 操作，即可得到其相同元素个数。

然后问题就解决了？

我们注意到按照下标存储处理的一定是 不可重集合，而这一道题要求可重，所以我们需要先对其进行离散化

如对于全集为 {1,1,2,3,3}，处理区间集合为 {1,2,3,3}

存储的 bitset 为：

1
2
3
全集： 00000000000111110
集合： 00000000000111010
        n   <-----    0

这个样子才能解决。

然后问题就解决了？

我们发现如果每一次都重新把每一个区间存入其中，与暴力没什么两样，但是我们发现每一个区间之间有很大的重叠，所以考虑与莫队结合，这样就可以以大概为 \(\mathcal O(N\sqrt{N})\) 的时间处理每一次把对应区间元素插入集合。 但是还有一点需要注意：

虽然说 bitset 的空间复杂度比较小，但是因为是离线，我们要求把每一次询问产生的 bitset 记录下来，一遍统计答案，所以 \(\mathcal O(\frac{N^2}{w})\) 会炸，需要将其分为多个部分（每一个处理 2e4 次询问）。

::::

::::info[CF126B Password - 洛谷]

标签： KMP

首先题目需要找的是一个字串满足即使前缀，又是后缀，还在中间出现。

满足即使前缀，又是后缀及其 公共先后缀，可以使用 while(j) j=nxt[j]，遍历所有。

但是如果考虑在中间也出现过，其实就是一个前缀的 公共前后缀，所以直接使用一个桶存储，就可以解决这个问题 ::::

::::info[P1470 [IOI 1996 / USACO2.3] 最长前缀 Longest Prefix - 洛谷]

标签： KMP

这里我们定义 f[i] 为长度为 i 的前缀是否能够被拼出

可以推出递推式: f[i]|=f[i-s[i].size] ,（s[i].size 表示第 i 个字符串的长度）。

这里有一个条件，就是这个时候的后缀必须与 s[i] 完全匹配。

所以直接使用 KMP 就可以了，用 hash 的效果一样。 ::::

::::info[P4696 [CEOI 2011] Matching - 洛谷]

标签： KMP

重点依然是如何重定义两个字符是相同的。

首先我们需要确定为什么能够使用 KMP 。

这里十分重要！！！

KMP 的一个利用特性在于字符串的连等： S1=S2 , S2=S3 => S1=S3 。

这道题目显然满足，我们可以把题目中的第一个序列 a[] 转换为 b[] ，即以值为下标，存储数值为位置。

例如序列 2 1 5 3 4 变成 2 1 4 5 3 。

这个样子就可以把两个序列相等的条件转化为两个序列经过离散化之后相同，比如 4 2 ==> 2 1 与 2 1 相同。

这个时候显然有连等性。

然后考虑如何定义相等：

  • 思路一： 我们发现只要两个序列中当前比较字符的比他小的元素的个数相等，那么一定相同，于是出现了题解中有一篇使用树状数组的解法。
  • 优化： 我们可以变为比较其前驱和后记，记录一下其中一个字符串每一个字符相对其前驱和后继的距离，然后再另一个字符传中是否也满足前驱后继（直接比较大小）。

但是这里也有一个需要注意的，我们记录的前驱和后继必须是在当前比较区间中的（下面那一道题一样）。

因为当前比较的字符一定是目前区间的最后一个，所以只需要保证前驱和后继都在当前字符之前，所以直接搞一个链表，然后从后往前便利，把一个字符处理完了之后就把他在链表中删去（把前后连在一起）。 ::::

::::info[P5256 [JSOI2013] 编程作业 - 洛谷]

标签： KMP

如果把‘相同’当作完全相同，则这就是一个 KMP 板子，所以我们主要是要知道如何判断两个字符是 相同的。

我们定义两个数组 s，t，表示当前字符对应的最近的上一个字符的距离，如 abcab 为 00033,（这里仅是示例），我们可以观察到如果两个字符串是‘相同的’，则它们按这个规则组成的数组也一定相等 \(\color {white} 吗\)。

有一种特殊情况，比如 ababb 和 cdd。这时两个分别为 00221 和 001, 所以需要特判是否在比较范围内，及 KMP 时的 j. ::::

::::info[P5304 [GXOI/GZOI2019] 旅行者]

标签： 二进制分组：

对于这种求两两点都要计算的问题（求得是最小值，因而可以重复计算）。

我们可以拆分成多个 A，B 两个点集的之间的关联。

我们按照二进制的每一位 \(0/1\) 区分 A B，因为两个不同的点至少有一位二进制不同。

这样假设处理两个集合之间子问题时间复杂度为 \(\mathcal O(f(N))\) 那么总体时间复杂度为 \(\mathcal O(\log N * f(N))\)。

::::

::::info[P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus]

标签： 图论，最短路

这里主要是一个优化：

优化：

这里要求不经过那一条边的最短路

可以预处理出没有该条件的普通最短路组成的树：

  • 如果去除的这一条边不是树边，那么直接返回预处理的值
  • 否则重新计算

这样因为树边只有 \(N-1\) 条，所以最多跑 \(N\) 次最短路。

::::

::::info[P2371 [国家集训队] 墨墨的等式]

标签： 同余不等式

首先我们能够想出一个暴力建图的做法。

我们连接每一个 \((i,i+a_j)\) 然后求解从 \(0\) 出发的连通性，但是很明显这样要有 \(1e12\) 个点，不知道多少条边。

所以我们需要找到一种办法减少图的规模。

我们令 \(a_{min}\) 为 \(a_i\) 中最小的一个；

我们把所有目标是 \(x\) 满足 \(x \equiv y \mod a_{min}\) 放在一起计算，假设此时通过凑 \(a_i\) 能凑出 \(sum \equiv y \mod a_{min}\) 的 \(sum\) 为 \(dis_y\) ，那么这一组的 \(ans = \lfloor{\frac{x-dis_y}{y}}\rfloor+1\) 所以需要让 \(dis_y\) 最小。

所以连接边 \((i,(i+a_j)\mod a_{min})\) 求解最短路。

::::

::::info[P7515 [省选联考 2021 A 卷] 矩阵游戏]

标签： 图论，差分约束

这里如果没有 (\(0 \le a_i \le 10^6\)) 是十分简单的。

我们规定最后一列一行都为0，就可以依次推出所有 \(a\) 的值，但是不满足题目要求。

所以我们可以选择调整。

基础做法是对于 每一列 每一行 ，奇数增，偶数减。

吧每一行每一列增减个数作为未知量进行差分约束

但是这样 有破绽 ，就是有可能会出现 \(0 \le a_{i,j}+L_{i}+R_j \le 10^6\) 或 \(0 \le a_{i,j}-L_{i}-R_j \le 10^6\)，差分约束无法解决。

我们其实只需要改变调整的方法，变成：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
L:

+ - + - + -
- + - + - +
+ - + - + -
- + - + - +
+ - + - + -

R:

- + - + - +
+ - + - + -
- + - + - +
+ - + - + -
- + - + - +

这样就不会出现了.

::::

::::info[P2045 方格取数加强版]

对于每一个格子，分成一个入点和一个出点。

在之间连边：

  • 流量 \(1\) ，费用 \(a_{i,j}\)。
  • 流量 \(k-1\) ， 费用 \(0\) 。

格子之间连边：

  • 流量 \(k\) ，费用 \(0\)

然后从 \((1,1)\) 的入点 到 \((n,n)\)的出点 跑最大费用流。

::::

::::info[P3358 最长k可重区间集问题]

对于每一个点 \(i\) ，连接 \(i+1\) 流量 \(k\) ,费用 \(0\) 表示最多每一个点被覆盖 \(k\) 次。

然后对于每一条线段，链接 \((l,r)\) ，流量 \(1\) ，费用 \(len\) ，表示每一条线段只能被走一次，计算一次贡献。

然后跑最大费用。 ::::

::::info[P4249 [WC2007] 剪刀石头布]

标签： 网络流，费用流

首先我们可以考虑 正难则反 ，计算没有三个点不组成三元组的个数。

我们能发现此时有一个点入度为 \(2\) , 一个点入度出度都为 \(1\) ，一个点出度为 \(2\)。

所以对于一个点 \(x\) ，如果他入度为 \(du_x\) ，那么会产生 \(C_{du_x}^2\) 对三元组不满足成环。

所以 \(ans=C_n^3-\sum C_{du_x}^2 = C_n^3-\sum \frac{du_x*(du_x-1)}{2}=C_n^3-\sum{\frac{du_x^2}{2}} + \sum \frac{du_x}{2}\)。

而 \(\sum du_x = \frac{n*(n-1)}{2}\) ， 于是我们需要最小化 \(\sum {\frac{du_x^2}{2}}\) 。

由于对于一串 \(x^2\) ： \(1,4,9,16,25···\) 差分后为 \(1,3,5,7,9···\)，所以我们对于一个点 \(x\) ，拆成两个点，一个入，一个处，然后入点出点之间连接多条边，容量都为 \(1\) ，费用为 \(1,3,5,7,···\) 。

因为如果流这个点，就一定会先走小的边，所以总费用就按照 \(1,4,9,16,25···\) 累加。

然后对于每一个边，建一个点，连接他对应的两个顶点，并从 \(s\) 连接一个容量为 \(1\) 的边，表示这个边最多选择一个方向。

最终的图类似如下：

然后跑 \(\texttt{Dinic}\) ，输出方案。 ::::

::::info[善意的投票 / [JLOI2010] 冠军调查]

标签： 网络流，最小割

最小割解决的问题就是需要分配多个东西到两个集合，使得代价最小。

这道题睡不睡午觉就是两个选择，如果一个节点（表示一个人），连接了 \(S\) 说明他选择不睡，如果一个节点最后保持 \(T\) 说明他选择睡

所以我们连两种边。

  • 对于违背自己意愿： 如果本来要睡，连接 \(T\) ，容量为 \(1\) ，不睡同理。
  • 对于违背朋友意愿： 连接自己和朋友，容量为 \(1\)。

然后求最小割。

::::

::::info[P4313 文理分科]

标签： 网络流，最小割

和上一道题基本相似，主要是处理同时选择三个人。

我们可以把那三个人连接到一个虚拟点上，在有那个点链接到 \(S\) 或 \(T\)

一个小技巧，如果把一条边设为 \(\inf\) ，那么代表一定不能割这一条边。最开始我陷入的思维误区就是既然一定不能割这一条边，那么被连接的三个点补救一定会在一边了嘛？

这个主要是边是单向边，然后最小割是割边直到 \(S\) 不能到 \(T\) ，所以我们有两个选择：

  1. 割掉 虚拟点 到 源汇点 的路径，代表不然这三个点在一遍，此时就算不割掉 \(\inf\) 的边，通过这条路也无法到达 \(T\)
  2. 割掉 源汇点 到这三个点的边，代表三个点在一边。

::::

::::info[P3227 [HNOI2013] 切糕]

标签： 网络流，最小割

同样的道理，边的长度为 \(\inf\) 代表必须选择在同一边，这里分配长方体每一个点的两个选择为是否切下来，代价为不和谐值。 ::::

::::info[P3749 [六省联考 2017] 寿司餐厅]

标签： 网络流，最大全闭合子图

最大全闭合子图

基础模板问题是有 \(n\) 个选择，每一个选择有一个贡献（可能为负），然后但是如果选择计算了一个贡献,就必须得要计算其他一些提前设定好的贡献，每一个贡献只能记算一次

首先建图，对于依赖进行连边，依然是进行最小割。

但是我们发现不太好处理容量为负的最小割，所以对于点权为负的节点我们先默认不其计算贡献，然后连接到 \(T\) ，如果割掉代表选择该节点。

然后边权为正就连接 \(S\) ，如果割掉就代表不选择该节点

有了这个模板这个题也就是一个模板了。

::::

::::info[P4843 清理雪道]

标签： 网络流,上下界网络流

首先对于每一条边，必须被走一次，所以设定每一条边为下界 \(1\) ，上界为 \(\inf\) 。

而对于每一个点 - 从 \(S\) 连过去，下界 \(0\) ， 上界 \(\inf\) ， 表示一条路径从这里出发。 - 连接到 \(T\)，下界 \(0\) ， 上界 \(\inf\) ， 表示一条路径在这里结束。

然后跑上下界最短路 ::::

::::info[CF708D Incorrect Flow]

标签： 网络流，上下界网络流

题目概述： 对于一个流量不平衡的一个网络流调整流量和容量，使其满足网络流要求，不一定是最大流。

首先分成两种情况：

1. \(f(e)\le g(e)\)

  • 流量减少，从而调整流量平衡，这个操作最多进行 \(f(e)\) 次。
  • 流量增加，从而调整流量平衡，这个操作最多进行 \(g(e)-f(e)\) 。
  • 流量和容量同时增加，能做无限次。
  • （容量一定不会减少，费用自己应该都知道）

2. \(f(e) > g(e)\)

首先能够确定，要么加 \(g(e)\) ，要么减少 \(f(e)\) ，一定会先操作 \(f(e)-g(e)\) 次使得流量小于等于容量。

  • 流量减少，这个操作可以进行 \(f(e)-g(e)\) 次，费用为 \(0\)。
  • 流量继续减少，这个操作进行 \(g(e)\) 次，费用为 \(1\)。
  • 流量和容量继续增加，这个操作进行无限次，费用为 \(2\)
  • （这里如果流量增加，那么容量也一定会继续增加）

然后就是一个问题，如何确保最后流量守恒，直接连一条上下界都为 \(f(e)\) 的边，相当于固定流量。

然后就直接跑上下界最小费用流：

:::info[上下界最小费用流:]

  1. 加边是记录每一个点流量不匹配的值，du[a]-=c,du[b]+=c;。
  2. 对于流量不匹配的点连接超级源点。
  3. 连接 \(t\) 到 \(s\) 流量为 \(\inf\) 。
  4. 从超级源汇点跑 \(\texttt{Dinic}\)。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace UDFLOW{
    //有源汇上下界最小费用可行流

    ll sum;

    int du[N];
    void add(int a,int b,int c,int d,int w){
        FLOW::add(a,b,d-c,w);
        du[a]-=c,du[b]+=c;
        sum+=1ll*c*w;
    }

    ll solve(int n,int s,int t){
        int ss=n+1,tt=n+2;
        for(int i=0;i<=n;i++){
            if(du[i]>0) FLOW::add(ss,i,du[i],0);
            if(du[i]<0) FLOW::add(i,tt,-du[i],0);
        }

        FLOW::add(t,s,inf,0);

        FLOW::Dinic(n+2,ss,tt);
        return sum+FLOW::cost;
    }
}

:::

::::

::::info[P4251 [SCOI2015] 小凸玩矩阵]

标签： 网络流，二分图

每一行每一列选一个，一看就像是二分图。

所以左部为 \(i\) ，右部为 \(j\) 。

然后显然答案具有单调性，所以把所有 \(A_{i,j} \le mid\) 的点加入二分图中 \((i,j)\) ，然后看一下最大匹配是否大于 \(n-k+1\) 。

::::

::::info[P2764 最小路径覆盖问题]

标签： 网络流，二分图

其实就是每一个节点需要最多选择一个节点接下去，此时这两个点就在一个路径上了。

所以把每一个点拆分成一个入点和一个出点，然后连边时从入点连到出点，然后跑二分图。

最后每一个左端点选择的右端点就在同一个路径上。

::::

::::info[P4055 [JSOI2009] 游戏]

标签： 二分图，网络流

一道图博弈的模板题：

:::info[图博弈]{open}

对于一个 DAG (有向无环图) ，最开始一个棋子放在 \(x\)。

每一个人一次移动一次通过一条边。

当一个人无法走动是他就输了。

:::

结论：

如果这个点 \(x\) 是最大匹配的闭经点，那么先手必胜。

否则先手必败

证明:

首先一个 DAG 一定是一个二分图。

然后进行一次二分图最大匹配（任意方案）

然后如果 \(x\) 是最大匹配的闭经点，那么他一定在一对匹配边上，因此一定可以移动到另一个成对的点上。

这样子他们走的路一定是一条 增广路 ，但是如果后手走到了一个未匹配的点上，那先手不久输了吗？

但是此时我们可以通过饭庄 增光路 上的匹配信息从而把这个点变成匹配点，起点不是匹配点，此时不满足 \(x\) 是最大匹配的闭经点 。

因此如果先手必败：

  • 对于当前情况， \(x\) 为未匹配点。
  • 能够从一个未匹配点通过一条 增广路 到达 \(x\)。

实现：

对于这道题，需要验证多个点是否为必胜点。

所以可以从每一个为匹配点跑 dfs 跑增广路，走到的点打上标记。

::::

::::info[P4298 [CTSC2008] 祭祀]

标签： 二分图，最长反链

最长反链

对于一个 DAG ，寻找一组点，满足这组点互相无法到达，且点数最多

定理： 最长反链 长度为 可重最少路径覆盖 的路径数。

这个证明我只会感性证明：

证明：

先证 \(A\) 的确是一个反链：这是容易的，因为任取 \(x \in A\)，\(x_{in}\) 就一定是被 DFS 到的点，而 \(x_{out}\) 一定是没被 DFS 到的点，任何两个 \(x, y \in A\) 之间若是有连边就和 DFS 的过程冲突了。

首先有 \(|I| = 2n - |S| = 2n - m\)，而 \(|I| - |A|\) 可以看作是满足「\(x_{out}\) 或 \(x_{in}\) 属于 \(I\)」的 \(x\) 的个数，显然这样的 \(x\) 不会超过 \(n\) 个，所以 \(|I| - |A| \le n\)，所以 \(|A| \ge |I| - n = n - m\)。

但是 \(A\) 再大，也不能大过 \(n - m\)，所以 \(|A| = n - m\)，也就是一个最长反链。

by 小粉兔

但是对于构造一组方案怎么办。

  1. 首先可以排除选 链头/链尾， 自行构造
  2. 既然是选择中间的点，这个就很难办了

但是我们可以先解决下一问，即那些点可以被选，

我们只需要把当前枚举到的点的上下游都删除，然后在跑一次，如果 \(ans' = ans-1\) 那么说明这个点可以选。

此时我们已经知道拿一些点能够选了。

所以我们只需要一次选择那些可以选且不在已选点上下游的点，然后就可以得到一组构造。

::::

::::info[ARC106E Medals]

标签： 二分图，Hool定理

首先 \(nk\le ans \le 2nk\)

然后明显外面是一个二分答案，现在假设当前正在执行 check(x) ， \(x\) 表示需要 \(x\) 天。

然后建出二分图，即左边每个人有 \(k\) 个点（表示每一个奖牌），右边有 \(x\) 个点（表示每一天），然后每一个左部点连到所有他工作的时间，然后如果存在完美匹配，就返回 \(1\) 。

但是很明显会 TLE 。

首先我们发现对于一个点分裂的 \(k\) 个点，他们连的边一定是相同的，所以未了让 \(|S|\) 尽量大，所以可以在枚举左侧端点子集时直接选择它的所有 \(k\) 个点，因而假设现在枚举子集只需要枚举 \(n\) 个人 选or不选 ,此时左侧节点个数为 \(|S| = mk\) （\(m\) 为选人的数量）。

但是对于右侧节点，我们假设 \(d_i\) 为第 \(i\) 天上班人的集合，所以我们需要找到的是 \(|S|\) 和 \(d_i\) 有交的结点个数。

有交不是很好求，但是我们可以转化为 总结点 - 不相交的节点 ，而不相交的节点相当于 \(|S|\) 的补集的子集。

对于求解一个 \(s_i\) 为有多少天工作人集合为 \(i\) 的子集，这个就好求多了。

::::

::::info[P5811 [IOI 2019] 景点划分]

标签： DFS树

首先通过贪心策略，如果 \(a \le b \le c\)，那么选择 \(a\) 和 \(b\) 使他们联通一定是最优的，我们顺带还能得出结论 \(a \le \frac{n}{3}, b \le \frac{n}{2}\) 。

对于图为树的情况

这个问题其实等价于找到一条边，是的这条边左右两边的大小一个大于 \(a\) ，一个大于 \(b\) 。

假设当前一边为 \(x\) ，那么另一边为 \(n-x\) 。即 $n-x \ge b , x \ge a $ ，所以 \(a \le x \le n-b\) 。
有或者前一边为 \(n-x\) ， 那么另一边为 \(x\)。即 \(x \ge b , n-x \ge a\) ， 所以 \(n-b \le x \le a\) 。

将上面两个合并， \(x \in [a,n-a]\) 。于是，我们就相出了树的解法： 计算每一颗子树大小，然后看看有没有子树满足要求。

但是对于图呢？

我们发现如果原图为 \(\texttt{True}\) 一定存在该图的一种生成树满足求出一种解 。

所以我们考虑先随便选一颗生成树（比如 DFS树），然后进行调整。

但是如何调整呢？？

首先我们寻找是否有子树大小在 \([a,n-a]\) 之间的，如果有，直接输出构造方案。

如果没有，那么找到深度最大的一个点 \(x\) 满足其子树大小大于 \(\frac{2n}{3}\) ，现在我们需要想一些办法把他的子树大小减小到 \([a,n-a]\) （此时只能减小这个子树大小，因为其他子树大小总和加起来也最多只有 \(\frac{n}{3}\)）。

如果这颗子树是孤立的（相当于没有返祖边），那么一定无法调整，直接为 \(\texttt{False}\) 。

如果存在返祖边，就可以连接返祖边为树边，是的这颗大子树的子树大小减去返祖边引导的子树大小，可以发现此时一定有解。

证明：

返祖边引导的子树大小满足 \(siz \in [1,\frac{n}{3}]\) ，而大子树满足 \(siz \in [\frac{n}{3},\frac{2n}{3}]\) ，因此固然不可能直接减到 \([1,\frac{n}{3}]\) 。

因为 $[\frac{n}{3},\frac{2n}{3}] \subset [a,n-a] $ ，所以一定能够构造出解。

至于解法，就是不停的找到返祖边，然后删掉他的子树。

代码实现过于困难

::::

:::align{center} __EOF__ :::