期望得分：100+40+100=240
实际得分：100+40+100=240
将每个联通块的贡献乘起来就是答案
如果一个联通块的边数>点数 ，那么无解
如果边数=点数，那么贡献是 2
如果边数=点数-1,那么贡献是点数
#include<queue>
#include<cstdio>
#include<iostream> using namespace std; const int mod=1e9+; #define N 100001 int front[N],to[N<<],nxt[N<<],tot; bool vis[N]; int d[N]; queue<int>q; int ans=; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
d[v]++;
} bool bfs(int s)
{
while(!q.empty()) q.pop();
int p=,e=;
q.push(s); vis[s]=true;
int now;
while(!q.empty())
{
now=q.front(); q.pop();
p++; e+=d[now];
for(int i=front[now];i;i=nxt[i])
if(!vis[to[i]]) vis[to[i]]=true,q.push(to[i]);
}
if(e>p) return false;
if(e==p) ans=ans*%mod;
else ans=1ll*ans*p%mod;
return true;
} int main()
{
freopen("girl.in","r",stdin);
freopen("girl.out","w",stdout);
int n,m;
read(n); read(m);
int u,v;
for(int i=;i<=m;i++)
{
read(u); read(v);
add(u,v);
}
for(int i=;i<=n;i++)
if(!vis[i])
if(!bfs(i)) { cout<<; return ; }
cout<<ans;
return ;
}
显然的结论：
若一个数的K进制和-k进制相同
那么他的k进制/-k进制的偶数位一定是0
然后乱搞就好了
也可以数位DP
#include<iostream>
#include<cstdio>
#include<cmath> using namespace std; typedef long long LL; LL bit[]; int a[]; int main()
{
freopen("endless.in","r",stdin);
freopen("endless.out","w",stdout);
long long n;int k;LL ans=;
scanf("%I64d%d",&n,&k);
int len=;
while(n) a[++len]=n%k,n/=k;
if(!(len&))
{
ans=pow(1LL*k,len/);
cout<<ans;
}
else
{
for(int i=len;i>=;i--)
if(a[i])
{
if(!(i&)) { ans+=pow(1LL*k,i/); break; }
ans+=1LL*a[i]*pow(1LL*k,i/);
if(i==) ans++;
}
cout<<ans;
}
}
40暴力
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; int fbit[]; int a[],b[]; int pre[]; int main()
{
freopen("endless.in","r",stdin);
freopen("endless.out","w",stdout);
int n,k;
scanf("%d%d",&n,&k);
fbit[]=;
int la,lb; int x,ans=min(k-,n)+;
for(int i=k;i<=n;i++)
{
la=;
x=i;
while(x) a[la++]=x%k,x/=k; la--;
x=i;
int c=-,now=;
pre[]=k-;
while()
{
fbit[++now]=fbit[now-]*c*k;
if(!(now&))
{
pre[now]=pre[now-]+(k-)*fbit[now];
if(pre[now]>=x) break;
}
else pre[now]=pre[now-];
}
lb=now;
memset(b,,sizeof(b));
while(now)
{
if(!(now&)) while(x>pre[now-]) b[now]++,x-=fbit[now];
else
{
while(x< && abs(x)>pre[now-]) b[now]++,x-=fbit[now];
while(x>pre[now-]) b[now]++,x+=fbit[now];
}
now--;
}
b[]=x;
if(la!=lb) continue;
bool ok=true;
for(int i=;i<=la && ok ;i++) if(a[i]!=b[i]) ok=false;
if(!ok) continue;
// printf("%d\n",i);
ans++;
}
cout<<ans;
}
考场思路：
每次旅行一定是找当前贡献最大的叶子节点
用线段树维护所有的叶子节点的贡献
修改：
每个点只会修改一次
所以用并查集记录这个点到根节点路径上第一个没有被修改的点
修改沿着并查集的father找上去
对于每个要改的点，预处理出它会影响到的叶子节点，
按dfs到的叶子节点的顺序在线段树中加点，那每个点影响到的叶子节点就是一段连续的区间
dfs记下来，线段树区间修改即可
其实可以不用并查集
往上改到已经改过的点，直接break
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 typedef long long LL; int n,m;
int val[N]; int front[N],nxt[N<<],to[N<<],tot; int F[N],fa[N],id[N]; int cnt,L[N],R[N]; LL w[N]; LL mx[N<<],pos[N<<],tag[N<<]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
} void init()
{
read(n); read(m);
for(int i=;i<=n;i++) read(val[i]);
int u,v;
for(int i=;i<n;i++)
{
read(u); read(v);
add(u,v);
}
} void dfs(int x,int f,LL sum)
{
L[x]=cnt+;
F[x]=x; bool leaf=true;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=f) leaf=false,fa[to[i]]=x,dfs(to[i],x,sum+val[to[i]]);
if(leaf) w[++cnt]=sum,id[cnt]=x;
R[x]=cnt;
} void build(int k,int l,int r)
{
if(l==r) { mx[k]=w[l]; pos[k]=l; return; }
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
mx[k]=max(mx[k<<],mx[k<<|]);
pos[k]= mx[k]==mx[k<<] ? pos[k<<] : pos[k<<|];
} void down(int k)
{
mx[k<<]-=tag[k];
mx[k<<|]-=tag[k];
tag[k<<]+=tag[k];
tag[k<<|]+=tag[k];
tag[k]=;
} void change(int k,int l,int r,int opl,int opr,LL sum)
{
if(l>=opl && r<=opr)
{
mx[k]-=sum;
tag[k]+=sum;
return;
}
if(tag[k]) down(k);
int mid=l+r>>;
if(opl<=mid) change(k<<,l,mid,opl,opr,sum);
if(opr>mid) change(k<<|,mid+,r,opl,opr,sum);
mx[k]=max(mx[k<<],mx[k<<|]);
pos[k]=mx[k]==mx[k<<] ? pos[k<<] : pos[k<<|];
} int find(int i) { return F[i]==i ? i : F[i]=find(F[i]); } void solve()
{
int p; LL ans=;
while(m--)
{
p=id[pos[]]; // 第pos个叶子节点
ans+=mx[];
while(p)
{
change(,,cnt,L[p],R[p],val[p]);
F[p]=find(F[fa[p]]);
p=F[p];
}
}
cout<<ans;
} int main()
{
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
init();
dfs(,,val[]);
build(,,cnt);
solve();
}