本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-10 18:17:11

P2756 飞行员配对方案问题

做法

将每个外籍飞行员向他对应的英国飞行员连一条流量限制为 $1$ 的有向边
然后设两个点 $s,t$，分别代表源点和汇点。
$s$ 对所有的外籍飞行员连流量限制为 $1$ 的边。
所有的英国飞行员都向 $t$ 连流量限制为 $1$ 的边。
然后跑最大流就行了

Code

还没写

P1251 餐巾计划问题

做法

最小费用流
因为最终流的大小肯定是固定的 $\sum_{i=1}^n r_i$，而且每天都可以购买最多 $r_i$ 餐巾纸，所以可以从源点向每一天连一条费用为 $0$，流限制为 $r_i$ 的边。

而考虑到快洗部，第 $i$ 天都可以将一些脏餐巾用 $f$ 的代价洗了之后送到第 $i+m$ 天，所以可以从第 $i$ 天向第 $i+m$ 天连一条费用为 $f$，流量限制为 $\infty$ 的边。

慢洗部同理。

对于延期送洗，从第 $i$ 天 向 第 $i+1$ 天连一条费用为 $0$，流量限制为 $\infty$ 的边。
最后，因为要统计结果，每天都要向汇点连一条费用为 $0$，流量限制为 $r_i$ 的边。
最后从源点出发跑最小费用流即可。

Code

没写

P2754 [CTSC1999]家园 / 星际转移问题

做法

数据范围小得离谱。

枚举时间作为答案。

枚举时间的时候的过程：

1. 上一个时间段的地球，月球，需要向这个时间段的地球连一条流量限制为 $\infty$ 的边作为时间的转移。
2. 同样的，上一个时间段的每个太空站也需要向这个时间段的太空连一条流量限制为 $\infty$ 的边作为时间的转移。
3. 对于太空船，将每个太空船上一个时间段所在的地方连向它下一个要去的地方，边的流量限制为 $h_i$。
4. 前三个步骤新建的边相当于构造了一张新的图，只不过每个点都与上一个时间段的图对应的点相连，为了保持一致还需要把之前图的点之间的边复制到这张新的图里。

Code

没写。

P2761 软件补丁问题

做法

这道题正解不是网络流。
可以发现，每个 bug 都只有修复好和未修复两种状态，可以看成 $1$ 和 $0$。而 bug 总数最多只有 $n (1 \le n \le 20)$ 个。

所以说可以状压。

可以将每个 bug 的状态压入一个数 $S$，S 的第 $i$ 位代表第 $i$ 的 bug 的修复状况。

这样 $S$ 就有 $2^n$ 种情况，可以看成 $2^n$ 个点。

初始状态（起点）是所有 bug 都未修复（$S$ 的每一位都是 $0$，$S =0$），最终状态（终点）是所有 $bug$ 都已经修复（$s$ 的每一位都是 $1$，$S = 2^n - 1$）

这些点之间的边，则是补丁。

每个点（状态），都可以通过任意一个当前点（状态)下可用的补丁走到另一个点（状态），代价则是这个补丁的耗时。

从起点跑最短路即可。

另外，由于边太多了，不能存储边。Dijkstra 的时候应当直接枚举每一个补丁行转移，而不是从当前点出发的边。

至于无解，如果起点无法到达终点，那么无解。

Code

没写

P2763 试题库问题

做法

每道题都可以对应很多个类型，而每个类型都共同对应了一套试卷，而题目要求每个类型都必须包含一定题目（数量题目给定）。

非常显然，就是最大匹配！。

对于这样的问题，当然是用匈牙利算法最大流来解决。

因为初始有 $n$ 道题目，从源点向每一道题连一条限制为 $1$ 的边。

因为每道题只能贡献一个类型，所以将每道题向其对应的每一个类型连一条流量限制为 $1$ 的边。

而每个类型都要向试卷贡献，设试卷为汇点，那么每个类型都向汇点连一条限制为 [该类型试题的需要量] 的边。

最后从源点出发跑最大流。

如果求得的最大流不是 $m$，那么说明无法给每个类型都分配足够的试题，无解。

如果有解，那么就要找每个类型所拥有的题目了。

因为网络流反向边的存在，可以从每个类型出发沿着反向边回到试题部分。

由于某道题匹配上了某个类型（就是说这道题到汇点的增广路径上有这种类型），那么它正向边限制就会变为 $0$，而反向边为 $1$（网络流的特性）

此时只要判断当前的反向边的限制是否为 $1$ 就行了，如果为 $1$ 说明这道试题属于当前类型。

另外要判断从类型节点出发的边是不是反向边，只要判断当前边的 $to$ 是试题节点就行了。

Code

没写。

P2764 最小路径覆盖问题

做法。

想一下，如果有 $n$ 个点，每个点之间都不连边，那么将会有 $n$ 条路径。

