首页 > 其他分享 >近期总结

近期总结

时间:2024-11-12 09:42:31浏览次数:1  
标签:总结 10 return int mi 近期 fa num

一些近期的模拟赛,被暴打。

9.18 D

超级无敌线段树题目。


给出 \(n\) 个 \(a_i,b_i\),然后 \(q\) 组询问。

每组询问给出 \(l,r,x\)。然后令 \(i=l\),一直做到 \(r\)。

若 \(x>a_i\),则 \(x\gets x+b_i\)。


暴力送你 \(10\ \texttt{pts}\),然后离线的话有 \(50\ \texttt{pts}\)。

离线应该可以用平衡树之类的数据结构乱搞。

正解是线段树,对每个节点开个 vector,每个 vector 存一个二元组 \((a,b)\),表示进入这个区间时,若 \(x\ge a\),则 \(x\gets x+b\)。那么查询的时候二分一下再来个前缀和就可以 \(\mathcal O(\log^2 n)\) 回答每个询问。

难点是怎么合并区间。

对于左区间的二元组肯定不会发生变化,但是右区间会。

如果右区间的一个二元组为 \((x',y')\),那么新的二元组就是 \((\max\{x,x'-sum\},y')\).

其中 \(x\) 是最大小于等于 \(x'\) 的,\(sum\) 是所有小于等于 \(x\) 的 \(y\) 之和。

双指针可以搞,建树时间复杂度是 \(\mathcal O(n \log n)\) 的,代码时间复杂度 \(\mathcal O(n \log n +q\log^2 n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,q,t,now;
int a[N],b[N];
struct ccf
{
	int x,y,s;
};
vector<ccf>f[N<<2];
void in(int id,ccf k)
{
	int s=f[id].empty()?0:f[id].back().s;
	f[id].push_back({k.x,k.y,s+k.y});
}
void solve(int k)
{
	int l=k*2,r=k*2+1,id=0,sum=0;
	while(id<f[r].size()&&f[r][id].x<f[l][0].x)
		f[k].push_back(f[r][id]),id++;
	for(int i=0;i<f[l].size();i++)
	{
		in(k,f[l][i]),sum+=f[l][i].y;
		while(id<f[r].size()&&(i==f[l].size()-1||f[r][id].x-sum<f[l][i+1].x))
			in(k,{max(f[r][id].x-sum,f[k].back().x),f[r][id].y,0}),id++;
	}
}
void build(int k,int l,int r)
{
	if(l==r)return f[k].push_back({a[l],b[l],b[r]}),void();
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	solve(k);
}
int find(int id,int k)
{
	if(k<f[id][0].x)return 0;
	int l=0,r=f[id].size();
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(f[id][mid].x<=k)l=mid;
		else r=mid;
	}
	return f[id][l].s;
}
void ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x)return ;
	if(x<=l&&r<=y)return now+=find(k,now),void();
	int mid=(l+r)/2;
	ask(k*2,l,mid,x,y);
	ask(k*2+1,mid+1,r,x,y);
}
signed main()
{
	scanf("%lld%lld%lld",&n,&q,&t);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),a[i]++;
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	build(1,1,n);
	while(q--)
	{
		int l,r,x;
		scanf("%lld%lld%lld",&l,&r,&x);
		l^=t*now,r^=t*now,x^=t*now,now=x;
		ask(1,1,n,l,r);
		printf("%lld\n",now);
	}
	return 0;
}

9.19 D

\(m\) 个部落,\(n\) 个洞穴。一开始每个洞穴被 \(a_i\) 占领,或无人。

有两种操作:

  1. 给出 \(l,r,k\)。区间 \([l,r]\) 更改为 \(k\) 占领。

  2. 给出 \(l,r,k\)。区间 \([l,r]\) 的每个洞穴出现价值为 \(k\) 的宝物,由占领该洞穴的部落获得,若无部落占领,则由下一个占领的部落获得。

求最终各个部落获得的宝物价值总和。


想了一会在线,发现不是很可做。反着做也想了好一会,鉴定为对数据结构的使用不够熟练。

想到反着做就基本结束了其实,原本的 1 操作就是 \(ans_k\) 加上区间和,然后区间归零。

2 操作就是一个简单的区间加。

