个人记录

#include<bits/stdc++.h>
using namespace std;
const int N=8e4+5;
typedef long long ll;
int a[N];
int main(){
	int n;
	cin>>n;
	int top=0;
	ll ans=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		while(top>0&&a[top]<=x)top--;
		ans+=top;
		a[++top]=x;
	}
	cout<<ans;
	return 0;
}

P1950 长方形

题目大意：

想在一张由 $n*m$ 个格子组成的长方形纸片上裁剪出长方形。

有以下要求：1.只能沿着格子的边缘剪（注意这里说的不是长方形纸片的边而是格子的边，意思就是要沿着格子剪） 2.剪出的长方形不能包含 $*$ 3.长方形没有大小限制

现在想问问有多少种裁剪的方法。

这道题让我想起了玉蟾宫。有点点相似。
一行一行地去统计三个数组： $h,l,r$
（只统计 $.$ 格子，不统计 $*$ 格子）。

$h$ 存放当前格子和上方的第一个 $*$ 格子的距离（即能拓展的高度）。
$l$ 存放当前格子左边第一个 $h$ 数值的小于等于自己的格子。 $r$ 存放当前格子右边第一个 $h$ 数值小于自己的格子。（注意这里说辞的差距，l是小于等于，r是小于。这是为了防止重复统计，所有的格子只往右边拓展）

依据乘法原理，截至当前这一行，包含当前格子且受 $h$ 高度限制的长方形的数量为 $h*(i-l[i])*(r[i]-i)$ 。

最后就是时间复杂度的问题了。如果暴力求取总时间复杂度为 $O(n^3)$ ，会超时。
此时我们可以用单调栈来优化寻找“寻找在自己左边 $h$ 值第一个小于等于自己的数”的操作。时间复杂度就会优化到 $O(n^2)$ ，可以写了。

另外：记得开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
char a[N][N];
int h[N][N],l[N][N],r[N][N];
int st1[N],top1;
ll ans;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='.')h[i][j]=h[i-1][j]+1;
			//统计l 
			while(top1>0&&h[i][st1[top1]]>h[i][j])top1--;
			l[i][j]=st1[top1];
			st1[++top1]=j;
		}
		top1=0;
        st1[0]=m+1;
		for(int j=m;j>=1;j--){
			while(top1>0&&h[i][st1[top1]]>=h[i][j])top1--;
			r[i][j]=st1[top1];
			st1[++top1]=j;
		}
        top1=0;
        st1[0]=0;
		for(int j=1;j<=m;j++){
			ans+=h[i][j]*(j-l[i][j])*(r[i][j]-j);
		}
	}
	cout<<ans;
	return 0;
}

2026/6/2

P10112 [GESP202312 八级] 奖品分配

题目大意：

$n$ 名同学，学号从 $0$ 到 $n-1$ 。有 $m$ 种奖品，第i中奖品总共有 $a[i]$ 个。
每位同学都可以恰好分到一个奖品，最最后剩余的奖品不超过 $1$ 个。
要求求出每个班级礼物分配的方案数对 $10^9+7$ 取模后的结果。

前情提要：排列与组合

1.排列：从 $n$ 个不同元素中，取出 $m$ 个按顺序排列（也就是关注每个被取出来的元素在哪个位置）。记作 $A^m_n$ 。（我觉得可以这么记： $n$ 大 $m$ 小， $n$ 在下(位置比较像分母) $m$ 在上（位置比较像分子），母比子大，所以是从 $n$ 个元素中挑选 $m$ 个元素（即从下面的数中挑选上面数的个数））。

可以看成一个有 $m$ 个坑， $n$ 个萝卜，要把萝卜塞进坑里。每塞一个，下一个坑的选项就少一个。

公式： $A_n^m=n(n-1)(n-2)*...*(n-m+1)=\frac{n!}{(n-m)!}$

规定： $0!=1$

2.组合：从 $n$ 个不同元素中，取出 $m$ 个不考虑顺序排成一组。记作 $C_n^m$ 。

如果说前面是要塞萝卜进坑，那么现在就是要从 $n$ 个坑里拔 $m$ 个萝卜，然后堆在一起，不记顺序。

公式： $C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$

来源： $A_n^m=C_n^m*A_m^m$ （从 $n$ 个东西中选取出来 $m$ 个并且排序（即要求顺序）的方案数=从 $n$ 个东西中选出 $m$ 个的方案数 $*$ 给 $m$ 个物品排序的方案数）

其他：

$C_n^m=C_n^{n-m}$ （计算出来其实是一样的： $\frac{n!}{m!(n-m)!}=\frac{n!}{(n-m)!(n-n+m)!}$ ）

$C_n^0=C_n^n$ （常识形问题。不过你也可以选择计算，反正算出来是一样的。）

$C_{n-1}^m+C_{n-1}^{m-1}=C^m_n$ (这个不建议死记硬背。可以这样记：从 $n$ 个数里选 $m$ 个，第一个可以选也可以不选。第一个选了，那么就是从后面的 $n-1$ 个中选取 $m-1$ 个。第一个没有选，那么就是从后面的 $n-1$ 个中选取 $m$ 个。两个加在一起就是完整的方案了)

接下来关于本题内容来自CleverRaccon的题解。如果你们真的对本题有疑问，还是去看这个题解吧，TA写的更好。后续的内容本质是我用来给自己理解写的。

本题需要两层理解：

1.需要用到排列组合且组合需要初始化

可以将本题看作是往 $n$ 个坑（小朋友）里放 $m$ 个萝卜（礼物）。第 $i$ 个礼物有 $C_{n-\sum_{j = 1}^{i-1}a[j]}^{a[i]}$ 种摆放方案。
所有的拜访方案就是将从 $1$ 到 $n$ 所有的拜访方案乘起来（乘法原理）。

2.空气领奖位

注意到总奖品的个数可能是 $n$ 但也可能是 $n+1$ 。我们可以把多出来的那个奖品看作发给了
空气。如果奖品总数是 $n+1$ 我们就可以设置一个空白领奖位（初始人数+1）。

