6
17
2015
0

一些杂题

NOI之前的杂题就放这儿了

现在做了几道:

                                                         18

【BZOJ4144】有一个结论,如果我们可以从$A$直接走到$B$,其中$A$和$B$都是加油站,那么这条路径一定是一开始离得最近的加油站是$A$,过一会儿变成$B$,一直到$B$为止。为什么呢?不妨设中间出现了一个点$X$离$C$最近,那么我们大可以从$A$到$X$,然后从$X$到$C$,从$C$返回$X$,再从$X$到$B$。这样一定不会差。所以$A,B$之间是否有边就看是否满足这样的条件。首先我们可以$dijkstra$求出每个点距离最近的加油站。那么每一条边就给我们提供了最近从$A$到$B$的分界点,我们按每条边可以构建出一条新的边。然后要求最大边最小,只要$MST$然后倍增就好了。

【BZOJ4152】我们如果将点按x轴排序,那么我们发现$dist(a_1,a_3)<=dist(a_1,a_2)+dist(a_2,a_3)$。所以我们只需要相邻的边就可以。

然后在按y轴排序建一遍边,跑最短路即可。

【IPSC2015F】题目大意是有$n$对夫妇,一对夫妇熟悉当且仅当丈夫之间是朋友且妻子之间也是朋友。现在有$q$个事件,每次都是$x$和$y$的丈夫成为朋友或妻子成为朋友。朋友之间具有传递性。求每个时刻熟悉的$cp$的对数。$n,q<=1000000$

考场上一直在想并查集无果。看了题解发现好神啊。我们不用并查集而用启发式合并,每次把小的合并到大的上。

这样♂和♀的所属集合都很好维护,一对$cp$同属一个集合当且仅当♂所在集合和♀所在集合都相同。我们可以在暴力合并♂或♀的所属集合的时候顺便合并$cp$所在的集合。代码的实现由很多技巧。

map<pa,int>mp;
int n,m,now;
struct rec
{
	int fa[maxn],size[maxn],head[maxn],tot;
	struct edge{int go,next;}e[maxn];
	inline void clear()
	{
		for1(i,n)fa[i]=size[i]=head[i]=0;tot=0;
	}
	inline void add(int x,int y)
	{
		e[++tot]=(edge){y,head[x]};head[x]=tot;
	}
	inline void merge(int xx,int yy)
	{
		if(xx==yy)return;
		if(size[xx]>size[yy])swap(xx,yy);
		size[yy]+=size[xx];
		int tmp=0;
		for4(i,xx){fa[y]=yy;if(e[i].next==0)tmp=i;}
		e[tmp].next=head[yy];
		head[yy]=head[xx];
	}
}a,b,c;
inline void merge(int aa,int bb,int cc,int dd)
{
	int x=mp[pa(aa,bb)],y=mp[pa(cc,dd)];
//	cout<<aa<<' '<<bb<<' '<<cc<<' '<<dd<<' '<<x<<' '<<y<<endl;
	if(c.fa[x]==c.fa[y])return;
	(now+=(ll)c.size[c.fa[x]]*c.size[c.fa[y]]%mod)%=mod;;
	if(!y)mp[pa(cc,dd)]=c.fa[x];
	else c.merge(c.fa[x],c.fa[y]);
}
int main()
{
    freopen("f2.in","r",stdin);
    freopen("output.txt","w",stdout);
    int T=read();
    while(T--)
    {
    	n=read();m=read();int ans=0;now=0;
    	mp.clear();
    	for1(i,n)
		{	
		  a.fa[i]=b.fa[i]=c.fa[i]=i;
		  a.size[i]=b.size[i]=c.size[i]=1;
		  a.add(i,i);b.add(i,i);c.add(i,i);
		  mp[pa(i,i)]=i;  
		 // cout<<i<<endl;
	    }
		for1(j,m)
		{
			int t=read(),xxx=read(),yyy=read();//cout<<t<<' '<<xxx<<' '<<yyy<<endl;
			if(t==1)
			{
				int xx=a.fa[xxx],yy=a.fa[yyy];
				if(xx!=yy)
				{
				if(a.size[xx]>a.size[yy])swap(xx,yy);
				for5(a,i,xx)merge(a.fa[y],b.fa[y],yy,b.fa[y]);
                a.merge(xx,yy);
                }
			}else
			{
				int xx=b.fa[xxx],yy=b.fa[yyy];
				if(xx!=yy)
				{
				if(b.size[xx]>b.size[yy])swap(xx,yy);
				for5(b,i,xx)merge(a.fa[y],b.fa[y],a.fa[y],yy);
                b.merge(xx,yy);
                }
			}
			(ans+=(ll)now*j%mod)%=mod;
			//cout<<j<<' '<<now<<endl;
		}
		cout<<ans<<endl;
		a.clear();b.clear();c.clear();
    }
    return 0;
}

【IPSC2015G】题目大意就是给你一颗$n$个节点的树,每个节点有一个颜色,每次可以输入$x,y,z$,把$x$子树中离$x$距离不超过$y$的点的颜色改为$z$,或者询问$x$的颜色。$n,q<=1000000$

比赛的时候想$bfs$序,写出来发现子树内的点并不一定是连续的所以说$bfs$序能维护什么呢?

看题解发现好神啊!!!

因为每次修改的$dep$是连续的,那我们以$dep$为值建立线段树,每个线段树里面放上属于该$dep$范围的点。那这个顺序按什么呢?

很容易想到按$dfs$序,因为一个$dep$确定了之后,点按$dfs$序排列的话,$x$子树内的点就是连续的了。我们可以再放棵线段树。

