Java教程

NOIP 模拟六 考试总结

本文主要是介绍NOIP 模拟六 考试总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

T1辣鸡

T1就搞得这莫不愉快。。

大致题意是给你几个矩形,矩形覆盖的点都标记上,每个矩形无重复部分,求满足(x,y)
(x+1,y+1)都标记过的点对数,范围1e9。

看起来很牛的样子,我确实也被1e9吓怕了,可是事实上这道题的处理方式就是暴力。首先有N=1的部分分,这也提示我们计算时要分成矩形内部和边界上。考虑到要相邻才行,而数据是无序的,上来先根据X1,Y1来sort一下,这样做方便暴力查找。

找的时候竖着就是X1+1==X2之时,横着有两种,因为第一关键字是X1,所以Y1不一定严格递增。那么就是i的Y1+1 ==j的Y2 或 i,j反过来。这里用的是或的关系,是因为Y1和Y2有相等的情况,并列的话会算两次;

还有一个重要的细节就是x,y和x+1,y+1;此时不会有相邻的边,但是会有一个点对。好了,就这样暴力的解决了,细节还是蛮多的。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
struct ss
{int x1,x2,y1,y2;}zxb[100001];
inline bool cmp1(ss i,ss j)
{if(i.x1==j.x1)return i.y1<j.y1;
return i.x1<j.x1;
}
signed main()
{	scanf("%lld",&n);
	int mx=0,my=0;
	for(int i=1;i<=n;++i)
	{	int a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		mx=max(mx,c);my=max(my,d);
		zxb[i].x1=a,zxb[i].y1=b;zxb[i].x2=c;zxb[i].y2=d;
		ans+=(d-b)*(c-a)*2;

	}
	sort(zxb+1,zxb+1+n,cmp1);
	for(int i=1;i<=n;++i)
	for(int j=i+1;j<=n;++j)
	{	if(zxb[i].x2+1<zxb[j].x1)break;
		if(zxb[i].x2+1==zxb[j].x1)
		{	int mm=min(zxb[i].y2,zxb[j].y2)-max(zxb[i].y1,zxb[j].y1);
			if(mm>=0)
			{	ans+=mm*2;
				if(zxb[i].y2!=zxb[j].y2)++ans;
				if(zxb[i].y1!=zxb[j].y1)++ans;
			}
		}
		if(zxb[i].y2+1==zxb[j].y1 || zxb[i].y1-1==zxb[j].y2)
		{	int mm=min(zxb[i].x2,zxb[j].x2)-max(zxb[i].x1,zxb[j].x1);
			if(mm>=0)
			{
				ans+=mm*2;
				if(zxb[i].x2!=zxb[j].x2)++ans;
				if(zxb[i].x1!=zxb[j].x1)++ans;
			}
		}
		if(zxb[i].x2+1==zxb[j].x1 and (zxb[i].y2+1==zxb[j].y1 or zxb[i].y1==zxb[j].y2+1))++ans;
	}
	cout<<ans<<endl;
}

T2模板

嗯?模板?你确定?

反正我是不信。。。

考场上我感觉数据结构很亲切,似乎是最可做的一题,于是开干。LCT 合并打了TM
俩小时,最后越打越TM像暴力,好吧,就算是暴力也有好多分数的,但是TM的tag根本就打不下去,然后上了欧拉序,in,out肯本JB加不起来,MD傻逼桶卡的难受。
2 hours later 考试过半,我还一分没拿,当场暴毙。还是老老实实打暴力。结果暴力TM忘了判重,就十分。。。。。。

部分分有一档是不需要考虑桶的,然而我直接弃掉了,根本没看见。

正解是线段树merge,比较新颖的操作是以时间为下标,然后维护操作时不用管到根怎样怎样,把操作节点的信息合并上去就好。其实好象是树套树,因为每一个节点都是一颗权值线段树。我一时间为下标是为了统计优先级,线段树干这个活要用二分,其实平衡树貌似更适合干这事。话说我也好久没打平衡树了,就当review.

