noip模拟56

A. 爆零

原题,但是我的复杂度是假的.

A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define lf double
	#define ull unsigned ll
	#define mp make_pair
	#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,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read(){
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e6+21;

ll m,n,ts,ans,tail,tot;
ll head[N],fa[N],dep[N],stk[N],rk[N];
vector<ll> vec[N];
struct I { ll u,v,nxt; } e[N<<1];
inline void add(ll u,ll v){
	e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u],
	head[u]=ts;
}
inline bool comp(ll i,ll j){ return i > j ; } 
void dfs(ll u,ll depth){
	dep[u]=depth,rk[u]=(tail ? stk[tail--] : ++tot );
	ll x=rk[u],cnt=0;
	if(!head[u]){
		ans+=dep[u];
		vec[x].push_back(dep[u]);
		return ;
	}
	for(int i=head[u];i;i=e[i].nxt){
		dfs(e[i].v,depth+1);
		for(int j : vec[rk[e[i].v]]){
			vec[x].push_back(j);
		}
		vec[rk[e[i].v]].clear(),stk[++tail]=rk[e[i].v],rk[e[i].v]=0;
	}
	sort(vec[x].begin(),vec[x].end(),comp);
	for(int i=vec[x].size()-1;i>=1;i--){
		if(vec[x][i]-depth<depth){
			cnt++,ans+=vec[x][i]-depth*2;
		}
	}
	while(cnt--) vec[x].pop_back();
}
signed main(){
	FILE(a);
	n=read(); ll u,v; 
	for(int i=2;i<=n;i++){
		u=read(),add(u,i),fa[i]=u;
	}
	dfs(1,0);
	printf("%lld\n",ans),exit(0);
}

B. 底垫

首先需要了解一下珂朵莉树,而且这题卡不掉珂朵莉,因为题目性质.

按照右端点排序后,我们选择移动一个指针指向右端点.

然后分别根据 \(l\) 的位置进行加减即可.

B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf 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,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		int ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

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

ll n,m;
ll L[N],R[N],ans[N];
struct I {
	ll l,r,w;
	I(){}
	I(ll x,ll y,ll z){ l=x,r=y,w=z; } 
	I(ll x){ l=x; }
	inline bool operator <(const I &x)const{
		return l<x.l;
	}
};
#define sit set<I>::iterator
set<I> s;
struct BIT{
	ll res; ll c[N<<1];
	inline void update(ll x,ll w){ for(;x;x&=x-1) c[x]=(c[x]+w)%mod; }
	inline ll query(ll x){ res=0; for(;x<=n;x+=lbt(x)) res=(res+c[x])%mod; return res; }
}b,bl,br,blr;
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;
}
inline sit split(ll pos){
	sit it=s.lb(I(pos));
	if(it!=s.end() and it->l==pos) return it;
	--it;
	ll l=it->l,r=it->r,w=it->w;
	s.erase(it),s.insert(I(l,pos-1,w));
	return s.insert(I(pos,r,w)).first;
}
inline void assign(ll l,ll r,ll x){
	sit itr=split(r+1),itl=split(l);
	for(sit it=itl;it!=itr;it++){
		ll k=it->r-it->l+1,t=it->w;
	 	bl.update(x,(x-1)*k%mod),bl.update(t,(1-x+mod)*k%mod);
	 	br.update(x,(x+1)*k%mod),br.update(t,(mod-1-t)*k%mod);
		blr.update(x,mod-k),blr.update(t,k);
		b.update(x,(1-x*x%mod+mod)%mod*k%mod);
		b.update(t,(x*t%mod+x-t-1+mod)%mod*k%mod);
	}
	s.erase(itl,itr),s.insert(I(l,r,x));
}
struct II { ll l,r,id; } q[N];
inline bool comp(II i,II j){ return i.r<j.r; } 
signed main(){
	FILE(b);
	n=read(),m=read();
	for(int i=1;i<=n;i++) L[i]=read(),R[i]=read()-1;
	for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
	s.insert(I(1,1e9,0)),sort(q+1,q+1+m,comp);
	ll p=0,resl,resr,reslr,resb,res;
	for(int i=1;i<=m;i++){
		while(p<q[i].r) p++,assign(L[p],R[p],p);
		resl=q[i].l*bl.query(q[i].l)%mod;
		resr=q[i].r*br.query(q[i].l)%mod;
		reslr=q[i].l*q[i].r%mod*blr.query(q[i].l)%mod;
		resb=b.query(q[i].l);
		res=(resl+resr+reslr+resb)%mod;
		ans[q[i].id]=res*ksm((q[i].r-q[i].l+1)*(q[i].r-q[i].l+2)>>1,mod-2,mod)%mod;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	exit(0);
}

C.高考

二项式反演,比较裸的题目了.

C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf 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) memset(x,y,sizeof x)
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline int read() {
		int ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

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

ll n,m,ans;
ll frc[(int)1e6+21],inv[(int)1e6+21];
ll f[N][N],g[N][N];
inline ll ksm(ll a,ll b,ll c){
	a%=c; ll res=1;
	while(b){
		if(b&1) res=(res*a)%c;
		a=(a*a)%c,b>>=1;
	}
	return res%c;
}
inline ll C(ll a,ll b){
	if(a>b) return 0;
	return frc[b]*inv[a]%mod*inv[b-a]%mod;
}
signed main(){
	FILE(c);
	n=read(),m=read(),frc[0]=1,inv[0]=1; ll res;
	for(ll i=1;i<=1e5;i++){
		frc[i]=frc[i-1]*i%mod,inv[i]=ksm(frc[i],mod-2,mod);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m/i;j++){
			for(int k=i;k<=m/j;k++){
				res=C(i,k)*C(k,n)%mod*C(n-1,m+n-1-j*k)%mod;	
				if((k&1)==(i&1)) g[i][j]=(g[i][j]+res)%mod;
				else g[i][j]=(g[i][j]-res+mod)%mod;
			}
		}
	}	
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			f[i][j]=(f[i+1][j]+g[i][j])%mod;
		}
	}
	res=ksm(C(n-1,n+m-1),mod-2,mod);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans=(ans+f[i][j])%mod;
		}
		printf("%lld\n",(ans*res%mod+i)%mod);
	}
	exit(0);
}

D. 种田

上一篇:剑指 Offer 56 - I. 数组中数字出现的次数


下一篇:【LeetCode】137. 只出现一次的数字 II(剑指offer 56-II)