本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-25 20:55:35

题目

期望概率题目。
题目简述：
有两种选择：

• 花费 $x$ 元把 $n$ 变成 $\lfloor\frac{n}{a}\rfloor$。
• 花费 $y$ 元，扔一次骰子得到一个数 $p(1\le p\le 6)$，把 $n$ 变成 $\lfloor\frac{n}{p}\rfloor$。

求花费钱数的期望（不同操作得到的所有钱数的平均值），误差不大于 $10^{-6}$。

我们先往暴力的方向想，定义 $f_i$ 表示 $n=i$ 时的期望，按照题目中的意思写状态转移方程：
$$f_i=\begin{cases}0&i=0\\min(f_{\lfloor\frac{i}{a}\rfloor}+y,\frac{\sum_{p=1}^{6}f_{\lfloor\frac{i}{p}\rfloor}}{6}+x)&otherwise\end{cases}$$ 但是，$f_i$ 又引用了 $f_i$，显然得不出正确答案，我们把式子变换一下： $$\begin{aligned}\frac{\sum_{p=1}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+x&=\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+\frac{f_i}{6}+x\&=\frac{6}{5}(\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{6}+x)\&=\frac{\sum_{p=2}^6f_{\lfloor\frac{i}{p}\rfloor}}{5}+\frac{6}{5}x\end{aligned}$$ 这样我们就可以得到 $f_i$ 了。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
int n,a,x,y;
map<int,double>mp;
inl double dfs(int n){
	if(n==0) return 0;
	if(mp[n]) return mp[n];
	double tmp=0;
	rep(i,2,6) tmp+=dfs(n\/i);
	return mp[n]=min((tmp)\/5.0+y\/5.0*6,dfs(n\/a)+x);
}
signed main(){
	FAST;
	cin>>n>>a>>x>>y;
	cout<<fixed<<setprecision(15)<<dfs(n);
	return 0;
}	

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-26 16:39:03

题目

递推题。
题目简述：给你 $a,b,c,p,n$，使 $x_1,x_2$ 为 $ax^2+bx+c=0$ 的两根，求 $(x_1^n+x_2^n)\bmod p$。

众所周知，一元二次方程的公式是 $\displaystyle x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$，但是最后的小数取模就很难弄，我们应该换个思路。

我们往递推的角度想，设 $f_i=(x_1^i+x_2^i)\bmod p$，则：
$$\begin{aligned}f_i&=(x_1^i+x_2^i)\bmod p\&=(x_1^i+x_2^i+x_1^{i-1}x_2+x_1x_2^{i-1}-x_1^{i-1}x_2-x_1x_2^{i-1})\bmod p\&=((x_1+x_2)(x_1^{i-1}+x_2^{i-1})-x_1x_2(x_1^{i-2}+x_2^{i-2}))\bmod p\&=((x_1+x_2)f(i-1)-x_1x_2f(i-2))\bmod p\end{aligned}$$ 这样我们就推出了状态转移方程，那么（$\Delta=b^2-4ac$）： $$\begin{aligned}x_1+x_2&=\frac{-b+\sqrt\Delta}{2a}+\frac{-b-\sqrt\Delta}{2a}\&=\frac{-b+\sqrt\Delta-b-\sqrt\Delta}{2a}\&=\frac{-2b}{2a}\&=\frac{-b}{a}\end{aligned}$$ 我们用 exgcd（费马小定理也可以）求逆，exgcd 详见 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 讲解。
$$\begin{aligned}x_1x_2&=(\frac{-b+\sqrt\Delta}{2a})(\frac{-b-\sqrt\Delta}{2a})\&=\frac{(-b+\sqrt\Delta)(-b-\sqrt\Delta)}{4a^2}\&=\frac{b^2-b\sqrt\Delta+b\sqrt\Delta-\Delta}{4a^2}\&=\frac{b^2-\Delta}{4a^2}\&=\frac{b^2-(b^2-4ac)}{4a^2}\&=\frac{4ac}{4a^2}\&=\frac{c}{a}\end{aligned}$$ 同上用 exgcd 求 $\displaystyle\frac{c}{a}$。

这样我们成功得到了矩阵 $res$：
$$\begin{bmatrix}\frac{-b}{a}&-\frac{c}{a}\
&0\end{bmatrix}$$ 然后我们得到 $res^{n-2}$，再来一个矩阵 $ans$： $$\begin{bmatrix}f_2\f_1\end{bmatrix}$$ $\displaystyle f_1=\frac{-b}{a}$，我们再求 $f_2$： $$\begin{aligned}f_2&=x_1^2+x_2^2\&=x_1^2+x_2^2+2x_1x_2-2x_1x_2\&=(x_1+x_2)^2-2x_1x_2\&=(\frac{-b}{a})^2-\frac{2c}{a}\end{aligned}$$ 这样 $res^{n-2}\times ans$ 的 $a_{1,1}$ 就是答案。

代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
int a,b,c,p,n,x,y,sum,ts,numm; 
struct matrix{
	int a[5][5];
	inl matrix init(){
		matrix res;
		memset(res.a,0,sizeof(res.a));
		return res;
	} 
	inl matrix init2(){
		matrix res=init();
		res.a[1][1]=res.a[2][2]=1;
		return res;
	}
	inl friend matrix operator*(matrix a,matrix b){
		matrix res=res.init();
		rep(i,1,2)
			rep(j,1,2)
				rep(k,1,2) (res.a[i][j]+=a.a[i][k]*b.a[k][j])%=p;
		return res;
	}
	inl friend matrix operator^(matrix a,int b){
		matrix num=a,ans=ans.init2();
		while(b){
			if(b&1) ans=ans*num;
			num=num*num;
			b>>=1;
		}
		return ans;
	}
}ans,num;
inl void exgcd(int a,int b,int p){
	if(p==0){
		x=a;
		y=0;
		return;
	}
	exgcd(a,p,b%p);
	int tx=x;
	x=y;
	y=tx-b\/p*y;
}
signed main(){
	FAST;
	cin>>a>>b>>c>>p>>n;
	exgcd(-b,a,p);
	sum=((x%p)+p)%p;
	exgcd(c,a,p);
	ts=((x%p)+p)%p;
	numm=(sum*sum%p-(ts<<1)%p+p)%p;
	ans=num=ans.init();
	num.a[1][1]=numm;
	num.a[2][1]=sum;
	ans.a[1][1]=sum;
	ans.a[1][2]=((-ts)%p+p)%p;
	ans.a[2][1]=1;
	if(n==1){
		cout<<sum;
		return 0;
	}
	if(n==2){
		cout<<numm;
		return 0;
	}
	ans=ans^(n-2);
	ans=ans*num;
	cout<<ans.a[1][1];
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 12:35:30

这道题我会讲解很多种思路。

30 分做法：

暴力枚举这条路的每个点， 取最小值。
时间复杂度为 $O(nt)$

70 分做法：

通过分析， 我们发现只需要考虑这 $n$ 个房子即可。（样例是迷惑你的）
为什么呢？
因为若左边的人数比右边多， 按照少数服从多数的原则， 应往左找左边那个点， 右边也一样。
若两边人数相同， 则在左边那个点到右边那个点这个区间代价是一样的。
时间复杂度为 $O(n^2)$。

100 分做法 1：

我们用前缀和和后缀和来维护， 设 $sum_i$ 为这个点左边的人走到这个点的代价，$summ_i$ 是右边的代价。
最后枚举每个点即可。
时间复杂度为 $O(n)$。
代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll n,l,x[100005],r[100005],sum[100005],summ[100005],num,numm,minn=INF;
int main(){
	cin>>l>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>r[i];
	for(int i=2;i<=n;i++){
		num+=r[i-1];
		sum[i]=sum[i-1]+(x[i]-x[i-1])*num;
	}
	for(int i=n-1;i;i--){
		numm+=r[i+1];
		summ[i]=summ[i+1]+(x[i+1]-x[i])*numm;
	}
	for(int i=1;i<=n;i++) minn=min(minn,sum[i]+summ[i]);
	cout<<minn;
	return 0;
} 

100 分做法 2：

此做法是 $70$ 分做法的强剪枝， 若左边的人数加上这栋房子的人数还没右边多， 就不需要费时间算了。
代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],sum[100005],minn=0x3f3f3f3f3f3f3f3f;
int main(){
	cin>>l>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>r[i];
		sum[i]=sum[i-1]+r[i];
	}
	for(int i=1;i<=n;i++){
		if(sum[i]>=sum[n]-sum[i]&&sum[i-1]<=sum[n]-sum[i-1]){
			ll sum=0;
			for(int j=1;j<=n;j++){
				sum+=r[j]*abs(x[i]-x[j]);
			}
			minn=min(minn,sum);
		}
	}
	cout<<minn;
	return 0;
} 