另：方案数（比如组合数排列数）一定要开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int mod=1e9+7;
ll C[N][N];//组合数 c[n][m]：从n个数字中选取m个有多少种方案 
int a[N],pre[N];
int main(){
	int t;
	cin>>t;
	for(int i=0;i<=1004;i++){
		for(int j=0;j<=1004;j++){
			if(j==0)C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	while(t--){
		int n,m;
		cin>>n>>m;
		int sum=0;
		for(int i=1;i<=m;i++){
			cin>>a[i];
			sum+=a[i];
			pre[i]=pre[i-1]+a[i];
		}
		n=sum;
		ll ans=1;
		for(int i=1;i<=m;i++)ans=(ans*C[n-pre[i-1]][a[i]])%mod;
		cout<<ans<<'\n';
	}
	return 0;
}

前缀和可以用来求取区间和，而差分可以用来做区间修改操作。

P2367 一维差分模板

P1719 二维前缀和例题

这道题目有两种做法。一种 $O(n^4)$ ，一种 $O(n^3)$ .

法一： $O(n^4)$

二维前缀和和以为前缀和其实差不多。
$s[i][j]$ 的定义是从 $a[1][1]$ 到 $a[i][j]$ 所有数值加起来的和。
公式： $s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$

$(x_1,y_1)$ 到 $(x_2,y_2)$ 的和= $s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]$

注： $x_1，y_1，x_2，y_2$ 之间是有大小关系的。

#include<bits/stdc++.h>
using namespace std;
const int N=125;
int a[N][N],s[N][N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	int ans=INT_MIN;
	for(int x_1=1;x_1<=n;x_1++){
		for(int y_1=1;y_1<=n;y_1++){
			for(int x_2=x_1;x_2<=n;x_2++){
				for(int y_2=y_1;y_2<=n;y_2++){
					ans=max(ans,s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]);
                    int sum=s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1];
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

2026/6/3

法二： $O(n^3)$

O(n^3)方法前置知识点

//最大字段和
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int ans=INT_MIN;//ans不从0开始
	int f=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		f=max(a,f+a);//考虑包含a[i]的最大值。
		ans=max(ans,f);
	}
	cout<<ans;
	return 0;
}

优化的方式是：枚举 $i,j$ 。枚举上边界为第 $i$ 行，下边界为第 $j$ 行的最大矩形。第一层循环遍历 $i$ ，第二层循环遍历 $j$ ，第三层循环遍历 $k$ 。 $k$ 枚举列。

#include<bits/stdc++.h>
using namespace std;
const int N=125;
int a[N][N],s[N][N];
int q(int x_1,int y_1,int x_2,int y_2){
	return s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
		}
	}
	int ans=INT_MIN;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int sum=0;
			for(int k=1;k<=n;k++){
				int qsum=q(i,k,j,k);
				sum=max(sum+qsum,qsum);
				ans=max(ans,sum);
			}
		}
	}
	cout<<ans;
	return 0;
}

P2367 一维差分（重做）

P1950 长方形
6/1做过的题目。这边来提一个比较容易弄错的点。

正确的代码：

for(int j=1;j<=m;j++){
    if(a[i][j]=='.')h[i][j]=h[i-1][j]+1;
    while(top>0&&h[i][st[top]]>h[i][j])top--;
    l[i][j]=st[top];
    st[++top]=j;
}

错误的代码：

for(int j=1;j<=m;j++){
    if(a[i][j]=='.')h[i][j]=h[i-1][j]+1;
    else continue;
    while(top>0&&h[i][st[top]]>h[i][j])top--;
    l[i][j]=st[top];
    st[++top]=j;
}

在写代码的时候，可能会认为加上一条continue是无关紧要的。~~并且还减小时间复杂度~~。但是如果加上continue代码就是错的。这是因为在正常不加的时候，st是会有变化的。

当有一行是这样**..的时候，第三个字符的 $l$ 数值应该是 $2$ 。但是如果直接continue，那么值就会变成 $0$ ，最后算ans的时候就会算错。

B - Two Rings

这道题主要考察的是数学知识。在平面直角坐标系中，圆 $C_1$ 的半径是 $R_1$ ，圆 $C_2$ 的半径是 $R_2$ 。当两个元存在公共点 $|R_1-R_2|\le$ 两圆圆心的距离 \leR_1+R_2。

由于精度问题。我们可以把它们都算成平方。不过平方一定要开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int t;
	cin>>t;
	while(t--){
		ll x1,y1,r1,x2,y2,r2;
		cin>>x1>>y1>>r1>>x2>>y2>>r2;
		ll d=(x2-x1)*(x2-x1)+(y1-y2)*(y1-y2);
		if((r1-r2)*(r1-r2)<=d&&d<=(r1+r2)*(r1+r2))cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

公倍数问题

打暴力可以获得 $50pts$ ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+5;
int c[N][N];
int main(){
	int n,m,k;
	cin>>n>>m>>k;
    ll ans1=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]=__gcd(i,j);
        }
    }
	for(int z=1;z<=k;z++){
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				long long sum=c[i][j]*(i/c[i][j])*(j/c[i][j]);
				if(z%sum==0)ans++;
			}
		}
		ans1+=ans*z;
	}
    cout<<ans1;
	return 0;
}

接下来我的称述内容大部分来自superballll的题解。如果你真的对本题有疑问，建议直接去看这位同学的题解。TA的思路妙极了。

本题其实在表述方面埋了坑。如果有心可以发现，题面在引导你往二维数组的方向去想。但如果你用了二维数组，开出 $10^{10}$ 大小的数组你就会发现：要完。

转变思路可以发现， $k$ 是 $i$ 和 $j$ 的公倍数，也就是说 $i$ 和 $j$ 是 $k$ 的因数。

$1=1*1$ ， $1$ 是 $1$ 的因数，所以 $A[1][1]$ 的值可以是 $k$ ； $2=1*2$ ， $1$ 和 $2$ 都是 $2$ 的因数，所以 $A[1][1],A[1][2],A[2][1],A[2][2]$ 的值都可以是 $k$ 。

总结出来，如果想要 $A[i][j]$ 有可能是 $k$ ，那么 $i$ 和 $j$ 都是 $k$ 的因数。
这里容易想出来一些会TLE的思路。比如说：枚举 $k$ 的每一个因数。

这里需要一个巧妙的思路转变： $i$ 和 $j$ 都是 $k$ 的因数。那么我们可以用两个两层循环，

1.第一层遍历 $1-n$ ，第二层循环遍历 $1-k$ ，统计出 $i$ 是哪个 $k$ 的因数。

2.第一层遍历 $1-m$ ，第二层循环遍历 $1-k$ ，统计出 $j$ 是哪个 $k$ 的因数。

最后用乘法原理的思路：两个两层循环各得出一个数组，存储每个 $k$ 有多少个因数，将它们乘在一起就好。

时间复杂度：

前置知识点：调和级数

$H_n = \sum_{k = 1}^{n} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{k}$

当 $n=10^5$ ， $H_n$ 大概是 $10$ 。

本题中，第二层循环看似遍历 $1-k$ ，超时离谱，实则每次循环都遍历 $H_{10^6}$ ，时间复杂度并不太高，不会超时。