懒得打了于是 Copy 的线段树 2,区间归零就是区间乘 \(0\)。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
#define int long long
using namespace std;
const int N=5e5+10;
int n,m,q;
int c[N],ans[N];
struct node
{
	int op,l,r,x;
}a[N];
struct ccf
{
	int l,r,num,la1,la2;
}f[N<<2];
void build(int k,int l,int r)
{
	f[k].l=l,f[k].r=r,f[k].la1=1,f[k].la2=0;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
}
void pushdown(int k)
{
	if(f[k].la1!=1||f[k].la2)
	{
		int l=k*2,r=k*2+1;
		f[l].num*=f[k].la1;
		f[l].num+=(f[l].r-f[l].l+1)*f[k].la2;
		f[r].num*=f[k].la1;
		f[r].num+=(f[r].r-f[r].l+1)*f[k].la2;
		f[l].la1*=f[k].la1;
		f[l].la2=f[l].la2*f[k].la1+f[k].la2;
		f[r].la1*=f[k].la1;
		f[r].la2=f[r].la2*f[k].la1+f[k].la2;
		f[k].la1=1,f[k].la2=0;
	}
}
void change(int k,int l,int r,int x,int y,int v,int op)
{
	if(l>y||r<x)return ;
	if(x<=l&&r<=y)
	{
		if(op==1)f[k].num*=v,f[k].la1*=v,f[k].la2*=v;
		else f[k].num+=(r-l+1)*v,f[k].la2+=v;
		return ;
	}
	pushdown(k);
	int mid=(l+r)/2;
	change(k*2,l,mid,x,y,v,op);
	change(k*2+1,mid+1,r,x,y,v,op);
	f[k].num=f[k*2].num+f[k*2+1].num;
}
int ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x)return 0;
	if(x<=l&&r<=y)return f[k].num;
	pushdown(k);
	int mid=(l+r)/2;
	return ask(k*2,l,mid,x,y)+ask(k*2+1,mid+1,r,x,y);
}
signed main()
{
	cin>>n>>m>>q;
	build(1,1,n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&c[i]);
	for(int i=1;i<=q;i++)
		scanf("%lld%lld%lld%lld",&a[i].op,&a[i].l,&a[i].r,&a[i].x);
	build(1,1,n);
	for(int i=q;i>=1;i--)
	{
		if(a[i].op==1)
		{
			ans[a[i].x]+=ask(1,1,n,a[i].l,a[i].r);
			change(1,1,n,a[i].l,a[i].r,0,1);
		}
		else change(1,1,n,a[i].l,a[i].r,a[i].x,2);
	}
	for(int i=1;i<=n;i++)
		if(c[i])ans[c[i]]+=ask(1,1,n,i,i);
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

9.24 D

给出一个 \(n\) 个点,\(m\) 条边的有向图,求有多少个点集 \(S\) 满足,\(\forall i\in S\),若存在边 \((i,j)\),则 \(j\in S\)。同时点集 \(S\) 是连续的,即点的编号是连续的。


一眼顶针 \(O(n^2)\) 做法,枚举左右端点:

#include<bits/stdc++.h>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=3e5+10;
int n,m,ans;
int x[N],y[N];
vector<int>v[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	memset(x,127,sizeof(x));
	for(int i=1;i<=n;i++)
		for(int k:v[i])
			x[i]=min(k,x[i]),y[i]=max(k,y[i]);
	for(int i=1;i<=n;i++)
	{
		int mi=1e9,ma=0;
		for(int j=i;j<=n;j++)
		{
			mi=min(mi,x[j]),ma=max(ma,y[j]);
			if(mi<i)break;
			if(ma<=j)ans++;
		}
	}
	cout<<ans;
	return 0;
}

然后就不会优化了,鉴定为不会用数据结构。

琢磨了一下午,但还是不会。场上切这题的人还不少。

问了大神,表示这是线段树应用模板。

对于每个 \(i\),它为左端点的贡献区间只有 \([i,r_i]\),这个 \(r_i\) 是可以二分在 \(\mathcal O(n)\) 内求出来的,那么可以在枚举右端点到 \(i\) 时丢到线段树上,然后在 \(r_i\) 时将它再拿出来。

同样的,它为右端点的贡献区间为 \([l_i,i]\),\(l_i\) 可以二分,然后在线段树求区间 \([l_i,i]\) 的和即可。

用 st 表预处理可以做到 \(\mathcal O(n\log n)\)。

线段树还是要多练啊!!!!!

#include<bits/stdc++.h>
#define int long long
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=3e5+10,mod=1e9+7;
int n,m,ans;
int mi[N],ma[N],st[N][25],ts[N][25],f[N<<2];
vector<int>v[N];
int check(int l,int r)
{
	if(l>r)return 1e9;
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
int chec(int l,int r)
{
	int k=log2(r-l+1);
	return max(ts[l][k],ts[r-(1<<k)+1][k]);
}
int find(int k)
{
	int l=k-1,r=n+1;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check(k,mid)>=k)l=mid;
		else r=mid;
	}
	return l;
}
int fin(int k)
{
	int l=0,r=k+1;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(chec(mid,k)<=k)r=mid;
		else l=mid;
	}
	return r;
}
void add(int k,int l,int r,int x,int y)
{
	if(l==r)return f[k]+=y,void();
	int mid=(l+r)/2;
	if(x<=mid)add(k*2,l,mid,x,y);
	else add(k*2+1,mid+1,r,x,y);
	f[k]=f[k*2]+f[k*2+1];
}
int ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x)return 0;
	if(x<=l&&r<=y)return f[k];
	int mid=(l+r)/2;
	return ask(k*2,l,mid,x,y)+ask(k*2+1,mid+1,r,x,y);
}
signed main()
{
	memset(mi,127,sizeof(mi));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		mi[x]=min(mi[x],y);
		ma[x]=max(ma[x],y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!ma[i])ma[i]=i;
		st[i][0]=mi[i];
		ts[i][0]=ma[i];
	}
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)<=n;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]),
			ts[i][j]=max(ts[i][j-1],ts[i+(1<<j-1)][j-1]);
	for(int i=1;i<=n;i++)
		if(mi[i]>=i)v[find(i)+1].push_back(i);
	for(int i=1;i<=n;i++)
	{
		if(mi[i]>=i)add(1,1,n,i,1);
		for(int j:v[i])
			add(1,1,n,j,-1);
		ans+=ask(1,1,n,fin(i),i);
	}
	cout<<ans%mod;
	return 0;
}

9.27 D

完了,不知道可以在实数上二分。


原题:AT_njpc2017_f


思考怎么 check。

假设现在做到了 \(i\),要去下一个点 \(i+1\)。

首先现在肯定有个点在 \(i\),然后有个点可以随便跑,能去的地方是一个区间,不妨记为 \([l,r]\)。

如果两个点有且仅有一个点能到达 \(i+1\),那直接让那个点去就好了,更新 \([l,r]\)。

都不能去的话那直接就 \(\texttt{false}\) 了。

都能去的话贪心,使覆盖的区间最大即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const double eps=1e-9;
int n;
double t[N];
double a[N];
bool check(double k)
{
	double l=0,r=0;
	for(int i=0;i<n;i++)
	{
		double s=k*(t[i+1]-t[i]);
		bool x=fabs(a[i+1]-a[i])<=s+eps,y=l-s<=a[i+1]+eps&&a[i+1]<=r+s+eps;
		if(!x&&!y)return false;
		else if(x&&!y)l-=s,r+=s;
		else if(!x&&y)l=a[i]-s,r=a[i]+s;
		else l=min(a[i],l)-s,r=max(a[i],r)+s;
	}
	return true;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&t[i],&a[i]);
	double l=eps,r=2e6;
	while(l+eps<r)
	{
		double mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%.9lf",r);
	return 0;
}

9.29 D

