比赛期间一直在颓废有其他的事情，这两天补一补
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}$$
后面是个等差数列*等比数列的形式，我们可以用错位相消的方法得出前缀和。
所以这题就是这么做。
这题我刚开始想的是记录$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$，而倍增的写法却很容易的解决了这一问题。
而序列上的东西用倍增写也是非常简单的
评论 (0)
