一行超人

蒟蒻来写题解骗访问AK爷们都不屑于写题解

 

A.巴厘岛的雕塑

 

题意：

n个数的数列a,要求分段，最小化每段的和的或。然后要求分成的段数 k∈[A,B].

a[i]<=10亿

一部分数据 满足n<=100 1<=A<=B<=n

另一部分数据满足 n<=1000 A=1 B<=n

题解：

显然位运算的极值问题都应该从高位向低位考虑。

优先让这一位为0，如果行的话这一位就是0，否则就设为1。

然后如何判断某一段是否合法呢？也就是满足我们之前的限制条件呢。

不放认为我们已经确定了ans的前k位，x为ans的前k位，然后y为这一段和的前k位。

那么如果x|y==x显然满足条件。否则说明这一段和在ans为0的位置出现了1，这是不合法的。

然后要求这一段在第k+1位为0也只要判断一下就可以了。

所以判断一段区间是否合法我们可以做到O(1).

所以问题在于判断在满足限制的情况下能否将序列分成[A,B]内段。

直接判断显然不可能，所以考虑DP。

f[i][j]表示前i个数分成j段是否可行。然后枚举i所在段的起点即可。

复杂度O(n^3*log(sum(a[i]))) 然后可以得到71分。过掉n<=100的数据。

然后用bitset优化可以过掉n=1000的数据

最后一部分数据我们发现是A=1的，也就是没有下界。所以我们要尽可能的分成较少的段数。

那么就可以DP了。g[i]表示前i个数最少可以分为多少段。然后枚举i所在段的起点即可。

复杂度O(n^2*log(sum(a[i]))) 可以得到100分。

int n,A,B;
bool f[maxn][maxn];
ll a[maxn];
inline bool check(ll x,ll y)
{
	return (x|y)==y;
}
inline void work1()
{
	ll ans=0;int cnt=log2(a[n]);
	for3(k,cnt,0)
	{
		f[0][0]=1;
		for1(i,n)for1(j,i)for0(l,i-1)if(f[l][j-1])
		{
			ll x=a[i]-a[l];
			if(check(x>>(k+1),ans)&&!((x>>k)&1))f[i][j]=1;
		}
		int t=0;
		for2(i,A,B)t|=f[n][i];  
		ans<<=1;
		if(!t)ans|=1;
		for1(i,n)for1(j,i)f[i][j]=0;
	}
	cout<<ans<<endl;
}
int g[maxn];
inline void work2()
{
	ll ans=0;int cnt=log2(a[n]);
	for1(i,n)g[i]=inf;
	for3(k,cnt,0)
	{
		g[0]=0;
		for1(i,n)for0(j,i-1)
		{
			ll x=a[i]-a[j];
			if(check(x>>(k+1),ans)&&!((x>>k)&1))g[i]=min(g[i],g[j]+1);
		}
		ans<<=1;
		if(g[n]>B)ans|=1;
		for1(i,n)g[i]=inf;
	}
	cout<<ans<<endl;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	n=read();A=read();B=read();
	for1(i,n)a[i]=a[i-1]+(ll)read();
	if(A!=1)work1();
	else work2();
	return 0;
}

B.雅加达的摩天楼

 

题意：

有n个点[0,n-1]和m只青蛙。每只青蛙有一个初始位置b[i]以及一个跳跃能力p[i]。若i青蛙在x，那么它跳一次可以跳到i+x或者i-x。

现在1号青蛙想给2号青蛙传话，可以让其他青蛙帮忙传话。问青蛙们的最少跳跃步数。

n<=3W m<=3W

题解：

我们发现一只青蛙只可能通知下一只青蛙而不会通知多只。所以就是一个1到2的最短路问题。

然后我们可以打个暴力spfa发现AC了

我们要看正解！！！

这么萎的数据范围显然和分块有关。实际上是因为想不到什么乱搞的方法了。

按谁分块呢？显然是步长的大小。

如果p[i]<=sqrt(n)。那么我们可以直接

设f[i][j]表示从1青蛙开始 到达 步长为i的青蛙到j的时候所需的最少步数。

否则我们发现一只青蛙可以更新的状态很少。

那很简单我们暴力更新啊！

设g[i][j]表示从1青蛙开始 到达 j号青蛙走了i步所需的最少步数。

（后面这个奇葩的东西是因为我们要用bfs，所以不能一次走了所有能走的，而是按权值递增来update。

所以就可以bfs了。每到达一个新的点就把所有青蛙拎出来加入队列。

总状态只有O（n√n）。更新也是O（1）的。所以总复杂度是O（n√n）的。