感觉是一个很妙的东西,他们说这是 Kruskal 重构树(?


\(n\) 个人,一开始两两之间关系度都为 \(0\)。

\(m\) 个操作:

  1. 给出 \(x\ y\),两个人的关系度加一。

  2. 给出 \(x\),\(x\) 认识的人两两关系度加一。

  3. 给出 \(x\ y\),询问 \(x\) 和 \(y\) 的关系度。

认识的定义:是个并查集。


思考怎么去刻画两个联通块的合并过程。

两个联通块合并的时候可以新开一个节点,并用这个节点指向两个联通块的根。

然后就可以建出了一棵树。

离线之后把这棵树的 dfn 序给搞出来。

对于操作一,直接搞个 map 就好。

对于操作二,给整个当前 \(x\) 的联通块每个点的权值加一。因为 dfn 序已经求了,直接上线段树。

对于操作三,首先是操作一单独加的,然后如果 \(x\) 和 \(y\) 已经在一个联通块里面了,那么就加上 \(\text{lca}(x,y)\) 的权值。

上面的操作是非常正确的,思考一下可以发现。

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
int n,m,tot,cnt;
int f[N][25],s[N],fa[N],dfn[N],l[N],r[N],de[N];
map<pair<int,int>,int>mp;
vector<int>v[N];
struct ccf
{
	int op,x,y,fa;
}a[N];
int find(int k)
{
	return fa[k]==k?k:fa[k]=find(fa[k]); 
}
void dfs(int x,int fa)
{
	f[x][0]=fa,de[x]=de[fa]+1;
	l[x]=dfn[x]=++cnt;
	for(int i:v[x])
		dfs(i,x);
	r[x]=cnt;
}
int lca(int x,int y)
{
	if(de[x]<de[y])swap(x,y);
	for(int i=20;i>=0;i--)
		if(de[f[x][i]]>=de[y])
			x=f[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
struct tree
{
	struct node
	{
		int x,l,r,la;
	}f[N<<2];
	void pushdown(int k)
	{
		if(!f[k].la)return ;
		int &x=f[k].la,l=k*2,r=k*2+1;
		f[l].x+=(f[l].r-f[l].l+1)*x,f[l].la+=x;
		f[r].x+=(f[r].r-f[r].l+1)*x,f[r].la+=x;
		x=0;
	} 
	void build(int k,int l,int r)
	{
		f[k].l=l,f[k].r=r;
		if(l==r)return ;
		int mid=(l+r)/2;
		build(k*2,l,mid);
		build(k*2+1,mid+1,r);
	}
	void add(int k,int l,int r,int x,int y,int z)
	{
		if(l>y||r<x)return ;
		if(x<=l&&r<=y)return f[k].x+=(f[k].r-f[k].l+1)*z,f[k].la+=z,void();
		pushdown(k);
		int mid=(l+r)/2;
		add(k*2,l,mid,x,y,z);
		add(k*2+1,mid+1,r,x,y,z);
		f[k].x=f[k*2].x+f[k*2+1].x;
	}
	int ask(int k,int l,int r,int x)
	{
		if(l>x||r<x)return 0;
		if(l==r)return f[k].x;
		pushdown(k);
		int mid=(l+r)/2;
		return ask(k*2,l,mid,x)+ask(k*2+1,mid+1,r,x);
	}
}t;
int main()
{
	cin>>n>>m;
	tot=n;
	for(int i=1;i<=n*2;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int &op=a[i].op,&x=a[i].x,&y=a[i].y;
		scanf("%d%d",&op,&x);
		if(op==1)
		{
			scanf("%d",&y);
			int l=find(x),r=find(y);
			if(l==r)continue;
			fa[l]=fa[r]=++tot;
			v[tot].push_back(l);
			v[tot].push_back(r);
		}
		else if(op==2)a[i].fa=find(x);
		else if(op==3)scanf("%d",&y);
	}
	dfs(tot,0);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=tot;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1;i<=n;i++)
		fa[i]=i;
	t.build(1,1,tot);
	for(int i=1;i<=m;i++)
	{
		int &op=a[i].op,&x=a[i].x,&y=a[i].y;
		if(op==1)
		{
			if(x>y)swap(x,y);
			mp[{x,y}]++;
			fa[find(x)]=find(y);
		}
		else if(op==2)t.add(1,1,tot,l[a[i].fa],r[a[i].fa],1);
		else
		{
			if(x>y)swap(x,y);
			int ans=t.ask(1,1,tot,dfn[lca(x,y)]);
			printf("%lld\n",ans*(find(x)==find(y))+mp[{x,y}]);
		}
	}
	return 0;
}

10.5 A

放了个假之后啥也不会了。


给出 \(n\) 个区间。选择尽可能多对区间,使每对区间不相交。

\(n\le 4\times 10^5\)。


很好的贪心,使我的大脑旋转。

首先肯定要把区间排序。

贪心地,维护两个堆 \(x,y\),一个是没有匹配的 \(r\),另一个存已经匹配的一对中最大的 \(r\)。

做到当前 \(i\),如果 \(x\) 里面有能和 \(i\) 直接匹配的,匹配上一定不劣。

否则,在 \(y\) 里面找最小的 \(r\),如果小于现在的右端点,就把它们交换,这样可以使后面的尽量能有匹配的。

在否则,直接丢到 \(y\) 里面。

注意上面的前两种情况要不要往 \(x\) 或者 \(y\) 里面丢新的 \(r\) 或者被换下来的 \(r\)。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=4e5+10;
int n,ans;
int f[N];
pair<int,int>a[N];
priority_queue<int,vector<int>,greater<int>>x,y;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].fi,&a[i].se);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		if(!x.empty()&&x.top()<a[i].fi)ans++,y.push(a[i].se),x.pop();
		else if(!y.empty()&&y.top()<a[i].se)x.push(y.top()),y.pop(),y.push(a[i].se);
		else x.push(a[i].se);
	}
	cout<<ans;
	return 0;
}

10.5 B

被 A 心态搞爆,其实这题质量也挺高的。


给你一个长度为 \(n\) 的排列 \(a\),有 \(2\times n\) 次操作:

  1. 把 \(a\) 中的第一个数丢到一个大大根堆里面,然后把这个数从 \(a\) 中删除(\(a\) 不为空时才能执行此操作)。

  2. 把大根堆里面最大的数取出来,并放在序列 \(b\) 的末尾(堆不为空才能执行此操作)。

问最终的序列 \(b\) 有多少种可能,答案对 \(8580287\) 取模,\(n\le 100\)。


阅读题解后可以发现,假设 \(1\) 在 \(a\) 中的位置是 \(x\),在 \(b\) 中的位置是 \(y\),那么一定有 \(y\ge x\),证明是不难的。

这启发我们往最小值的方向进行思考。

所以 \(1\) 在 \(b\) 中位置的范围是 \([x,n]\)。然后可以枚举 \(1\) 所在的位置 \(i\),\(a\) 序列 \([1,i]\) 中的数构成的集合 和 \(b\) 序列 \([1,i]\) 中的数构成的集合 是一样的。

然后就可以递归下去了,区间 \([1,i]\) 和 \([i+1,n]\) 互不干涉,答案相乘。

\([l,r]\) 的限制是不够的,要多开一个 \(v\) 表示只考虑区间中不小于 \(v\) 的数。

其实这是一个区间 dp,答案就是 \(dp(1,n,1)\)。

简单推广一下,现在不是 \(1\) 了,是区间 \([l,r]\) 中的最小值 \(mi\)。(妈的题解没写这个部分害得我搞这题搞了好久)

首先如果区间所有的数都大于 \(v\) 的话直接返回 \(1\),可能是 \(v>n\) 或者区间的数都已经确定了导致的。

枚举 \(mi\) 的位置,范围是 \([f_{mi},n]\),其中 \(f_{mi}\) 是 \(mi\) 在 \(a\) 序列中的位置。

注意:如果 \(a_i < v\) 的话,\(mi\) 是不能在这个位置的!!!!

因为我们忽略了所有小于 \(v\) 的数,实际上是没有这个位置来选择的。

比如对于下面这个序列 \(a\):3 2 1

求 \(dp(1,3,3)\) 的时候,如果你枚举到了第二个或者第三个位置,那么就错误了。会导致 \(2\) 和 \(1\) 没有位置放。

记忆化一手,状态一共有 \(\mathcal O(n^3)\) 种,但是还要枚举 \(mi\) 的位置,所以时间复杂度是 \(\mathcal O(n^4)\) 的,可以通过。

对了,还要注意一手边界的判断。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110,mod=8580287;
int n,ans;
int a[N],f[N],chk[N];
int mp[110][110][110];
int dp(int l,int r,int v)
{
	if(mp[l][r][v])return mp[l][r][v];
	if(l>=r)return 1;
	int mi=1e9,sum=0;
	for(int i=l;i<=r;i++)
		if(a[i]>=v&&a[i]<mi)
			mi=a[i];
	if(mi==1e9)return 1;
	for(int i=f[mi];i<=r;i++)
		if(a[i]>=v)sum+=dp(l,i,mi+1)*dp(i+1,r,mi+1)%mod,sum%=mod;
	return mp[l][r][v]=sum;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],f[a[i]]=i;
	cout<<dp(1,n,1);
	return 0;
}

10.6 B

傻波一构造题,我真服了。


