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

前言：

主要是记录一下 $\text{\color{black}{皎}\color{red}{月半洒花}}$ 大佬的讲题思路

题目翻译：

给定一个 $n$，求由 $n$ 个点组成的无向连通图个数。
多测

正文：

用 $h_n$ 代表 $n$ 个点组成的无向图个数，$f_n$ 代表 $n$ 个点组成的无向连通图个数，$g_n$ 代表 $n$ 个点组成的无向不连通图个数。
来想一下每一项的计算方式：

• $h_n$
  $n$ 个点两两之间互相连边，一共有 $C_n^2$ 条。而每一条边可以存在也可以不存在，所以一共有 $2^{C_n^2}$ 种情况。
• $g_n$
  显然，$g_n = h_n - f_n$
• $f_n$
  可以将图分割成，「包含 $1$ 的连通块」和「其他点」两个集合。然后枚举 「包含 $1$ 的连通块」 集合的大小从 $1 \rightarrow n-1$。集合大小为 $i$ ，可以看作在 $n-1$ 个点中挑选 $i-1$ 个非 $1$ 的点，也就是 $C_{n-1}^{i-1}$。同时这 $i$ 个点还会以 $f_i$ 种形态组成连通图。另外 $n-i$ 个没有选上的点将以 $h_{n-i}$ 种形态组成图。最后答案就是 $\sum_1^{n-1} C_{n-1}^{i-1} \cdot f_i \cdot h_{n-i}$

现在知道了转移方法，就可以做了。

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

思路

选择的 $m$ 个区间的花费是其中最长的区间减去最短区间，那么，为了使花费最小，这 $m$ 个区间在长度排名上是要连续的。
所以先对这 $n$ 个区间排序，然后枚举每一个要选的区间。每枚举一个区间，都将区间中每一个点覆盖次数加一，然后判断是否有一个点的覆盖次数超过了 $m$ 次，那么就开始更新答案，具体细节：

1. 删除最先加入且还没被删的区间
2. 更新答案
3. 如果仍然有一个点的覆盖次数超过了 $m$ 次，go to step 1

至于区间覆盖次数记录，使用线段树记录即可，另外注意要离散化。