不懂的可以找我要代码 QQ973446154

int n,m,t1,t2,tot,head[maxn],b[maxn],p[maxn],f[maxm][maxn],g[maxm][maxn];
struct rec{int x,y,z;};
queue<rec>q;
struct edge{int go,next;}e[maxn];
bool v[maxm][maxn],vv[maxm][maxn],vis[maxn];
inline void add(int x,int y)
{
	e[++tot]=(edge){y,head[x]};head[x]=tot;
}
inline void update(int x,int z)
{
	for4(i,x)if(p[y]<=sqrt(n))
	{
	   v[p[y]][x]=1;
	   f[p[y]][x]=z;
	   q.push((rec){p[y],x,0});
    }
	else 
	{
	   vv[0][y]=1;
	   g[0][y]=z;
	   q.push((rec){0,y,1});
    }
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    n=read();m=read();
    for1(i,m)
	{
	  int x=read();p[i]=read();
	  if(i==1)t1=x;
	  if(i==2)t2=x;
	  add(x,i);
	  b[i]=x;
	}
	int ans=inf;
	int size=(int)sqrt(n);
	for0(i,size)for0(j,max(m,n-1))f[i][j]=g[i][j]=inf;
	vis[t1]=1;
	if(t2==t1)ans=min(ans,0);
	update(t1,0);
    while(!q.empty())
    {
       rec t=q.front();q.pop();
       if(!t.z)
       {
       	 int x=t.y+t.x;
       	 if(x==t2)ans=min(ans,f[t.x][t.y]+1);
       	 if(x<n&&x>=0)
       	 {
       	 	if(!v[t.x][x])
       	 	{
       	 		v[t.x][x]=1;
       	 		f[t.x][x]=f[t.x][t.y]+1;
       	 		q.push((rec){t.x,x,0});
       	 	}
       	 	if(!vis[x])
       	 	{
       	 	vis[x]=1;
       	 	update(x,f[t.x][t.y]+1);
       	    }
       	 }
         x=t.y-t.x;
       	 if(x==t2)ans=min(ans,f[t.x][t.y]+1);
       	 if(x<n&&x>=0)
       	 {
       	 	if(!v[t.x][x])
       	 	{
       	 		v[t.x][x]=1;
       	 		f[t.x][x]=f[t.x][t.y]+1;
       	 		q.push((rec){t.x,x,0});
       	 	}
       	 	if(!vis[x])
			{
       	 	vis[x]=1;
       	 	update(x,f[t.x][t.y]+1);
       	    }
       	 }
       }else
       {
       	 int x=b[t.y]+(t.x+1)*p[t.y];
       	 if(x==t2)ans=min(ans,g[t.x][t.y]+1);
       	 if(x<n&&x>=0)
       	 {
       	 	if(!vv[t.x+1][t.y])
       	 	{
       	 		vv[t.x+1][t.y]=1;
       	 		g[t.x+1][t.y]=g[t.x][t.y]+1;
       	 		q.push((rec){t.x+1,t.y,1});
       	 	}
       	 	if(!vis[x])
       	 	{
       	 	vis[x]=1;
       	 	update(x,g[t.x][t.y]+1);
       	    }
       	 }
       	 x=b[t.y]-(t.x+1)*p[t.y];
       	 if(x==t2)ans=min(ans,g[t.x][t.y]+1);
       	 if(x<n&&x>=0)
       	 {
       	 	if(!vv[t.x+1][t.y])
       	 	{
       	 		vv[t.x+1][t.y]=1;
       	 		g[t.x+1][t.y]=g[t.x][t.y]+1;
       	 		q.push((rec){t.x+1,t.y,1});
       	 	}
       	    if(!vis[x])
       	    {
       	 	vis[x]=1;
       	 	update(x,g[t.x][t.y]+1);
       	    }
       	 }
       }
   }
    cout<<(ans==inf?-1:ans)<<endl;
    return 0;
}

C.巴邻旁之桥

 

题意：

有一条河，上下分别有0-10亿这么多点。有n个人，每个人在上方有一个家a[i]，下方有一个办公室b[i]。

要求建立k座桥，使得所有人从家到办公室走的距离之和最小。

k=1/2 n<=10w

题解：

