noip模拟67(待补)

A. 数据恢复

又一次徘徊于正解的边缘.

什么都可以想到,但偏是实现的方法不对.

本来可以直接用 \(set\) 的东西结果非要打线段树.

别的东西推推性质就行了.

A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long 
	#define ull unsigned ll
	#define lf long double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=3e5+21;

ll m,n,ans,ts;
ll head[N],fa[N],tn[N],to[N],in[N];
multiset<pair<lf,ll> > s;
struct I { ll a,b; lf c; } p[N],bin[N];
ll find(ll x){ return x==fa[x] ? x : fa[x]=find(fa[x]); } 
inline void getc(ll x){ p[x].c=1.0*p[x].a/(1.0*p[x].b); }
inline void merge(ll x,ll y){
	ans+=p[y].b*p[x].a;
	p[y].a+=p[x].a,p[x].a=0;
	p[y].b+=p[x].b,p[x].b=0;
	getc(y),fa[find(x)]=find(y);
}
signed main(){
	File(data);
	n=read(); ll u,v,sum=0;
	for(int i=2;i<=n;i++) to[i]=read();
	for(int i=1;i<=n;i++){
		p[i].a=read(),p[i].b=read(),getc(i);
		s.insert(mp(p[i].c,i)),in[i]=1,fa[i]=i;
	}
	while(s.size()){
		auto it=s.begin();
		u=it->second,v=find(to[u]);
		s.erase(s.begin()),in[u]=0; 
		if(!to[u]) continue;
		if(in[v]){
			s.erase(s.find(mp(p[v].c,v)));
			merge(u,v);
			s.insert(mp(p[v].c,v));
		}
		else{
			merge(u,find(v));
		}
	}
	printf("%lld\n",ans);
	exit(0);
}

B. 下落的小球

感觉这个题目比 \(T1\) 更可做.

数学题,可以看成两个可重集排列来做.

第一个可重集排列:
考虑每个子树除了要落下自己的子树上的点之外,还要落下祖先上的点.
但是落到每棵子树上的祖先上的点的个数是固定的,只是落到不同子树的顺序不同.
所以这个时候可以给顺序写一个可重集排列.

第二个可重集排列:
每个子树在降落完祖先上的点之后,再去分别降落自己子树上面的点.
发现仍然只需要考虑各个子树的降落顺序.
再写一个可重集排列就行了.

最后两个方案数乘起来就是答案.

B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long 
	#define ull unsigned ll
	#define lf long double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=1e6+21,mod=1e9+7;

ll m,n,ts,ans;
ll head[N],req[N],frc[N],siz[N],inv[N];
struct I { ll u,v,nxt; } e[N];
inline void add(ll u,ll v){
	e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u];
	head[u]=ts;
}
inline ll ksm(ll a,ll b,ll c){
	ll res=1; a%=c;
	for(;b;b>>=1,a=a*a%c) if(b&1) res=res*a%c;
	return res%c;
}
void dfs(ll u){
	siz[u]=1; if(!head[u]) return ;
	for(int i=head[u];i;i=e[i].nxt){
		dfs(e[i].v),siz[u]+=siz[e[i].v];
	}
	for(int i=head[u];i;i=e[i].nxt){
		ans=ans*inv[siz[e[i].v]]%mod*inv[req[e[i].v]-siz[e[i].v]]%mod;
		req[u]+=req[e[i].v];
	}
//	if(req[u]<siz[u]) puts("0"),exit(0);
	ans=ans*frc[siz[u]-1]%mod*frc[req[u]-siz[u]+1]%mod;
}
signed main(){
	File(ball);
	n=read(),frc[0]=1,ans=1; ll u;
	for(int i=2;i<=n;i++) u=read(),add(u,i);
	for(int i=1;i<=n;i++) req[i]=read(),frc[i]=frc[i-1]*i%mod;
	inv[n]=ksm(frc[n],mod-2,mod);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	dfs(1),printf("%lld\n",ans),exit(0);
}

C. 消失的运算符

D. 古老的序列问题

上一篇:[NOIP 2005 普及组] 校门外的树


下一篇:noip模拟78(dp待补,扫描线待补)