Java教程

(联考)noip83

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

T1

考场拿 \(O(n)\) 拍自己 \(O(n\log n)\) 的,交的后者,于是死了
,只有60pts,本地1.3s的,accoder上跑不出来....

\(O(n)\) 的还要大力卡常...

本地0.7s才能过就离谱。

直接搜即可。

每个点只会被更新一次,均摊 \(O(n)\) 。

T2

部分分很多,80pts。

25pts:暴力乱写。

25+20pts:直接sort完二分。

25+20+20pts:monkey说拿指针乱扫。

25+20+20+15pts:用树状数组维护一下到根节点有多少比当前点小的,dfs一遍即可。

100pts:

题目实际上就是在求在以 \(rt\) 为根时,每个点的子树内有多少个点权值比它小的点的个数的总和。

用task4的做法,先求出以1为根时的答案。

然后就可以用换根dp求出每个点 \(u\) 的答案。

具体转移:

从点 \(u\) 转移到点 \(v,v\in son_{u}\) 时,通过画图可以发现,以1为根时点 \(v\) 的子树内的点,都少经过一个点 \(u\) ,整棵树除了以 \(v\) 为根节点的子树的那部分,都要多经过一个点 \(v\) 。

于是可以设 \(g_{v,1}\) 表示以 \(v\) 为根的子树有多少点的权值比 \(w_{v}\) 小, \(g_{v,0}\) 表示以 \(v\) 为根的子树中多少比 \(u,u=fa_{v}\) 的权值小的点, \(f_{v}\) 表示以 \(v\) 为根时的答案。

转移则有: \(f_{v}=f_{u}-g_{v,0}+query(w_{v}-1)-g_{v,1}\)

\(g\) 数组同样可以通过dfs+BIT得到,差分即可。

\(query\) 为BIT的查询函数,查询有多少比当前点权值小的点。

求 \(g\) 时的dfs已经更新了BIT,所以转移时的差分直接用BIT即可。

Code
#include<cstdio>
#include<cctype>
#include<algorithm>
#define re register
const int MAX = 1e6+7;
#define scanf oma=scanf
#define freopen file=freopen
using std::sort;
using std::unique;
using std::lower_bound;
int oma;
FILE* file;
namespace some
{
	struct stream
	{
		template<typename type>inline stream &operator >>(type &s)
		{
			bool w=0; s=0; char ch=getchar();
			while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
			while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
			return s=w?-s:s,*this;
		}
	}cin;
	int n,q,w[MAX];
	int tmp[MAX],tot;
	#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Binary_Index_Tree
{
	struct BIT
	{
		int val[MAX];
		#define lowbit(x) x&-x
		void modify(int x,int w)
		{ for(re int i=x; i<=n+1; i+=lowbit(i)) { val[i] += w; } }
		int query(int x,int res = 0)
		{ for(re int i=x; i; i-=lowbit(i)) { res += val[i]; } return res; }
	}bit;
}using namespace Binary_Index_Tree;
namespace Graph
{
	struct graph
	{ int next,to; }edge[MAX<<1];
	int cnt=1,head[MAX];
	auto add = [](int u,int v) { edge[++cnt] = (graph){head[u],v},head[u] = cnt; };
	int g[MAX][2]; // 0 fa 1 self
	long long f[MAX];
	void dfs_rt(int u,int fa)
	{
		bit.modify(w[u],1);
		for(re int i=head[u],v; i; i=edge[i].next)
		{
			v = edge[i].to;
			if(v!=fa)
			{ f[1] += bit.query(n+1)-bit.query(w[v]); dfs_rt(v,u); }
		}
		bit.modify(w[u],-1);
	}
	void dfs_pre(int u,int fa)
	{
		g[u][1] -= bit.query(w[u]-1);
		if(u!=1) { g[u][0] -= bit.query(w[fa]-1); }
		bit.modify(w[u],1);
		for(re int i=head[u],v; i; i=edge[i].next)
		{
			v = edge[i].to;
			if(v!=fa)
			{ dfs_pre(v,u); }
		}
		g[u][1] += bit.query(w[u]-1);
		if(u!=1) { g[u][0] += bit.query(w[fa]-1); }
	}
	void dfs_ex(int u,int fa)
	{
		for(re int i=head[u],v; i; i=edge[i].next)
		{
			v = edge[i].to;
			if(v!=fa)
			{ f[v] = f[u]-g[v][0]+bit.query(w[v]-1)-g[v][1]; dfs_ex(v,u); }
		}
	}
}using namespace Graph;
namespace right
{
	auto solve = []() -> void
	{
		for(re int i=1; i<=n; i++)
		{ tmp[i] = w[i]; }
		sort(tmp+1,tmp+1+n);
		//printf("%d\n",lower_bound(tmp+1,tmp+1+n,w[2])-tmp-1);
		tot = unique(tmp+1,tmp+1+n)-tmp-1;
		for(re int i=1; i<=n; i++)
		{ w[i] = lower_bound(tmp+1,tmp+1+tot,w[i])-tmp; }
		dfs_rt(1,0),dfs_pre(1,0),dfs_ex(1,0);
		for(re int i=1,u; i<=q; i++)
		{ cin >> u; printf("%lld\n",f[u]); }
	};
};
namespace OMA
{
	auto main = []() -> signed
	{
		//freopen("node.in","r",stdin); freopen("my.out","w",stdout);
		freopen("tears.in","r",stdin); freopen("tears.out","w",stdout);
		cin >> n >> q;
		for(re int i=1; i<=n; i++)
		{ cin >> w[i]; }
		for(re int i=1,u,v; i<n; i++)
		{ cin >> u >> v; add(u,v),add(v,u); }
		right::solve();
		return 0;
	};
}
signed main()
{ return OMA::main(); }

T3

经典dp+线段树维护矩阵。

T4

求个差分数组 \(delta\),如果 \(delta>0\) 则压入队列,反之,如果要求最大值,则用队尾元素来消当前 \(delta\) ,把距离远的留给后边的。最小值则相反,用队首元素来消,距离近的留给后面的。

差分数组要算到 \(n+1\) ,因为操作区间实际上是 \([l,r-1]\) 。

同时不难发现,最短时间则为 \(\sum_{i=1}^{n}\max(delta_{i},0)\) 。

因为 \(d_{i}\ge0\) ,所以当前小于0的 \(delta_{i}\) 一定能被队列里的元素消成0。

用deque实现即可。

反思总结

csp后第一次模拟,还是联考,考的并不太行,T1没算复杂度,高估了accoders的评测机,T2沉迷于部分分,还打挂了,正解不算难,却往换根dp上想,T4的部分分同样写挂。

很多地方做的还是不太行,T1没细想,T3暴力浪费了时间,考试过程中也会走私。

noip也不远了,只能说继续加油吧。

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