noip83

本文主要是介绍noip83，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考试过程：这次考试，总体来说难度是不大的，我觉得前两题是可做的，首先是第一题，我觉得是个线段树板子题，也没多想，就是数据范围有点大，但是我没什么好方法优化，就打了个线段树走了。
然后是T2，首先想出了\(o(n\times log(n))\)求出以1为根的答案，然后考虑移动。不难发现，当根节点移动一次时，答案相对于上一次的变化量由两部分组成：
1.当前点为根的子树内的点的\(w\)小于上一次的根节点的\(w\)的数量。
2.除去当前点为根的子树，剩下的点中\(w\)小于当前根节点的数量。
但是我在考场上想复杂了，这是我经过优化之后的想法，当时的做法还要考虑每个子树对当前点的贡献，比较复杂，打了个树套树，但是卡在最后一个问题没有解决。就是如何在总复杂度在\(O(n\times log(n))\)左右求出以每个点为根的子树内\(w\)值小于当前根节点的点的个数。
考虑解决这个问题：因为主席树可以支持查询区间第\(k\)大，那么我们可以在\(dfs\)序上建一颗主席树，那么显然我们把\(w\)数组经过离散化之后就知道了\(w\)的排名，那么我们直接在主席树上查询即可。
剩下的T3，T4没什么时间做了，就打了个暴力。

T1 树上的数

思路：因为5e6的数据带个\(log\)达到了\(1e8\)级别，在那个超快的评测机上根本过不去，但是线段树无法进行优化，考虑另外的思路。
思考如果我们要打暴力，那么应该是从当前根节点往下递归，统计出当前子树的大小。
考虑优化这个过程，我们可以对经过的节点打上标记，这样我们就不会经过重复的节点，这样的复杂度是\(o(n+m)\)的。
代码如下：

AC_code


#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define next netetet
#define head heaeaea
using namespace std;
const int N=5e6+10;
int n,m,tot,ans,sum;
int to[N],next[N],head[N],Q[N];
int fa,q,l,r;
bool vis[N];
ii read()
{
	int x=0;char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?(x):(-x);
}
iv check(int st)
{
	vis[st]=1;--sum;
	for(re i=head[st];i;i=next[i]) if(!vis[to[i]]) check(to[i]); 
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int a,b,x,y;
	n=read(),m=read();
	a=read(),b=read();
	fa=1;
	to[++tot]=2;
	next[tot]=head[1];
	head[1]=tot;
	for(re i=3;i<=n;++i)
	{
		fa=((1ll*fa*a+b)^19760817)%(i-1)+1;
		to[++tot]=i;
		next[tot]=head[fa];
		head[fa]=tot;
	}
	q=read(),x=read(),y=read();
	sum=n;
	for(re i=1;i<=m;i++)
	{
		if(!sum) break;
		if(i!=1) q=(((1ll*q*x+y)^19760817)^(i<<1))%(n-1)+2;
		if(!vis[q])
		{
			l=1,r=0;
			Q[++r]=q;
			while(l<=r)
			{
				int now=Q[l++];
				vis[now]=1;
				--sum;
				for(re j=head[now];j;j=next[j])
				{
					if(!vis[to[j]]) Q[++r]=to[j];
				}	
			}
		}
		ans^=sum;
	}
	printf("%d\n",ans);
	return 0;
}

T2 时代的眼泪

思路：首先想出了\(o(n\times log(n))\)求出以1为根的答案，然后考虑移动。不难发现，当根节点移动一次时，答案相对于上一次的变化量由两部分组成：
1.当前点为根的子树内的点的\(w\)小于上一次的根节点的\(w\)的数量。
2.除去当前点为根的子树，剩下的点中\(w\)小于当前根节点的数量。
但是我在考场上想复杂了，这是我经过优化之后的想法，当时的做法还要考虑每个子树对当前点的贡献，比较复杂，打了个树套树，但是卡在最后一个问题没有解决。就是如何在总复杂度在\(O(n\times log(n))\)左右求出以每个点为根的子树内\(w\)值小于当前根节点的点的个数。
考虑解决这个问题：因为主席树可以支持查询区间第\(k\)大，那么我们可以在\(dfs\)序上建一颗主席树，那么显然我们把\(w\)数组经过离散化之后就知道了\(w\)的排名，那么我们直接在主席树上查询即可。
代码如下：

AC_code


