6
8
2015
0

51nod算法马拉松2题解

比赛期间一直在颓废有其他的事情,这两天补一补

A.天堂里的游戏  

  这题我不会,但是AC还是没有问题的

  其实我看了半大天没看懂题目在搞毛线,然后发现给了个补充说明。那就按说明的列个方程就过了。。。

B.集合计数  

  就是个$exgcd$啦,细节处理一下。

C.混合序列

  数列题。。。

  ①如果$p!=1$的话,我们先推出$a_n$的通项公式。

    利用配凑法:令$$a_n+x=p*(a_{n-1}+x)$$

    对比原来的递推式可知  $$x=\frac{r}{p-1}$$

    那么 $$a_n=p^n*x-x=(p^n-1)*x$$

    而$$b_n=3*q^n$$

    所以$$ans=\sum_{i=0}^{n}{a_i*b_{n-i}}=\sum_{i=0}^{n}{(p^i-1)*x*3*q^{n-i}}$$

           $$=3*x*\sum_{i=0}^{n}(p^i*q^{n-i}-q^{n-i})$$

    显然$q^{n-i}$可以等比数列直接求出来,而$p^i*q^{n-i}$也可以,把$q^n$提出来即可我本来想用矩阵乘法     

  ②如果$p=1$的话,那么

    $$ans=\sum_{i=0}^{n}a_i*b_{n-i}=\sum_{i=0}^{n}i*r*3*q^{n-i}=3*r*q^n*\sum_{i=0}^{n}{i*(\frac{1}{q})^i}$$

    后面是个等差数列*等比数列的形式,我们可以用错位相消的方法得出前缀和。

  所以这题就是这么做。

D.哈利与他的机械键盘

  这题我刚开始想的是记录$f[i][j]$表示现在在$i$位置,然后$i$以及它前后$18$个字母的打了的情况为$j$,用二进制数来表示。

  然后用$spfa$来转移。

  空间上的问题我们可以先预处理把不合法的$j$去掉,然后建立一个映射关系。

  时间上我并不知道复杂度

  然后转移的时候枚举没有填的,判一下是否合法,然后转化一下二进制数balabala

  然而写起来感觉太麻烦了,于是我就弃疗了看题解。

  题解是这样的:

  $f[i][j][k]$表示前$i-10$个字母都填满了,现在在$i-9$到$i$这$10$个字母的$j$位置,然后$i-9$到$i$这$10$个字母是否填了的状态为$k$。

  转移的时候有两种,一种就是继续填$i-9$到$i$的字母,一种就是足以填后面的字母,那就填好了。

  贴一下最后的代码吧,细节好多。

struct rec{int x,y;}a[105];
int n,f[105][12][1<<11],b[105];
char s[105];
inline int dist(rec a,rec b){return abs(a.x-b.x)+abs(a.y-b.y);}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    for0(i,25)a[i].x=read(),a[i].y=read();
    scanf("%s",s);n=strlen(s);
    for1(i,n)b[i]=s[i-1]-'a';
    memset(f,60,sizeof(f));
    for1(i,min(10,n))f[10][i-1][1<<(i-1)]=0;
    for2(i,10,max(n,10))
     for0(j,(1<<10)-1)
      for0(k,9)if(j&(1<<k))
      {
      	//cout<<i<<' '<<j<<' '<<k<<' '<<f[i][k][j]<<endl;
      	if(f[i][k][j]>=inf)continue;
       for0(l,9)if(!(j&(1<<l)))
       {
       	 int tmp=0;
       	 if(l<k){for3(t,k,l+1)if(j&(1<<t))tmp++;}
       	 else {for2(t,k+1,l-1)if(j&(1<<t))tmp++;}
       	 //cout<<k<<' '<<l<<' '<<tmp<<' '<<dist(a[b[i-9+k]],a[b[i-9+l]])<<endl;
       	 f[i][l][j^(1<<l)]=min(f[i][l][j^(1<<l)],f[i][k][j]+tmp+dist(a[b[i-9+k]],a[b[i-9+l]]));
	   }
	   int tmp=j;
	   for0(l,9)
	   {
	   	 if(!(j&(1<<l)))break;
	   	 if(i+l+1>n)break;
	   	 tmp>>=1;
	   	 int cnt=0;
	   	 for2(t,k+1,9)if(j&(1<<t))cnt++;
	   	 f[i+l+1][9][tmp+(1<<9)]=min(f[i+l+1][9][tmp+(1<<9)],f[i][k][j]+cnt+dist(a[b[i+l+1]],a[b[i-9+k]]));
       }
     }
	int ans=inf;
	for0(i,9)ans=min(ans,f[max(10,n)][i][(1<<min(10,n))-1]);
	cout<<ans<<endl;  
    return 0;
}

