已经114514天没有写了。
老师你为什么要加题啊……
[A]
是一个暴力分类讨论的题。
首先直接dfs一遍预处理求 LCA 所需的 dep/fa 数组。
然后分成三类讨论。
具体见代码
/*
(Standard IO)
时间限制: 2 s 空间限制: 512 MB
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+5;
int n,q,number;
int h[N],e[N<<1],ne[N<<1],idx;
int d[N],fa[N][27];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int father)
{
d[u]=d[father]+1;
fa[u][0]=father;
for(int j=1;j<=25;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father)continue;
dfs(j,u);
}
}
int LCA(int a,int b)
{
if(d[a]<d[b])swap(a,b);
for(int i=25;~i;i--)
{
if(d[fa[a][i]]>=d[b])a=fa[a][i];
}
if(a==b)return a;
for(int i=25;~i;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&q,&number);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
while(q--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int lca_AB=LCA(a,b),lca_BC=LCA(b,c),lca_AC=LCA(a,c);
if(lca_AB==lca_BC)
{
if(d[lca_AB]<=d[lca_AC])printf("%d\n",d[lca_AC]-d[lca_AB]+d[b]-d[lca_AB]+1);
}
else if(lca_AB==lca_AC)
{
if(d[lca_AB]<=d[lca_BC])printf("%d\n",d[b]-d[lca_BC]+1);
}
else if(lca_AC==lca_BC)
{
if(d[lca_BC]<=d[lca_AB])printf("%d\n",d[b]-d[lca_AB]+1);
}
}
return 0;
}
[B]
结论题，但是构造方案。
考虑如果已经选出 k 个时候的答案，如果要求返回原点，答案很显然是 2(k-1) 的。
但是不要求回原点，因此会留下一条链不会计入答案。
因此做法就显然了：
我们寻找树中最长的链，若链上已经有 k 个答案，直接输出。
否则从遍历这一条链，每一次将以这个节点的子树全部放入答案直到满足链上已经有 k 个答案。
/*
(Input: doc.in, Output: doc.out)
时间限制: 1 s 空间限制: 512 MB
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
typedef pair<int,int> PII;
int n,k,D,JD,d[N],par[N],st[N];
int h[N],e[N<<1],ne[N<<1],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int father)
{
d[u]=d[father]+1;
par[u]=father;
if(D<d[u])
{
D=d[u];
JD=u;
}
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father)continue;
dfs(j,u);
}
}
vector<int>ans;
int cnt=0;
void dfs2(int u)
{
ans.push_back(u);
cnt-=(!st[u]);
if(!cnt)return;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==par[u])continue;
if(!st[j])
{
dfs2(j);
ans.push_back(u);
if(!cnt)return;
}
}
}
void work()
{
ans.clear();
memset(h,-1,sizeof h);
memset(st,0,sizeof st);
D=JD=idx=0;
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
//now we have cnt=D,still need k-D
vector<int>res;
int t=JD;
while(t)
{
res.push_back(t);
st[t]=1;
t=par[t];
}
reverse(res.begin(),res.end());
if(k<=D)
{
printf("%d\n",k);
for(int i=0;i<k;i++)printf("%d ",res[i]);
puts("");
return;
}
cnt=k-D;
ans.clear();
for(int i=0;i<res.size();i++)
{
if(cnt)dfs2(res[i]);
else ans.push_back(res[i]);
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);
puts("");
}
int main()
{
freopen("doc.in","r",stdin);
freopen("doc.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)work();
return 0;
}
[T3]
感谢 CQR/SLT 的大力卡常。
首先矩阵快速幂优化，这是可以看出来的。
考虑 n=1 的答案，是 $F A^i_{0,0}，扩展到n>1， 答案是F \prod{i=1}^{n} \sum{j=0}^{x_i-1} A^j，其中A$
是矩阵快速幂中所使用的矩阵。
至于计算 \sum_{j=0}^{x_i-1} A^j ，考虑分治算法。
接下来是无优化代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
typedef long long LL;
const int N=15,M=45;
int n,m;
LL c[M];
struct Matrix
{
LL a[M][M];
Matrix(){memset(a,0,sizeof a);}
Matrix operator +(const Matrix &W)const
{
Matrix res;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)res.a[i][j]=(a[i][j]+W.a[i][j])%mod;
}
return res;
}
Matrix operator *(const Matrix &W)const
{
Matrix res;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=1;k<=m;k++)res.a[i][j]=(res.a[i][j]+(a[i][k]*W.a[k][j]%mod))%mod;
}
}
return res;
}
void print()
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)printf("%d ",a[i][j]);
puts("");
}
}
}Id,A,F;
Matrix quick_power(Matrix a,LL b)
{
Matrix res=Id;
while(b)
{
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
Matrix solve(LL r)
{
if(!r)return Id;
if(r==1)return A+Id;
LL mid=(r-1)/2;
Matrix res=solve(mid);
if(r&1)return res+quick_power(A,mid+1)*res;
else return res+quick_power(A,mid+1)*res+quick_power(A,r);
}
int main()
{
freopen("recursion.in","r",stdin);
freopen("recursion.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%lld",&c[i]);
for(int i=1;i<=m;i++)
{
scanf("%lld",&F.a[1][m-i+1]);
Id.a[i][i]=1;
A.a[i][1]=c[i];
if(i<m)A.a[i][i+1]=1;
}
Matrix res=Id;
for(int i=1;i<=n;i++)
{
LL x;
scanf("%lld",&x);
res=res*solve(x-1);
}
res=F*res;
printf("%lld\n",res.a[1][m]%mod);
return 0;
}
优化如下：
1.快读快写（常见太常见了）
2.if-else 改三目运算符
3.去除矩阵最开始的统一赋值为0
4.(!)改成每8次模一次，并将初始值赋成-mod*mod
5.一些火车头
6.由于矩阵快速幂是log(n) 级别的，而log 在前半部分降低的效率慢，在后部分降低效率快，因此考虑预处理部分幂，(注意空间16MB，因此400~500)较为合适。
然后……过了……
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define WW 460
#include<bits/stdc++.h>
using namespace std;
namespace INPUT_SPACE{
const int S=(1<<22)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; }
inline unsigned int inn() { unsigned int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x; }
}using INPUT_SPACE::inn;
#define mod 1000000009
typedef long long LL;
#define N 15
#define M 40
int n,m;
inline void print(LL x)
{
if(x<0)
{
putchar('-');
x=~x+1;
}
if(x>9)print(x/10);
putchar(x%10^48);
}
struct Matrix
{
LL a[M][M];
inline Matrix operator +(const Matrix &W)const
{
Matrix res;
for(register int i=0;i<m;++i)
{
for(register int j=0;j<m;++j)
{
res.a[i][j]=a[i][j]+W.a[i][j];
((res.a[i][j]>=mod)&&(res.a[i][j]-=mod));
}
}
return res;
}
inline Matrix operator *(const Matrix &W)const
{
Matrix res;
for(register int i=0;i<m;++i)
{
for(register int j=0;j<m;++j)
{
res.a[i][j]=0;
for(register int k=m-1;~k;--k)
{
res.a[i][j]+=(a[i][k]*W.a[k][j]);
if(!(k&7)) res.a[i][j]%=mod;
}
}
}
return res;
}
}Id,A,F,power[WW];
Matrix quick_power(Matrix a,LL b)
{
if(!b)return Id;
if(b<WW)return power[b];
Matrix res=quick_power(a,b>>1);
return ((b&1)?(res*res*a):(res*res));
}
Matrix solve(LL r)
{
if(!r)return Id;
if(r==1)return A+Id;
LL mid=(r-1)>>1;
Matrix res=solve(mid);
return ((r&1)?(res+quick_power(A,mid+1)*res):(res+quick_power(A,mid+1)*res+quick_power(A,r)));
}
int main()
{
freopen("recursion.in","r",stdin);
freopen("recursion.out","w",stdout);
n=inn(),m=inn();
memset(Id.a,0,sizeof Id.a);
for(int i=0;i<m;i++)
{
A.a[i][0]=inn();
Id.a[i][i]=1;
if(i+1<m)A.a[i][i+1]=1;
}
power[0]=Id;
for(int i=0;i<WW;i++)
{
if(i<m)F.a[0][m-i-1]=inn();
if(i)power[i]=power[i-1]*A;
}
Matrix res=Id;
for(int i=1;i<=n;i++)
res=res*solve(inn()-1);
res=F*res;
print(res.a[0][m-1]);
return 0;
}