k=1的时候，ans=sigma（abs(a[i]-x)+abs(b[i]-x））显然可以分开，就成了一个中位数。直接用中位数即可。

k=2的时候。我们可以沿用上面的思路，继续使用中位数求解。

考虑一座桥的位置对一个人走的距离的影响。

图片来自卢爷

一定是这样的。所以哪座桥离a[i]和b[i]的中点近，这个人就选择走哪座桥。

所以我们按中点排序，然后一定是某个前缀走左边的桥，剩下的走右边的桥。

某个前缀的ans显然我们可以中位数求解。

动态维护中位数？treap/splay均可。我作死写了splay好像会T。建议大家写treap.

UPD:其实这题写动态开点权值线段树更简单。发现很多平衡树可以搞得东西都可以用（可持久化）（动态开点）（权值）线段树艹过。

int n,k,b[maxn];
ll ans;
struct rec{int x,y;}a[maxn];
inline int get()
{
	char ch=getchar();
	while(ch!='A'&&ch!='B')ch=getchar();
	return ch=='A'?1:2;
}
inline void work1()
{
	k=0;
	for1(i,n)b[++k]=a[i].x,b[++k]=a[i].y;
	sort(b+1,b+k+1);
	int t=b[(k+1)>>1];
	ll tmp=0;
	for1(i,k)tmp+=abs(b[i]-t);
	cout<<tmp+ans+n<<endl;
}
struct BST
{
	int rt,t1,t2,tot,fa[maxn],c[maxn][2],s[maxn],v[maxn];
	ll sum[maxn];
	inline void pushup(int x)
	{
		int l=c[x][0],r=c[x][1];
		s[x]=s[l]+s[r]+1;
		sum[x]=sum[l]+sum[r]+v[x];
	}
	inline void rotate(int x,int &k)
	{
		int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
		if(y!=k)c[z][c[z][1]==y]=x;else k=x;
		fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
		c[y][l]=c[x][r];c[x][r]=y;
		pushup(y);pushup(x);
	}
	inline void splay(int x,int &k)
	{
		while(x!=k)
		{
			int y=fa[x],z=fa[y];
			if(k!=y)
			{
				if(c[z][1]==y^c[y][1]==x)rotate(x,k);else rotate(y,k);
			}
			rotate(x,k);
		}
	}
	inline int find(int x,int k)
	{
		int l=c[x][0],r=c[x][1];
		if(s[l]+1==k)return x;
		else if(s[l]>=k)return find(l,k);
		else return find(r,k-s[l]-1);
	}
	inline int rank(int x,int k)
	{
		int l=c[x][0],r=c[x][1];
		if(v[x]==k)return s[l]+1;
		else if(k<v[x])return rank(l,k);
		else return s[l]+1+rank(r,k);
	}
	inline void split(int l,int r)
	{
		t1=find(rt,l);t2=find(rt,r);
		splay(t1,rt);splay(t2,c[t1][1]);
	}
	inline void ins(int &x,int f,int k)
	{
		if(!x)
		{
			x=++tot;fa[x]=f;v[x]=k;s[x]=1;sum[x]=v[x];
			return;
		}
		if(k<=v[x])ins(c[x][0],x,k);
		else ins(c[x][1],x,k);
		pushup(x);
	}
	inline void erase(int k)
	{
		int x=rank(rt,k);
		split(x-1,x+1);
		c[t2][0]=0;
		pushup(t2);pushup(t1);
	}		
	inline void add(rec a)
	{
		ins(rt,0,a.x);splay(tot,rt);
		ins(rt,0,a.y);splay(tot,rt);
	}
	inline void del(rec a)
	{
		erase(a.x);
		erase(a.y);
	}
	inline ll query()
	{
		int x=find(rt,(s[rt]+1)>>1);
		splay(x,rt);
		int l=c[x][0],r=c[x][1];
		return (ll)s[l]*v[x]-sum[l]+sum[r]-(ll)s[r]*v[x];
	}
}L,R;
inline bool cmp(rec a,rec b){return a.x+a.y<b.x+b.y;}
inline void work2()
{
	sort(a+1,a+n+1,cmp);
	a[0]=(rec){-1,inf+1};
	L.add(a[0]);
	for0(i,n)R.add(a[i]);
	ll tmp=(ll)1<<60;
	for1(i,n-1)
	{
		L.add(a[i]);
		R.del(a[i]);
		tmp=min(tmp,L.query()+R.query());
	}
	cout<<tmp-2*inf-4+ans+n<<endl;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    k=read();n=read();int m=0;
    for1(i,n)
    {
    	int x=get(),y=read(),z=get(),w=read();
    	if(x==z)ans+=abs(w-y);
    	else a[++m]=(rec){y,w};
    }
    n=m;
    if(!n){cout<<ans<<endl;return 0;}
    if(k==1)work1();
    else work2();
    return 0;
}