具体思路,先把操作插入每个节点,然后dfs从叶子往根上进行平衡树合并,其实就是把size较小的一棵树插入size较大的树中,然后更新父亲所对应的平衡树id。这样的话我们时间就解决了,考虑个数种数。一种思路是把相同种的球时间靠前的val设为1,如果出现过,则设为0.这样是考虑时间优先,注意此处的val设为0并不是说这个点不放球,而是说放但是对ans没有贡献.这里需要在插入时判断之前有,val插成0,如果已有的时间更靠后,则需change一下,将靠后的val设为0.Q时讯问每一个点,直接输出在dfs时得到的每一个点的答案.至于桶的limit,对于平衡树查找是轻而易举的.需要注意limit查找是根据size,是球的个数,而ans是由cnt,球的种类数产生贡献的.好了,此题解决.

code

#include<bits/stdc++.h>
#define f() cout<<"fuck"<<endl
#define N 500001
using namespace std;
int head[N],n,m,k[N],now1,q,id[N],cnt,tot,ans[N],num,ans1;
struct x813x
{int to,next;
}bian[N];
struct y1111y
{int ch[2],cnt,siz,col,fa,tim,val;}t[N*40];
struct	I000I
{	int root;map<int ,int >mp;
	inline int size()
	{return t[root].siz;}
	inline bool get(int x)
	{return t[t[x].fa].ch[1]==x;}
	inline void update(int x)
	{	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
		t[x].cnt=t[t[x].ch[0]].cnt+t[t[x].ch[1]].cnt+t[x].val;
	}
	inline void rotate(int x)
	{	int die=t[x].fa,ye=t[die].fa,hao=get(x);
		t[die].ch[hao]=t[x].ch[hao^1];
		t[t[die].ch[hao]].fa=die;
		t[x].ch[hao^1]=die;
		t[die].fa=x;t[x].fa=ye;
		if(ye)t[ye].ch[t[ye].ch[1]==die]=x;
		update(die);update(x);
	}
	inline void splay(int x)
	{	for(int i;i=t[x].fa;rotate(x))
		if(t[i].fa)rotate((get(i)==get(x))?i:x);
		update(x);
		root=x;
	}
	inline void insert(int tim,int col,int val)
	{	int f=0,x=root;
		while(x and t[x].tim!=tim)
		{	f=x;
			x=t[x].ch[t[x].tim<tim];
		}
		x=++num;
		if(f)t[f].ch[t[f].tim<tim]=x;
		t[x].tim=tim;t[x].col=col;t[x].fa=f;
		t[x].cnt=t[x].val=val;t[x].siz=1;
		splay(x);
	}
	inline void change(int tim)
	{	int now=root;
		while(now and t[now].tim!=tim)now=t[now].ch[t[now].tim<tim];
		if(now)t[now].val=0;
		splay(now);
	}
	inline bool find1(int tim,int col)
	{	if(!mp[col])
		{	mp[col]=tim;
			return 1;
		}
		else
		if(mp[col]>tim)
		{	change(mp[col]);
			mp[col]=tim;
			return 1;
		}
		else
		return 0;
	}
	inline int findx(int x,int limit)
	{	if(!x)return 0;
		if(t[t[x].ch[0]].siz>=limit)findx(t[x].ch[0],limit);
		else if(t[t[x].ch[0]].siz+1>=limit)return ans1+t[t[x].ch[0]].cnt+t[x].val;
		else ans1+=t[t[x].ch[0]].cnt+t[x].val,findx(t[x].ch[1],limit-t[t[x].ch[0]].siz-1);
	}
	inline int findval(int limit)
	{	ans1=0;
		if(!limit)return 0;
		if(t[root].siz<=limit)return t[root].cnt;
		int x=findx(root,limit);
		return x;
	}
}a[N];
namespace AYX
{	inline void update(int x)
	{	if(!x)return;
		update(t[x].ch[0]);
		a[now1].insert(t[x].tim,t[x].col,a[now1].find1(t[x].tim,t[x].col));
		update(t[x].ch[1]);
	}
	inline void dfs(int x,int fa)	
	{	for(int i=head[x];i;i=bian[i].next)
		{	int y=bian[i].to;
			if(y==fa)continue;
			//f();
			dfs(y,x);
			if(a[id[x]].size()<a[id[y]].size())
			{	now1=id[y];
				update(a[id[x]].root);
				id[x]=now1;
			}
			else
			{	now1=id[x];
				update(a[id[y]].root);
			}
		}
		ans[x]=a[id[x]].findval(k[x]);
	}
	inline void add(int u,int v)	
	{	bian[++cnt].to=v;
		bian[cnt].next=head[u];
		head[u]=cnt;
	}
	inline short main()
	{	scanf("%d",&n);
		for(int i=1;i<n;++i)
		{	int a,b;
			scanf("%d%d",&a,&b);
			add(a,b);add(b,a);
		}
		for(int i=1;i<=n;++i)id[i]=i,scanf("%d",&k[i]);
		scanf("%d",&m);
		for(int i=1;i<=m;++i)
		{	int x,c;
			scanf("%d%d",&x,&c);	
			a[id[x]].insert(i,c,a[id[x]].find1(i,c));
		}	
		dfs(1,0);
		scanf("%d",&q);
		for(int i=1;i<=q;++i)
		{	int v,x;	
			scanf("%d",&x);
			printf("%d\n",ans[x]);
		}
	}
}
signed main()
{return AYX::main();}