最优解：

这就是题解里大佬的思路了， 我用快读快写优化了一下， 实际就是将上述满分做法 $1$ 写成了一个循环。

k=min(r[le],r[ri]);
r[le]-=k;
r[ri]-=k;

这一段表示左右两边有 $k$ 个人已经转移完成。

ans+=k*(x[ri]-x[le]);

这是累加答案，$(x_{ri}-x_{le})$ 实际就是双方向中间走的路程和。

if(!r[le]) ++le;
if(!r[ri]) --ri;

这是左右端点转移。
最终代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],ans,le=1,ri,k;
long long read(){
	long long f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
void write(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10){
		write(x\/10);
	}
	putchar(x%10^48);
}
int main(){
	l=read();
	ri=n=read();
	for(int i=1;i<=n;++i){
		x[i]=read();
		r[i]=read();
	}
	while(le<ri){
		k=min(r[le],r[ri]);
		r[le]-=k;
		r[ri]-=k;
		ans+=k*(x[ri]-x[le]);
		if(!r[le]) ++le;
		if(!r[ri]) --ri;
	}
	write(ans);
	return 0;
} \/\/44ms 最优解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-12 18:54:23

题目
相信很多人是被数据范围劝退的 $\dots\dots$
数据范围为：
$$1\le n,k\le 10^{10}$$ 你可能觉得输出 $10^{10}$ 个数是不可能的事情。
但是我们思考一下：
都知道高斯的求和公式吧：
$$\sum_k^{i=1} i=n(n+1)/2$$ 因为 $(1+1.5\times 10^5)(1.5\times 10^5)/2>10^{10}$， 所以当 $k\ge 1.5\times 10^5$ 的时候， 直接输出 $-1$ 就可以了。
上述行为是为了防止爆 long long， 再次特判， 若 $k(k+1)/2>n$， 则依然输出 $-1$。
然后我们设序列的第 $i$ 个数为 $a_i$， 最大公约数为 $m$， 根据同余定理， 不难得到：
$$n\bmod m=(\sum_k^{i=1}a_i)\bmod m=(\sum_k^{i=1}(a_i\bmod m))\bmod m=0$$ 所以， 我们需要找出 $n$ 的全部因数， 从大到小排个序， 做完上述步骤后的时间复杂度为 $O(\sqrt n+k\log_2k)$，简化为 $O(k\log_2 k)$， 是可承受的。
下一步我们枚举 $a_i$， 直到找到符合 $a_i\times (k(k+1)/2)\le n$ 条件的数， 最后输出即可， 此处的复杂度仅仅只有 $O(\sqrt n+k)$。
代码：