注：十年OI一场空。不开long long 见祖宗。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll sn[N],sm[N],ans;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=k;j+=i){
			sn[j]++;
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=i;j<=k;j+=i){
			sm[j]++;
		}
	}
	for(int i=1;i<=k;i++){
		ans+=sn[i]*sm[i]*i;
	}
	cout<<ans;
	return 0;
}

P2669 金币

P5722 数列求和

P5723 质数口袋

P1217 Prime
这道题我想稍微提一下质数筛法。

这是我比较常用的质数筛写法：for(int j=2;j<i;j++)

这是OIer普遍使用的质数筛写法：for(int j=2;j<=i*i;j++)

为什么第二种写法能够使用呢？答：由于因数都是成对出现的。如果，一个数是质数，那么你一定能在 $\sqrt{i}$ 以内找到它得因数。

P1423 游泳

2026/6/4

分治，就是把一个复杂的问题转换成为若干个简单一些的问题，然后递归下去解决简单一些的问题。（from《深入浅出进阶篇》）
这让我想到了DP的”重叠子问题“（虽然不确定是不是同一种东西）。或许计算机本身的意义，就是去帮助人类做一下重复的东西。但是也不禁让人感慨，缺乏了那些无趣的重复，我们还能有创新吗？

P1177 归并排序模板

归并排序

归并排序是基于分治的思想去完成的。分治，分而治之。假设有两个有序的数组 $a$ 和 $b$ （ $a$ 数组有 $n$ 个元素， $b$ 数组有 $m$ 个元素），如何将它们合并成一个有序的数组呢？

维护两个下标 $i$ 和 $j$ 。将 $a[i]$ 和 $b[j]$ 进行比较：如果 $a[i]<b[j]$ ，将 $a[i]$ 填到新数组中，让 $i$ 自增。如果 $b[j]$ 较小，让 $j$ 自增。当 $i=n$ 或者 $j=m$ 的时候，我们就可以把另一个数组剩下的所有数值给添加到最终数组中。

这是在 $a$ 和 $b$ 都有序的情况下。那么我们如何将一个无序数组变成这样呢。这个时候就要利用分而治之的思想。一个数组长度为 $n$ ，当它只有一个数的时候，它天然有序。当 $n>1$ ，尝试将它分成两个长度为 $\frac{n}{2}$ 的数组。对这两个子序列递归地进行排序：先分成两块往前递归，递归完成后会吐出两个有序序列，然后再按照上述操作进行排序。

时间复杂度为 $O(nlogn)$ 。

大概是长这样：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
void sor_t(int s,int e){
	if(e==s)return;
	sor_t(s,s+(e-s)/2),sor_t(s+(e-s)/2+1,e);
	int mid=(e-s)/2;
	int now_x=s,now_y=s+(e-s)/2+1,sum=0;
	while(now_x<=(s+(e-s)/2)&&now_y<=e){
		if(a[now_x]<=a[now_y])b[sum++]=a[now_x],now_x++;
		else if(a[now_y]<=a[now_x])b[sum++]=a[now_y],now_y++;
	}
	for(int i=now_x;i<=s+mid;i++)b[sum++]=a[i];
	for(int i=now_y;i<=e;i++)b[sum++]=a[i];
	for(int i=0;i<sum;i++)a[i+s]=b[i];
	return;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sor_t(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

P1908 逆序对

逆序对

在做逆序对之前，我想稍微提一提分治。二分是分治的儿子，不难发现无论是二分答案还是二分查询，它都有一个类似于 $check$ 函数的东西。而分治的分而治之，一般情况下它做的都是同一套体系的东西（不管是从宏观的角度：所有的分治是有相似点的。还是从微观的角度：一道题中使用分治，每一次”治“的过程都是同一份代码），往往是一个函数，去做递归。从大的分到小的，再从小的回到大的。

分治既是一种无形的思想，也是有形的框架。（回到逆序对）

我们不再分析分治的框架了，直接沿用归并排序的框架。尝试一边排序一边寻找逆序对。当序列长度 $n=1$ 时，肯定没有逆序对。当 $n>1$ ，将其拆分成两个序列。对两个子序列递归地求出内部的逆序对。

递归地计算好之后，考虑如何合并。一个大序列中的逆序对，肯定有一个元素来自前半序列；一个元素来自后半序列。如何计算两个子序列对答案的贡献？

回忆归并排序的过程。如果我们现在要将 $a[i]$ 放入新数组，而和 $a[i]$ 作比较的是 $b[j]$ ，那么就代表： $b[1],b[2]...b[j-1]$ 全部小于 $a[i]$ 。此时出现了 $j-1$ 对逆序对。答案加上 $j-1$ 。

我们可以用这样的思路去完成代码。
注：逆序对偏向于方案数，建议开 long long。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
ll ans;
int a[N],b[N];
void sor_t(int s,int e){
	if(s==e)return;
	int mid=(s+e)>>1;
	int now_x=s,now_y=mid+1,sum=0;
    sor_t(now_x,mid),sor_t(now_y,e);
	while(now_x<=mid&&now_y<=e){
		if(a[now_x]<=a[now_y]){
			b[sum++]=a[now_x++];
			ans+=now_y-mid-1;
		}else if(a[now_y]<=a[now_x])b[sum++]=a[now_y++];
	}
	for(int i=now_x;i<=mid;i++)b[sum++]=a[i],ans+=now_y-mid-1;
	for(int i=now_y;i<=e;i++)b[sum++]=a[i];
	for(int i=0;i<sum;i++)a[i+s]=b[i];
	return;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sor_t(1,n);
	cout<<ans;
	return 0;
}

P1966 火柴排队

首先，我们将 $\sum{(a[i]-b[i])^2}$ 进行拆解（如果题面中有这种神奇的数学公式，那我们肯定优先选择去拆解它，看看能拆出什么）。

$\sum{(a[i]-b[i])^2}=\sum{(a[i]^2+b[i]^2-2a[i]b[i])}=\sum{a[i]^2}+\sum{b[i]^2}-\sum{2a[i]b[i]}$

显然，无论如何拆解， $\sum{a[i]^2}+\sum{b[i]^2}$ 都不会有变化。想要使得距离最小，那就得想办法让 $\sum{2a[i]b[i]}$ 最大。

前置知识点：

排序不等式证明

结论：当有两组实数 $a$ 和 $b$ ， $a$ 和 $b$ 都为乱序时的 $\sum{a_ib_i}$ 小于 $a$ 和 $b$ 数列都单调不减时的 $\sum{a_ib_i}$ 。

即 $a_1\le a_2\le ... \le a_n$ 且 $b_1\le b_2\le ... \le b_n$ 时， $\sum{a_ib_i}$ 最大。

证明：

当 $a_1\le a_2\le ... \le a_n$ 且 $b_1\le b_2\le ... \le b_n$ 时，任给一组乱序配对 $a_1b_{x_1},a_2b_{x_2},...,a_nb_{x_n}$

只要存在两个下标 $p<q$ 且 $x_p>x_q$ ，交换 $b_{x_q}$ 和 $b_{x_p}$ ， $\sum{a_i b_{x_i}}$ 就会变大。

有了这个结论，我们可以知道：对于每个 $k$ ，我们应该将第 $k$ 小的 $a_k$ 元素与 $b_k$ 元素配对，这样 $\sum{a_ib_i}$ 最大。可以发现：在第一盒火柴交换 $i$ 和 $i+1$ 根，与在第二盒火柴中交换是一样的。所以，我们只需要考虑对一盒火柴进行交换。

首先排序，然后计算出两个数组 $c$ 和 $d$ 。 $c_i$ 表示 $a[i]$ 在数组 $a$ 中是第 $c_i$ 大的。 $d_i$ 表示 $b[i]$ 在数组 $b$ 中是第 $d_i$ 的。

如果只是单想着如何把 $c$ 序列变成 $d$ 序列，是有难度的。所以我们可以换个方向去想： $n\le 10^5$ ，需要使用的算法时间复杂度可能是 $O(n)$ 或者是 $O(nlogn)$ ，想要将第 $k$ 小的 $a_k$ 元素与 $b_k$ 元素配对。我们可以使用映射+排序的方法。

我们将 $d_i$ 映射成 $i$ 。由此，数组 $d$ 变成了 $1,2,3..,n$ 。即 $pos[d[i]]=i$ 。接着，我们将 $c_i$ 映射成 $pos[c[i]]$ 。问题转化为每次可以交换相邻两个位置，求至少要交换多少次来排序一个序列。

可以这样考虑：

1.当前序列中没有一个相邻的逆序对，就代表已经完成任务了

2.当前序列中有相邻的逆序对，那么我最多需要也最少需要一次“交换相邻两个位置”的操作，将数列中的逆序对数量减少一个。

现在，我们只需要算出 $c$ 中逆序对数量，就可以得出最终答案了。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e8-3;
typedef long long ll;
ll ans;
const int N=1e5+5;
struct Node{
	int now;//数字
	int px;//下标 
}a[N],b[N];
int d[N],pos[N];
int c[N],bc[N]; 
bool cmp(Node aa,Node bb){
	return aa.now<bb.now;
}
void sor_t(int x,int y){
	if(x==y)return;
	int mid=(x+y)>>1;
	int nox=x,noy=mid+1,sum=0;
	sor_t(nox,mid),sor_t(noy,y);
	while(nox<=mid&&noy<=y){
		if(c[nox]<=c[noy]){
			bc[sum++]=c[nox++];
			ans=(ans+noy-mid-1)%mod;
		}else bc[sum++]=c[noy++];
	}
	for(int i=nox;i<=mid;i++){
		bc[sum++]=c[nox++];
		ans=(ans+noy-mid-1)%mod;
	}
	for(int i=noy;i<=y;i++)bc[sum++]=c[noy++];
	for(int i=0;i<sum;i++)c[i+x]=bc[i];
	return;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].now,a[i].px=i;
	for(int i=1;i<=n;i++)cin>>b[i].now,b[i].px=i;
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)c[a[i].px]=i,d[b[i].px]=i;
	for(int i=1;i<=n;i++)pos[d[i]]=i;
	for(int i=1;i<=n;i++)c[i]=pos[c[i]];
	sor_t(1,n);
    cout<<ans;
	return 0;
}