给出一个长度为 \(n\) 的排列 \(a\),每次可以选择一个 \(x<n\),如果 \(a_x \neq x\) 且 \(a_{x+1}\neq x+1\),那么可以交换 \(a_x\) 和 \(a_{x+1}\)。

要求构造方案,使 \(\forall i \in[1,n],a_i=i\),操作次数不超过 \(\frac{n(n-1)}{2}\)。


先来一个错解。

考虑先把 \(1\) 移了,再移 \(2\),以此类推。

然后有问题就是假设现在 \(1\) 在第 \(i\) 位,\(1\) 的前面就是 \(i\),无法交换。

那直接找到 \(i\) 之前第一个比 \(i\) 大的然后交换过来。

获得了 \(50\) 的高分,一直不知道错哪了。

马龙怎么输了我去!!!!没心情调。

第二天脑子清醒了思考了一波,下面这个数据会挂:

1 8 7 3 6 2 5 4

按照上面去搞的话,第一次就把 \(7\) 和 \(3\) 给交换了。

诶我真服了啊。

看了一眼题解,发现找到第一个在 \(i\) 之前的 \(x\) 使得 \(a_x \not= x+1\) 即可。

有些小细节,无解的情况也是不难判断的。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,m;
int a[N],mi[N],ma[N],f[N];
vector<pair<int,int>>ans;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		ma[i]=max(ma[i-1],a[i]);
		f[a[i]]=i;
	}
	memset(mi,127,sizeof(mi));
	for(int i=n;i>=1;i--)
		mi[i]=min(mi[i+1],a[i]);
	for(int i=1;i<=n;i++)
		if(a[i]==i&&ma[i]>mi[i])
			return puts("NO"),0;
	puts("YES");
	if(m==-1)return 0;
	for(int i=1;i<=n;i++)
	{
		int now=f[i];
		while(f[i]!=i)
		{
			if(a[f[i]-1]!=f[i])
			{
				ans.push_back({f[i]-1,f[i]});
				swap(a[f[i]-1],a[f[i]]);
				swap(f[a[f[i]]],f[i]);
			}
			else
			{
				now=min(now,f[i]-2);
				while(now>=1)
				{
					if(a[now]!=now+1&&a[now]!=now)break;
					else now--;
				}
				if(now<1)
				{
					ans.push_back({f[i]-1,f[i]});
					swap(a[f[i]-1],a[f[i]]);
					swap(f[a[f[i]]],f[i]);
				}
				else
				{
					for(int j=now;j<f[i]-1;j++)
					{
						ans.push_back({j,j+1});
						swap(a[j],a[j+1]);
						swap(f[a[j]],f[a[j+1]]);
					}
				}
			}
		}
	}
	cout<<ans.size()<<endl;
	for(auto [i,j]:ans)
		printf("%d %d\n",i,j);
	return 0;
}

10.9 C

Long time no see, CSP-S RP ++.

很妙的建图。

原题:AT_joisc2014_e


使两点间边权的最大值最小,应该想到克鲁斯卡尔重构树。

但是不知道要怎么建图。

从每个安全区开始,对图进行染色如果有点被染过了就不染。

bfs 跑一遍,时间复杂度是 \(\mathcal O(nm)\) 的。

然后两个相邻的点如果颜色不同就把它们连边,点的编号就是安全区的编号。最后搞一个克鲁斯卡尔重构树,查询的时候求 LCA 的点权就没了。

这样子做是很对的,不想证明。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
using namespace std;
const int N=4e5+10,M=2e3+10;
int n,m,k,t,cnt,tot;
int fa[N],f[N][25],de[N],vis[N],val[N];
int mp[M][M],id[M][M],c[M][M];
int ax[]={0,1,-1,0,0},ay[]={0,0,0,1,-1};
struct ccf
{
	int x,y,z;
}a[M*M];
vector<int>v[N];
queue<ccf>q;
void bfs()
{
	while(!q.empty())
	{
		auto [x,y,z]=q.front();
		q.pop();
		for(int i=1;i<=4;i++)
		{
			int nx=x+ax[i],ny=y+ay[i];
			if(nx<1||ny<1||nx>n||ny>m||id[nx][ny]||mp[nx][ny])continue;
			id[nx][ny]=z,c[nx][ny]=c[x][y]+1,q.push({nx,ny,z});
		}
	}
}
bool cmp(ccf a,ccf b)
{
	return a.z<b.z;
}
int find(int k)
{
	return fa[k]==k?k:fa[k]=find(fa[k]);
}
void dfs(int x)
{
	vis[x]=1;
	for(int i:v[x])
	{
		f[i][0]=x,de[i]=de[x]+1;
		dfs(i);
	}
}
int lca(int x,int y)
{
	if(de[x]<de[y])swap(x,y);
	for(int i=20;i>=0;i--)
		if(de[f[x][i]]>=de[y])
			x=f[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	cin>>n>>m>>k>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			mp[i][j]=c=='#';
		}
	for(int i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		id[x][y]=i;
		q.push({x,y,i});
	}
	bfs();
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			if(id[i][j]&&id[i][j+1]&&id[i][j]!=id[i][j+1])
				a[++cnt]={id[i][j],id[i][j+1],c[i][j]+c[i][j+1]};
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			if(id[i][j]&&id[i+1][j]&&id[i][j]!=id[i+1][j])
				a[++cnt]={id[i][j],id[i+1][j],c[i][j]+c[i+1][j]};
	sort(a+1,a+1+cnt,cmp);
	tot=k;
	for(int i=1;i<=2*k;i++)
		fa[i]=i;
	for(int i=1;i<=cnt;i++)
	{
		int l=find(a[i].x),r=find(a[i].y);
		if(l==r)continue;
		tot++;
		v[tot].push_back(l),v[tot].push_back(r),val[tot]=a[i].z;
		fa[l]=fa[r]=tot;
	}
	for(int i=tot;i>=1;i--)
		if(!vis[i])dfs(i);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=tot;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	while(t--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(find(x)!=find(y))puts("-1");
		else printf("%d\n",val[lca(x,y)]);
	}
	return 0;
}

10.10 C

矩阵加速 dp,菜就多练。


有 \(n\) 种代币,每种面值为 \(a_i\) 。每次小明会给每个顾客依次发放任意多次任意一种代币(可以不发)。两个发代币的方案不同当且仅当给两个顾客发放代币的次数不同或发放了不同种的代币,求有多少种发放代币的方案使得发放的总面值小于等于 \(K\)。

\(a_i \le 100\)。


