0915 星际旅行 砍树 超级树

星际旅行

所有边都是双向边，建完图后每个点的度数都是偶数

去掉两条边，剩下的边一定可以组成欧拉回路

1>去掉两条有公共顶点的边

2>去掉两个字自环

3>去掉1个自环+一条边（不是自环）

注意检查边是否连通，不是点是否连通

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100005
#define LL long long
using namespace std;
int n,m;
struct edge
{
int x,y;
}e[maxn];
int fa[maxn],d[maxn];
LL ans=0,cnt;
bool vis[maxn];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
//reopen("tour2.in","r",stdin);
scanf("%d%d",&n,&m);
int op;
for(int i=1;i<=n;i++) fa[i]=i;
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
op=x;
vis[x]=vis[y]=1;
e[i].x=x;
e[i].y=y;
if(x!=y){
d[x]++; d[y]++; }
else cnt++;
fa[find(x)]=find(y);
}
int t=find(op);
bool no=0;
for(int i=1;i<=n;i++)
if(vis[i]&&find(fa[i])!=t){ no=1;break; }
if(no){
printf("0n");
return 0;
}
for(int i=1;i<=n;i++)
ans+=(LL)d[i]*(LL)(d[i]-1)/2;
ans+=cnt*(m-cnt)+cnt*(cnt-1)/2;
printf("%lldn",ans);
//while(1);
return 0;
}

砍树

C=K+sum(a[i]);

sum(|a[i]/d|)<=C/d;  C/d 大概有C^0.5过个取值

f[d]=C/d

l1=1, r=C/(C/l)

对于每一段当d==r时，t=sum(| a[i]/d| )会最小，如果t<=f[t],更新ans

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define maxn 1000002
using namespace std;
int n,num;
LL a[105];
LL f[maxn],R[maxn];
long long K,sum;
inline void pre()
{
LL l=1,r;
num=0;
while(1)
{
if(!(sum/l)) break;
r=sum/(sum/l);
R[++num]=r;
f[num]=sum/r;
l=r+1;
}
}
LL get(LL x,LL y)
{
if(!(x%y)) return x/y;
else return (x/y)+1;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("cut10.in","r",stdin);
scanf("%d%lld",&n,&K);
sum+=K;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=(LL)a[i];
}
pre();
LL t=0,ans=0;
for(int i=1;i<=num;i++)
{
t=0;
for(int j=1;j<=n;j++)
t+=get(a[j],R[i]);
if(t<=f[i]) ans=R[i];
}
printf("%lldn",ans);
//while(1);
return 0;
}

超级树

f[i][j]深度为i的树，同时存在j条点不重复的路径的方案数

考虑i->i+1

num=f[i-1][l]*f[i-1][r]

什么也不增加 f[i][l+r]+=num

加上根节点     f[i][l+r+1]+=num

根节点与左(右)子树中一条路径连边 f[i][l+r]+=num*(l+r)*2

根节点把左子树与右子树的一条路径连起来   f[i][l+r-1]+=num*l*r*2

根节点与左子树（右子树）的两条路径连边    f[i][l+r-1]+=num*(l*(l-1)+r*(r-1))

  

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
int K;
LL mod,num;
LL f[305][605];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("tree2.in","r",stdin);
scanf("%d%lld",&K,&mod);
f[1][0]=f[1][1]=1;
int t;
for(int i=2;i<=K;i++){
t=K-i+2;
for(int j=0;j<=t;j++)
for(int k=0;k<=t;k++)
if(j+k<=t){
num=(f[i-1][j]*f[i-1][k])%mod;
f[i][j+k]=(f[i][j+k]+num)%mod;//
f[i][j+k+1]=(f[i][j+k+1]+num)%mod;//
f[i][j+k]=(f[i][j+k]+num*(j+k)*2)%mod;
if(j+k-1>=0){
if(j-1>=0) f[i][j+k-1]=(f[i][j+k-1]+num*(j*(j-1)))%mod;
if(k-1>=0) f[i][j+k-1]=(f[i][j+k-1]+num*(k*(k-1)))%mod;
f[i][j+k-1]=(f[i][j+k-1]+num*j*k*2)%mod;
}
}
else break;
}
printf("%lldn",f[K][1]%mod);
//while(1);
return 0;
}