另注：
如果到最终也没有更新答案，那么无解

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=5e5+5;
	\/\/---------IO----------
	int n,m;
	struct Section
	{
		int l,r,len;
		bool operator <(const Section& b)
		{
			return len<b.len;
		}
	}sec[maxn<<3];
	int cnt;
	int all[maxn<<3];
	\/\/------Trie--------
	struct Trie
	{
		int max,lazy;
	}trie[maxn<<3];
	inline void push_down(int node)
	{
		if(trie[node].lazy==0)return;
		trie[node<<1].lazy+=trie[node].lazy;
		trie[node<<1].max+=trie[node].lazy;
		trie[node<<1|1].lazy+=trie[node].lazy;
		trie[node<<1|1].max+=trie[node].lazy;
		trie[node].lazy=0;
	}
	inline void push_up(int node)
	{
		trie[node].max=max(trie[node<<1].max,trie[node<<1|1].max);
	}
	void Modify(int node,int _l,int _r,int l,int r,int val)
	{
		if(_r<l||_l>r)
		{
			return;
		}
		if(_l>=l&&_r<=r)
		{
			trie[node].lazy+=val;
			trie[node].max+=val;
			return;
		}
		push_down(node);
		int mid=(_l+_r)>>1;
		if(l<=mid)Modify(node<<1,_l,mid,l,r,val);
		if(r>mid)Modify(node<<1|1,mid+1,_r,l,r,val);
		push_up(node);
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		int li,ri;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&li,&ri);
			all[++cnt]=li;
			all[++cnt]=ri;
			sec[i].l=li;
			sec[i].r=ri;
			sec[i].len=sec[i].r-sec[i].l;
		}
		sort(all+1,all+cnt+1);
		cnt=unique(all+1,all+cnt+1)-all-1;
		for(int i=1;i<=n;i++)
		{
			sec[i].l=lower_bound(all+1,all+cnt+1,sec[i].l)-all;
			sec[i].r=lower_bound(all+1,all+cnt+1,sec[i].r)-all;
		}
		sort(sec+1,sec+n+1);
		int fir=1;
		int ans=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
		{
			Modify(1,1,cnt,sec[i].l,sec[i].r,1);
			while(trie[1].max>=m)
			{
				ans=min(ans,sec[i].len-sec[fir].len);
				Modify(1,1,cnt,sec[fir].l,sec[fir].r,-1);
				fir++;
			}
		}
		if(ans==0x3f3f3f3f)
		{
			printf("-1");
		}
		else
		{
			printf("%d",ans);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

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

做法

使用差分来做，设 $cf_i$ 表示 $i$ 点到根节点的路径上每一个点加上 $cf_i$。这样对于 $u \rightarrow t$ 的路径上每一个点加一，处理方式如下：

1. $cf_u$ 加一
2. $cf_t$ 加一
3. $cf_{lca(u,t)}$ 减一
4. $cf_{lca(u,t).father}$ 减一

这是十分显然的。然后 dfs 处理出每个点的值大小即可
另外，由于每个 $a_i (i \in [2,n-1])$都算了两次（既做过起点又做过终点），所以这些点要减去 1，对于 $a_n$，因为这个点不需要作为终点单独放置糖，但是计算的时候它被作为终点算了一次，所以也要减去 1。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=3e5+5;
	int a[maxn];
	int n;
	int head[maxn<<1];
	ll cf[maxn];
	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 dep[maxn];
	int father[maxn][31];
	void dfs(int u,int fa)
	{
		dep[u]=dep[fa]+1;
		father[u][0]=fa;
		for(int i=1;i<=30;i++)
		{
			father[u][i]=father[father[u][i-1]][i-1];
		}
		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=30;i>=0;i--)
		{
			if(dep[father[a][i]]>=dep[b])
			{
				a=father[a][i];
			}
		}
		if(a==b)return a;
		for(int i=30;i>=0;i--)
		{
			if(father[a][i]!=father[b][i])
			{
				a=father[a][i];
				b=father[b][i];
			}
		}
		return father[a][0];
	}
	void dfs2(int u,int fa)
	{
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa)continue;
			dfs2(to,u);
			cf[u]+=cf[to];
		}
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		int x,y;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
		dfs(1,0);
		for(int i=1;i<n;i++)
		{
			int as=a[i],bs=a[i+1];
			int _lca=lca(as,bs);
			cf[as]++;
			cf[bs]++;
			cf[_lca]--;
			cf[father[_lca][0]]--;
		}
		dfs2(1,0);
		for(int i=2;i<=n;i++)
		{
			cf[a[i]]--;
		}
		for(int i=1;i<=n;i++)
		{
			printf("%lld\n",cf[i]);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

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

思路

设一条路径为 $(a,b)$，另一条为 $(c,d)$，两条路径如果相交，那么有 $lca(a,b)$ 在 $(c,d)$ 上或 $lca(c,d)$ 在 $(a,b)$上，这个东西画一下图就能理解，但是我不知道怎么证明

可以这么理解：
首先已知对于任意两个点 $x,y$，$lca(x,y)$ 一定在 $x$ 到 $y$ 的路径上。
先确定了一条路径 $(a,b)$ 和路径外的一点 $c$，还有一个点 $d$ 未知。要使 $(a,b)$ 与 $(c,d)$ 相交，就要使 $lca(c,d)$ 成为路径 $(a,b)$ 上的一点。

那么如何判断一个点是否在某条路径上呢？
设判断 $a$ 是否在 $(c,d)$ 上，如果 $dis_{c,a} + dis_{a,d} = dis_{c,d}$，那么 $a$ 就在 $(c,d)$ 上
另外显然，$dis_{a,b} = dep_a + dep_b - 2 \cdot dep_{lca(a,b)}$（$dep$ 是节点的深度）

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=100005;
	int n,q;
	int head[maxn<<1];
	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 dep[maxn];
	int fa[18][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];
	}
	inline int dis(int a,int b)
	{\/\/计算 a,b 两点的距离 
		int _lca=lca(a,b);
		return dep[a]+dep[b]-2*dep[_lca];
	}
	inline bool check(int a,int b,int c)
	{\/\/判断 c 是否在 a,b 的链上 
		if(dis(a,c)+dis(c,b)==dis(a,b))
		{
			return 1;
		}
		return 0;
	}
	void main()
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		dfs(1,0);
		for(int i=1;i<=q;i++)
		{
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			int _lca_ab=lca(a,b);
			int _lca_cd=lca(c,d);
			if(check(a,b,_lca_cd)||check(c,d,_lca_ab))
			{
				printf("Y\n");
			}
			else printf("N\n");
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

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

题外话

赛时 C 题先是被卡了 40min，然后感觉没希望滚去做 E，然后没做出来，又跳回 C，又思考了 10min，找不出错，随手输入了一组数据结果 Successful hack，然后我对着这组 hack 数据改，最终将其 AC。此时还剩下 7min，去看了下 D，看上去很简单的样子，可是没时间做了。赛后把 D 题切了

又掉了大分

A

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	int a[3][3];
	int r,c;
	void main()
	{
		cin>>r>>c;
		cin>>a[1][1]>>a[1][2];
		cin>>a[2][1]>>a[2][2];
		cout<<a[r][c];
	}
}
int main()
{
	Main::main();
	return 0;
}