#include<bits/stdc++.h>
#define ll long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define next netetetetet
using namespace std;
const int N=1e6+10;
int n,q,tot,cnt,timi,zx;
int w[N],fa[N],lsh[N],dfn[N],size[N],root[N];
ll ans[N],he[N];
int to[N<<1],next[N<<1],head[N];
ii read()
{
	int x=0;char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?(x):(-x);
}
iv add(int x,int y)
{
	to[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
struct Segment_Tree
{
	#define mid ((l+r)>>1)
	int sum[N<<2],lc[N<<2],rc[N<<2];
	ii insert(int las,int l,int r,int p)
	{
		int now=++zx;
		lc[now]=lc[las];
		rc[now]=rc[las];
		if(l==r)
		{
			sum[now]=sum[las]+1;
			return now;
		}
		if(mid>=p) lc[now]=insert(lc[las],l,mid,p);
		else rc[now]=insert(rc[las],mid+1,r,p);
		sum[now]=sum[lc[now]]+sum[rc[now]];
		return now;
	}
	ll query(int las,int now,int l,int r,int z)
	{
		if(l==r) return (l==z)?0:sum[now]-sum[las];
		int out=0;
		if(mid<z)
			return sum[lc[now]]-sum[lc[las]]+query(rc[las],rc[now],mid+1,r,z);
		return query(lc[las],lc[now],l,mid,z);
	}
	#undef mid
}T;
struct Seg
{
	int sum[N<<1];
	iv add(int x) {for(;x<=cnt;x+=(x&(-x))) ++sum[x];}
	iv del(int x) {for(;x<=cnt;x+=(x&(-x))) --sum[x];}
	ll query(int x)
	{
		int out=0;
		for(;x;x-=(x&(-x))) out+=sum[x];
		return out;
	}		
}S;
iv dfs(int st,int f)
{
	dfn[st]=++timi;
	size[st]=1;
	root[timi]=T.insert(root[timi-1],1,cnt,w[st]);
	S.add(w[st]);
	ans[1]+=S.query(cnt)-S.query(w[st]);
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==f) continue;
		dfs(p,st);
		size[st]+=size[p];
		S.del(w[p]);
	}
}
iv check(int st,int f)
{
	if(st!=1)
	{
		ll now=ans[f];
		now-=T.query(root[dfn[st]-1],root[dfn[st]+size[st]-1],1,cnt,w[f]);
		now+=he[w[st]-1]-T.query(root[dfn[st]-1],root[dfn[st]+size[st]-1],1,cnt,w[st]);
		ans[st]=now;
	}
	for(re i=head[st];i;i=next[i])
	{
		if(to[i]==f) continue;
		check(to[i],st);
	}
}
signed main()
{
	freopen("tears.in","r",stdin);
	freopen("tears.out","w",stdout);
	n=read(),q=read();
	for(re i=1;i<=n;i++) w[i]=read(),lsh[i]=w[i];
	sort(lsh+1,lsh+n+1);
	cnt=unique(lsh+1,lsh+n+1)-lsh-1;
	for(re i=1;i<=n;i++)
	{
		w[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
		++he[w[i]];	
	}
	for(re i=1;i<=cnt;i++) he[i]+=he[i-1];
	int x,y;
	for(re i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
	dfs(1,0);
	check(1,0);
	while(q--)
	{
		x=read();
		printf("%lld\n",ans[x]);
	}
	return 0;
}

T3 传统艺能

思路，先考虑没有修改的情况，设\(f_{i,a}\)表示考虑前\(i\)个位置，以\(a\)为结尾的方案数，那么转移是这样的\(f_{i,a}=f_{i-1,a}+f_{i-1,b}+f_{i-1,c}+1,f_{i,b}=f_{i-1,b},f_{i,c}=f_{i-1,c}\),其余情况同理。
那么这样的转移是\(o(n)\)的，考虑优化。不难发现我们的转移可以写成矩阵乘的形式，
以\(A\)结尾为例：
1 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
一到三行分别表示\(A,B,C\),最后一行表示\(1\).
因为有修改和区间查询，那么我们可以考虑用线段树维护这个东西。
线段树的每个叶子几点都是一个矩阵，上面的节点维护矩阵相乘的结果。那么修改操作就是单点修改。
对于询问操作，我们可以定义一个初始矩阵\(0 0 0 1\)表示\(A,B,C,1\)，将初始矩阵与线段树进行区间查询的矩阵相乘即可。但是我们发现答案就是线段树上矩阵的第四行的前三列的加和，那么我们直接输出即可。
代码如下：

AC_code


#include<bits/stdc++.h>
#define ll long long
#define int long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
using namespace std;
const int N=1e5+10;
const int mo=998244353;
int n,m;
long long ans;
char s[N],c[N];
ii read()
{
	int x=0;char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?(x):(-x);
}
struct mat
{
	int a[5][5];
};
mat calc(mat x,mat y)
{
	mat z;
	memset(z.a,0,sizeof(z.a));
	for(re i=1;i<=4;i++)
	{
		for(re j=1;j<=4;j++)
		{
			for(re k=1;k<=4;k++)
			{
				z.a[i][j]=(z.a[i][j]+1ll*x.a[i][k]*y.a[k][j])%mo;
			}
		}
	}
	return z;
}
struct Segment_Tree
{
	#define mid ((l+r)>>1)
	#define lc (rt<<1)
	#define rc (rt<<1|1)
	mat sum[N<<2];
	iv pp(int rt)
	{
		sum[rt]=calc(sum[lc],sum[rc]);
	}
	iv build(int rt,int l,int r)
	{
		if(l==r)
		{
			if(s[l]=='A')
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==1) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			else if(s[l]=='B')
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==2) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			else
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==3) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			return;	
		}
		build(lc,l,mid),build(rc,mid+1,r);
		pp(rt);
	}
	iv change(int rt,int l,int r,int p)
	{
		if(l==r)
		{
			if(s[l]=='A')
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==1) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			else if(s[l]=='B')
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==2) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			else
			{
				for(re i=1;i<=4;i++)
				{
					for(re j=1;j<=4;j++)
					{
						if(i==3) sum[rt].a[j][i]=1;
						else
						{
							if(j==i) sum[rt].a[j][i]=1;
							else sum[rt].a[j][i]=0;
						}
					}
				}
			}
			return;	
		}
		if(mid>=p) change(lc,l,mid,p);
		else change(rc,mid+1,r,p);
		pp(rt);	
	}
	mat query(int rt,int l,int r,int L,int R)
	{
		if(L<=l and r<=R) return sum[rt];
		if(mid>=R) return query(lc,l,mid,L,R);
		if(mid<L) return query(rc,mid+1,r,L,R);
		return calc(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
	}
	#undef mid
	#undef lc
	#undef rc
}T;
signed main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	n=read(),m=read();
	scanf("%s",s+1);
	T.build(1,1,n);
	int opt,x,y;
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			x=read();
			scanf("%s",c+1);
			if(s[x]==c[1]) continue;
			s[x]=c[1];
			T.change(1,1,n,x);
		}
		else
		{
			x=read(),y=read();
			mat ans=T.query(1,1,n,x,y);
			printf("%lld\n",(ans.a[4][1]+ans.a[4][2]+ans.a[4][3])%mo);
		}
	}
	return 0;
}