#include<bits\/stdc++.h>
using namespace std;
long long n,k,a[100005],summ,maxn;
bool cmp(long long x,long long y){ return x>y; }
void work(){
	for(long long i=1;i*i<=n;i++)
		if(n%i==0)
			if(i*i==n) a[++summ]=i;
			else{
				a[++summ]=i;
				a[++summ]=n\/i;
			}
	return;
}
int main(){
	cin>>n>>k;
	if(k>=150000){
		cout<<-1;
		return 0;
	}
	if((1+k)*k\/2>n){
		cout<<-1;
		return 0;
	}
	work();
	sort(a+1,a+summ+1,cmp);
	for(int i=1;i<=summ;i++)
		if(n*2\/k\/(k+1)>=a[i]){
			maxn=a[i];
			break;
		}
	for(int i=1;i<k;i++){
		cout<<i*maxn<<' ';
		n-=i*maxn;
	}
	cout<<n;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-26 15:33:17

看一眼题目， 就能发现是一道裸 dp 题。
既然是 dp， 那就三步走起：

第 1 步： 设状态

下面的 $n$，$a_i$ 如题所述， 我们将连击 $i$ 次得到的奖励设为 $cc_i$，$dp_{i,j}$ 为在第 $i$ 时刻连击 $j$ 次能够得到的最大分数， 初始时设 $dp_{1,0}$ 为 $0$。
这样最后的答案就是 $\max(dp_{n,j})(1\le j\le n)$。

第 2 步： 设状态转移方程

根据题意， 在第 $i$ 时刻， 若不点击，那么 $dp_{i,0}$ 就等于：
$$dp_{i,0}=\max(dp_{i-1,k})(1\le k\le n)$$ 那若点击， 即 $j\ne 0$， 那么 $dp_{i,j}$ 就等于：
$$dp_{i,j}=dp_{i-1,j-1}+a_i+cc_j$$ 写在一起就是：
$$dp_{i,j}=\begin{cases}\max(dp_{i-1,k})(1\le k\le n)&(j=0)\\dp_{i-1,j-1}+a_i+cc_j&(j\ne 0)\end{cases}$$ 思路有了， 实现还会远吗？

第 3 步： 写代码

写的时候， 我们发现这道题与其他题一样， 第一维也是可以压掉的， 只需要开个变量暂存最大值， 循环方向从顺序改为逆序即可。
代码：

#include<bits\/stdc++.h>
using namespace std;
long long n,m,a[5005],b,c,dp[5005],cc[5005],ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>b>>c;
		cc[b]=c;
	}
	for(int i=1;i<=n;i++){
		long long maxn=0;
		for(int j=1;j<=i;j++) maxn=max(maxn,dp[j]);
		for(int step=i;step>=1;step--) dp[step]=dp[step-1]+a[i]+cc[step];
		dp[0]=maxn;
	}
	for(int step=1;step<=n;step++) ans=max(ans,dp[step]);
	cout<<ans;
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 15:46:21