\(\mathcal O(Kn)\) 的完全背包是很容易的。然后 \(a_i\le 100\),所以你只关注 \(dp\) 数组的后 \(100\) 位是什么。维护矩阵 \([\sum dp,dp_0,dp_1,\dots,dp_{99}]\),构造 \(101\times 101\) 大小的转移矩阵,快速幂即可。但是真想了我好久,菜就多练。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
#define int long long
using namespace std;
const int N=110,mod=1e9+7;
int n,m,ans=1;
int f[N],dp[N];
struct martix
{
	int n,m;
	int a[N][N];
	void init()
	{
		n=m=101;
		for(int i=1;i<=101;i++)
			a[i][i]=1;
	}
	martix operator *(const martix b)const
	{
		martix ans;
		ans.n=n,ans.m=b.m;
		assert(m==b.n);
		memset(ans.a,0,sizeof(ans.a));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=b.m;j++)
				for(int k=1;k<=m;k++)
					ans.a[i][j]+=a[i][k]*b.a[k][j],ans.a[i][j]%=mod;
		return ans;
	}
	martix operator *=(const martix b)
	{
		return *this=*this*b;
	}
}x,y;
martix qpow(martix x,int y)
{
	martix ans;
	ans.init();
	while(y)
	{
		if(y%2==1)ans*=x;
		x*=x,y/=2;
	}
	return ans;
}
signed main()
{
//	freopen("sale.in","r",stdin);
	cin>>n>>m;
	for(int i=1,x;i<=n;i++)
		scanf("%lld",&x),f[x]++;
	if(m<=100)
	{
		dp[0]=1;
		for(int i=1;i<=m;ans+=dp[i],ans%=mod,i++)
			for(int j=1;j<=n;j++)
				if(i>=j)dp[i]+=dp[i-j],dp[i]%=mod;
		cout<<ans;
		return 0;
	}
	dp[0]=1;
	for(int i=1;i<=100;i++)
		for(int j=1;j<=i;j++)
			dp[i]+=f[j]*dp[i-j]%mod,dp[i]%=mod;
	for(int i=1;i<=99;i++)
		ans+=dp[i],ans%=mod;
	x.n=1,x.m=101,y.n=y.m=101;
	x.a[1][1]=ans,y.a[1][1]=y.a[101][1]=1;
	for(int i=1;i<=100;i++)
		x.a[1][i+1]=dp[i];
	for(int i=2;i<=100;i++)
		y.a[i+1][i]=1;
	for(int i=2;i<=101;i++)
		y.a[i][101]=f[102-i];
	martix ans=qpow(y,m-99);
	cout<<(x*ans).a[1][1];
	return 0;
}

10.11 C

原题:AT_joisc2017_c


首先不难想到二分,考虑如何 check。

然后其实两个人碰到一起后可以先不传火,等火炬即将燃尽的时候再传,这样一定是最优的。

接着我是真不会了,我投降。

抄题解的。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const double eps=1e-12;
int n,k,t;
int a[N];
vector<double>f,g;
vector<pair<double,double>>x,y;
bool check(double now)
{
	now*=2;
	f.clear(),g.clear();
	for(int i=k-1;i>=1;i--)
		f.push_back((a[i+1]-a[i])/now);
	for(int i=k+1;i<=n;i++)
		g.push_back((a[i]-a[i-1])/now);
	x.clear(),y.clear();
	double num=0,mi=1e18;
	int id=-1;
	for(int i=0;i<f.size();i++)
	{
		num-=f[i];
		mi=min(mi,num);
		num+=t;
		if(num>-eps)x.push_back({mi,num}),num=0,mi=1e18,id=i;
	}
	num=0,mi=1e18;
	int idd=-1;
	for(int i=0;i<g.size();i++)
	{
		num-=g[i];
		mi=min(mi,num);
		num+=t;
		if(num>-eps)y.push_back({mi,num}),num=0,mi=1e18,idd=i;
	}
	int l=0,r=0;
	num=t;
	while(l<x.size()||r<y.size())
	{
		if(l<x.size()&&num+x[l].fi>=0)num+=x[l].se,l++;
		else if(r<y.size()&&num+y[r].fi>=0)num+=y[r].se,r++;
		else return false;
	}
	x.clear(),y.clear();
	num=0,mi=1e18;
	for(int i=f.size()-1;i>=id+1;i--)
	{
		num-=t;
		mi=min(mi,num);
		num+=f[i];
		if(num>-eps)x.push_back({mi,num}),num=0,mi=1e18;
	}
	num=0,mi=1e18;
	for(int i=g.size()-1;i>=idd+1;i--)
	{
		num-=t;
		mi=min(mi,num);
		num+=g[i];
		if(num>-eps)y.push_back({mi,num}),num=0,mi=1e18;
	}
	l=0,r=0,num=t;
	for(double i:f)
		num-=i,num+=t;
	for(double i:g)
		num-=i,num+=t;
	if(num<0)return false;
	while(l<x.size()||r<y.size())
	{
		if(l<x.size()&&num+x[l].fi>=0)num+=x[l].se,l++;
		else if(r<y.size()&&num+y[r].fi>=0)num+=y[r].se,r++;
		else return false;
	}
	return true;
}
signed main()
{
	cin>>n>>k>>t;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	if(a[1]==a[n])
	{
		puts("0");
		return 0;
	}
	int l=0,r=1e9;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<r<<endl;
	return 0;
}

10.18 D

哦对了其实 10.14 和 10.17 都各有一场,但题目也太傻波一了。

这题 \(n\le 2\times 10^6\) 你还带 \(\log\)????


对于每个 \(i\in [0,n]\),求出有多少个区间 \(\texttt{mex}\) 值为 \(i\)。


也许是我做太少关于 \(\texttt{mex}\) 的题了,但是怎么想到先求出 \(s_i \gets [\texttt{mex} \ge i]\) 的?答案就是 \(s_i-s_{i+1}\)。

然后一个区间 \([l,r]\) 满足 \(\texttt{mex}\ge i\) 当且仅当 \([0,i-1]\) 都在 \([l,r]\) 中出现过。

接着从零开始枚举 \(i\),计 \(l_x\) 为 区间 \([l_x,x]\) 满足 \([0,i-1]\) 都出现过,且 \(l_x\) 最大。

那么 \(s_i=\sum \limits _{x=1}^n l_x\)。

考虑怎么求出这个 \(l_x\)。

\(i=0\) 时 \(l_x=x\),思考怎么从 \(i\) 拓展到 \(i+1\)。

\([l_x,x]\) 可能没有 \(i+1\),那么令 \(l_x\) 为最大的 \(y\) 满足 \(a_y=i+1\) 且 \(y\le x\) 即可。

当然,如果 \([l_x,x]\) 有 \(i+1\) 就不用管了。

直接做的话时间复杂度是 \(\mathcal O(n^2)\) 的,需要优化。