修改直接打标记即可。每次新标记覆盖旧标记。查询的话遍历$O(logn)$棵线段树,查找最近一次的标记即可。

【BZOJ4145】很容易想到$dp_{i,j}$表示考虑了前$i$个商店,然后买的物品集合是$j$的最小花费。如何转移呢?如果我们枚举子集来做的话,这样复杂度是$O(n3^m)$,无法承受。考虑对于一个物品选或不选进行背包,这样复杂度就是$O(nm2^m)$。可以通过。

【BZOJ2396】真是黑科技啊。判断两个矩阵相乘是否等于另一个矩阵。我们随机一个$1×n$的矩阵然后乘到两边,判是否相等。据说错的概率$<=\frac{1}{2}$

【BZOJ4151】这题有点儿厉害啊。首先暴力判肯定不行,然而要是每次把符合条件的$ans++$,这样也不好搞,因为满足条件的分布的并不十分有规律,可以说十分零散,不能整体修改。那我们就考虑构造型的解法,不放认为现在处在$1$,那么如果满足所有条件的话,输出就好了。否则不放认为我们不满足$(x,y,z)$的限制,也就是说$dist(1,x)+dist(1,y)>z$,那我们就必须沿着$LCA(x,y)$的方向走若干步,至少也得到达$LCA(x,y)$的$\frac{z-dist(x,y)}{2}$级祖先。那我们根据$m$个条件就可以得出许多这样的条件,如果有两个要求不在同一棵子树内,显然无解。否则我们就走到最深的这个祖先,然后判一下是否合法就行了。正确性显然。

【BZOJ4149】一道水题。。。我们发现固定右端点,左端点并不单调,所以不能用单调队列。我们考虑计算贡献,对于一个数$a[i]$来说,不妨认为它作为唯一的最小最远扩展到两边是$[l,r]$,也就是说任选左端点$∈[l,i]$,右端点$∈[i,r]$,那么这段区间的最小值都唯一且是$i$。所以我们可以考虑把所有这些区间都$++$。最大值类似这样去$++$。那么如果一个区间被加了两次,显然就是符合条件的一个区间。然而上述矩形加,我们可以用差分+线段树,而对答案的查询我们就是枚举起点算最远的$=2$的点,这样也直接用线段树查询就可以了。复杂度$O(nlogn)$。一开始抱着这么好写的题写不错的态度交了$T$了几发,后来改成标记永久化还是$T$。最后要来数据发现区间修改写成单点了。不过也因此$get了clock()$的使用方法。

【BZOJ1576】被USACO的题虐了题解君  我比较好奇 次短路一定只有一条非树边吗?不可能经过走多条吗?

【BZOJ2216】就是求$max(a[j]+\sqrt{i-j})$,显然$O(n\sqrt{n})$的算法随意,只要枚举后面那部分,前面最大用一个$st$表搞就好了。这其实是个$dp$。$dp$优化显然就是单调队列,决策单调性,四边形不等式什么的。这题我们可以考虑 如果某个时刻$i$的最优值在$j$选,那么$i$之后的点根本不会以$j$之前的点作为最优决策点。因为$f(x)=\sqrt{x}$这个函数的导数是递减的,所以更前面的值增加的还慢。所以就有决策单调性了。可以维护一个栈二分,也可以直接写分治。

【BZOJ4033】令$dp[i][j]$表示$i$的子树中选了$j$个黑点的代价,而这个代价应该是什么呢?应该是这$j$个黑点之间两两的距离以及这$j$个黑点对其他所有黑点的距离的贡献以及白点balabala,这样一定具有子问题最优性。所以才可以$dp$。然后转移的话就暴力好了。复杂度$O(n^2)$的。因为这个复杂度和枚举所有的点对的复杂度是一样的。可以意会一下。

【51nod算法马拉松3A】数据范围这么小,爆搜!T的不行,强行快超时的时候退出。

【51nod算法马拉松3B】强行最小到大加进去就完了

【51nod算法马拉松3C】会做4033这题就是傻逼了

【51nod算法马拉松3D】区间询问最容易想到的就是线段树,所以搞搞搞!记录一下左右端点选不选然后balabala

【51nod算法马拉松3F】比赛的时候非常傻逼,不知道从哪里下手。看了题解发现其实很简单,$<=\sqrt{n}$的质数至多只有$11$个,$>\sqrt{n}$的质数至多只有$157$个,而一个数里顶多有一个$>\sqrt{n}$的质数,所以就直接无脑状压$dp$,$dp_{i,j}$表示已经用了前$i$个$>\sqrt{n}$的质数,然后$<=\sqrt{n}$的质数的使用情况是$j$。然后枚举这次用的。这一步如果用子集的话会$T$。鉴于数据这么小,我们可以直接枚举合法的。这样就是$O(168*\sqrt{n}*2^{11})$

【BZOJ3288】求行列式肯定不能定义来搞,我们高斯消元然后把对角线上的数乘起来就是答案。这题的话打个表发现对角线上就是$fai(i)$,那么直接暴力算$fai$就好了。以后碰到这种题不打表就剁手!

【BZOJ3067】区间统计问题用前缀和比较好,$f[i][j]$表示前$i$个字符中$j$字符出现的次数$/%2$。然后$[l,r]$可以是回文的充要条件是$f[r]$和$f[l-1]$至多只有一位不同,那么就和spring这题的想法一样了。$hash$即可。我被卡常数卡到死最后实在受不鸟了交了别人的代码

Category: 杂题 | Tags: | Read Count: 1692

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com