• 注： 2024.1.31 更新 tarjan 做法

倍增做法

题目
这道题是一道模板题， 很适合来练练手。

建树+dfs：

建树就不多说了， 你可以把它当成一个图来建， 用动态数组和结构体都可以。
但是不管用哪种方法， 都需要用 dfs 来辅助， 确认它们的父子关系， 详细解释看代码。
dfs 代码：

void dfs(int now,int step){
	maxdep=max(maxdep,step);\/\/maxdep表示这棵树的深度
	vis[now]=true;\/\/打访问标记
	dep[now]=step;\/\/记录该点的深度
	for(int i=0;i<g[now].size();i++)\/\/枚举
		if(!vis[g[now][i]]){
			fath[g[now][i]][0]=now;\/\/记录父亲
        		 \/\/这里fath[i][0]表示 i 点的父亲，fath[i][1]表示其父亲的父亲
        		 \/\/以此类推
			dfs(g[now][i],step+1);\/\/继续dfs
		}
	return;\/\/结束
}

确认祖先：

这里， 确认祖先的思想与 ST 表很接近， 都是先枚举 $j$， 这道题就是 ST 表的模板题。
那么我们思考一下， 例如这棵树：

可以看到， 这棵树上的 $5$ 的父亲是 $4$，$4$ 的父亲是 $2$，$2$ 就是 $5$ 的父亲的父亲。(废话)
所以我们得到：
$$fath_{i,j}=fath_{fath_{i,j-1},j-1}(1\le i\le n,1\le j\le \log_2(maxdep-1))$$ 那么， 我们可以提前维护一个数组来维护 $\log_2(x)(1\le x\le n)$， 我给它命名为 $lg$。
维护 $lg$ 代码：

lg[1]=0;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;

维护 $fath$ 代码：

for(int len=1;len<=lg[maxdep-1];len++)
	for(int i=1;i<=n;i++) fath[i][len]=fath[fath[i][len-1]][len-1];

终于要 LCA 了！

暴力跳：

LCA 的第一步是要保证两个点的深度相同， 不相同则让更深的那个点跳到与较浅的那个点一样深， 再让两个点一起向上跳， 直到两点重合。
说起来轻松， 但若这个点特别深， 难道要一层一层的向上跳吗？

正解：

那么， 我们假如这个点要跳 $19$ 层， 对 $(19)_{10}$ 进行二进制拆分是 $(010011)_2$。
我们发现， 实际就是下面这样一个过程：

1. 判断剩余要跳的层数的二进制的第 $i$ 位是否是 $1$（实际上就是在判断往上跳 $2^i$ 层后有没有超过另一个点）， 如果是 $1$， 转至第 $2$ 步， 否则， 转至第 $3$ 步。
2. 向上跳 $2^i$ 层， 并转至第 $3$ 步。
3. $i$ 减一（就是要判断下一位）， 并判断两点深度是否相同， 若相同， 则退出循环， 否则， 转至第 $1$ 步。