可以发现 \(l\) 是单调不降的。那么我们可以枚举 \(y\),找到 \(l_x>y\) 的修改为 \(y\)。当然,还要满足 \(x\) 小于下一个 \(i+1\) 的位置。在线段树上二分并区间覆盖,时间复杂度为 \(\mathcal O(n \log n)\),略微卡常。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
#define ll long long
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
const int N=3e6+10;
int n;
ll s[N];
vector<int>v[N];
struct ccf
{
	ll x;
	int la,len,num;
}f[N<<2];
void build(int k,int l,int r)
{
	f[k].len=r-l+1,f[k].la=-1;
	if(l==r)return f[k].x=f[k].num=l,void();
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	f[k].x=f[k*2].x+f[k*2+1].x;
	f[k].num=f[k*2+1].num;
}
void pushdown(int k)
{
	if(f[k].la==-1)return ;
	int &x=f[k].la,l=k*2,r=k*2+1;
	f[l].x=(ll)x*f[l].len,f[l].la=x,f[l].num=x;
	f[r].x=(ll)x*f[r].len,f[r].la=x,f[r].num=x;
	x=-1;
}
int ask(int k,int l,int r,int x)
{
	pushdown(k);
	if(l==r)return l+(f[k].num<x);
	int mid=(l+r)/2,s=f[k*2].num;
	if(s>=x)return ask(k*2,l,mid,x);
	return ask(k*2+1,mid+1,r,x);
}
void change(int k,int l,int r,int x,int y,int z)
{
	if(x>y)return ;
	pushdown(k);
	if(x<=l&&r<=y)return f[k].x=(ll)f[k].len*z,f[k].la=f[k].num=z,void();
	int mid=(l+r)/2;
	if(x<=mid)change(k*2,l,mid,x,y,z);
	if(y>mid)change(k*2+1,mid+1,r,x,y,z);
	f[k].x=f[k*2].x+f[k*2+1].x;
	f[k].num=f[k*2+1].num;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		v[read()].push_back(i);
	for(int i=0;i<=n;i++)
		v[i].push_back(n+1);
	build(1,1,n);
	int ma=0;
	for(int i=0;i<=n;i++)
	{
		s[i]=f[1].x;
		if(v[i][0]-1>ma)change(1,1,n,ma+1,v[i][0]-1,0),ma=v[i][0]-1;
		for(int j=0;j+1<v[i].size();j++)
		{
			int l=v[i][j],r=v[i][j+1]-1;
			int k=ask(1,1,n,l);
			change(1,1,n,max(l,k),r,l);
		}
	}
	for(int i=0;i<=n;i++)
		printf("%lld ",s[i]-s[i+1]);
	return 0;
}

10.21 B

定义一棵生成树的权值为所有边权的按位或。给出一张图,\(q\) 次询问,每次询问加一条边权为 \(0\) 的边,询问独立。


赛时只打了 \(\mathcal O((n+m)q \log V)\) 的,主要原因是 C 打太久了

\(\mathcal O((n+m)q \log V)\) 的并不难想,从高到低位每次贪心尝试能不能删除这一位即可。

考虑怎么优化。

如果某一次剩下 \(2\) 个联通块,那么就有可能对答案造成影响。那直接把这两个连通块连起来再跑一次就好了,时间复杂度是 \(\mathcal O((n+m) \log ^2 V+q \log V)\) 的。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
using namespace std;
const int N=1e5+10;
int n,m,q;
int f[N],chk[N],fa[30][N],now[N];
struct ccf
{
	int x,y,z;
}a[N];
int find(int id,int k)
{
	return fa[id][k]==k?k:fa[id][k]=find(id,fa[id][k]);
}
int ___(int k)
{
	return now[k]==k?k:now[k]=___(now[k]);
}
bool check(int id,int s)
{
	int cnt=0;
	for(int i=1;i<=n;i++)
		fa[id][i]=i;
	for(int i=1;i<=m;i++)
	{
		if((a[i].z|s)!=s||find(id,a[i].x)==find(id,a[i].y))continue;
		fa[id][find(id,a[i].x)]=find(id,a[i].y),cnt++;
	}
	for(int i=1;i<=n;i++)
		find(id,i);
	if(cnt==n-1)return true;
	if(cnt!=n-2)return false;
	int x=-1,y=-1;
	for(int i=1;i<=n;i++)
		if(fa[id][i]==i)
			x==-1?x=i:y=i;
	chk[id]=1;
	for(int v=id-1;v>=0;v--)
	{
		int cnt=1,_=s;
		s^=(1<<v);
		for(int i=1;i<=n;i++)
			now[i]=i;
		now[x]=now[y];
		for(int i=1;i<=m;i++)
		{
			if((a[i].z|s)!=s||___(a[i].x)==___(a[i].y))continue;
			now[___(a[i].x)]=___(a[i].y),cnt++;
		}
		if(cnt!=n-1)s^=(1<<v);
	}
	f[id]=s;
	return false;
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	int ans=(1<<30)-1;
	for(int i=29;i>=0;i--)
		ans^=check(i,ans^(1<<i))*(1<<i);
	while(q--)
	{
		int x,y,sum=ans;
		scanf("%d%d",&x,&y);
		for(int i=29;i>=0;i--)
		{
			if(!chk[i]||i==20||i==21)continue;
			if(chk[i]&&fa[i][x]!=fa[i][y])
				sum=min(sum,f[i]);
		}
		printf("%d\n",sum);
	}
	return 0;
}

10.21 C

一个字符串 \(S\) 的长度为 \(k\) 的前缀记作 \(S[1:k]\)。初始时给定 \(n\) 个字符串,第 \(i\) 个字符串记作 \(S_i\),初始时其数值 \(a_i\) 为 \(0\)。

有 \(Q\) 个操作,每个操作是以下其中一种(假设操作时的字符串数量为 \(M\)):

  1. \(\texttt{i\ K\ x}\),对于每个 \(1\le j\le M\),如果 \(S_j[1:K]=S_i[1:K]\),那么将 \(a_j\) 加上 \(x\)。
  2. \(\texttt{i\ K\ T}\),加入新字符串 \(S_{M+1}=S_i[1:K]+T\),\(a_{M+1}=0\)。随后将 \(M\) 增加 \(1\)。
  3. \(\texttt{i}\),查询 \(a_i\)。

一眼丁真,鉴定为 trie 树。

前面 \(n\) 个字符串建树没什么好说的,但是 \(2\) 操作怎么加入?

暴力找 \(s_i\) 的第 \(k\) 位编号显然会 TLE,考虑加速这个过程。

不难想到可以倍增,把 \(S_i\) 最后一个字符的编号记下来,再记下每个点的第 \(2^x\) 个父亲就能倍增了。

之后离线把树建完之后 \(1\) 操作就是给子树的所点加 \(x\),\(3\) 操作就是找字符串最后一个字符的点权。

线段树或者树状数组维护均可。