但是如果加上了一条边，那么路径数减一，将会有 $n-1$ 条路径。

也就是说，路径数等于总点数减去已经匹配到路径的点数（注：这里的点数不应该包括路径的起点）

此时问题转化成了最多有多少个点能匹配到路径里。

可以将每一个点 $i$ 拆成两个点 $a_i$ 和 $b_i$

由源点向每一个 $a_i$ 连一条流量限制为 $1$ 的边，代表可以从任一点出发。从每个 $b_i$ 向汇点连一条限制为 $1$ 的边，相当于将答案汇到了汇点。

另外对于题目给定的 $m$ 条边，假设 $i$ 和 $j$ 相连，那么从 $a_i$（代表起始） 向 $b_j$（$b_j$ 与汇点相连，用于统计答案） 连一条限制为 $1$ 的边。

解释：
这么连边就说明了从一个点出发顶多找到长度为 $2$ 的链，而真实的链肯定不会仅仅长度为 $2$，所以要从每个点出发才能找全。
另外由于每次都只会找到长度最多为 $2$ 的链（如果某个点不和其他任何点连通那么什么也找不到），这样最后产生的贡献最多为 $1$（就算这个点有好几个点相连，也只能和其中一个点形成链，因为和别的点再形成链答案也照样不变，画图可理解，再说了这些路径应该是顶点不相交的），所以源点到所有点连的边的限制只能是 $1$。
而每个点如果得到了流量那么说明这个点匹配上了，也仅仅说明这个点匹配上了，所以为了统计答案，每个点连向汇点的边的限制也只能是 $1$

至于路径输出，我的一个比较蠢的想法是爆搜记录每个点的后一个点，搜完了之后，对于每一个点暴力跳回最早的点输出。

Code

没写。

P2765 魔术球问题

做法

由于可以将相加起来是完全平方数的球放在一起，可以将将相加起来是完全平方数的球连边。

由于只能从最顶上放，而且是依次放编号为 $1,2,3,......$ 的球的，所以连边的时候应当从编号小的向编号大的连一条有向边。

$n$ 根柱子的存在，说明了要将这些球划分成 $n$ 份。也就是说将图划分成 $n$ 条路径。

问题转化为 $n$ 条路径最多能覆盖多少点。