B

对于每个人，$O(k)$ 计算照亮他的最小光照半径，记为 $p_i$。
答案就 $p$ 数组的最大值

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=1005;
	int a[maxn];
	ll x[maxn],y[maxn];
	map<int,bool> im;
	double problem[maxn];
	int n,k;
	double dis(ll x,ll y,ll x2,ll y2)
	{
		double c1=double(x-x2);
		double c2=double(y-y2);
		return sqrt(c1*c1+c2*c2);
	}
	void main()
	{
		cin>>n>>k;
		for(int i=1;i<=k;i++)
		{
			cin>>a[i];
			im[a[i]]=1;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>x[i]>>y[i];
			problem[i]=1e9;	
		}
		double ans=0.0;
		for(int i=1;i<=k;i++)
		{
			double col=0;
			problem[a[i]]=0;
			for(int j=1;j<=n;j++)
			{
				if(im[j])continue;
				problem[j]=min(problem[j],dis(x[j],y[j],x[a[i]],y[a[i]]));
			}
		}
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,problem[i]);
		}
		printf("%.10lf",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

C

这道题需要分成 $d \ge 0$ 和 $d \le 0$ 两种情况讨论

• $d \ge 0$
  考虑一下极端情况，$x$ 可能会超出数列的最大元素或小于数列的最小元素，此时要进行特判
  普通情况下（$x$ 处于数列的最大元素与最小元素之间），那就计算出 $x$ 与其在数列中的最接近的元素的差的绝对值
• $d \le 0$
  总体思路和 $d \ge 0$ 的情况一样，不过计算最大元素和最小元素的部分要改变。

代码（赛时的代码不是给人看的，格式化了一下）：

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef __int128 ll;
	void main() {
		long long x,a,d,n;
		cin>>x>>a>>d>>n;
		if(d>=0) {
			ll imax=a+ll(n-1)*(ll)d;
			\/\/-----------极端情况---------- 
			if(x<=a) {
				cout<<(long long)(a-x);
				return;
			}
			if(x>=imax) {
				cout<<(long long)(x-imax);
				return;
			}
			\/\/-----------蒲通的情况------------- 
			ll ans1=(x-a)%d;\/\/靠左 
			ll ans2=abs(d-(x-a)%d);\/\/靠右 
			cout<<(long long)(min(ans1,ans2));
		} else {\/\/d<0
			ll imin=a+ll(n-1)*(ll)d;
			if(x>=a) {
				cout<<(long long)(x-a);
				return;
			}
			if(x<=imin) {
				cout<<(long long)(imin-x);
				return;
			}
			ll ans1=abs((x-a)%d);
			ll ans2=abs(abs(d)-abs((x-a)%d));
			cout<<(long long)(min(ans1,ans2));
		}
	}
}
int main() {
	Main::main();
	return 0;
}

D

这道题看完了之后，肯定感觉：“要是所有的元素全都大于等于 $x_i$ 或者全都小于 $x_i$ 就好了”
为了创建这种条件，考虑将它们分成两组，一组全部大于等于 $x_i$，一组全部小于 $x_i$。 现在的瓶颈就在于如何快速分开。显然如果暴力分的话是 $O(n)$ 的，乘上 $q$ 就爆了。
但是如果预先排一下序，那么每次询问就能以 $O(logn)$ 的复杂度找到分割点。 然后这道题就做出来了

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	int n,q;
	ll a[maxn];
	ll qzh[maxn];
	void main()
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			qzh[i]=qzh[i-1]+a[i];
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
		{
			qzh[i]=qzh[i-1]+a[i];
		}
		ll xi;
		for(int i=1;i<=q;i++)
		{
			scanf("%lld",&xi);
			int pos=lower_bound(a+1,a+n+1,xi)-a;
			if(pos==-1)
			{
				ll ans=(xi*n)-qzh[n];
				printf("%lld\n",ans);
				continue;
			}
			ll ans=0;
			ans+=xi*(pos-1)-qzh[pos-1];
			ans+=(qzh[n]-qzh[pos-1])-xi*(n-pos+1);
			printf("%lld\n",ans);
		}
	} 
}
int main()
{
	Main::main();
	return 0;	
} 

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 14:40:43