在两点同时跳时， 也是这样一个过程。
代码：

for(int i=1;i<=m;i++){
		u=read();
		v=read();
		if(dep[u]<dep[v]) swap(u,v);\/\/保证u的层数大于等于v的层数
		for(int j=lg[maxdep-1];j>=0&&dep[u]>dep[v];j--)
			if(dep[fath[u][j]]>=dep[v]) u=fath[u][j];\/\/让u向上跳
		if(u==v){\/\/特判
			write(u);
			putchar('\n');
			continue;
		}
		for(int j=lg[dep[u]];j>=0;j--)\/\/让两点同时向上跳
			if(fath[u][j]!=fath[v][j]){
				u=fath[u][j];
				v=fath[v][j];
			}
		write(fath[u][0]);
		putchar('\n');
	}

总代码：

#include<bits\/stdc++.h>
#define N 500005
#define int long long
using namespace std;
vector<int>g[N];
int n,m,s,dep[N],fath[N][30],u,v,maxdep,lg[N];
bool vis[N];
int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
void write(int x){
	if(x<0) x=-x;
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
void dfs(int now,int step){
	maxdep=max(maxdep,step);
	vis[now]=true;
	dep[now]=step;
	for(int i=0;i<g[now].size();i++)
		if(!vis[g[now][i]]){
			fath[g[now][i]][0]=now;
			dfs(g[now][i],step+1);
		}
	return;
}
signed main(){
	n=read();
	m=read();
	s=read();
	lg[1]=0;
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<n;i++){
		u=read();
		v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(s,1);
	for(int len=1;len<=lg[maxdep-1];len++)
		for(int i=1;i<=n;i++) fath[i][len]=fath[fath[i][len-1]][len-1];
	for(int i=1;i<=m;i++){
		u=read();
		v=read();
		if(dep[u]<dep[v]) swap(u,v);
		for(int j=lg[maxdep-1];j>=0&&dep[u]>dep[v];j--)
			if(dep[fath[u][j]]>=dep[v]) u=fath[u][j];
		if(u==v){
			write(u);
			putchar('\n');
			continue;
		}
		for(int j=lg[dep[u]];j>=0;j--)
			if(fath[u][j]!=fath[v][j]){
				u=fath[u][j];
				v=fath[v][j];
			}
		write(fath[u][0]);
		putchar('\n');
	}
	return 0;
}

tarjan 上的 dfs:

当然， 倍增有些人可能觉得有些难， 那么我再来补一下 tarjan 做法。

简介 tarjan

先放个图： 假设我要求 $4$ 和 $7$，$4$ 和 $10$ 的 LCA， 那么我们再建个图。 然后我们进行 dfs， 搜到哪里就在哪里打访问标记， 并确定父子关系。
等到遍历完成后， 再来到第二个图， 按照第一个图的父子关系进行查找。
详细流程如下：

建图

第一步还是建图， 不过这次我用结构体再建一遍。
代码如下：

void add(int x,int y){\/\/原图
	t[++tot].to=y;
	t[tot].nxt=head[x];
	head[x]=tot;
   	return;
}
void addx(int x,int y){\/\/节点关系建图
	tx[++totx].to=y;
	tx[totx].nxt=headx[x];
	headx[x]=totx;
   	return;
}
\/\/以上均为模板，不再赘述
\/\/主程序内调用
for(int i=1;i<n;i++){
   u=read();
   v=read();\/\/原图
   add(u,v);
   add(v,u);
}
for(int i=1;i<=m;i++){
   u=read();
   v=read();
   addx(u,v);\/\/节点之间建图
   addx(v,u);\/\/注意，单向建图与双向建图会影响后面的代码
}

tarjan 操作

这里将结构体 dfs 模板修改一下即可。
详细解释看代码：

void tarjan(int now){
    vis[now]=true;\/\/打访问标记，还是dfs的套路
    for(int i=head[now];i;i=t[i].nxt){\/\/原图dfs
        int ta=t[i].to;
        if(vis[ta]) continue;\/\/不重复查找
        tarjan(ta);\/\/递归调用
        fa[ta]=now;\/\/修改父子关系
    }
    for(int i=headx[now];i;i=tx[i].nxt){\/\/结点关系dfs
        int ta=tx[i].to;
        if(vis[ta]){
        	lca[i]=find(ta);\/\/查找函数代码在下面
        	if(i&1) lca[i+1]=lca[i];\/\/这里就是刚刚说的不一样， 由于双向建边导致需要存两次， 不然会出错
        	else lca[i-1]=lca[i];
		}
    }
    return;\/\/结束
}

find 函数代码：

int find(int u){
	if(u!=fa[u]) fa[u]=find(fa[u]);
	return fa[u];
}\/\/标准find函数

输出就不用看了吧
总代码：

#include<bits\/stdc++.h>
#define N 500005
#define int long long
using namespace std;
struct trees{
	int to,nxt;
}t[N<<1],tx[N<<1];
int n,m,s,u,v,head[N<<1],tot,headx[N<<1],totx,fa[N<<1],lca[N<<1];
bool vis[N<<1];
int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
void write(int x){
    if(x<0) x=-x;
    if(x>=10) write(x\/10);
    putchar(x%10^48);
}
void add(int x,int y){
	t[++tot].to=y;
	t[tot].nxt=head[x];
	head[x]=tot;
    return;
}
void addx(int x,int y){
	tx[++totx].to=y;
	tx[totx].nxt=headx[x];
	headx[x]=totx;
    return;
}
int find(int u){
	if(u!=fa[u]) fa[u]=find(fa[u]);
	return fa[u];
}
void tarjan(int now){
	vis[now]=true;
	for(int i=head[now];i;i=t[i].nxt){
        int ta=t[i].to;
        if(vis[ta]) continue;
        tarjan(ta);
        fa[ta]=now;
    }
    for(int i=headx[now];i;i=tx[i].nxt){
        int ta=tx[i].to;
        if(vis[ta]){
        	lca[i]=find(ta);
        	if(i&1) lca[i+1]=lca[i];
        	else lca[i-1]=lca[i];
		}
    }
    return;
}
signed main(){
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<n;i++){
        u=read();
        v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=m;i++){
        u=read();
        v=read();
        addx(u,v);
        addx(v,u);
    }
    tarjan(s);
    for(int i=1;i<=m;i++){
    	write(lca[i<<1]);
    	putchar('\n');
	}
    return 0;
}