各种整形与二的次幂之间的关系

$-2^{31} \le int < 2^{31}$

$-2^{63} \le long long < 2^{63}$

$0 \le unsigned long long < 2^{64}$

2026/6/6

P1217 Prime

如何巧妙压缩时间

这里只是列举一些比较常见的（因为刚好做到了Prime这题）。
它的代码是这样的：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
    cin>>a>>b;
	for(int i=a;i<=b;i++){
        if(i%2==0)continue;//优化1
		int si=i;
		int ni=0;
		while(si){
			ni=ni*10+si%10;
			si/=10;
		}
		if(i!=ni)continue;//优化2
		bool sum=0;
		for(int j=2;j*j<=i;j++){//优化3
			if(i%j==0){
				sum=1;
				break;
			}
		}
		if(!sum)cout<<i<<'\n';
	}
	return 0;
}

注意到我用了三个优化。将看似不能卡过去的题卡过去了。优化3前几天已经分析过了。我们来说说优化1和优化2.

优化1：注意到除了2之外的偶数不可能是质数。且 $a>5$ ，所以我们可以在开头直接把偶数特判掉。不要认为这样没用，加了这行代码，你就会多过一个测试点。苍蝇再小也是肉。万一你就差这一个点呢。

优化2：我们在“质数”和“回文数”之间进行比较。发现回文数的数量小于质数。所以我们先判断回文，如果不是直接将它continue掉即可。（也就是将更能筛的判断放在前面，且回文的时间复杂度也小于质数筛）。

另外还有一些优化，比如剪枝什么的。不过这个就有门槛了，后面我会着重提及。

P10263 公倍数问题

将时间复杂度比较高的循环分解

在谈论循环分解之前，我要先提一个比较常见也比较容易错的问题：神奇的long long 问题。这是正确代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
const int N=1e6+5;
ll a[N],b[N];
int main(){
	int n,m;
    ll k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=k;j+=i){
			a[j]++;
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=i;j<=k;j+=i){
			b[j]++;
		}
	}
	for(int i=1;i<=k;i++)ans+=a[i]*b[i]*i;
	cout<<ans;
	return 0;
}

注意到 $k,a,b$ 都开了long long。你做题的时候很有可能会以偏概全，认为只有 $ans$ 需要开long long，而 $a[i]*b[i]*i$ 不需要开。我的建议是：

1.直接全开：
不过这样会有一点点MLE的风险（当然啦，不多）。但是这样真的比较保险。

2.分析全面：
这是很难做到的。比如说S组四个小时，你就算带一箱子精神饮料，也未必能保证每时每刻你的精神都足够好。想要分析全面，最好的方法是检查。第一次如果难免疏漏，那就用后面的时间来补。这种习惯建议从小题养起，不然等到考场上，挂分的就是你。（比如你样例全过了之后，不着急交，而是返回检查）

回到我真正想说的：将时间复杂度比较高的循环分解

这是这道题目很妙的一个点。如果正常人来做，你第一时间可能会想到这个代码：

没写完

二叉堆

P3378 堆

给定一个数列，初始为空，请支持下面三种操作：

给定一个整数 $x$ ，请将 $x$ 加入到数列中。
输出数列中最小的数。
删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