T3大佬

这完蛋玩意,又是假期望.其实这题也不是很难,就是题面看错了.......

好吧,在来看一下,取值范围是1-m,而对应的劳累值是题目中给出的m[i]......而不是直接随机取m[i].好吧,话说题面搞错了还有十分?

正解就是算贡献,貌似是在计数,嗯,确实在计数.试想对于一个值i,他成为u最大值的方案数是多少呢?要想他是最大值,那我k天之内的取值都得在i之内,所以是ik.但是这里面有最大值不是i的情况,所以再减去(i-1)k.方案数乘上值,最后乘上总天数除以总方案数m^k即可.

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,m,k,w[1011],ans;
inline int qpow(int a,int b)
{	int base=1;	
	while(b)
	{	if(b&1)base=base*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return base;
}
signed main()
{	scanf("%lld%lld%lld",&n,&m,&k);if(k>n){cout<<0;return 0;}
	for(int i=1;i<=m;++i)
	{	int s;scanf("%lld",&s);
		(ans+=(qpow(i,k)-qpow(i-1,k)+mod)%mod*s%mod)%=mod;
	}
	printf("%lld",ans*(n-k+1)%mod*qpow(qpow(m,k),mod-2)%mod);
}

T4宝藏

状压好题,但是不知道为什么我考场上看着总想克鲁斯卡尔重构树,最后当然是完蛋的.

本题瓶颈在于那个边权上要乘的系数,也就是深度.还有他去跟谁连边,这些东西都是变量,搞得人头疼.其实可以换个思路,神魔东西不好搞,就把它扔到状态里嘛,层数不好弄,我们就让他进数组第一层,第二层是状态,表示已经连了那些边.方程已经很明显了,只需预处理出i状态变为j状态的最小值是多少.我们对于dp是不用担心后效性的,因为再二进制枚举中每一个1都覆盖过不同的情况,同样都是取min.

代码实现中要枚举子集,这里有一个巧妙的方法实现,code

#include<bits/stdc++.h>
using namespace std;
int zxb[1<<14][1<<14],dis[103][103],n,m;long long dian[111];
long long ans=0x7fffffff;
long long dp[15][1<<14];
signed main()
{	scanf("%d%d",&n,&m);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;++i)
	{	int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(dis[a][b]>c)dis[a][b]=dis[b][a]=c;
	}
	for(int i=1;i<=n;++i)dian[i]=(1<<(i-1));
	for(int i=0;i<(1<<n);++i)
	for(int j=i;j;j=(j-1)&i)
	{	int temp=i^j;bool bo=0;
		for(int k=n;k;--k)
		{	int tin=0x3f3f3f3f;
			if(temp>=dian[k])
			{	tin=0x3f3f3f3f;
				for(int p=1;p<=n;++p)
				if((dian[p]&j)==dian[p])
				tin=min(tin,dis[p][k]);
				if(tin==0x3f3f3f3f){bo=1;break;}
				zxb[j][i]+=tin;
				temp-=dian[k];
			}
		}
		if(bo)zxb[j][i]=0x3f3f3f3f;
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;++i)dp[1][dian[i]]=0;
	for(int ceng=2;ceng<=n;++ceng)
	for(int i=0;i<(1<<n);++i)
	for(int j=i;j;j=(j-1)&i)if(zxb[j][i]!=0x3f3f3f3f)
	dp[ceng][i]=(long long)min(dp[ceng-1][j]+(long long )(ceng-1)*zxb[j][i],dp[ceng][i]);
	for(int i=1;i<=n;++i)ans=min(ans,dp[i][(1<<n)-1]);
	printf("%lld\n",ans);
}
这篇关于NOIP 模拟六 考试总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!