思路

如果能在 $t_1$ 的时间内解决，那么一定能在 $t_2 (t_2 \ge t_1)$ 的时间内解决。
所以可以二分最短时间。
那如何写 check 呢
设 check 的任务是判断能否在 $t$ 时间内解决，把 $m$ 个运输计划看成树上的 $m$ 条链。

1. 计算出长度最大的链，将其长度设为 $imax$
2. 算出有多少条链的长度大于 $t$，设为 $sum$
3. 求树上每个边被（长度大于 $t$ 的链）经过的次数。
4. 计算出边权最大的（被（长度大于 $t$ 的链）经过的次数等于 $sum$ 的边），将其边权设为 $w$
5. 判断删除（步骤 4 求出的边）之后能否在 $t$ 时间内解决

解释：

• 步骤 4 中，某条边被经过次数等于 $sum$，意思就是说这条边被所有（长度大于 $t$ 的链）经过，就是在找最大公共边
• 步骤 5 的求解方法：如果 $imax - w \le t$，那么可以在 $t$ 时间内解决，否则不可以

另外，求链长可以 lca 求出，另外对于一条边，它对应它的起点 $u$ 和终点 $t$ 中深度大的点。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=300005;
	int n,m;
	int head[maxn];
	struct EDGE
	{
		int to,val,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to,int val)
	{
		edge[++cnt].to=to;
		edge[cnt].val=val;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int fa[20][maxn];
	int dep[maxn];\/\/每个点的深度 
	int dis[maxn];\/\/每个点到根节点的距离 
	int imax;\/\/最长的链的长度 
	int node_to_edge[maxn];
	void dfs(int u,int _fa)
	{
		fa[0][u]=_fa;
		dep[u]=dep[_fa]+1;
		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;
			node_to_edge[to]=i;
			dis[to]=dis[u]+edge[i].val;
			dfs(to,u);
		}
	}
	inline int lca(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		for(int i=19;i>=0;i--)
		{
			if(dep[fa[i][x]]>=dep[y])
			{
				x=fa[i][x];
			}
		}
		if(x==y)return x;
		for(int i=19;i>=0;i--)
		{
			if(fa[i][x]!=fa[i][y])
			{
				x=fa[i][x];
				y=fa[i][y];
			}
		 } 
		 return fa[0][x];
	}
	struct Question
	{
		int u,v,len;
	}q[maxn];
	int cf[maxn]; 
	inline int get_dis(int a,int b)
	{
		int _lca=lca(a,b);
		return dis[a]+dis[b]-2*dis[_lca];
	}
	int sum,w;
	void dfs2(int u,int _fa)
	{
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs2(to,u);
			cf[u]+=cf[to];
		}
		if(cf[u]==sum)
		{
			w=max(w,edge[node_to_edge[u]].val);
		}
	}
	inline bool check(int t)
	{
		sum=w=0;
		for(int i=1;i<=m;i++)
		{
			if(q[i].len>t)
			{
				sum++;
				cf[q[i].u]++;
				cf[q[i].v]++;
				cf[lca(q[i].u,q[i].v)]-=2;
			}
		}
		dfs2(1,0);
		for(int i=1;i<=n;i++)
		{
			cf[i]=0;
		}
		if(imax-w<=t)return 1;
		return 0;
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<n;i++)
		{
			int ai,bi,ti;
			scanf("%d%d%d",&ai,&bi,&ti);
			add(ai,bi,ti);
			add(bi,ai,ti);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].u,&q[i].v);
			q[i].len=get_dis(q[i].u,q[i].v);
		}
		for(int i=1;i<=m;i++)
		{\/\/求最大链长 
			imax=max(imax,q[i].len);
		}
		int l=0,r=imax;
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		printf("%d",l);
	}
}
int main()
{
	Main::main();
	return 0; 
}

参考博客

1. communist 的博客
2. CodyTheWolf 的博客

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 16:25:16

思路