E.跳跳树

  真是一道不错的题目。

  先考虑这个问题的一个简化版,如果只能用体力走,也就是说没有树的高低这么一说。

  每次最多走$k$,至少需要走多少次呢?

  一个显然的结论就是尽量能走多远走多远。

  然后看数据范围显然单次询问只能$O(logn)$,而想一想发现并没有什么数据结构能够派的上用场。

  而树上$O(logn)$的算法还有倍增。

  倍增什么呢?$f[i][j]$表示从$i$到$i$的$2^j$层祖先最少需要的体力?

  不能快速合并,因为上一次可能还剩了点儿可行距离。

  $f[i][j]$表示从$i$花费$2^j$体力最远走到的祖先?

  这个十分靠谱,合并非常简单。$f[i][j]=f[f[i][j-1]][j-1]$即可。

  然而现在我们不仅要上去,然后还要下去。

  这时候怎么办呢?

  带胶布,我们再设一个数组$g[i][j]$表示花费$2^j$体力就能到达i的最远的祖先。

  然后不断的往上跳并且保证时刻在$LCA$下方即可。

  还有一个问题就是$LCA$的特殊性,我们需要在到达$LCA$之前用一点体力,然后到了$LCA$,再看看剩下的距离能够往下走到哪

  这个是可以二分的,然而也可以很方便的利用倍增数组来搞。

  然后加强一下就是此题,存在不需要消耗体力就可以移动的情况,我们只要时刻利用这个就行。

  有一个细节就是可能往上跳了最后一步还没到$LCA$,但是却可以通过从高到低的操作到达。被这个坑了好久

  代码写起来也不是很好写。不过思路清晰的话应该还是没问题的。

  

int n,k,dep[maxn],h[maxn],f[maxn],g[maxn],fa[maxn][19],up[maxn][19],dw[maxn][19],head[maxn],tot;
struct edge{int go,next,w;}e[2*maxn];
ll len[maxn];
queue<int>q;
inline void add(int x,int y,int w)
{
	e[++tot]=(edge){y,head[x],w};head[x]=tot;
	e[++tot]=(edge){x,head[y],w};head[y]=tot;
}
inline void bfs()
{
	q.push(1);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for1(i,18)
	    {
	     up[x][i]=up[up[x][i-1]][i-1];
	     dw[x][i]=dw[dw[x][i-1]][i-1];
        }
        for4(i,x)if(y!=fa[x][0])
        {
          fa[y][0]=x;
    	  for1(j,18)fa[y][j]=fa[fa[y][j-1]][j-1];
    	  len[y]=len[x]+e[i].w;
    	  dep[y]=dep[x]+1;
    	  if(h[y]>h[x])
          {
    		f[y]=f[x];
    		up[y][0]=up[x][0];
    		g[y]=y;
    		int t=y;
    		for3(j,18,0)if(len[y]-len[fa[t][j]]<=k)t=fa[t][j];
    		dw[y][0]=g[t];
    	  }else if(h[y]<h[x])
    	  {
    		g[y]=g[x];
    		dw[y][0]=dw[x][0];
    		f[y]=y;
    		int t=y;
    		for3(j,18,0)if(len[y]-len[fa[t][j]]<=k)t=fa[t][j];
    		up[y][0]=f[t];
    	  }else
    	  {
    		f[y]=g[y]=y;
    		int t=y;
    		for3(j,18,0)if(len[y]-len[fa[t][j]]<=k)t=fa[t][j];
    		up[y][0]=f[t];
			dw[y][0]=g[t];
    	  }
    	  q.push(y);
         }
    }
}
inline int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y); 
	int t=dep[x]-dep[y];
	for3(i,18,0)if(t&(1<<i))x=fa[x][i];
	if(x==y)return x;
	for3(i,18,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
inline int get(int x,int y,int z)
{
	for3(i,18,0)if(len[fa[y][i]]-len[x]>z)y=fa[y][i];
	return len[y]-len[x]>z?fa[y][0]:y;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    n=read();k=read();
    for1(i,n-1){int x=read(),y=read();add(x,y,read());}
    for1(i,n)h[i]=read();
    f[1]=g[1]=dep[1]=1;
    bfs();
    int T=read();
    while(T--)
    {
    	int x=read(),y=read(),z=lca(x,y),ans=0;
    	for3(i,18,0)if(dep[up[x][i]]>dep[z])x=up[x][i],ans+=1<<i;
    	if(dep[f[x]]>dep[z])
		{
		   ans++;
		   if(k>len[f[x]]-len[z])x=get(z,y,k-(len[f[x]]-len[z]));
		   else x=z;
	    }
        else x=z;
    	for3(i,18,0)if(dep[dw[y][i]]>dep[x])y=dw[y][i],ans+=1<<i;
    	if(dep[g[y]]>dep[x])ans++;
    	printf("%d\n",ans);
    }	
    return 0;
}

   在写这题的时候我发现二分其实也可以用倍增的写法。

   就是我们从$2^k$枚举到$2^0$,如果$r-2^i$合法,那么就$r-=2^i$。

   这样就可以找到第一个合法的位置。其余类型的二分类似。

   感觉是个很不错的东西。

   或者说树上的倍增本质都是二分?

   或者说倍增是二分的另一种写法?

   树上的话知道$x$和$y$并不容易快速知道到$x$和$y$距离相等的点是什么,也就是中点$mid$,而倍增的写法却很容易的解决了这一问题。

   而序列上的东西用倍增写也是非常简单的

Category: 51nod | Tags: | Read Count: 909

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com