两者对比

tarjan 时间复杂度为 $O(n+m)$， 而倍增为 $O(n\log_2n)$，tarjan 更优。
但其致命缺陷也很明显， 就是无法修改。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-02 13:10:42

题目
本题考察内容： 排序， 贪心， 二分， 前缀。

40~60 分做法

首先我们先将初始成绩降序排序， 方便运行。
要使第 $i$ 位选手获得第一名， 那么就要让其获得 $n$ 分， 让第 $1$，$2$，$\dots$，$i-1$ 位选手获得 $1$，$2$，$\dots$，$i-1$ 分， 让第 $i+1$，$i+2$，$\dots$，$n$ 位选手获得 $i$，$i+1$，$\dots$，$n-1$ 分。
如果第 $i$ 位选手是第一名， 那么他就能当第一名； 否则他就不能当第一名。
上面就是我们的贪心思想。
时间复杂度为 $O(n^2)$， 无法通过 $n\le 3\times 10^5$ 的数据。

100 分做法一

我们发现， 在循环内我们做了许多无用的事情， 我们可以提前处理好一个前缀最值， 后面直接调用即可。
总体时间复杂度为 $O(n)$（撇开排序）， 可以通过。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register\/\/一点常数优化
using namespace std;
const int N=3e5+5; 
int a[N],n,maxx,sum;
inl int read(){\/\/快读函数， 可以直接用 cin 代替
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){\/\/快写， 可用 cout 代替
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
	return;
}
signed main(){
    n=read();
    for(reg int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+1+n,greater<int>());\/\/降序排序
    for(reg int i=1;i<=n;++i) maxx=max(maxx,a[i]+i);\/\/前缀最值
    for(reg int i=1;i<=n;++i)
        if(a[i]+n>=maxx) sum++;\/\/一重循环查找
    write(sum);
    return 0;
}

100 分做法二

