很久没有打比赛了，内部模拟赛天天垫底，第一次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=0; while(x>0)x/=2,t++; return t-1; } 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=0; while(u!=0&&v!=0) { if(((x&u)==0)^((y&v)==0))break; ret=(ret<<1)|((x&u)?1:0); u>>=1,v>>=1; } return ret; } int op[maxn]; int main() { int n;LL u,v,w; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&op[i]); if(op[i]==1) { 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),-2*w); } else { scanf("%lld%lld",&u,&v); b[++blen]=opera1(i,u,1); b[++blen]=opera1(i,v,1); b[++blen]=opera1(i,LCA(u,v),-2); } } for(int i=1;i<=alen;i++) for(int j=1;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=1;i<=n;i++) if(op[i]==2)printf("%lld ",as[i]); return 0; }
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]=1; 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]+1+(double)(tot[x]-1-tot[a[k].y])/2.0; dfs2(a[k].y); } } int main() { int n,F; scanf("%d",&n); for(int i=2;i<=n;i++) scanf("%d",&F),ins(F,i); dfs(1); f[1]=1;dfs2(1); for(int i=1;i<n;i++)printf("%.6lf ",f[i]); printf("%.6lf ",f[n]); return 0; }
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+7; LL quick_pow(LL A,LL p) { LL ret=1; while(p!=0) { if(p%2==1)ret=ret*A%mod; A=A*A%mod;p/=2; } return ret; } int main() { int n; LL p,a=2,b=mod-1; 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(3,mod-2)%mod; a=a*quick_pow(2,mod-2)%mod; printf("%lld/%lld ",(mod+a-z)%mod,a); return 0; }
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=200+10; const int maxS=200+10; const int maxc=26+4; const LL inf=(1LL<<62); int li; struct Matrix { LL mp[maxS][maxS]; void clear(){memset(mp,0,sizeof(mp));} void Mmin(){for(int i=0;i<li;i++)for(int j=0;j<li;j++)mp[i][j]=-inf;} friend Matrix operator *(Matrix a,Matrix b) { Matrix c;c.Mmin(); for(int i=0;i<li;i++) for(int j=0;j<li;j++) for(int k=0;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!=0) { if(p%2==1)c=c*a; a=a*a;p/=2; } return c; } struct Trie { int w[maxc],fail; LL s; }tr[maxS];int trlen; char ss[maxS]; void insert(int d) { int now=0,len=strlen(ss+1); for(int i=1;i<=len;i++) { int x=ss[i]-'a'+1; if(tr[now].w[x]==0)tr[now].w[x]=++trlen; now=tr[now].w[x]; } tr[now].s+=d; } int head,tail,list[maxS]; void bfs() { head=1,tail=2;list[head]=0; while(head!=tail) { int now=list[head]; for(int x=1;x<=26;x++) { int son=tr[now].w[x]; if(son==0)continue; if(now==0)tr[son].fail=0; else { int pre=tr[now].fail; while(pre!=0&&tr[pre].w[x]==0)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=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%s",ss+1),insert(a[i]); li=trlen+1; bfs(); A.Mmin(); for(int now=0;now<=trlen;now++) for(int x=1;x<=26;x++) { int pre=now; while(pre!=0&&tr[pre].w[x]==0)pre=tr[pre].fail; int son=tr[pre].w[x]; if(son!=0)A.mp[now][son]=tr[son].s; } ans.Mmin();ans.mp[0][0]=0; ans=quick_pow(ans,A,L); LL mmax=0; for(int i=0;i<=trlen;i++)mmax=max(mmax,ans.mp[0][i]); printf("%lld ",mmax); return 0; }
E、F留坑待填