MZOI20200801
starseven
2020-08-01 16:50:00
[试题题目](https://www.maipdf.com/pdf/?email=jegki8Kj/FQIYz)
------------------------------
T1
这个就是一个裸的后缀数组和**最基本的height数组**运用。所以这道题就只是以后的模板复习题。
没什么值得说的，全都是套路。
$Code:$
```cpp
#include<cstdio>
#include<algorithm>
#define ri register int
#define Starseven main
const int N=2e4+20;
int read(){
char ch=getchar();int re=0,op=1;
while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
return re*op;
}
void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}//记得自己加空格和换行
int max(int x,int y){return x<y?y:x;}
int min(int x,int y){return x<y?x:y;}
int abs(int x){return x<0?-x:x;}
int n,tim,m;
struct node{
int id,val,hsh;
}txt[N];
bool cmp(const node &a,const node &b){
return a.val<b.val;
}
bool vast(const node &a,const node &b){
return a.id<b.id;
}
int tong[N],x[N],y[N],sa[N],rk[N],height[N];
struct xyx{
void Tsort(){
for(ri i=1;i<=m;i++) tong[i]=0;
for(ri i=1;i<=n;i++) tong[x[i]]++;
for(ri i=1;i<=m;i++) tong[i]+=tong[i-1];
}
void Get_SA(){
for(ri i=1;i<=n;i++) x[i]=txt[i].hsh;
Tsort();
for(ri i=n;i>=1;i--) sa[tong[x[i]]--]=i;
for(ri k=1;k<=n;k<<=1){
int num=0;
for(ri i=n-k+1;i<=n;i++) y[++num]=i;
for(ri i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
Tsort();
for(ri i=n;i>=1;i--) sa[tong[x[y[i]]]--]=y[i],y[i]=0;
std::swap(x,y);
num=1;x[sa[1]]=1;
for(ri i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
if(num==n) break;
m=num;
}
}
void Get_height(){
for(ri i=1;i<=n;i++) rk[sa[i]]=i;
int k=0;
for(ri i=1;i<=n;i++){
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&txt[j+k].hsh==txt[i+k].hsh) k++;
height[rk[i]]=k;
}
}
}wly;
int que[N];
void Init(){
freopen("1.in","r",stdin);
}
int Starseven(void){
// Init();
n=read(),tim=read();
for(ri i=1;i<=n;i++) txt[i].id=i,txt[i].val=read();
std::sort(txt+1,txt+1+n,cmp);
txt[1].hsh=1;
for(ri i=2;i<=n;i++)
txt[i].hsh=(txt[i].val==txt[i-1].val?txt[i-1].hsh:txt[i-1].hsh+1);
m=txt[n].hsh;
std::sort(txt+1,txt+1+n,vast);
wly.Get_SA();wly.Get_height();
int tail=-1,head=0,ans=0;
for(ri i=1;i<=n;i++){
if(i-tim+1>=0)
if(que[head]==i-tim+1) head++;
while(tail>=head&&height[que[tail]]>=height[i]) tail--;
que[++tail]=i;
if(i-tim+1>=0) ans=max(ans,height[que[head]]);
}
write(ans);puts("");
return 0;
}
```
------------------------------------------------
T2
这是一个博弈论，而且是最基础（并不是最简单）的取石子游戏。但是有所变形，所以我猜测是$Fibonacci\;Nim$，只是有点变形，将$SG$函数弄出来找规律就直接出来了。
$Code:$
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<string>
#define maxn 100005
#define INF (1ll<<60)
using namespace std;
inline long long getint()
{
long long num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
long long k,N;
long long f[maxn],fib[maxn],cnt;
long long ans;
inline void solve(int x)
{
if(k>f[x])ans++;
for(int i=0;i<x;i++)if(k>f[i])ans+=fib[x-i];
}
int main()
{
f[0]=0,f[1]=1,cnt=1,fib[0]=0,fib[1]=1;
while(1)
{
cnt++;
f[cnt]=f[cnt-1]+f[cnt-2]+1;
fib[cnt]=fib[cnt-1]+fib[cnt-2];
if(f[cnt]>INF)break;
}
int T=getint();
while(T--)
{
k=getint(),N=getint();ans=0;
if(N==1){printf("0\n");continue;}
N-=2;
for(int i=cnt;i>=0;i--)if(N>=f[i])solve(i),N-=f[i]+1;
printf("%lld\n",ans);
}
}
```
---------------------------------
T3
这是一道倍增+树形换根dp的题，我没有做到，但是听懂了讲解，现在记录下来。
- 分析
我们对于一个$u->v$的路径，可以想到，我们在走这个路径的时候，在$u->v$的路径上的边只走一次，也就是单向，但是我们在走到一个节点时，可以选择**先绕道走一颗子树，然后在绕回来**的方案
#### 这提示我们要求出一个数组$f[i]$,以一个点为根的子树走一下能达到的最大收益（不一定要走完）。
然后我们还可以想象，当我们的两个节点走到其最近公共祖先$LCA(u,v)$时，我们可以向上走，走了可以走到的最大收益过后再回来，然后在走。
#### 这提示我们要求出一个数组$g[i]$，代表从这个点向上走，走到最大收益后回来所得到的收益
$\text{\color{red}{But,one\;thing\;important\;is\dots}}$
我们在以一条链向上走的时候，难道运用$f[i]$一个一个求，那不就是暴力的$O(n\times q)$的做法吗，所以我们还要继续想。
看到是树上的$LCA$一类的东西，自然而然地想到了**树链剖分**（~~假装自己是个树剖dalao~~）或者倍增来统计自己的答案。
统计什么答案呢？
#### 按照倍增的思想，我们每一次倍增都是得到的一条链的首尾，所以我们可以求出一个$F[i][j]$数组，表示从i点向上跳$2^j$个深度，这条链所能作出的最大贡献
按照前面的思想，而这个链当然不需要来回，但是进入子树需要。
#### 而我们之前的$f[i]$数组就起到辅助的作用了
而既然求出了向上的，我们当然要求出向下的。
$\text{设F2[i][j]为点}(i-2^j)\text{到点}(i)\text{所需能得到的最大收益}$
然后就可以写代码了。
--------------------------
细节很多，逐个逐个理解数组的含义
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 200005
#define R register
#define INF1 0x3f3f3f3f
using namespace std;
typedef long long lxl;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
struct edge
{
int v,w,next;
}e[maxn<<1];
int head[maxn],k;
inline void add(int u,int v,int w)
{
e[k]=(edge){v,w,head[u]};
head[u]=k++;
}
int n,q,a[maxn];
int f[maxn];
inline void dp(int u,int fa)
{
f[u]=a[u];
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dp(v,u);
if(f[v]-e[i].w-e[i^1].w>0) f[u]+=f[v]-e[i].w-e[i^1].w;
}
}
int p[maxn][30],F1[maxn][30],F2[maxn][30],g[maxn];
int dep[maxn];
inline void dfs(int u,int fa)
{
dep[u]=dep[p[u][0]=fa]+1;
for(int i=1;i<=25;++i)
{
p[u][i]=p[p[u][i-1]][i-1];
F1[u][i]=F1[u][i-1]+F1[p[u][i-1]][i-1]-f[p[u][i-1]];
F2[u][i]=F2[u][i-1]+F2[p[u][i-1]][i-1]-f[p[u][i-1]];
}
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
F1[v][0]=f[v]+f[u]-e[i^1].w;
if(f[v]-e[i].w-e[i^1].w>0) F1[v][0]-=f[v]-e[i].w-e[i^1].w;
F2[v][0]=f[v]+f[u]-e[i].w;
if(f[v]-e[i].w-e[i^1].w>0) F2[v][0]-=f[v]-e[i].w-e[i^1].w;
g[v]=max(g[v],g[u]+F1[v][0]-e[i].w-f[v]);
dfs(v,u);
}
}
inline int Query(int u,int v)
{
int ans=0,a=u,b=v;
if(dep[u]>dep[v])
{
for(int i=25;i>=0;--i)
if(dep[p[u][i]]>=dep[v])
{
ans+=F1[u][i]-f[u];
u=p[u][i];
}
if(u==v) return ans+f[a]+g[u];
}
else
{
for(int i=25;i>=0;--i)
if(dep[p[v][i]]>=dep[u])
{
ans+=F2[v][i]-f[v];
v=p[v][i];
}
if(u==v) return ans+f[b]+g[u];
}
for(int i=25;i>=0;--i)
if(p[u][i]!=p[v][i])
{
ans+=F1[u][i]-f[u];
ans+=F2[v][i]-f[v];
u=p[u][i];
v=p[v][i];
}
return ans+F1[u][0]-f[u]+F2[v][0]-f[v]-f[p[u][0]]+f[a]+f[b]+g[p[u][0]];
}
int main()
{
freopen("strawberry2.in","r",stdin);
freopen("c.out","w",stdout);
n=read(),q=read();
for(int i=1;i<=n;++i)
a[i]=read();
memset(head,-1,sizeof(int)*(n+5));
for(int i=1;i<n;++i)
{
int u=read(),v=read();
add(u,v,read());
add(v,u,read());
}
dp(1,0);
dfs(1,0);
while(q--)
{
int u=read(),v=read();
printf("%d\n",Query(u,v));
}
return 0;
}
```