分 $t$ 在 $a$ 到 $b$ 的链上和 $t$ 不在 $a$ 到 $b$ 的链上两种情况化简一下

• $t$ 在 $x$ 到 $y$ 的链上
  $dis_{a,t} \oplus dis_{t,b} = dis_{a,b}$
• $t$ 不在 $a$ 到 $b$ 的链上
  因为 $dis_{t,lca(a,b)}$ 是 $t \rightarrow a$ 与 $t \rightarrow b$ 两条路径上重复的，被异或了两次，相当于没异或，实际上要计算的是：$dis_{a,lca(a,b)} \oplus dis_{lca(a,b),b} = dis_{a,b}$

所以其实就是判断 $dis_{a,b}$ 是否等于 $k$

另外要注意开 unsigned long long

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef unsigned long long ull;
	const int maxn=5e5+5;
	int head[maxn];
	struct EDGE
	{
		int to,nxt;
		ull val;
	}edge[maxn<<1];
	int cnt=0;
	inline void add(int u,int to,ull val)
	{
		edge[++cnt].to=to;
		edge[cnt].val=val;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	ull dis[maxn];
	int n,m;
	void dfs(int u,int fa)
	{
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa)continue;
			dis[to]=dis[u]^edge[i].val;
			dfs(to,u);
		}
	}
	ull get_dis(int x,int y)
	{
		return dis[x]^dis[y];
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<n;i++)
		{
			int x,y;
			ull l;
			scanf("%d%d%llu",&x,&y,&l);
			add(x,y,l);
			add(y,x,l);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			int a,b;
			ull k;
			scanf("%d%d%llu",&a,&b,&k);
			if(get_dis(a,b)==k)
			{
				printf("Yes\n");
			}
			else printf("No\n");
		}
;	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 20:33:30

思路

设任意一个点 $u$，$dis_{u,x} \oplus dis_{u,y} = k$

• 预先转化
  $u \rightarrow x$ 和 $u \rightarrow y$ 两条路径肯定有一段重复的，然后在 $x \rightarrow y$ 的链上的某个点 $t$ 分开，现在要计算的只剩下 $x \rightarrow y$ 的链上的点。设 $s_i$ 代表根节点到当前点的异或和（$dis_{1,i}$)，一个暂时的答案是 $s_x \oplus s_y$
• 上一步中有些还没考虑到
  如 $lca_{x,y}$ 在 $x \rightarrow y$ 的链上，是有贡献的（在 $lca_{x,y}$ 不等于 $t$ 的情况下），但是异或之后没了，所以需要再次异或加上。而 $t$ 是没有贡献的，应该再异或一次删掉（如果 $lca_{x,y} = t$，那么会导致多异或一下，下面会解释）
• 解释一下上一步
  如果 $lca_{x,y}$ 等于 $t$（也就是说路径在 $lca_{x,y}$ 分开，这样$lca_{x,y}$ 就没有贡献了）,那么也可以直接异或，因为这样 $lca_{x,y}$ 部分多异或了一下，$t$ 部分多异或了一下，异或两次相当于没异或，又对了
• 总结第二步
  $dis_{u,x} \oplus dis_{u,y} = k$ 转化为：
  $s_x \oplus s_y \oplus w_{lca_{x,y}} \oplus w_t = k$
  继续转化：
  $w_t = k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}} $

问题转化为，$x \rightarrow y$ 的链上是否有一个点，权值是 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ ，也就是统计 $x \rightarrow y$ 这条链上权值为 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ 的点的数量（注意这个权值仅仅是当前询问对应的！）
对于每一组这样的 $x,y$ ，设 $z_i$ 表示从 $1$ 到 $i$ 点权值为 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ 的数量 （注意这个 $z_i$ 仅仅是当前询问对应的 $z_i$ ！），答案就是 $z_x + z_y - z_{lca_{x,y}} - z_{lca_{x,y}.father}$。把所有询问离线一下，将 $x,y,lca_{x,y},lca_{x,y}.father$ 在树上做一下标记，dfs 的时候集中处理
dfs 具体如下：
dfs 前打标记部分：在树上指定部分标上 +1 或 -1，代表这次询问要加上还是减去这个点的贡献。
dfs 部分：设当前 dfs 到了点 $u$，那么将该点权值对应的 $z_u$ 乘上该点标记加到对应的询问里去。

最后看每个询问的值是否大于 0 就行了

注意：