注意一个字符串要加入之后点权才能被增加。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,q,tot=1,cnt;
int trie[N][30],fa[N][30],f[N],len[N],l[N],r[N],id[N];
string s;
struct query
{
	int op,x,y,k;
}a[N];
void add(int k,int id,string s)
{
	for(int i=0;i<s.size();i++)
	{
		int c=s[i]-'a';
		if(!trie[k][c])
		{
			trie[k][c]=++tot;
			fa[tot][0]=k;
			for(int j=1;j<=20;j++)
				fa[tot][j]=fa[fa[tot][j-1]][j-1];
		}
		k=trie[k][c];
	}
	f[id]=k;
}
int find(int id,int k)
{
	int now=f[id];
	k=len[id]-k;
	for(int i=20;i>=0;i--)
		if(k>=(1<<i))
			k-=1<<i,now=fa[now][i];
	return now;
}
void dfs(int x)
{
	l[x]=++cnt;
	for(int i=0;i<26;i++)
	{
		int to=trie[x][i];
		if(to)dfs(to);
	}
	r[x]=cnt;
}
struct tree
{
	struct ___
	{
		int x,la;
	}f[N<<2];
	void pushdown(int k)
	{
		if(!f[k].la)return ;
		int &x=f[k].la,l=k*2,r=k*2+1;
		f[l].x+=x,f[l].la+=x;
		f[r].x+=x,f[r].la+=x;
		x=0;
	}
	void add(int k,int l,int r,int x,int y,int z)
	{
		if(l>y||r<x)return ;
		if(x<=l&&r<=y)return f[k].x+=z,f[k].la+=z,void();
		pushdown(k);
		int mid=(l+r)/2;
		add(k*2,l,mid,x,y,z);
		add(k*2+1,mid+1,r,x,y,z);
		f[k].x=f[k*2].x+f[k*2+1].x;
	}
	int ask(int k,int l,int r,int x)
	{
		if(l==r)return f[k].x;
		pushdown(k);
		int mid=(l+r)/2;
		return x<=mid?ask(k*2,l,mid,x):ask(k*2+1,mid+1,r,x);
	}
}t;
int tg[N];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		len[i]=s.size();
		add(1,i,s);
	}
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int &op=a[i].op,&x=a[i].x,&y=a[i].y,&k=a[i].k;
		string s;
		scanf("%lld%lld",&op,&x);
		if(op==1)scanf("%lld%lld",&y,&k);
		else if(op==2)
		{
			scanf("%lld",&k);
			cin>>s;
			id[i]=++n;
			len[id[i]]=k+s.size();
			add(find(x,k),n,s);
		}
	}
	dfs(1);
	for(int i=1;i<=q;i++)
	{
		if(a[i].op==1)
		{
			int k=find(a[i].x,a[i].y);
			t.add(1,1,cnt,l[k],r[k],a[i].k);
		}
		else if(a[i].op==2)
		{
			int k=t.ask(1,1,cnt,l[f[id[i]]]);
			tg[id[i]]=k;
		}
		else printf("%lld\n",t.ask(1,1,cnt,l[f[a[i].x]])-tg[a[i].x]);
	}
	return 0;
}

10.23 D

给出一个序列 \(a_i\),可以给一段长度为 \(m\) 的区间加上一个等差数列。问序列第 \(k\) 大能是多少。


看见第 \(k\) 大就不会了。看了题解发现可以二分,这种套路要速速学会。

二分答案为 \(x\),记 \(f_i\) 为以 \(i\) 为左端点能使多少个数大于 \(k\)。

容易发现能使一个点大于 \(k\) 的左端点使一段区间。

这个区间并不难找,作差然后在等差数列上找第一个比差大的即可。细节略多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,k,m,c,d;
int a[N],f[N];
bool check(int x)
{
	for(int i=1;i<=n;i++)
		f[i]=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=x)f[1]++;
		else
		{
			if(c+min(i-1,m-1)*d+a[i]<x)continue;
			int l=x-a[i]-c,r=x-a[i]-c;
			l=max(1ll,i-m+1);
			r=r<=0?i:max(0ll,d==0?0:i-(r/d+(r%d!=0)));
			f[l]++,f[r+1]--;
		}
	}
	for(int i=1;i<=n;i++)
	{
		f[i]+=f[i-1];
		if(f[i]>=k)return true;
	}
	return false;
}
signed main()
{
	cin>>n>>k>>m>>c>>d;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	int l=0,r=1e15;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

11.11 B

CSP 结束喽,NOIP RP++++++++++++++++++++++++++!!

最近不想钻研难题,怎么会是呢?

B 和 C 都挺有质量的,但看到是紫题就都直接看题解了。马上纠正错误思想!

其实前面还有两场模拟赛,但是题目不是过难就是过水,质量不高。


原题:AT_agc016_d

一个序列,一次操作可以将某个位置变成整个序列的异或和。问最少几步到达目标序列。


很遗憾,直接开题解了,所以不能一步一步分析题目。

手玩样例再随意证明一下,可以发现如果原异或和是 \(x\),并用 \(x\) 替换了 \(a_i\),那么新的异或和就是 \(a_i\)。

也就是说,不妨令 \(a_{n+1}=\bigoplus\limits_{i=1}^n a_i\),每次操作就是在交换 \(i\in [1,n]\) 的 \(a_i\) 和 \(a_{n+1}\)。

判断无解是容易的,令 \(a_{n+1}=\bigoplus\limits_{i=1}^n a_i\),\(b_{n+1}=\bigoplus\limits_{i=1}^n b_i\)。然后判断 \(a\) 和 \(b\) 构成的可重集是否相同即可。

接着观察题解发现可以建图。若 \(a_i\neq b_i\),连边 \(b_i\to a_i\),有解的情况下会建成若干个环。假设现在手上的异或和为 \(k\)。

把 \(k\) 作为当前位置,考虑现在操作 \(a_i\) 在图上的意义,分为两种情况讨论:

  • 存在边 \(k\to a_i\),那么将 \(k\) 移动到 \(a_i\),删除这条边,边数减一。

  • 不存在边 \(k\to a_i\),但存在边 \(y\to a_i\)。那么将这条边更改为 \(y\to k\),并把 \(k\) 移动到 \(a_i\)。

考虑初始的 \(k\) 是不是一个孤立点,若不是,直接从当前环开始一条一条边消除,做完一个连通块后通过操作二前往下一个环,答案为 边数+环个数-1。若是,则需要额外花费一次前往第一个环,答案为 边数+环个数。

实现略有细节,需要离散化。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,l,r,tot,m,ans;
int a[N],b[N],e[N],f[N];
multiset<int>sa,sb;
int find(int k)
{
	return f[k]==k?k:f[k]=find(f[k]);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),sa.insert(a[i]),l^=a[i];
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]),sb.insert(b[i]),r^=b[i];
	n++;
	a[n]=l,b[n]=r;
	sa.insert(l),sb.insert(r);
	if(sa!=sb)return puts("-1"),0;
	for(int i=1;i<=n;i++)
		if(a[i]!=b[i]||i==n)
			e[++tot]=a[i],e[++tot]=b[i],ans+=i<n;
	sort(e+1,e+1+tot);
	m=unique(e+1,e+1+tot)-e-1;
	for(int i=1;i<=m;i++)
		f[i]=i;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==b[i])continue;
		a[i]=lower_bound(e+1,e+1+m,a[i])-e;
		b[i]=lower_bound(e+1,e+1+m,b[i])-e;
		f[find(a[i])]=find(b[i]);
	}
	for(int i=1;i<=m;i++)
		ans+=find(i)==i;
	cout<<ans-1;
	return 0;
}

11.11 C

原题:AT_arc108_f

给定一棵 \(n\) 个节点的树。你需要对每个节点黑白染色。

设 \(x\) 表示白色点之间的最大距离,\(y\) 表示黑色点之间的最大距离,那么定义一种染色的权值为 \(\max(x,y)\)。如果某种颜色没有出现那么对应的 \(x/y\) 就是 \(0\)。

求所有 \(2^n\) 种染色方式的权值和。对 \(10^9+7\) 取模。


需要对树有一定的理解,这样能够发现最大距离的一对点一定至少有一个在直径的端点上。