堆是建立在完全二叉树基础上的一种数据结构，首先了解完全二叉树的存储方式：

观察每个结点的编号，可以得出两个结论：

1. $x$ 结点的父亲节点编号是 $\lfloor \frac{x}{2} \rfloor$

2.编号为 $x$ 的节点左子节点编号是 $2x$ ，右子节点编号是 $2x+1$

依靠着这种性质，如果想找一个节点的父亲或孩子，只需要对下表进行算术运算。这种存储方式叫做“堆式存储”经常用于存储二叉堆之类的完全二叉树。只需要一个数组，就可以存储二叉堆。

二叉堆是一棵树，每个节点有一个值。满足以下性质：1.二叉堆是一颗完全二叉树 2.对于大根堆而言，父节点的值一定大于或等于子节点的值。小根堆刚好相反。

这是一个大根堆示例：

这是一个小根堆示例：

接下来我们来看看如何完成题目中的三个要求：

1.输出数列中最小的数：这个比较简单，直接输出数组中的第一个值就好了

2.将元素 $x$ 加入集合

首先，我们先将 $x$ 放入树的尾部

这个时候，我们需要考虑到 $x$ 有可能会违反二叉堆的性质2，所以我们需要对二叉堆进行调整和修复。“修复”是二叉堆的主要思想。

刚刚插入的节点在最底层，对它进行以下操作：

(1).如果它大于等于自己的父节点，或者已经是根，停止操作

(2).如果它小于自己的父节点，将它的父节点和自己交换位置。然后对父节点执行同样的操作。（这里建议配合下面的代码一起理解，不然可能会对“父节点”是谁产生混淆）

3.删除堆顶元素

我们显然不能直接将堆顶元素去除。不然二叉树就没有头了，它会彻彻底底地分裂成两半。我们在此选择将堆顶元素和最后一个元素互换位置，然后开始修复。这次修复的逻辑和加入集合的修复逻辑差不多。

(1).如果自己已经是叶子节点，或者数值比自己的两个自己点小，停止操作

(2).否则，把自己与子结点中数值较小的那个交换，然后继续修复。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
void pus_h(int x){
	if(x==1||a[x]>=a[x/2])return;
	swap(a[x],a[x/2]);
	pus_h(x/2);
}
int sum;
void po_p(int x){
	if(x*2>sum||(a[x]<=a[x*2]&&a[x]<=a[x*2+1]))return;
	int sw=0;
	if(a[x*2]<a[x*2+1])sw=x*2;
	else sw=x*2+1;
	swap(a[x],a[sw]);
	po_p(sw);
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<=n+1;i++)a[i]=INT_MAX;
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1){
			int x;
			cin>>x;
			//x要加入数列
			a[++sum]=x;
			pus_h(sum); 
		}
		if(op==2)cout<<a[1]<<'\n';
		if(op==3){
			//要删除数列中的最小值
			swap(a[1],a[sum]);
            a[sum]=INT_MAX;
            sum--;
			po_p(1); 
		}
	}
	return 0;
}

堆排序
一个堆的应用，和上一题是相似的逻辑。
所有需要的零部件也是一样的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int sum;
void pus_h(int x){
	if(x==1||a[x]>=a[x/2])return;
	swap(a[x],a[x/2]);
	pus_h(x/2);
}
void po_p(int x){
	if(x*2>sum||(a[x]<=a[x*2]&&a[x]<=a[x*2+1]))return;
	int now=0;
	if(a[x*2]<a[x*2+1])now=x*2;
	else now=x*2+1;
	swap(a[now],a[x]);
	po_p(now);
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n+1;i++)a[i]=INT_MAX;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[++sum]=x;
		pus_h(sum);
	}
	for(int i=1;i<=n;i++){
		cout<<a[1]<<" ";
		swap(a[1],a[sum]);
		a[sum]=INT_MAX;
		sum--;
		po_p(1);
	}
	return 0;
}

优先队列

P1090 合并果子
一个比较容易的贪心，每次选择最小的两堆加在一起，把这个每次加出来的和用一个 $ans$ 加在一起，然后把加出来的和重新塞进优先队列里，重复上述操作即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;
priority_queue<int,vector<int>,greater<int>>q;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		q.push(x);
	}
	while(q.size()!=1){
		int a1=q.top();
		q.pop();
		int a2=q.top();
		q.pop();
		q.push(a1+a2);
        ans+=(a1+a2);
	}
	cout<<ans;
	return 0;
}

P2168 河马史诗

前置知识点：哈夫曼树

1.基础定义

给定 $n$ 个带权叶子节点 $w_1,w_2,w_3,...,w_n$ ，构造一棵二叉树，带权路径总长最小，即为哈夫曼树。

·带权路径长度:

$WPL = \sum_{i = 1}^{n}w_i*l_i$

· $l_i:$ 叶子 $w_i$ 路径长度：根 ——> 该节点经过的边数

构造规则：

(1).初始时，每个节点各为单节点树

(2).每次选出根节点权值最小的两棵树，新建父节点，权=两子权之和，合并为新树

(3).放回森林，重复直到只剩下一棵树

2.哈夫曼树性质

(1).无度为1的节点（度：一个节点相连的边的条数）
哈夫曼树中所有的节点要么有两个子节点，要么是个叶子节点。

BIT逆序对

2026/6/8

未来想要多尝试思维独立。自从拿了深入浅出的教材书，感觉自己有点太依赖教材，失去了独立思考的能力。所以每道题会分为两个部分：1.自己独立思考20min思考出的部分内容 2.看完题解理解并融会贯通后的内容

P11380 [GESP202412 八级] 排队

自己的思考部分：
将 $m$ 对这样的关系建模成图，统计图上一共有多少个连通块，设一共有 $x$ 个连通块。
问题在于如何判断有没有相互违背的关系，还需要去重边。
违背关系应该不止需要一个判断方面：1.两人需要在队伍中相邻。这个我已经想到办法了，我可以统计它们的入度。如果一个点的入度 $>1$ 就代表有问题，直接输出 $0$ 即可.

难点在于如何统计“互相违背”，就像是样例 $3$ 中的那种情况。将这种有可能很复杂的情况进行简化，就会变成： $A$ 要在 $B$ 的前面， $B$ 又要在 $A$ 的前面，这种情况就会出问题。我认为这种情况化成图就会变成这样：