T4 铺设道路

注意是差分的过程，所以要算\(n+1\)项。
代码如下：

AC_code


#include<bits/stdc++.h>
#define int long long
#define ll long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
using namespace std;
const int N=3e5+10;
const int mo=1e9+7;
int n,ans,mx,mn;
int d[N],b[N],c[N];
queue<int> q;
stack<int> s;
ii read()
{
	int x=0;char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?(x):(-x);
}
signed main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	n=read();
	for(re i=1;i<=n;i++) d[i]=read();
	for(re i=1;i<=n+1;i++) b[i]=d[i]-d[i-1],c[i]=b[i];
	for(re i=1;i<=n+1;i++) ans=ans+max(0ll,b[i]);
	printf("%lld\n",ans);
	for(re i=1;i<=n+1;i++)
	{
		if(b[i]>0) q.push(i),s.push(i);
		else
		{
			if(b[i]==0) continue;
			int tmp=-b[i];
			while(tmp>0 and q.size())
			{
				if(b[q.front()]<=tmp)
				{
					tmp-=b[q.front()];
					mx=(mx+(i-q.front())*(i-q.front())%mo*b[q.front()])%mo;
					q.pop();
				}
				else
				{
					mx=(mx+(i-q.front())*(i-q.front())%mo*(tmp))%mo;
					b[q.front()]-=tmp;
					break;
				}
			}
			tmp=-c[i];
			while(tmp>0 and s.size())
			{
				if(c[s.top()]<=tmp)
				{
					tmp-=c[s.top()];
					mn=(mn+(i-s.top())*(i-s.top())%mo*c[s.top()])%mo;
					s.pop();
				}
				else
				{
					mn=(mn+(i-s.top())*(i-s.top())%mo*(tmp))%mo;
					c[s.top()]-=tmp;
					break;
				}
			}
		}
	}
	printf("%lld\n%lld\n",mn,mx);
	return 0;
}

这篇关于noip83的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

noip83

T1 树上的数

T2 时代的眼泪

T3 传统艺能

T4 铺设道路

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