首先如果直径的端点颜色相同,那么其它 \(n-2\) 个点随便染都不影响答案,权值和为 \(2^{n-1}\times L\),其中 \(L\) 为直径,多乘一个 \(2\) 是端点颜色可以是黑或白。

然后考虑端点颜色不同的情况,记 \(g_i\) 为答案为 \(i\) 的染色方案数,答案即为 \(\sum g_i\times i\)。

再记每个点到两个端点的距离为 \(dis_{1/2}\)。考虑一下刚才那个的上下界,也就是权值的最大最小值。

最大值显然是直径的长度,最小值仔细思考发现是 \(\max(\min(dis1_i,dis2_i))\)。求这个上下界的原因下面再说。

考虑怎么去求这个 \(g_i\),再记 \(f_i\) 为答案不超过 \(i\)(\(\le i\))的方案数,那么 \(g_i=f_i-f_{i-1}\)。

继续考虑怎么去求这个 \(f_i\),再再记 \(cnt_i\) 为 距离两个端点都不超过 \(i\)(\(\le i\))的点的个数,那么 \(f_i=2^{cnt_i}\)。稍微解释一下这个式子,距离不超过 \(i\) 的点可以随便染色,反正答案不超过 \(i\)。但是距离超过了 \(i\) 的点必须染 \(dis1_i\) 和 \(dis2_i\) 中更小的那种颜色,通过上面的求下界可以保证 \(\min(dis1_x,dis2_x)\le i\)。最后的答案还要乘 \(2\),黑白颜色可以交换。

思维的跳跃很多,真做不出来。膜拜大神。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,_,l,r,ans;
int dis[N],dis1[N],dis2[N],cnt[N],f[N];
vector<int>v[N];
int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y%2)ans*=x,ans%=mod;
		x*=x,x%=mod,y/=2;
	}
	return ans;
}
void dfs(int x,int fa,int *dis,int &k)
{
	if(dis[x]>dis[k])
		k=x;
	for(int i:v[x])
	{
		if(i==fa)continue;
		dis[i]=dis[x]+1;
		dfs(i,x,dis,k);
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0,dis,l);
	dfs(l,0,dis1,r);
	dfs(r,0,dis2,_);
	int mi=0,ma=0;
	for(int i=1;i<=n;i++)
	{
		ma=max(ma,dis1[i]);
		if(i==l||i==r)continue;
		mi=max(mi,min(dis1[i],dis2[i]));
		cnt[max(dis1[i],dis2[i])]++;
	}
	for(int i=1;i<=n;i++)
		cnt[i]+=cnt[i-1];
	for(int i=mi;i<=n;i++)
		f[i]=qpow(2,cnt[i]);
	for(int i=mi;i<=ma;i++)
	{
		int g=f[i]-f[i-1]+mod;
		ans+=g*i%mod,ans%=mod;
	}
	ans*=2;
	ans+=qpow(2,n-1)*ma%mod;
	cout<<ans%mod;
	return 0;
}

标签:总结,10,return,int,mi,近期,fa,num
From: https://www.cnblogs.com/XuFromGD-FS/p/-/NOIP

相关文章

  • LangGraph高级特性:总结与注意事项
    LangGraph作为一个强大的图结构程序设计工具,提供了许多高级特性来支持复杂的AI应用开发。本文将深入探讨LangGraph的一些关键概念和注意事项,帮助开发者更好地利用这个工具。1.数据状态与归纳函数在LangGraph中,理解数据状态的处理方式至关重要。默认情况下,节点返回的字典数据会......
  • 2024ICPC杭州赛后总结
    首先,还是恭喜一下我们队第一次参赛就拿到了,非常的幸运赛前事情还得从网络赛说起,由于我们队网络赛的发挥实在不好,导致最后只得到了一场比赛机会,在选择赛站的时候,就非常的犹豫,我们知道等学长都选完之后,留下给我们的赛站就不多了,我们应该选一个比较有举办经验的赛站,但是杭州站......
  • CSP2024总结(学术版)
    J组T4一道/赛上觉得很难/下来也听说很难/但听老师一讲也觉得只有中位绿/的题。题目传送门,首先想到\(r=1\)时的做法,不难看出可以使用一个标记数组来存储,然后依次寻找离他最近的\(1\)看是否满足要求,标记即可。\(5\)pts拿到手。然后发现可以扩展出一种类似递推的思想,设\(f_......
  • 2024.11.11总结
    John的农场是一张N*N的方格图,贝茜住在左上角(1,1),John住在右下角(N,N)。现在贝茜要去拜访John,每次都只能往四周与之相邻的方格走,并且每走一步消耗时间T。同时贝茜每走三步就要停下来在当前方格吃草,在每个方格吃草的用时是固定的,为H[i][j]。John想知道贝茜最少要多久才能到达Joh......
  • NOIP2024模拟赛#18 总结
    头要炸了。T1题面很好懂,手玩了一下发现答案最小是\((m-1)\timesn\)。可能会多出来一个长度为\(k\)的部分,会发现如果多出来一个长度为\(k\)的部分且合法,那么单个串\(1\simk\)位与\(n-k+1\simn\)位一定相同,\(k+1\simn\)位与\(1\simn-k\)一定相同。Hash判一下即......
  • 2024/11/11日工作总结
    完成数据结构pta实验题:6-3链表逆置:本题要求实现一个函数,将给定单向链表逆置,即表头置为表尾,表尾置为表头。链表结点定义如下:structListNode{intdata;structListNode*next;};函数接口定义:structListNode*reverse(structListNode*head);其中head是用户传入的链......
  • 快速排序,思路总结与实现
    思路找基准值(pivot)pivot=startorend比基准值小的放左边,大的放右边实现双指针,left从左到右找比基准值大的元素,right从右到左找比基准值小的元素找到后交换left和right指针的内容直到left=right这是递增排序,递减排序情况相反如果pivot=start,则右指针先动,否......
  • DP 技巧总结
    DP技巧总结进行了为期接近一周的DP特训,做了很多同学找的高质量题目,也学到了很多技巧。现在来把一些感觉比较有价值的技巧进行一些统一的总结。插入型DP这个东西之前应该在选拔期间的一场周测中见过,但是隔了很久,已经有所遗忘。这次题单里出现了两道类似的题目,我都不会做。其......
  • 迟来的2023秋招总结,互联网&银行&国企&腾讯
    复制自本人知乎首先现在是2023年四月中旬,毕业的事情暂时告一段落,于是想吐槽顺便记录一下。23秋招其实是在2022年,而2022实在是这几年来行情最差的一年。犹记得20、21年秋天各个大厂号称“史上最大规模的秋招“,hc多开的薪资也高,一年比一年倒挂。当时我还觉得23年会更美好,没想到现......
  • 渗透测试中登录框骚操作总结(非常详细)零基础入门到精通,收藏这一篇就够了
    由于测试过程中很多系统我们能接触到的只有一个登陆界面,所以要充分挖掘漏洞,进行深入操作登录注册万能密码绕过登录存在SQL注入的情况下,有可能使用万能密码直接登录admin'or'1'='1'--``admin'OR4=4/*``"or"a"="a``'or''='``'or1=1--有超级多登录口SQL......