ABC107-D-Median of Medians

传送门

Solution

题意是求一个序列中"所有子序列的中位数"所组成的序列的中位数

首先二分一个答案，这样，所有小于它的都可以看成是-1，大于等于它的是1

如果一个区间的和(geq 0),那么它的中位数就不小于二分的答案

求区间数的话，对前缀和求逆序对就行了

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(x,y) (x^=y^=x^=y)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
#define MN 100005 
int n,m,a[MN],b[MN],c[MN];
int t[MN<<1];
void C(int x){for(;x<MN*2;x+=(x&-x))t[x]++;}
int G(int x){int res=0;for(;x;x-=(x&-x))res+=t[x];return res;}
inline bool check(int x)
{
	ll cnt=0ll;
	register int i;
	for(i=1;i<=n;++i) c[i]=c[i-1]+(a[i]>=x?1:-1);
	memset(t,0,sizeof t);
	for(i=1;i<=n;++i)
	{
		C(c[i-1]+MN);
		cnt+=G(c[i]+MN);
	}
	return cnt*4>=1ll*n*(n+1);
}
int main()
{
	n=read();register int i;
	for(i=1;i<=n;++i) a[i]=b[i]=read();
	std::sort(b+1,b+n+1);
	m=std::unique(b+1,b+n+1)-b-1;
	int l,r,ans;
	for(l=1,r=m,ans=0;l<=r;)
	{
		int mid=l+r>>1;
		if(check(b[mid])) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d
",b[ans]);
}

ARC101-E-Ribbons on Tree

传送门

Solution

题意：给定一棵点数为偶数的树，要求有多少种将点两两配对的方案使得每一条边至少被一对匹配点之间的最短路径覆盖。

容斥

令(F(E))表示(E)中的边不被覆盖的方案数

[ans=sum_{E}^{}(-1)^{|E|}F(E) ]

令(g(n))表示大小为n的序列中有多少中配对方法，当n为偶数时
$$g(n)=frac{n!}{(frac{n}{2})!cdot 2^{frac{n}{2}}}=(n-1)cdot (n-3)cdot ......cdot 3cdot 1 $$

当E确定时，原树被分成若干个联通块，且我们的点对必须同处一个块内

令f[i][j]表示以i为根的子树内，有j个点是与i的父亲节点同处一个联通块的方案数
然后就是树形dp了，在枚举子树的时候，虽然有三层的(for)，但是可以发现是和子树大小相关个，我们可以当作每次是选了两个子树做匹配，节点之间两两只会配对一次，所以复杂度仍然是(O(n^2))的

根据容斥，在计算(f[i][0])时，我们得变号

答案是(-f[1][0])，因为我们最后多变了一次号

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(x,y) (x^=y^=x^=y)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
#define MN 5005
#define mod 1000000007
ll dp[MN][MN],g[MN],t[MN],siz[MN];
int hr[MN],en;
struct edge{int to,nex;}e[MN<<1];
inline void ins(int f,int t)
{
	e[++en]=(edge){t,hr[f]};hr[f]=en;
	e[++en]=(edge){f,hr[t]};hr[t]=en;
}
void dfs(int x,int fa){
    siz[x]=1;dp[x][1]=1;register int i,j,k;
    for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa)
	{
    	dfs(e[i].to,x);
    	for(j=0;j<=siz[x];++j)
    		t[j]=dp[x][j],dp[x][j]=0;
    	for(j=0;j<=siz[x];++j)
    		for(k=0;k<=siz[e[i].to];++k)
    			(dp[x][j+k]+=t[j]*dp[e[i].to][k]%mod)%=mod; 
    	siz[x]+=siz[e[i].to];
	}
	for(i=0;i<=siz[x];i+=2)
		dp[x][0]=(dp[x][0]-dp[x][i]*g[i]%mod+mod)%mod;

}
int main(){
    register int i,n,x;
    n=read();
    for(i=1;i<n;++i) x=read(),ins(x,read());
    g[0]=1;for(i=2;i<=n;g[i]=g[i-2]*(i-1)%mod,i+=2);
    dfs(1,0);
    printf("%lld
",mod-dp[1][0]);
    return 0;
}

ARC101-F-Robots and Exits

传送门

Solution

题意是有n个机器人和m个出口，每次可以将所有机器人的坐标左移一格或者右移一格，当一个机器人正好在出口上时，它就会消失，问所有机器人消失的出口序列有多少种情况。

首先，机器人只会从左边或右边的第一个出口消失（除去那些最左边最右边和已经在出口上的）

一个点离左边出口距离为a，右边为i，我们可以把它看成是一个点(a,b)。

那么每次操作，就是把所有的点变成 (a-1,b)或者(a,b-1)。

你可能会问，不应该是(a-1,b+1)或者(a+1,b-1)吗？

其实上，当我们执行了一次操作后，那些正好碰到坐标轴的点就已经消失，我们不要管它

而对于剩下的点，显然它的坐标在这个范围内变化都是不会掉下去的，所以我们不妨以它的最靠近坐标轴的坐标作为它的坐标

或者说，这个坐标仅仅只是表示一个最大变化量而已

换一种理解方式，我们假设是原点从((0,0))处开始向右或向左走，最后将图分成两个部分

上半部分的点掉进了左边的出口（可以想象是y轴先碰到了它，也就是横坐标先变成了0），下半部分的点掉进了右边的出口

我们要询问有多少种这样的划线方式（两条折线不同当且仅当它们分出的两个部分是不同的）

设f[i]表示最后一个经过的点是i的方案数，最后一个的意思是，经过i之后，折线不再往上走

也就是i是位于折线下方的最高的点

[f[i]=1+sum_{x_j<x_i,y_j<y_i}f[j] ]

我们用树状数组就可以轻易维护

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(x,y) (x^=y^=x^=y)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
#define MN 100005
#define mod 1000000007
int ans,x[MN],y[MN];
int cnt,a[MN],b[MN],B[MN],id[MN];
inline bool cmp(const int&o,const int&oo){return a[o]==a[oo]?b[o]<b[oo]:a[o]<a[oo];}
int t[MN],s[MN];
void C(int x,int v){for(;x<MN;x+=(x&-x))(t[x]+=v)%=mod;}
int G(int x){int r=0;for(;x;x-=(x&-x))(r+=t[x])%=mod;return r;}
int main()
{
	register int i,j,n,m;
	n=read(),m=read();
	for(i=1;i<=n;++i) x[i]=read();
	for(j=1;j<=m;++j) y[j]=read();
	std::sort(x+1,x+n+1);std::sort(y+1,y+m+1);
	for(i=1;i<=n;++i)
	{
		int p=std::lower_bound(y,y+m+1,x[i])-y;
		if(p<=1||p>m||x[i]==y[p]) continue;
		a[++cnt]=x[i]-y[p-1];B[cnt]=b[cnt]=y[p]-x[i];id[cnt]=cnt;
	}
	std::sort(B+1,B+cnt+1);
	int Bcnt=std::unique(B+1,B+cnt+1)-B-1;
	for(i=1;i<=cnt;i++) b[i]=std::lower_bound(B+1,B+Bcnt+1,b[i])-B;
	std::sort(id+1,id+cnt+1,cmp);
	for(i=1,j=1;i<=cnt;++i)
	{
		if(a[id[i]]==a[id[i-1]]&&b[id[i]]==b[id[i-1]]) continue;
		for(;a[id[j]]<a[id[i]];++j) if(a[id[j]]!=a[id[j-1]]||b[id[j]]!=b[id[j-1]]) C(b[id[j]],s[j]%mod);
		s[i]=1+G(b[id[i]]-1);
		(ans+=(s[i]%mod))%=mod;
	}
	printf("%d
",ans+1);
	return 0;
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！