我们发现， 如果第 $i$ 位选手能获得第一名， 那么第 $i-1$，$i-2$，$\dots$，$1$ 位选手都可以获得第一名； 如果第 $i$ 位选手不能获得第一名， 那么第 $i+1$，$i+2$，$\dots$，$n$ 为选手也不能获得第一名。
可以发现， 它具有单调性！
这说明， 此题可以使用二分。
时间复杂度为 $O(n\log_2n)$。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define N 300005
#define INF 2147483647
using namespace std;
int n,a[N],b[N];
inl int read(){
    reg int f=1,x=0;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0) x=-x;
    if(x>=10) write(x\/10);
    putchar(x%10^48);
}
inl bool check(int x){
    reg int tot=n-1;
    for(reg int i=1;i<=n;++i,--tot)
        if(b[i]!=a[x]&&(b[i]+tot>a[x]+n||b[i]+tot==a[x]+n&&i<x)) return false;\/\/这个判断条件可能有点难理解
    return true;
}
inl int lower(){\/\/二分模板
    reg int l=1,r=n,mid=0,ans=0;
    while(l<=r){
        mid=l+r>>1;\/\/位运算
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return ans;
}
signed main(){
    n=read();
    for(reg int i=1;i<=n;++i) a[i]=read();
    memcpy(b,a,sizeof(a));\/\/复制数组，一个降序排，一个升序排
    sort(a+1,a+n+1,greater<int>());
    sort(b+1,b+n+1);
    write(lower());\/\/查找到的答案即此题答案
    return 0;
}

100 分做法三

你可以发现， 这两种方法是可以组合在一起的！
这样的话， 查找的时间复杂度仅为 $O(\log_2n)$！
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define N 300005
#define INF 2147483647
using namespace std;
int n,a[N],maxx;
inl int read(){
    reg int f=1,x=0;
    reg char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0) x=-x;
    if(x>=10) write(x\/10);
    putchar(x%10^48);
}
int lower(){
    int l=1,r=n,mid=0,ans=0;
    while(l<=r){
        mid=l+r>>1;
        if(a[mid]+n>=maxx){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }
    return ans;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;++i) maxx=max(maxx,a[i]+i);\/\/两种方法组合在一起，不解释
    write(lower());
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-12 20:48:04

二叉搜索树？我为什么要用？
这道题是可以直接模拟的呀。
下面我们就来分析它的每一个操作：

1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。 查询 $x$ 的排名。
   由于集合中没有重复元素， 故可以直接使用 STL 中的 lower_bound()， 复杂度为 $O(\log_2n)$。
2. 查询排名为 $x(1\le x)$ 的数。
   直接调用，$O(1)$ 解决。
3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。 若不存在则输出 $-2147483647$。
   再次 lower_bound() 二分查找， 复杂度为 $O(\log_2n)$。
4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。 若不存在则输出 $2147483647$。
   upper_bound() 查找， 同上。
5. 插入一个数 $x$。
   先 lower_bound() 找出应插入的位置，再插入（用动态数组是因为不想手写 insert() 函数）， 复杂度为 $O(n)$。
   总体复杂度为 $O(n^2)$。
   代码：

#include<bits\/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF 2147483647
using namespace std;
vector<int>g;
int q,op,x;
inl int read(){
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}                
	return f*x;      
}                 
inl void write(int x){
	if(x<0){         
		x=-x;        
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
inl void solve(){
	reg int xx;
	op=read();
	x=read();
	switch(op){
		case 1:
			xx=lower_bound(g.begin(),g.end(),x)-g.begin();
			write(xx);
			putchar('\n');
			break;
		case 2:
			write(g[x]);
			putchar('\n');
			break;
		case 3:
			xx=lower_bound(g.begin(),g.end(),x)-g.begin();
			if(xx-1==g.end()-g.begin()||!(xx-1)) write(-INF);
			else write(g[xx-1]);
			putchar('\n');
			break;
		case 4:
			xx=upper_bound(g.begin(),g.end(),x)-g.begin();
			if(xx==g.end()-g.begin()) write(INF);
			else write(g[xx]);
			putchar('\n');
			break;
		case 5:
			g.insert(lower_bound(g.begin(),g.end(),x),x);
			break;
	}
	return;
}
signed main(){
	g.push_back(0);
	q=read();
	while(q--) solve();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 17:28:00

题意：

给你一个数 $n(1\le n\le 10^6)$， 求：
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ 的解数。

进入正题：

先推式子： $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ 通分， 得：
$$\frac{x}{xy}+\frac{y}{xy}=\frac{1}{n!}$$ $$\frac{x+y}{xy}=\frac{1}{n!}$$ 整理， 得： $$(x+y)n!=xy$$ $$xn!+yn!=xy$$ 移项， 得： $$xy-xn!-yn!=0$$ 配方， 得： $$xy-xn!-yn!+n!^2=n!^2$$ $$(x-n!)(y-n!)=n!^2$$ 然后我们就把这个问题转化为了 “$n!^2$ 有几个因数”， 又因为求因数和公式：
$$n=a_1^{q_1}a_2^{q_2}\dots\dots a_i^{q_i}$$ $$m=(q_1+1)(q_2+1)\dots\dots (q_i+1)$$ 得：
$$m^2=(2q_1+1)(2q_2+1)\dots\dots (2q_i+1)$$ 故首先要筛质数， 然后再分解质因数， 最后统计即可。
代码：

#include<bits\/stdc++.h>
#define INF 214748364721474836
#define int long long
#define endl '\n'
#define inl inline
#define reg register
using namespace std;
const int N=1e6+5,MOD=1e9+7;
int n,prime[N],cnt,ans=1,sum[N];
bool vis[N];
inl int read(){
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
signed main(){
	n=read();
	for(reg int i=2;i<=n;++i)
		if(!vis[i]){
			prime[++cnt]=i;
			for(reg int j=i;j<=n\/i;++j) vis[i*j]=true;
		}
	for(reg int j=1;j<=cnt;++j){
	 	int x=n;
			while(x){
				sum[j]+=x\/prime[j];
				x\/=prime[j];
		}
			
			}
	for(reg int i=1;i<=cnt;++i) ans=(ans*(sum[i]<<1|1))%MOD;
	write(ans);
	return 0;
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-19 11:16:11

题目
目标：在以最小的遍历次数通关地图的前提下，从地图内刷到的药水最多，输出药水数量。
下面我们开始分析。

最小的遍历次数：

在最优策略下，我们到达任意一点后，如果他有子节点，那么我们会继续向下遍历。
故最小的遍历次数为子树内叶结点的数量，我们可以用一遍 dfs 来统计以 $u$ 点为根节点的子树内叶结点的数量，我们用 $g_u$ 表示。
设 $v$ 点为 $u$ 点的子结点，易得转移方程：
$$g_u=\sum g_v$$

最大药水数量：

在以 $u$ 点位根节点的子树内能拾取到的药水数量我们用 $f_u$ 表示，其必然由其子结点转移而来，设其子结点为 $v$ 点。
在遍历之后出现的药水自然无法捡到，那设 $u$ 点能捡到的药水的数量为 $a_u$，那么在任意一颗子树内，它最多遍历 $g_u$ 次，最多能拾取到的药水数量为 $(\sum f_v)+a_u$，易得转移方程：
$$f_u=\max(g_u,(\sum f_v)+a_u)$$ $f_1$ 便为答案。
代码：

#include<bits\/stdc++.h>
#define INF 2147483647
#define int long long
#define endl '\n'
#define inl inline
#define reg register
using namespace std;
const int N=1e5+5;
vector<int>g[N];
int n,p[N],u,v,ye[N],yao[N];
bool flag[N],vis[N];
\/*
n,p如题所述，g,u,v为了建树，ye,yao等同于上述g,f,a(yao代替了f,a)
*\/
inl int read(){\/\/快读
	reg int f=1,x=0;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){\/\/快写
	if(x<0) x=-x;
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
inl void dfs1(int now){\/\/求叶结点数
	flag[now]=true;
	for(reg int i=0;i<g[now].size();++i)
		if(!flag[g[now][i]]){
			dfs1(g[now][i]);
			ye[now]+=ye[g[now][i]];
		}
	flag[now]=false;
	return;
}
inl void dfs2(int now){\/\/求拾取药水数
	flag[now]=true;
	for(reg int i=0;i<g[now].size();++i)
		if(!flag[g[now][i]]){
			dfs2(g[now][i]);
			yao[now]+=yao[g[now][i]];
		}
	yao[now]=min(yao[now],ye[now]);
	flag[now]=false;
	return;
}
signed main(){
	n=read();
	for(reg int i=1;i<=n;++i) p[i]=read();
	for(reg int i=1;i<n;++i){
		u=read();
		v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(reg int i=2;i<=n;++i)
		if(g[i].size()==1) ye[i]+=1;
	dfs1(1);
	for(reg int i=1;i<=ye[1];++i) ++yao[p[i]];
	dfs2(1);
	write(yao[1]);
	return 0;\/\/结束
}