将这张图的情况简化成图，那么大致情况就是：编号三要在编号六前面，编号六又要在编号三前面，会出现问题。
如何将这种情况判断出来？我的初步判断是，它们会形成环。所以我只需要判断是否存在环就好了。
判断重边可以使用 $map$ ,它的时间复杂度是 $O(mlogm)$ 应该还不至于超时。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
map<int,int>mp[N];
vector<int>v[N];
int rd[N];
int vis[N];
bool sum=0;
void dfs(int x){
	for(int i=0;i<v[x].size();i++){
		vis[v[x][i]]++;
		if(vis[v[x][i]]>1){
			sum=1;
			return;
		}
		dfs(v[x][i]);
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(mp[x][y])continue;
		v[x].push_back(y);
		mp[x][y]=1;
		rd[y]++;
		if(rd[y]>1){
			cout<<0;
			return 0;
		}
	}
	int s=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		dfs(i);
		if(sum){
			cout<<0;
			return 0;
		}
		s++;
	}
	long long ans=1;
	for(int i=s;i>=1;i--)ans=(ans*i)%mod;
	cout<<ans;
	return 0;
}

用这段代码拿了 $40pts$ 。剩下的测试点看不了具体数据，就在外围看了看，发现大多是是误判为 $0$ 。为什么呢。

好吧我不太会。拼劲全力无法战胜。我要看题解。

看完题解后写的部分：我去看了一些和我思路相仿的题解，它们会使用并查集（应该是叫这个）去判环。但是我也不太能理解为什么我的判环会错。

列举一下自己的几个问题：
1.没有判断自环

实在是不太会调，发现自己的图论遍历和连通块判断这类比较基础的东西好像根本就没有学过（？）所以打算去寻觅一点别的图论题去写。

P3916 图的遍历

一开始写了一个很奇怪的MLE出来：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int dis[N];
int dfs(int x){
    if(dis[x])return dis[x];
	int sum=x;
	for(int i=0;i<v[x].size();i++){
		dis[v[x][i]]=max(v[x][i],max(dfs(v[x][i]),dis[v[x][i]]));
		sum=max(sum,dis[v[x][i]]);
	}
    dis[x]=sum;
	return sum;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(dis[i]){
			cout<<dis[i]<<" ";
			continue;
		}
		cout<<dfs(i)<<" ";
	}
	return 0;
}

问题主要集中在：会无限递归。
所以得加判断语句(vis)：

if(vis[x])return dis[x];
vis[x]=1;
vis[x]=0;

最后可以拿60pts。

写不动了。还要复习文化课。明天再调吧。可能后续会着重练一点图论基础相关的问题。

2026/6/9

先来梳理一下今天的文化课内容：1.语文练习册（20min）2.语文注释背诵(20min)3.数学一张卷子（30min)4.历史作文重写（15min）5.物理笔记整理（？）6.物理卷子半张（35min）
一共需要至少两个小时。所以我八点开始写文化课。OK。

另外我的数学老师和英语老师都和我说，我应该要试着去变得更细心，所以后续写代码的时候，我会尽量尝试仔细纠错，看看能不能一遍过。

P5318 【深基18.例3】查找文献

这是一道图论基础题。我打算从这里开始重新学一下图论。

自己的思考：唔。这道题是一道DFS和BFS的模板题嘛。然后还考了一点图的存储。那刚好把DFS和BFS复习一下。

DFS

（部分内容参考oi-wiki）
DFS是一种遍历或搜索树或图的算法，每次都朝着更深的节点走。行走路径大概像这样：

按照我以前的老师的说法，DFS有一种“不撞南墙不回头”的感觉，它会沿着一条路一直走，直到没有点可以让它继续遍历，而后它就返回，然后继续找路。

它一般是用递归函数实现的。（我有一个问题：为什么DFS会用函数实现，但是BFS一般用队列实现呢？关于这个没什么用但是我很好奇的问题我问了豆包，我直接把这个截图贴上来了，就不手打了）

我觉得这个还挺有意思的，是可以对日常做题产生启发的：你可以根据题目的逻辑去选择算法（或者说写程序）。DFS的操作需要它一层层深入，然后再一层层返回。这种操作方法就刚好对应了递归，而递归用函数实现。BFS中，一层一层的点都是平等的，先进先出，所以它用队列来实现。

DFS会在递归时，将自己遍历的点打上标记，遍历图的时候，跳过遍历过的顶点。

下面的代码是DFS的实现方案：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
bool vis[N];
void dfs(int x){
	cout<<x<<" ";
	vis[x]=1;
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		if(vis[to])continue;
		dfs(to);
	} 
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	dfs(1);
	return 0;
}

DFS的时间复杂度是 $O(n+m)$ ，空间复杂度是 $O(m)$ 。

BFS

广度优先搜索（又叫广度优先搜索）的遍历顺序与DFS不同。它每次都会访问一整层的节点，这一层访问完毕之后，再访问下一层。遍历顺序如下图所示：

BFS的遍历顺序会导致一个很直接的结果：BFS所遍历的路径是从起点开始最短的合法路径之一。因为这个特性，BFS天然地与“寻求最短路”适配，所以你可以发现最短路（dijkstra，bellman）都有一点BFS的影子，同时，如果图上的所有边权为1，那么你可以直接使用BFS进行求解。

BFS使用队列( $queue$ )实现：首先将头节点塞入队列。将队首元素视作当前元素，遍历所有与当前节点相邻的节点，如果没有标记，打上标记，并将其塞入队列。重复“将队首……到塞入队列”的操作，直到队列为空。

代码是这样的：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
bool vis[N];
queue<int>q;
void bfs(int x){
	memset(vis,0,sizeof vis);
	q.push(1);
	vis[1]=1;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		cout<<now<<" ";
		for(int i=0;i<v[now].size();i++){
			int to=v[now][i];
			if(vis[to])continue;
			vis[to]=1;
			a.push(to);
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	bfs(1);
	return 0;
}

但是不知道为什么。样例挂机了。重新阅读题目，发现题目要求说：如果有很多篇文章可以同时阅读，要先看较小的那篇。这个怎么弄呢。

在修改的过程中发现了一些问题：1.我输入的时候写的是for(int i=1;i<=n;i++)但是一共有 $m$ 条边。好鬼畜的错误。接下来做这样的修改就好了：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int>v[N];
bool vis[N];
queue<int>q;
int no[N],sum=0;;
void dfs(int x){
	cout<<x<<" ";
	vis[x]=1;
	sum=0;
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		if(vis[to])continue;
		no[++sum]=to;
	} 
	sort(no+1,no****um);
	for(int i=1;i<=sum;i++)dfs(no[i]);
}
void bfs(int x){
	memset(vis,0,sizeof vis);
	q.push(1);
	vis[1]=1;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		cout<<now<<" ";
		sum=0;
		for(int i=0;i<v[now].size();i++){
			int to=v[now][i];
			if(vis[to])continue;
			vis[to]=1;
			no[++sum]=to;
		}
		sort(no+1,no****un);
		for(int i=1;i<=sum;i++)q.push(no[i]);
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	dfs(1);
    cout<<'\n';
	bfs(1);
	return 0;
}

