很久没有打比赛了，内部模拟赛天天垫底，第一次vp之旅又是和**一样，这样下去GDOI之后直接退役算了
整场都在忘开LL
A. Lorenzo Von Matterhorn
这个题一看我就想直接虚树+树剖强行搞，但是这个是A题啊。。。写着中途看榜已经100+的人A了，冷静思考发现可以暴力计算每个修改对询问的印影响，用树上差分搞搞，两个点的LCA可以用位运算求，反正心态崩着乱推乱玩各种出锅浪费了1h最后给混过去了，不过还是一个很不错的题
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=3e3+_; struct opera1
{
int t; LL x,w;
opera1(){}opera1(int T,LL X,LL W){t=T,x=X,w=W;}
}a[maxn],b[maxn];int alen,blen;LL as[maxn];
int DEP(LL x)
{
int t=;
while(x>)x/=,t++;
return t-;
}
LL LCA(LL x,LL y)
{
LL u,v;
for(u=x;u!=(u&-u);u-=(u&-u));
for(v=y;v!=(v&-v);v-=(v&-v));
LL ret=;
while(u!=&&v!=)
{
if(((x&u)==)^((y&v)==))break;
ret=(ret<<)|((x&u)?:);
u>>=,v>>=;
}
return ret;
}
int op[maxn];
int main()
{
int n;LL u,v,w;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&op[i]);
if(op[i]==)
{
scanf("%lld%lld%lld",&u,&v,&w);
a[++alen]=opera1(i,u,w);
a[++alen]=opera1(i,v,w);
a[++alen]=opera1(i,LCA(u,v),-*w);
}
else
{
scanf("%lld%lld",&u,&v);
b[++blen]=opera1(i,u,);
b[++blen]=opera1(i,v,);
b[++blen]=opera1(i,LCA(u,v),-);
}
}
for(int i=;i<=alen;i++)
for(int j=;j<=blen;j++)
if(a[i].t<b[j].t)
{
LL lca=LCA(a[i].x,b[j].x);
as[b[j].t]+=DEP(lca)*a[i].w*b[j].w;
}
for(int i=;i<=n;i++)
if(op[i]==)printf("%lld\n",as[i]); return ;
}
A. Lorenzo Von Matterhorn
B. Puzzles
这题是个sb题，先把子树tot搞出来，考虑一个兄弟在我前面被遍历的概率是1/2，直接算就可以了，过的很快
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=1e5+_; struct node
{
int x,y,next;
}a[maxn];int len,last[maxn];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
int tot[maxn];double f[maxn];
void dfs(int x)
{
tot[x]=;
for(int k=last[x];k;k=a[k].next)
{
dfs(a[k].y);
tot[x]+=tot[a[k].y];
}
}
void dfs2(int x)
{
for(int k=last[x];k;k=a[k].next)
{
f[a[k].y]=f[x]++(double)(tot[x]--tot[a[k].y])/2.0;
dfs2(a[k].y);
}
} int main()
{
int n,F;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&F),ins(F,i);
dfs();
f[]=;dfs2();
for(int i=;i<n;i++)printf("%.6lf ",f[i]);
printf("%.6lf\n",f[n]); return ;
}
B Puzzles
C.PLEASE
vp的时候看到这个题画了下柿子发现随便转移，分母是2^n，概率矩乘一下很好算，但是分数的形式很乱搞，就先过了，果然是我不会的数论。后来打了一侧和中间的表发现是一个很熟悉的数列x=x+y,y=2*x，对于一侧有fi=fi-1+2*fi-2（见过很多次了，原来这个是Jacobsthal sequence，这个东西一定是个奇数所以就可以分开做了）Jacobsthal sequence的第n项=(2^n-(-1)^n)/3，算出一侧的，推出中间的就好了
注意有个坑，就是数列是乘起来而不是加起来的。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
LL quick_pow(LL A,LL p)
{
LL ret=;
while(p!=)
{
if(p%==)ret=ret*A%mod;
A=A*A%mod;p/=;
}
return ret;
}
int main()
{
int n; LL p,a=,b=mod-;
scanf("%d",&n);
while(n--)
{
scanf("%lld",&p);
a=quick_pow(a,p)%mod;
b=quick_pow(b,p)%mod;
}
int z=((a-b+mod)%mod)*quick_pow(,mod-)%mod;
a=a*quick_pow(,mod-)%mod;
printf("%lld/%lld\n",(mod+a-z)%mod,a); return ;
}
C. PLEASE
D. Legen...
这也是一个一眼题，AC机+DP+矩乘优化，但是这个矩乘的运算方式有点诡异（max(cij,aik+bkj)）导致在时间内没有调出来，感觉还是惯性思维了，把一个最值题想成计数题
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=+;
const int maxS=+;
const int maxc=+;
const LL inf=(1LL<<);
int li;
struct Matrix
{
LL mp[maxS][maxS];
void clear(){memset(mp,,sizeof(mp));}
void Mmin(){for(int i=;i<li;i++)for(int j=;j<li;j++)mp[i][j]=-inf;}
friend Matrix operator *(Matrix a,Matrix b)
{
Matrix c;c.Mmin();
for(int i=;i<li;i++)
for(int j=;j<li;j++)
for(int k=;k<li;k++)
if(a.mp[i][k]!=-inf&&b.mp[k][j]!=-inf)
c.mp[i][j]=max(c.mp[i][j],a.mp[i][k]+b.mp[k][j]);
return c;
}
}ans,A;
Matrix quick_pow(Matrix c,Matrix a,LL p)
{
while(p!=)
{
if(p%==)c=c*a;
a=a*a;p/=;
}
return c;
} struct Trie
{
int w[maxc],fail;
LL s;
}tr[maxS];int trlen; char ss[maxS];
void insert(int d)
{
int now=,len=strlen(ss+);
for(int i=;i<=len;i++)
{
int x=ss[i]-'a'+;
if(tr[now].w[x]==)tr[now].w[x]=++trlen;
now=tr[now].w[x];
}
tr[now].s+=d;
}
int head,tail,list[maxS];
void bfs()
{
head=,tail=;list[head]=;
while(head!=tail)
{
int now=list[head];
for(int x=;x<=;x++)
{
int son=tr[now].w[x];
if(son==)continue;
if(now==)tr[son].fail=;
else
{
int pre=tr[now].fail;
while(pre!=&&tr[pre].w[x]==)pre=tr[pre].fail;
tr[son].fail=tr[pre].w[x];
tr[son].s+=tr[tr[son].fail].s;
}
list[tail++]=son;
}
head++;
}
} int a[maxn];
int main()
{
int n;LL L;
scanf("%d%lld",&n,&L);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)
scanf("%s",ss+),insert(a[i]);
li=trlen+;
bfs(); A.Mmin();
for(int now=;now<=trlen;now++)
for(int x=;x<=;x++)
{
int pre=now;
while(pre!=&&tr[pre].w[x]==)pre=tr[pre].fail;
int son=tr[pre].w[x];
if(son!=)A.mp[now][son]=tr[son].s;
}
ans.Mmin();ans.mp[][]=;
ans=quick_pow(ans,A,L); LL mmax=;
for(int i=;i<=trlen;i++)mmax=max(mmax,ans.mp[][i]);
printf("%lld\n",mmax); return ;
}
D. Legen...
E、F留坑待填