$z_i$ 并不需要预先求出，dfs 的时候每递归到一个点，就将其对应的 $z_i$ 更新一下就行了。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=5e5+5;
	int n,m;
	int w[maxn];
	int head[maxn];
	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[20][maxn];
	int dep[maxn];
	int s[maxn];
	void dfs(int u,int _fa)
	{
		s[u]=s[_fa]^w[u];
		dep[u]=dep[_fa]+1;
		fa[0][u]=_fa;
		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;
			dfs(to,u);
		}
	}
	inline int lca(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		for(int i=19;i>=0;i--)
		{
			if(dep[fa[i][x]]>=dep[y])
			{
				x=fa[i][x];
			}
		}
		if(x==y)return x;
		for(int i=19;i>=0;i--)
		{
			if(fa[i][x]!=fa[i][y])
			{
				x=fa[i][x];
				y=fa[i][y];
			}
		}
		return fa[0][x];
	}
	int t[maxn];
	vector<pair<int,int> > tag[maxn]; 
	int tot[10000005];
	int count[maxn];
	void dfs2(int u,int _fa)
	{
		tot[w[u]]++;
		for(int i=0;i<tag[u].size();i++)
		{
			int id=tag[u][i].first;
			int w=tag[u][i].second;
			count[id]+=w*tot[t[id]];
		} 
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs2(to,u);
		}
		tot[w[u]]--;\/\/退出当前链，记得清除标记 
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&w[i]);
		}
		for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			int a,b,k;
			scanf("%d%d%d",&a,&b,&k);
			int _lca=lca(a,b);
			t[i]=k^s[a]^s[b]^w[_lca];
			if(t[i]>1e7)continue;
			tag[a].emplace_back(make_pair(i,1));
			tag[b].emplace_back(make_pair(i,1));
			tag[_lca].emplace_back(make_pair(i,-1));
			tag[fa[0][_lca]].emplace_back(make_pair(i,-1));
		}
		dfs2(1,0);
		for(int i=1;i<=m;i++)
		{
			if(count[i]>0)
			{
				printf("Yes\n");
			}
			else 
			{
				printf("No\n");
			}
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

参考博客

一扶苏一的博客

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 21:57:46

思路

对于 $a$ 依赖 $b$ 这种，就连一条 $a$ 与 $b$ 的边，可以发现最后会形成一颗以 $0$ 为根的树。

• 对于安装软件 $x$，显然 $0 \rightarrow x$ 路径上所有的软件都要安装，也就是将 $0 \rightarrow x$ 路径上所有点的权值变为 1
• 对于删除软件 $x$，就是将以 $x$ 为根的子树内的所有节点变为0

树链剖分即可。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=100005;
	int n,q;
	int head[maxn];
	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 size[maxn<<3];
	int dfn[maxn<<3];
	int rank[maxn<<3];
	int hs[maxn<<3];
	int fa[maxn<<3];
	int nodecnt;
	int top[maxn<<3];
	int dep[maxn<<3];
	void dfs1(int u,int _fa)
	{
		dep[u]=dep[_fa]+1;
		size[u]=1;
		fa[u]=_fa;
		int imax=0;
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs1(to,u);
			size[u]+=size[to];
			if(size[to]>=imax)
			{
				imax=size[to];
				hs[u]=to;
			}
		}
	}
	void dfs2(int u,int _top)
	{
		dfn[u]=++nodecnt;
		rank[nodecnt]=u;
		top[u]=_top;
		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[u]||to==hs[u])continue;
			dfs2(to,to);
		}
	}
	int val[maxn<<3],lazy[maxn<<3];
	int L[maxn<<3],R[maxn<<3];
	void build(int pos,int l,int r)
	{
		L[pos]=l;
		R[pos]=r;
		lazy[pos]=-1;
		if(l==r)
		{
			return;
		}
		int mid=(l+r)>>1;
		build(pos<<1,l,mid);
		build(pos<<1|1,mid+1,r);
	}
	inline int get_len(int i)
	{
		return (R[i]-L[i]+1);
	}
	inline void push_down(int i)
	{
		if(lazy[i]==-1)return;
		lazy[i<<1]=lazy[i];
		lazy[i<<1|1]=lazy[i];
		val[i<<1]=lazy[i]*get_len(i<<1);
		val[i<<1|1]=lazy[i]*get_len(i<<1|1);
		lazy[i]=-1;
	}
	inline void push_up(int i)
	{
		val[i]=val[i<<1]+val[i<<1|1];
	}
	void modify(int pos,int _l,int _r,int l,int r,int _val)
	{
		if(_l>=l&&_r<=r)
		{
			lazy[pos]=_val;
			val[pos]=(_val)*get_len(pos);
			return;
		}
		if(_r<l||_l>r)return;
		push_down(pos);
		int mid=(_l+_r)>>1;
		if(mid>=l)modify(pos<<1,_l,mid,l,r,_val);
		if(mid<r)modify(pos<<1|1,mid+1,_r,l,r,_val);
		push_up(pos);
	}
	void Modify(int x,int y,int _val)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			modify(1,1,n,dfn[top[x]],dfn[x],_val);
			x=fa[top[x]];
		}
		if(dep[x]>dep[y])swap(x,y);
		modify(1,1,n,dfn[x],dfn[y],_val);
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<n;i++)
		{
			int b;
			scanf("%d",&b);
			add(i,b);
			add(b,i);
		}
		dfs1(0,n*6);
		dfs2(0,0);
		build(1,1,n);
		\/\/-------------------
		char op[10];
		int x;
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			scanf("%s%d",op,&x);
			if(op[0]=='i')
			{
				int ai=val[1];
				Modify(0,x,1);
				int bi=val[1];
				printf("%d\n",abs(ai-bi));
			}
			if(op[0]=='u')
			{
				int ai=val[1];
				modify(1,1,n,dfn[x],dfn[x]+size[x]-1,0);
				int bi=val[1];
				printf("%d\n",abs(ai-bi));
			}
		}		
	}
}
int main()
{
	Main::main();
	return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-16 14:48:01

题目翻译

给你一个 $n$ 个元素且只包含 $1$ 或 $0$ 两种元素的序列 $a$，以及一个正整数 $s$。
在一次操作中，你可以删掉第一个元素或最后的元素。
求使得剩下元素总和等于 $s$ 的最小操作次数。

思路

考虑到只能在首尾删元素，可以将问题转化为：
在数列 $a$ 中选择一个区间 $[l,r]$，使得 $\sum_l^r a_i = s$，并且这个区间必须是满足条件的区间中最长的。

暴力思路

显然可以暴力枚举每一个区间，前缀和 $O(1)$ 判断当前区间总和是否为 $s$，然后更新答案。
复杂度 $O(n^2)$。

优化

首先设数列第 $i$ 个元素的前缀和是 $qzh_i$。
枚举左端点的部分不太好优化，那就优化选择右端点的部分。
显然，固定了左端点 $l$ 后，右端点 $r$ 的前缀和值 $qzh_r$ 也就固定了。可以将其算出来，等于 $qzh_{l-1} + s$。
而前缀和数组是升序的！
也就是说可以用 lower_bound，$O(\log n)$ 把右端点求出来。
但是要注意，lower_bound 求出来的右端点 $r$，是第一个满足要求的 $r$，而因为要求区间最长，我们需要的是最后一个满足要求的 $r$，所以还要做一些处理。
算出 $a_r$ 后面有多少个元素 $0$，设有 $sum$ 个，将 $r$ 跳到 $r+sum - 1$，也就是这些 $0$ 元素的最后一个。
这道题就做完了。
复杂度 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=2e5+5;
	int t,n,s;
	int a[maxn];
	int qzh[maxn];\/\/前缀和
	int len[maxn];
    \/\/len[i] 代表第 i 个元素开始有多少个相邻的相同元素
	void main()
	{
		scanf("%d",&t);
		while(t--)
		{
			scanf("%d%d",&n,&s);
			for(int i=1;i<=n;i++)
			{
				scanf("%d",&a[i]);
				qzh[i]=qzh[i-1]+a[i];
			}
			for(int i=n;i>=1;i--)
			{
				if(i==n)
				{
					len[i]=1;
					continue;
				}
				if(a[i]==a[i+1])len[i]=len[i+1]+1;
				else len[i]=1;
			}
			if(qzh[n]<s)
			{
				printf("-1\n");
				continue;
			}
			int maxlen=0;
			for(int l=1;l<=n;l++)
			{
				int r=lower_bound(qzh+l,qzh+n+1,s+qzh[l-1])-qzh;
				if(a[r+1]==0&&r<n)r=r+1+len[r+1]-1;
				if(r==n+1)
				{
					continue;
				}
				maxlen=max(maxlen,r-l+1);
			}
			printf("%d\n",n-maxlen);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}