但是这样还是有问题。主要是在DFS里面。由于是递归，所以 $no$ 数组中的东西会随着递归变化。所以，我又进行了更改，并且通过了样例。
评测！

？我要验牌。

是这样的。如果把 $10^6$ 的数组开在一个不断递归的函数中，空间就会超限。那怎么办呢？

题解部分：我们可以将边现在开头排好。
代码长这样：

struct Node{
	int x,y;
}node[N];
bool cmp(Node a,Node b){
	return a.y<b.y;
}
for(int i=1;i<=m;i++)cin>>node[i].x>>node[i].y;
sort(node+1,node+1+m,cmp);
for(int i=1;i<=m;i++){
	v[node[i].x].push_back(node[i].y);
}

然后就过了。

由于洛谷的机子卡住了。在等的时候顺便写了一道入门。

然后我们看一下昨天把我给弄死的图的遍历。

我尝试把第八行的代码改成了：
if(vis[x]||dis[x])return dis[x];。现在TLE是不T了。WA了 $60pts$ 。

看题解。

2026/6/10

老样子，先来整理一下文化课的作业：1.半张困难数学卷子（35min）2.英语默写单（25min）3.复习物理(1h)。所以今天可以做3.5h。挺好。

书接上回。我看完题解了。我本来以为，这题只考图的遍历，没想到它还考了技巧（？）。
如果正常的遍历，我们对每一个点都进行一次DFS，时间复杂度为 $O(n(n+m))$ 。肯定会超时，拿到 $60pts$ 。如果你有一颗有点聪明的大脑，你会想到一个神奇的优化：在遍历一个点的过程中把路上的点一起给算了（就是我 $40pts$ 挂机的那个做法，有点类似于记忆化搜索）。但这种方法是错的。如果有一张这样的图：

比方说你现在在点 $2$ ，然后你就会以这个顺序遍历：2->3->4->5->2。你有可能在遍历别人的路上遍历到你自己。然后就看你的初始化和你的DFS怎么写的了。有可能是WA也有可能是TLE。

那么什么是正确的做法呢？我们需要做一个思想的转变：正难则反。当时我第一次听说应该是在某个排列组合的提里面，cjdst评论了几句，然后我就记住了，写在看来好像用于计算机也很合适。

包括后面的最短路里也很会有类似于反向建边的内容，感觉很相似。这道题的正确做法是：如果你找不到大的点，那就让大的点来找你。反向建边，从 $n$ 到 $1$ 去遍历顶点。从 $n$ 开始遍历，将遍历到的点的最大值设为 $n$ （因为当前以 $n$ 开头遍历，由于从大到小挨个遍历，所以被遍历到的点答案就是当前遍历正在遍历的点 $i$ ）。将每次遍历到的顶点标记，下次不再遍历。注意记得把开头的点标记，这是刚开始做图论的小朋友很容易忽略的地方。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
bool vis[N];
int dis[N];
void dfs(int x,int vv){
	dis[x]=vv;
	for(int i=0;i<v[x].size();i++){
		if(vis[v[x][i]])continue;
        vis[v[x][i]]=1;
		dfs(v[x][i],vv);
	}
	return;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[y].push_back(x);
	} 
	for(int i=n;i>=1;i--){
		if(vis[i])continue;
        vis[i]=1;
		dfs(i,i);
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}

P11380 [GESP202412 八级] 排队
重新搓了一版代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
vector<int>v[N];
int rd[N],cd[N];
int vis[N];
bool sum=0;
void dfs(int x){
	for(int i=0;i<v[x].size();i++){
		if(sum)return;
		vis[v[x][i]]++;
		if(vis[v[x][i]]>1)sum=1;
		dfs(v[x][i]);
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		rd[y]++,cd[x]++;
		if(rd[y]>1||cd[x]>1){
			cout<<0;
			return 0;
		}
	}
	int su=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;
		dfs(i);
		if(sum){
			cout<<0;
			return 0;
		}
		su++;
	}
	long long ans=1;
	for(int i=1;i<=su;i++)ans=(ans*i)%mod;
	cout<<ans;
	return 0;
}

?
我的心路历程：这次一定能对->可能能对->让我对吧求你了->我*

我知道可以用并查集做。但为什么我的DFS过不了。我不能理解。
我打算学习一下对拍。

我们需要几个东西：
1.一份肯定正确的代码 2.一份你想要知道对不对的代码 3.一个数据生成器 4.一个拍子

拍子比较简单，我们需要一份这样的代码：我忘记我的dev-c++用不了了。等我重新安装一下。在这个缝隙里，我们来看一下这个：

DAG与拓扑排序

因为拓扑排序没有系统性地学过。所以拓扑排序是现学的，大部分内容来自：深入浅出基础篇。

题目大意：有很多任务要完成，每一项任务都需要一定的时间。有些任务必须在另一些任务完成的情况下才能进行，把这些先要完成的工作成为准备工作。至少有一项任务不要求有准备工作，这个能够最早进行的工作成为任务一。现在需要完成的有 $n$ 个任务，并且这份清单是有一定的顺序的。杂物 $k$ 的准备工作只可能在杂物 $1$ 到 $k-1$ 。从 $1$ 到 $n$ 读入每个杂物的工作说明，计算出所有杂物都被完成的最短时间。互相没有关系的杂物可以同时工作。

分析：将整个任务关系建模成图。乐意发现这个图是一个有向无环图(杂物 $k$ 的准备只能在 $1$ 到 $k-1$ 中，即无环。工作有顺序，即有向)，简称 $DAG$ 。所有任务完成的最短时间取决于最晚被完成的那个任务。

问题简化成：求一个 $DAG$ 的最长链。

这里给出一个有动态规划思想的做法：用 $vis$ 数组来记录下需要完成这个任务的最短时间。然后考虑在DFS的过程中算出每个任务所需要的最短时间。由于每个人无必须在所有准备任务完成之后才能完成，所以完成每个任务所需要的最短时间就是其所有准备任务里面最晚完成的世间加上这个完成这个任务所需要的时间。

除此之外，我还要补充一个写代码的点：如何保证在dfs遍历一个点时，一个点所需要完成的任务都已经完成了？我们可以在每个点与别的点建边的时候，统计入度。

