第一次参加这种有奖励的比赛（没错，我就是为猴子而去的
一年没怎么碰代码果然手生，还是用没写多久的C++，差点全跪了
T1数学奇才琪露诺：
首先定义一个函数F(x)，F(x)=x的各个数位上的数字和
然后在区间[l,r]求F(x)k*p+q=x的所有x，按升序输出
T1题解：
枚举x肯定是不行的，F(x)的值只有0到81，我们枚举F(x)的值，然后算出F(x)k*p+q，看数位和是不是符合
可能会爆int，所以要开long long
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std; long long k,p,q,l,r,a[],tot; long long s(long long x){
long long ss=;
while(x>){
ss+=x%;
x=x/;
}
return ss;
} long long pow(long long x,long long y){
long long ipow=;
long long i;
for(i=;i<=y;++i)ipow=ipow*x;
return ipow;
} int main(){
scanf("%lld%lld%lld%lld%lld",&k,&p,&q,&l,&r);
long long i;
tot=;
for(i=;i<=;++i){
long long tmp;
tmp=pow(i,k)*p+q;
if((tmp>=)&&(s(tmp)==i)&&(tmp>=l)&&(tmp<=r))a[++tot]=tmp;
}
sort(a+,a++tot);
printf("%lld\n",tot);
for(i=;i<=tot;++i)printf("%lld ",a[i]);
return ;
}
T1
T2完美拓印：
给你一条轮廓线和一个印章，问有多少种方法可以让印章的一条边缘（上下两边）与轮廓线重合，印章可以180°旋转
T2题解：
我们注意到只要相邻两格的高度差一样就行，所以我们把相邻两项的差拿出来做kmp就行了
注意要做四次kmp，下面平的也要考虑，还有就是特判n=1的情况
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std; int n,m,a[],b[],nex[],ans; int work(){
int i,j;
for(i=n-;i>;--i)a[i]=a[i-]-a[i];
nex[]=;
nex[]=;
for(i=;i<n;++i){
j=nex[i-];
while((j>)&&(a[i]!=a[j+]))j=nex[j];
if(a[i]==a[j+])nex[i]=j+;
else nex[i]=;
}
i=;j=;
while(j<m-){
if(a[i+]==b[j+])++i,++j;
else
if(i==)++j;
else i=nex[i];
if(i==n-){
++ans;
i=nex[i];
}
}
for(i=;i<n;++i)a[i]=a[i-]-a[i];
return ;
} int swap(int &a,int &b){
int t;
t=a;a=b;b=t;
return ;
} int main(){
int i;
ans=;
scanf("%d%d",&n,&m);
for(i=;i<n;++i)scanf("%d",&a[i]);
for(i=;i<m;++i)scanf("%d",&b[i]);
if(n==){
printf("%d\n",*m);
return ;
}
for(i=m-;i>;--i)b[i]=b[i-]-b[i];
work();
for(i=;i<n/;++i)swap(a[i],a[n-i-]);
for(i=;i<n;++i)a[i]=-a[i];
work();
for(i=;i<n;++i)a[i]=;
work();
work();
printf("%d\n",ans);
return ;
}
T2
T3幻影阁的难题：
给你两棵树，你可以分别在两棵树上找一个点，然后在这两个点之间连一条长度为t的边
1.求连边之后最长路的最小值
2.求最长路的期望长度
T3题解：
首先我们看第一问，我们只要树dp算出从某个点出发的最长链，然后取两棵树的最小值相加再加t，但是我们还要考虑不经过新边的情况，那么就是原来树上的最长链，从这两个中取最大值就行了
第二问要求期望，所以我们要把所有的情况都算出来，然后总长除以n*m，我们先把两棵树计算好的最长链排好序
然后我们要计算的就是∑max(最长链,a[i]+b[j])，因为我们排好了序，所以对于每一个i，取最长链的是一段连续的区间，我们只要记一下前缀和就可以快速计算了
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std; long long n,m,t,tot;
long long nex[],las[],l[],aa[];
long long s1[],s2[],fa[],fir[],q[],len[];
bool f[];
long long ss2[],g[];
long long ans,ans1,ans2; int insert(int x,int y,int z){
++tot;
l[tot]=z;
las[tot]=y;
nex[tot]=fir[x];
fir[x]=tot;
} int work(){
int i,x,y,z;
tot=;
for(i=;i<=n;++i)fir[i]=,f[i]=false,s1[i]=,s2[i]=;
for(i=;i<n;++i){
scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
f[]=true;
int ll,rr;
ll=;rr=;
q[]=;
for(;ll<=rr;++ll){
int j;
for(j=fir[q[ll]];j!=;j=nex[j])
if(!f[las[j]]){
f[las[j]]=true;
q[++rr]=las[j];
len[rr]=l[j];
fa[rr]=ll;
}
}
len[]=;g[]=;
s1[]=;s2[]=;
for(i=n;i>;--i){
if(s1[i]+len[i]>s1[fa[i]])s2[fa[i]]=s1[fa[i]],s1[fa[i]]=s1[i]+len[i];
else
if(s1[i]+len[i]>s2[fa[i]])s2[fa[i]]=s1[i]+len[i];
}
long long tmp=;
for(i=;i<=n;++i){
if(s1[i]+len[i]!=s1[fa[i]])g[i]=s1[fa[i]]+len[i];
else g[i]=s2[fa[i]]+len[i];
g[i]=max(g[i],g[fa[i]]+len[i]);
tmp=min(tmp,max(g[i],s1[i]));
ans1=max(ans1,g[i]+s1[i]);
}
ans2+=tmp;
return ;
} long long gcd(long long a,long long b){
if(b==)return a;
return gcd(b,a%b);
} int main(){
scanf("%d%d%d",&n,&m,&t);
ans=;ans1=;ans2=;
work();
int i,j;
for(i=;i<=n;++i)aa[i]=max(g[i],s1[i]);
swap(n,m);
work();
for(i=;i<=n;++i)g[i]=max(g[i],s1[i]);
sort(aa+,aa++m);
sort(g+,g++n);
ans1-=t;
ss2[]=aa[];
for(i=;i<=m;++i)ss2[i]=ss2[i-]+aa[i];
j=m;
for(i=;i<=n;++i){
while((j>)&&(g[i]+aa[j]>ans1))--j;
ans+=ans1*j+g[i]*(m-j)+ss2[m]-ss2[j];
}
ans+=t*n*m;
ans2=max(ans2+t,ans1+t);
printf("%lld\n",ans2);
long long tmp;
tmp=gcd(ans,n*m);
printf("%lld",ans/tmp);
printf("/");
printf("%lld",n*m/tmp);
return ;
}
T3