解决这个问题，可以从小到大枚举每一个数，依次加进来。然后每次都一遍求当前状况下最少需要多少条边才能覆盖整张图(用上一道题的方法），记为 $cnt$，若 $cnt \ge n$ 那么退出，输出当前枚举到的数字减一。

关于输出每根柱子上的球编号：就是输出选中的 $n$ 条路径，从每个点顺着流满的边走。

Code

没写。

P2766 最长不下降子序列问题

做法

• 预先
  设以 $i$ 结尾的最长不下降子序列长度为 $f_i$
• 第一问
  暴力
• 第二问
  可以发现同一条不下降子序列之间的点是相互关联的，从前面的点走到后面的点 （这不废话吗）
  所以，按先后顺序，将前面的点与后面的点建边，因为一条路径上对答案的贡献最多是 $1$，所以边的流量限制为 $1$。
  另外，由于任意一点都可以作为一条不下降子序列的开头，所以从源点向这些点连一条限制为 $1$ 的边。
  另外，由于要汇集答案，而且只有长度为 $s$ 的不下降子序列才真正有贡献，所以从所有 $f_i = s$ 的点向汇点连一条限制为 $1$ 的边。
• 第三问
  因为在第二问中，每个元素只能使用一次，所以源点到它们的边限制只能是 $1$。但现在第 $1$ 个和第 $n$ 个元素可以多次使用，所以将源点和汇点与这两个元素的连边限制改为 $\infty$ 就行了

Code

还没写

P2770 航空路线问题

做法

虽然题目说先走到终点，然后再走回来，但是因为是无向图，所以可以认为题目实际上是找从起点出发的两条不同的到终点的路径。

这样起点和终点肯定都会经过 $2$ 次。

所以可以想到，可以设最大流为不同的路径数，费用则是经过的城市数，

所以应该跑最大费用最大流

因为起点和终点肯定都会经过 $2$ 次（从起点出发有两条路径到达终点），所以从源点向起点连一条费用为 $0$，限制为 $2$ 的边，从终点向汇点连一条费用为 $0$，限制为 $2$ 的边。

另外，对于普通的边，则是直接建一条费用为 $1$，限制也是 $1$ 的边。
注：刚才所说的 “点”，实际上应该是拆了之后的点。每个点都应该拆成一个入点 $x_i$ 和一个出点 $y_i$，设 $i$ 连向 $j$，那么应该是 $y_i$ 向 $x_j$ 连边。同时，为了把一个点拆成的两个点组合起来，应该让 $x_i$ 和 $y_i$ 之间连一条费用为 $0$，限制为 $1$ 的边（如果这个点是 $1$ 或 $n$，则限制应该是 $2$，因为要走两次）

对于解的判定，如果最大流小于 $2$，说明无法走到终点或者走到终点之后走不回来，无解。
但是最大流小于 $2$，不一定无解。因为起点可能直通终点，这样 起点 $\rightarrow$ 终点 $\rightarrow$ 起点 也是一个解，此时要进行特判。

最后，如果有解且起点不能直通终点，那么答案就是最大流减去 $2$，减去 $2$ 是因为起点和终点都访问了 $2$ 次。

Code

没写。

P3254 圆桌问题

做法

因为第 $i$ 个单位有 $r_i$ 个人，所以从源点向每个单位点连一条限制为 $r_i$ 的边。

因为每个桌子，同一个单位最多只有一人做，所以从每个单位点向每个桌子连一条限制为 $1$ 的边。

因为第 $i$ 个桌子最多 $c_i$ 人，所以从每个桌子点向汇点连一条限制为 $c_i$ 的边。

然后跑最大流

显然，如果最大流不等于总人数，那就说明无解。

如果有解，那么从每个单位出发沿着流满的路径找到对应的桌子输出就行了。

Code

没写。

P4016 负载平衡问题

做法

为了让它们平均，一定是多的给少的。

可以发现，最后结果只和它们与平均值之间的差有关。

所以，将平均值作为零，每个点的值变为 它原来的值减平均值。现在就是想要经过一定操作后使得每个点都变为 $0$

对于原值大于平均值的点，因为新的值是 它们原来的值减去平均值，所以从源点向它们建一条限制为 它们原来的值减去平均值，费用为 $0$ 的边，代表这些点在新图上的初始值。

对于相邻的仓库，互相连限制为 $\infty$，费用为 $1$ 的边，代表可以相互运。

对于原值小于平均值的点，因为这些点需要接收别的点的流量，会对答案产生贡献，为了统计这些贡献，需要从这些点向汇点建立一条限制为 平均值减去它们原来的值 的，费用为 $0$ 的边。

最小费用最大流

Code

没写。

P4015 运输问题

做法

千年一遇的水题，只写做法不解释

1. 从源点向每个仓库 $i$ 连一条容量为 $a_i$，费用为 $0$ 的边。
2. 从每个仓库 $i$ 向每个商店 $j$ 连一条容量为 $\infty$，费用为 $c_{i,j}$ 的边。
3. 从每个商店 $j$ 向汇点连一条容量为 $b_j$，费用为 $0$ 的边。
4. 最小费用最大流和最大费用最大流各跑一遍，输出答案。

Code

没写。

P4014 分配问题

做法

因为题目标签是网络流所以肯定是网络流算法
在这道题里，让求的是最小和最大总效益，也就是最小费用/最大费用流了，这也提示了将效益设为费用，同时最大流肯定就是总人数，所以边的流量跟人数有关。
这道题也是比较水的，下面只写做法，不解释：

1. 从源点向每个人连一条容量为 $1$，费用为 $0$ 的边。
2. 每个人 $i$ 向每个工作 $j$ 连一条容量为 $1$，费用为 $c_{i,j}$ 的边。
3. 每个工作再向汇点连一条容量为 $1$，费用为 $0$ 的边。

然后跑最小费用最大流/最大费用最大流

Code

没写。

P4011 孤岛营救问题

做法

发现 $P \le 14$，显然可以用二进制来存当前拥有的钥匙状态。
设 $i,j,k$ 表示到达 $(i,j)$，且钥匙状态为 $k$ 的最小花费。

暴力 bfs 即可。

Code

没写。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-20 21:15:02

原理

假设有 $n$ 个节点，而为了搜一个解需要遍历这 $n$ 个点。

如果复杂度较低，如遍历的复杂度为 $O(n)$，倒没有必要用这个算法。

但是如果复杂度很高，如 $O(n^2)$，而 $n \le 20000$；或者 $O(2^n)$，$n \le 40$ 等，就很有用了。

这个算法是分别从两端开始搜，两端分别搜索 $\frac{n}{2}$ 个节点，最后再把两端搜索到的结果拼接起来。

原来的 $O(n^2)$ 复杂度虽然还是 $O(n^2)$，但是由于 $n$ 除了 $2$，效率提升很大。

而 $O(2^n) \rightarrow O(2^\frac{n}{2})$，效率提升巨大。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-23 10:52:11

UPD：已修正格式错误。

题外话：

写一篇题解纪念第一次于 Div.2 切 D。

题意

给你一个 $n$ 行，$m$ 列的网格，每一列底部都有 $a_i$ 个障碍。
有 $q$ 次询问，每次询问给定一个起始坐标 $(x_s,y_s)$，一个终点坐标 $(x_f,y_f)$，以及一个正整数 $k$。
注意这里的 $x$ 代表第几行，$y$ 代表第几列。
你可以向前，向后，向左或向右走，但是每次都必须走 $k$ 步，并且不能走出网格或通过障碍。
问能否从起点走到终点。

$1 \le n \le 10^9$
$1 \le m \le 2 \cdot 10^5$
$1 \le q \le 2 \cdot 10^5$
$1 \le k \le 10^9$
保证给出的起点，终点不会在网格以外。

做法

来画一张图：

红色的障碍，绿色是起点，蓝色是终点。

显然，如果到达不了，怎么绕圈子都没有用。

先考虑一般的步骤，就是先向上走，避开障碍（到达一个没有障碍存在的行），然后向右走，走到终点所在的列，然后向下走到终点。

但是现在必须走 $k$ 步，所以有可能无法从起点到达没有障碍的那一行。
为了尽可能避开障碍，应该贪心的走到能走到的最高的，且不会越界的行。
显然这一行的行数就是 $(n-x_s) \bmod k$。
设 $maxh$ 代表起始列到终点列（$y_s$ 到 $y_f$）中最高的障碍的高度。
若 $(n-x_s) \bmod k \ge n - maxh$，那么说明无论如何都无法到达没有障碍的那一行，也就无法避开障碍到达终点的那一列，所以无解。
下一步就是判断从起点列能否通过走 $k$ 的倍数步到达 终点列，显然，如果 $\lvert y_f-y_s \rvert$ 不是 $k$ 的倍数，那么一定走不到。
最后，如果起始点与终点的高度差不是 $k$ 的倍数，那么仍然无解。

注：区间最高障碍可以用 st 算法求。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=2e5+5;
    int n,m;
    int a[maxn];
    int q;
    int st[19][maxn];
    int log[maxn];
    void main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            st[0][i]=a[i];
        }
        for(int i=2;i<=m;i++)
        {
            log[i]=log[i>>1]+1;
        }
        for(int i=1;i<=18;i++)
        {
            for(int j=1;j<=m-(1<<i)+1;j++)
            {
                st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            }
        }
        scanf("%d",&q);
        while(q--)
        {
            int x1,x2,y1,y2,k;
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
            if(y2<y1)swap(y2,y1);
            int lo2=log[y2-y1+1];
            int imax=max(st[lo2][y1],st[lo2][y2-(1<<lo2)+1]);
            \/\/起始列到终点列最高障碍
            int sy=n-imax;\/\/最高障碍离顶部有多少行
            bool flag=1;
            int sy2=(n-x1)%k;\/\/最高能到达第几行
            if(sy2>=sy)
            {\/\/第一步判断
                flag=0;
            }
            if(abs(y2-y1)%k!=0)
            {\/\/第二步判断
                flag=0;
            }
            if(abs(x2-x1)%k!=0)
            {\/\/第三步判断
                flag=0;
            }
            if(flag)printf("YES\n");
            else printf("NO\n");
        }
    }
}
int main()
{
    Main::main();
    return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-24 22:18:58

还没写完

做法

现根据题面把要求的式子列出来：
$\sum_{i=1}^{n} (\lfloor \frac{n}{i} \rfloor \cdot \sum_{j=0}^{k} i^j)$
用类似除法分块解决即可。

Code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-25 01:19:15

解法

• $m$ 是偶数的情况
  也就是说所有的数都可以选，输出 $0$。
• $m$ 是奇数的情况
  也就是说要选择一些数删掉，使得自己选择的数列中出现的好友对数数量为偶数个。
  考虑将两个好友连边。如果一个结点的度数为奇数，将其删掉之后将会破坏掉奇数对好友，剩下偶数对好友。
  另外，如果两个好友节点的度数都为偶数，那么将两个好友节点一起删掉，也将会破坏掉奇数对好友，剩下偶数对好友。
  所以，对这两种情况进行判断，取最小花费即可。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int t;
    int n,m;
    struct Peo
    {
        int id,a;
    }peo[maxn];
    vector<int> fri[maxn];
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                fri[i].clear();
                scanf("%d",&peo[i].a);
                peo[i].id=i;
            }
            int x,y;
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d",&x,&y);
                fri[x].emplace_back(y);
                fri[y].emplace_back(x);
            }
            if(m%2==0)
            {
                printf("0\n");
                continue;
            }
            int ans=0x3f3f3f3f;
            for(int i=1;i<=n;i++)
            {
                if(fri[peo[i].id].size()%2!=0)
                {
                    ans=min(ans,peo[i].a);
                }
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<fri[i].size();j++)
                {
                    if(fri[i].size()%2==0&&fri[fri[i][j]].size()%2==0)
                    {
                        ans=min(ans,peo[i].a+peo[fri[i][j]].a);
                    }
                }
            }
            printf("%d\n",ans);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 13:50:15