当我们建边的时候（绿）统计入度（黄）。当我们从点 $1$ 遍历到点 $5$ ，点 $5$ 会有一条与点 $1$ 相连的边，当我们for循环到这条边，我们就将入度为三的点 $2$ 的入度减一，后面点 $3$ 点 $5$ 依次类推即可，最后遍历到点五，点 $2$ 的入度为 $0$ ，这就代表它所有的预备任务都已经完成。可以开始遍历点 $2$ 了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
vector<int>v[N]; 
int ans=0;
int use[N],vis[N],rd[N];
void dfs(int x){
	for(int i=0;i<v[x].size();i++){
		vis[v[x][i]]=max(vis[v[x][i]],vis[x]+use[v[x][i]]);
		rd[v[x][i]]--;
		ans=max(ans,vis[v[x][i]]);
		if(rd[v[x][i]]==0)dfs(v[x][i]);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cin>>use[i];
		while(cin>>x){
			if(x==0)break;
			rd[i]++;
			v[x].push_back(i);
		}
	}
	vis[1]=use[1];
	dfs(1);
	cout<<ans;
	return 0;
}

好了，穿插了一点题外话。我们回到排队的拍子。

我们需要这么一段代码作为拍子：（接下来的这段代码来自oi-wiki，不过拍子都长得一样，文件名改一改也没什么区别了）

#include <cstdio>
#include <cstdlib>

int main() {
  // For Windows
  // 对拍时不开文件输入输出
  // 当然，这段程序也可以改写成批处理的形式
  while (true) {
    system("gen > test.in");  // 数据生成器将生成数据写入输入文件
    system("test1.exe < test.in > a.out");  // 获取程序1输出
    system("test2.exe < test.in > b.out");  // 获取程序2输出
    if (system("fc a.out b.out")) {
      // 该行语句比对输入输出
      // fc返回0时表示输出一致，否则表示有不同处
      system("pause");  // 方便查看不同处
      return 0;
      // 该输入数据已经存放在test.in文件中，可以直接利用进行调试
    }
  }
}

2026/6/11

分析一下有什么要做的文化课：1.数学卷子比较难的三道题（20min）2.化学三面练习（10min）今天剩的比较少，但是我马上要期末考试了，所以得复习化学，复习半个小时好了。那么我今天大概可以做三个半小时。今天想要做两道八级题，然后再做一点拓扑。还有对拍。

对拍

（对拍章节的大部分内容来自我一个老师录得视频，这个会讲的很详细，推荐看这个）

昨天写了拍子，今天来看看怎么写剩下的。比如如何生成数据。

#include<bits/stdc++.h>
using namespace std;
int main(){
    srand(time(0));
    int x,y;
    x=rand()%100;
    y=rand()%100;
    cout<<x<<" "<<y<<'\n';
    return 0;
}

这一段代码可以帮助我们生成两个 $int$ 类型的 $\le100$ 的随机数。
最后，我们需要一个肯定正确的代码和一个你想确定正不正确的代码。

然后我没来看一下它的集合体：

1.拍子

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t=0;
	while(1){
		cout<<"test:"<<t++<<'\n';
		system("data.exe > data.in");
		system("std.exe < data.in > std.out");
		system("solve.exe < data.in > solve.out");
		if(system("fc std.out solve.out > diff.log")){
			cout<<"WA\n";
			break;
		}		 
		cout<<"AC\n";
	}
	return 0;
}

（这里的"data","std","solve"都是文件名，如果需要更改的话不能只改这份对拍里的文件名哦）

2.一定正确的代码： $solve$ （这份代码的名字叫 $solve$ ）

#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,y;
	cin>>x>>y;
	cout<<x+y;
}

3.想知道是否正确的代码： $std$

#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,y;
	cin>>x>>y;
	if(x==1)cout<<y;
	else cout<<x+y;
	return 0;
}

4.数据生成器 $data$

#include<bits/stdc++.h>
using namespace std;
int main(){
	srand(time(0));
	int x,y;
	x=rand()%100;
	y=rand()%100;
	cout<<x<<" "<<y<<'\n';
	return 0;
}

注意：这四份代码需要在同一个文件夹里，也就是这样：

（多出来的那些文件是需要运行拍子得到的）

它们在你的dev中应该是这样呈现的：

最后，运行拍子（我这里的命名是duipai，你们可以写自己的名字），它就会弹出一个运行框，效果大概是这样：

如果你想知道自己的代码“WA”在了哪里，你可以看这些文件

$data.in$ 是当前的输入， $diff.log$ 里面有两份不同的文件分别的输入。

好了，对拍的内容就说完了，我们来看一下八级的题目：

八级-排队

这道题我已经做了好几天了，没能看出来为什么做错了，所以就拿拍子拍一下好了。
我先得写一份一定正确的代码：

~~? 就这么对我。~~

好的，接下来来看一下我正确的代码，~~忽略掉刚刚的意外~~。
这是一个用并查集判环（应该是这么叫）的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int c[N],rd[N],cd[N];
vector<int>v[N];
map<int,int>mp[N];
int f(int x){
	return (x==c[x])?c[x]:c[x]=f(c[x]);
}
bool vis[N];
int sum=0;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)c[i]=i;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
        if(mp[x][y])continue;
		rd[y]++,cd[x]++;
		if(rd[y]>1||cd[x]>1){
			cout<<0;
			return 0;
		}
		mp[x][y]=1;
		if(f(x)==f(y)){
			cout<<0;
			return 0;
		}
		c[f(y)]=f(x);
	}
	for(int i=1;i<=n;i++){
		if(!vis[f(i)])sum++;
		vis[f(i)]=1;
	}
	long long ans=1;
	for(int i=1;i<=sum;i++)ans=(ans*i)%mod;
	cout<<ans;
	return 0;
}

然后附上我错误的代码（但是我不知道哪里错了）：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
vector<int>v[N];
int rd[N],cd[N];
int vis[N];
map<int,int>mp[N];
bool sum=0;
void dfs(int x){
	for(int i=0;i<v[x].size();i++){
		if(sum)return;
		vis[v[x][i]]++;
		if(vis[v[x][i]]>1)sum=1;
		dfs(v[x][i]);
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(mp[x][y])continue;
		mp[x][y]=1;
		v[x].push_back(y);
		rd[y]++,cd[x]++;
		if(rd[y]>1||cd[x]>1){
			cout<<0;
			return 0;
		}
	}
	int su=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;
		dfs(i);
		if(sum){
			cout<<0;
			return 0;
		}
		su++;
	}
	long long ans=1;
	for(int i=1;i<=su;i++)ans=(ans*i)%mod;
	cout<<ans;
	return 0;
}

将它们一个放在 $solve$ ，一个放在 $std$ 。

然后做一个数据生成器。

#include<bits/stdc++.h>
using namespace std;
int main(){
	srand(time(0));
	int n=rand()%10+1;
	int m=rand()%6+1;
	cout<<n<<" "<<m<<'\n';
	for(int i=1;i<=m;i++){
		cout<<rand()%n+1<<" "<<rand()%n+1<<'\n';
	}
	return 0;
}