思路

利用线段树合并来辅助完成差分

做法

为了快速求出每个点的信息，可以树上差分，最后一遍 dfs 统一处理。

因为一个点可以有很多种救济粮，而要维护的信息是每个点数量最多的救济粮的具体数量及种类，所以可以每个点都开一个权值线段树，维护以上信息。

差分的时候，将 $x,y$ 点维护的 $z$ 型救济粮数量加一，代表 $1 \rightarrow x$ 和 $1 \rightarrow y$ 路径上的所有点 $z$ 型救济数量加一。由于 $lca(x,y)$ 多算了一次，$1 \rightarrow father(lca(x,y)$ 路径多算了两次，所以将 将 $lca(x,y)$ 以及 $father(lca(x,y))$ 两个点维护的 $z$ 型救济粮数量减一，去除多余贡献。

最后统一 dfs 的时候，将每个点与子树的贡献合并就行了。

最后，应该动态开点。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int n,m;
    int head[maxn];
    int maxr=0;
    struct EDGE
    {
        int to,nxt;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to)
    {
        edge[++cnt].to=to;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int fa[18][maxn],dep[maxn];
    void dfs(int u,int _fa)
    {
        dep[u]=dep[_fa]+1;
        fa[0][u]=_fa;
        for(int i=1;i<=17;i++)
        {
            fa[i][u]=fa[i-1][fa[i-1][u]];
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            dfs(to,u);
        }
    }
    inline int lca(int a,int b)
    {
        if(dep[a]<dep[b])swap(a,b);
        for(int i=17;i>=0;i--)
        {
            if(dep[fa[i][a]]>=dep[b])
            {
                a=fa[i][a];
            }
        }
        if(a==b)return a;
        for(int i=17;i>=0;i--)
        {
            if(fa[i][a]!=fa[i][b])
            {
                a=fa[i][a];
                b=fa[i][b];
            }
        }
        return fa[0][a];
    }
    struct Tree
    {
        int ls,rs,maxval,maxzl;
    }tree[maxn*100];
    int x[maxn],y[maxn],z[maxn];
    int nodecnt;
    int rt[maxn];\/\/原来节点对应的线段树节点编号
    inline void push_up(int node)
    {
        if(tree[tree[node].ls].maxval>=tree[tree[node].rs].maxval)
        {
            tree[node].maxval=tree[tree[node].ls].maxval;
            tree[node].maxzl=tree[tree[node].ls].maxzl;
        }
        else
        {
            tree[node].maxval=tree[tree[node].rs].maxval;
            tree[node].maxzl=tree[tree[node].rs].maxzl;
        }
    }
    int modify(int node,int l,int r,int pos\/*要修改的位置*\/,int val)
    {
        if(!node)node=++nodecnt;
        if(l==r)
        {
            tree[node].maxval+=val;
            tree[node].maxzl=l;
            return node;
        }
        int mid=l+r>>1;
        if(mid>=pos)
        {
            tree[node].ls=modify(tree[node].ls,l,mid,pos,val);
        }
        else tree[node].rs=modify(tree[node].rs,mid+1,r,pos,val);
        push_up(node);
        return node;
    }
    int merge(int a,int b,int l,int r)
    {
        if(!a)return b;
        if(!b)return a;
        int _rt=++nodecnt;
        if(l==r)
        {
            tree[_rt].maxval=tree[a].maxval+tree[b].maxval;
            tree[_rt].maxzl=l;
            return _rt;
        }
        int mid=l+r>>1;
        tree[_rt].ls=merge(tree[a].ls,tree[b].ls,l,mid);
        tree[_rt].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
        push_up(_rt);
        return _rt;
    }
    int ans[100005];
    void REdfs(int u,int _fa)
    {
        assert(u<=1e5);
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            REdfs(to,u);
            rt[u]=merge(rt[u],rt[to],1,maxr);
        }
        if(tree[rt[u]].maxval)
            ans[u]=tree[rt[u]].maxzl;
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        int ai,bi;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&ai,&bi);
            add(ai,bi);
            add(bi,ai);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&z[i]);
            maxr=max(maxr,z[i]);
        }
        for(int i=1;i<=m;i++)
        {
            assert(x[i]<=1e5&&y[i]<=1e5);
            rt[x[i]]=modify(rt[x[i]],1,maxr,z[i],1);
            rt[y[i]]=modify(rt[y[i]],1,maxr,z[i],1);
            int _lca=lca(x[i],y[i]);
            rt[_lca]=modify(rt[_lca],1,maxr,z[i],-1);
            if(fa[0][_lca])
                rt[fa[0][_lca]]=modify(rt[fa[0][_lca]],1,maxr,z[i],-1);
        }
        REdfs(1,0);
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",ans[i]);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 16:27:31

做法

对于一个点的 $k$ 级祖先，可以用倍增或长链剖分求出，十分容易。

对于一个点的所有 $k$ 级子孙，因为一个点 $i$ 的 $k$ 级子孙的深度是 $dep_i - k$，所以要查询的是，以 $i$ 为根的子树中，有多少个深度为 $dep_i + k$ 的。
所以可以对于每个点 $i$，建一棵权值线段树，维护以 $i$ 为根的子树中深度为 $j$（代表任意深度） 的节点有多少个。
这样通过线段树合并就能处理出所有信息了。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=3e5+5;
	int n,m;
	int log[maxn];
	int head[maxn];
	struct EDGE
	{
		int to,nxt;
	}edge[maxn<<1];
	int cnt=0;
	inline void add(int u,int to)
	{
		edge[++cnt].to=to;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int h[maxn],hs[maxn],fa[20][maxn];
	int dep[maxn];
	int ans[maxn];
	\/\/这里的h[i]是以i为根的子树的深度
	int count[maxn];
	\/\/count[i]是深度为i的点的个数
	void dfs1(int u,int _fa)
	{
		h[u]=dep[u]=dep[_fa]+1;
		fa[0][u]=_fa;
		count[dep[u]]++;
		for(int i=1;i<=19;i++)
		{
			fa[i][u]=fa[i-1][fa[i-1][u]];
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs1(to,u);
			h[u]=max(h[u],h[to]);
			if(h[to]>h[hs[u]])hs[u]=to;
		}
		h[u]++;
	}
	int top[maxn];
	vector<int> up[maxn],down[maxn];
	void dfs2(int u,int _top)
	{
		top[u]=_top;
		if(u==top[u])
		{
			for(int i=0,now=u;i<=h[u]-dep[u];i++)
			{

				up[u].emplace_back(now);
				now=fa[0][now];
			}
			for(int i=0,now=u;i<=h[u]-dep[u];i++)
			{
				down[u].emplace_back(now);
				now=hs[now];
			}
		}
		if(hs[u])
		{
			dfs2(hs[u],_top);
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa[0][u]||to==hs[u])continue;
			dfs2(to,to);
		}
	}
	int ask(int x,int k)
	{
		if(k==0)
		{
			return x;
		}
		int mbsd=dep[x]-k;\/\/目标深度
		if(mbsd<=0)return -1;
		int dqd=top[fa[log[k]][x]];
		if(dep[dqd]<mbsd)
		{
			dqd=down[dqd][mbsd-dep[dqd]];
		}
		if(dep[dqd]>mbsd)
		{
			dqd=up[dqd][dep[dqd]-mbsd];
		}
		return dqd;
	}
	struct Tree
	{
	    int ls,rs,val;
	}tree[maxn*100];
	int nodecnt;
	inline void push_up(int node)
	{
	    tree[node].val=tree[tree[node].ls].val+tree[tree[node].rs].val;
	}
	int rt[maxn];
    int modify(int node,int l,int r,int pos,int val)
    {
        if(!node)node=++nodecnt;
        if(l==r)
        {
            tree[node].val+=val;
            return node;
        }
        int mid=l+r>>1;
        if(mid>=pos)
        {
            tree[node].ls=modify(tree[node].ls,l,mid,pos,val);
        }
        else tree[node].rs=modify(tree[node].rs,mid+1,r,pos,val);
        push_up(node);
        return node;
    }
    int merge(int a,int b,int l,int r)
    {
        if(!a||!b)return a|b;
        int root=++nodecnt;
        if(l==r)
        {
            tree[root].val=tree[a].val+tree[b].val;
            return root;
        }
        int mid=l+r>>1;
        tree[root].ls=merge(tree[a].ls,tree[b].ls,l,mid);
        tree[root].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
        push_up(root);
        return root;
    }
    int query(int node,int l,int r,int pos)
    {
        if(l==r)
        {
            return tree[node].val;
        }
        int mid=l+r>>1;
        int ans=0;
        if(mid>=pos)ans=query(tree[node].ls,l,mid,pos);
        else ans=query(tree[node].rs,mid+1,r,pos);
        return ans;
    }
    struct Question
    {
        int k,id;
        Question(int k2,int id2)
        {
            k=k2;
            id=id2;
        }
    };
    vector<Question> qs[maxn];
    void solve(int u,int _fa)
    {
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==_fa)continue;
            solve(to,u);
            rt[u]=merge(rt[u],rt[to],1,n+1);
        }
        rt[u]=modify(rt[u],1,n+1,dep[u],1);
        for(int i=0;i<qs[u].size();i++)
        {
            ans[qs[u][i].id]=query(rt[u],1,n+1,dep[u]+qs[u][i].k)-1;
            if(ans[qs[u][i].id]<0)ans[qs[u][i].id]=0;
        }
    }
	void main()
	{
		scanf("%d",&n);
		for(int i=2;i<=n;i++)
		{
			log[i]=log[i>>1]+1;
		}
		int __fa;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&__fa);
			add(i,__fa);
			add(__fa,i);
		}
		dfs1(0,-1);
		dfs2(0,0);
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			int xi,ki;
			scanf("%d%d",&xi,&ki);
			int zx=ask(xi,ki);
			if(zx!=-1)
            {
                qs[zx].emplace_back(ki,i);
            }

		}
		solve(0,-1);
		for(int i=1;i<=m;i++)
        {
            printf("%d ",ans[i]);
        }
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 22:51:46

题外话

这是某蒟蒻为了 CSP-S2022 不爆零做的一点挣扎。

廊桥分配

做法

一个简单的思路就是枚举分配给国内航班和国际航班的航班数量，然后每枚举一种情况 $O(n)$ 计算答案，最后取最大值，总复杂度 $O(n^2)$。

想一想能不能对计算答案进行优化。

显然，设分配了 $i$ 个廊桥，那么答案等于这 $i$ 个廊桥分别有多少飞机停靠。

一个比较显然的结论是，当廊桥数量增加时，如果强制飞机进入编号最小的空闲廊桥，那么原来去哪个廊桥的飞机还去哪个廊桥。

所以，可以先预处理出在假设廊桥充足的情况下，每个廊桥有多少飞机停靠。

然后做个前缀和，前缀和数组第 $i$ 个元素表示如果有 $i$ 个廊桥，那么答案是多少。

枚举分配廊桥数量取最大值就行了。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int n,m1,m2;
    struct Plane
    {
        int a,b;
    }pl[maxn],pl2[maxn];
    bool cmp(Plane a,Plane b)
    {
        return a.a<b.a;
    }
    int qzh[maxn],qzh2[maxn];
    void calc1()
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> lk;
        \/\/待离开飞机队列
        \/\/pair的第一个元素是离开时间，第二个是占用的廊桥编号
        priority_queue<int,vector<int>,greater<int>> lq;
        \/\/空闲廊桥队列
        for(int i=1;i<=n;i++)
        {
            lq.push(i);
        }\/\/初始所有廊桥都是空的
        for(int i=1;i<=m1;i++)
        {
            while(!lk.empty()&&lk.top().first<pl[i].a)\/\/将第 i 架飞机到达前已经离开的飞机清除并释放廊桥
            {
                lq.push(lk.top().second);
                lk.pop();
                \/\/飞机离开，释放廊桥
            }
            if(lq.empty())continue;
            int used=lq.top();\/\/当前飞机使用的廊桥编号
            qzh[used]++;
            lq.pop();
            lk.push(make_pair(pl[i].b,used));
        }
        for(int i=1;i<=n;i++)
        {
            qzh[i]=qzh[i-1]+qzh[i];
        }
    }
    void calc2()
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> lk;
        \/\/待离开飞机队列
        \/\/pair的第一个元素是离开时间，第二个是占用的廊桥编号
        priority_queue<int,vector<int>,greater<int>> lq;
        \/\/空闲廊桥队列
        for(int i=1;i<=n;i++)
        {
            lq.push(i);
        }\/\/初始所有廊桥都是空的
        for(int i=1;i<=m2;i++)
        {
            while(!lk.empty()&&lk.top().first<pl2[i].a)\/\/将第 i 架飞机到达前已经离开的飞机清除并释放廊桥
            {
                lq.push(lk.top().second);
                lk.pop();
                \/\/飞机离开，释放廊桥
            }
            if(lq.empty())continue;
            int used=lq.top();\/\/当前飞机使用的廊桥编号
            qzh2[used]++;
            lq.pop();
            lk.push(make_pair(pl2[i].b,used));
        }
        for(int i=1;i<=n;i++)
        {
            qzh2[i]=qzh2[i-1]+qzh2[i];
        }
    }
    void main()
    {
        scanf("%d%d%d",&n,&m1,&m2);
        for(int i=1;i<=m1;i++)
        {
            scanf("%d%d",&pl[i].a,&pl[i].b);
        }
        for(int i=1;i<=m2;i++)
        {
            scanf("%d%d",&pl2[i].a,&pl2[i].b);
        }
        sort(pl+1,pl+m1+1,cmp);
        sort(pl2+1,pl2+m2+1,cmp);
        calc1();
        calc2();
        int ans=0;
        for(int i=0;i<=n;i++)
        {
            ans=max(ans,qzh[i]+qzh2[n-i]);
        }
        printf("%d",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

其他 3 题

还没做。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-27 21:16:47

做法

以 P5490 扫描线模板来说。
从题解区盗取一张图（没找到比这更清晰的图）：

可以看到这些图形被一条条纵线划分成了几个规则的矩形。

每一个矩形，都有两条竖线分别代表起始和终点。

所以可以在读入的时候就对始边和终边进行标记。

按横坐标升序，依次处理这些竖线。

处理的时候，考虑到多条边可能在同一横坐标上，每到达一个横坐标（有边存在），就记录当前坐标有多少个点被覆盖。

具体的说，就是遇到一条始边，就将这条边所覆盖的点标记上，代表当前坐标这些点被覆盖，遇到一条终边，就将这条边对应的点取消标记，代表一个矩形的结束。

值域很大，所以要离散化开个权值线段树完成标记。

至于答案，每到一个有边存在的横坐标时，答案就加上（当前横坐标被标记的点数，相当于当前坐标所有始边组合起来之后的长度）乘（下一个有边存在的横坐标减去当前横坐标）

用括号方便看。

完结

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    typedef __int128 ll128;
    const int maxn=1e5+5;
    struct OD
    {
        int x,y1,y2;
        int flag;\/\/权值
        \/\/x是纵线的横坐标，y1是下纵坐标，y2是上纵坐标
    }od[maxn<<1],lsh[maxn<<1];
    \/\/od存储原始读入的竖线信息，lsh存储横坐标不变，纵坐标离散化之后的信息
    int n;
    int h_rem[maxn<<1];\/\/暂时存储纵坐标相关信息
    inline bool cmp(OD a,OD b)
    {
        return (a.x!=b.x)?(a.x<b.x):(a.flag>b.flag);
    }
    struct Tree
    {
        int l,r,ls,rs,len,lazy;
    }tree[maxn*16];\/\/nlogn*2
    int val[maxn<<1];
    int ncnt;
    inline int ls(int i)
    {
        return tree[i].ls;
    }
    inline int rs(int i)
    {
        return tree[i].rs;
    }
    inline int len(int i)
    {
        return tree[i].r-tree[i].l+1;
    }
    inline void add(int i,int val)
    {
        tree[i].lazy+=val;
    }
    inline void push_up(int i)
    {
        if(tree[i].lazy)
        {
            tree[i].len=val[tree[i].r+1]-val[tree[i].l];
            return;
        }
        tree[i].len=tree[ls(i)].len+tree[rs(i)].len;
    }
    int build(int i,int l,int r)
    {
        i=++ncnt;
        tree[i].l=l,tree[i].r=r;
        if(l==r)return i;
        int mid=(l+r)>>1;
        tree[i].ls=build(ls(i),l,mid);
        tree[i].rs=build(rs(i),mid+1,r);
        return i;
    }
    inline void modify(int i,int l,int r,int val)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            add(i,val);
            push_up(i);
            return;
        }
        if(tree[i].r<l||tree[i].l>r)return;
        int mid=(tree[i].l+tree[i].r)>>1;
        if(mid>=l)modify(ls(i),l,r,val);
        if(mid<r)modify(rs(i),l,r,val);
        push_up(i);
    }
    void main()
    {
        scanf("%d",&n);

        int x_1,y_1,x_2,y_2;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
            od[i].x=x_1,od[i].y1=y_1,od[i].y2=y_2,od[i].flag=1;
            od[i+n].x=x_2,od[i+n].y1=y_1,od[i+n].y2=y_2,od[i+n].flag=-1;
            h_rem[i]=y_1;
            h_rem[i+n]=y_2;
        }
        sort(h_rem+1,h_rem+2*n+1);
        int tot=unique(h_rem+1,h_rem+2*n+1)-h_rem-1;
        for(int i=1;i<=2*n;i++)
        {
            lsh[i].x=od[i].x;
            lsh[i].flag=od[i].flag;
            lsh[i].y1=lower_bound(h_rem+1,h_rem+tot+1,od[i].y1)-h_rem;
            lsh[i].y2=lower_bound(h_rem+1,h_rem+tot+1,od[i].y2)-h_rem;
            val[lsh[i].y1]=od[i].y1;
            val[lsh[i].y2]=od[i].y2;
        }
        sort(lsh+1,lsh+2*n+1,cmp);
        int rt=build(1,1,2*n);
        ll128 ans=0;
        for(int i=1;i<2*n;i++)
        {
            modify(1,lsh[i].y1,lsh[i].y2-1,lsh[i].flag);
            ans+=(ll128)tree[1].len*(ll128)(lsh[i+1].x-lsh[i].x);
        }
        printf("%lld",(ll)ans);
    }
}
int main()
{
    Main::main();
    return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-30 10:21:52

看完了数学一本通的线性逆元，再自行推导一下。
记 $a$ 的逆元为 $a^{-1}$
已知：$1^{-1} \equiv 1 \pmod p$
设 $k = \lfloor \frac{p}{i}\rfloor,r = p \bmod i,p = k \cdot i + r$
$k \cdot i + r \equiv 0 \pmod p$
$(k \cdot i + r) \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p$
$k \cdot i \cdot i^{-1} \cdot r^{-1} + r \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p$
$k \cdot r^{-1} + i^{-1} \equiv 0 \pmod p$
$i^{-1} \equiv -k \cdot r^{-1} \pmod p$
$i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$

总体推导思路：先将 $p $用已知量表示出来，然后通过乘上一些数使得这个式子的其中一项为要求的逆元（$i^{-1}$），然后移项得到结果。