恩欧挨批模拟试题-20

水博客太快乐了

RT

考场

先看 \(T1\) ,乍一看是个期望 \(dp\) 。。。
果断看 \(T2\) ,貌似可以状压。。
再看 \(T3\) ,直接暴力。。。。

于是 \(T1\) 写了大力 \(DFS\) ,骗最暴力的那档分吧。。。。
\(T2\) 写了大力状压,时间复杂度 \(O(n·2^{d})\) ,显然是错的,但是貌似没有很好的优化,就这样吧。。。希望数据放水。。。。
\(T3\) 写了大暴力。。。针对数据作答。。。。

分数

预估 : \(t1\) \(30pts\) \(+\) \(t2\) \(72pts\) \(+\) \(t3\) \(65pts\) \(=\) \(167pts\)
实际 : \(t1\) \(30pts\) \(+\) \(t2\) \(72pts\) \(+\) \(t3\) \(65pts\) \(=\) \(167pts\)

把会的分都骗到手了。。。。
发现有巨佬场切了 \(t1\) 。。。

题解

A. 玩具

乍一看就不像是我这样的小蒟蒻会做的题。。。。
概率与期望 \(dp\) 。。

考虑如何设计状态。。。
一个显然的想法是令 \(f_{i,j}\) 等于 \(i\) 个点构成的树深度小于等于 \(j\) 的概率。
考虑 \(f_{i,j}\) 可以从哪里被更新得到。显然,若有一个 \(i-1\) 个点构成的深度小于等于 \(j-1\) 的森林,那么为其增加一个根节点,则构成了一棵高度小于等于 \(j\) 的有 \(i\) 个节点的树。
那么不妨设 \(g_{i,j}\) 表示有 \(i\) 个节点的深度小于等于 \(j\) 的森林的概率,这样 \(f_{i,j}\) 便可以直接从 \(g_{i-1, j-1}\) 转移过来。
考虑 \(g_{i,j}\) 可以从哪些状态转移过来,显然一个森林是由多个树构成的,也可以看成是由一棵小树和一个小森林转移过来。然而森林和一棵树的概率并不可以直接乘起来,因为森林可能有多种形态,直接乘起来可能算重,不妨设 \(dp_{i,j}\) 表示 \(i\) 个点的森林中有 \(j\) 个点和 \(1\) 号点在同一棵树上的概率是多少。
则:
\(g_{i,j}=\sum_{k=1}^{i} f_{k,j}·g_{i-k,j}·dp_{i,k}\)
\(dp_{i,j}\) 显然可以通过以下递推式得到:
\(dp_{i,j}= \frac{j-1}{i} dp_{i-1,j-1}+ \frac{i-j}{i} dp_{i-1,j}\)
注意因为是森林,所以新加入的点可以不加在任何一个点后而是单独另起一个点。。。

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=210;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch==‘-‘) f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int n, p, ans;
int dp[N][N], f[N][N], g[N][N], inv[N];
signed main(void){
	n=read(); p=read();
	inv[1]=inv[0]=1;
	for(int i=2; i<=n; ++i) inv[i]=(p-p/i)*inv[p%i]%p;
	dp[1][1]=f[1][0]=1;
	for(int i=2; i<=n; ++i) for(int j=1; j<=i; ++j)
		dp[i][j]+=(((dp[i-1][j-1]*(j-1)%p)+(dp[i-1][j]*(i-j)%p))%p)*inv[i]%p;
	for(int i=0; i<=n; ++i) g[0][i]=1;
	for(int i=1; i<=n; ++i){
		for(int j=0; j<=n; ++j){
			if(j) f[i][j]=g[i-1][j-1];
			for(int k=1; k<=i; ++k){
				g[i][j]+=f[k][j]*g[i-k][j]%p*dp[i][k]%p;
				g[i][j]%=p;
			}
		}
	}
	for(int i=1; i<=n; ++i) ans+=((f[n][i]-f[n][i-1])%p+p)*i%p, ans%=p;
	printf("%lld\n", (ans%p+p)%p);
	return 0;
}

B. y

首先有一个显然的状压,用 \(f_{s,u}\) 表示状态为 \(s\) 的以 \(u\) 结尾的路径是否存在。
考场我的写法就类似这样,但是这样显然会挂,于是考虑优化。
神之折半搜索。。。。
如果算出以 \(1\) 出发所有长度为 \(\frac{d}{2}\) 的路径,再算出从每个点出发长度为 \(\frac{d}{2}\) 的路径,就可以将这两条路径拼接在一起。
位运算看的我头疼。。。

code
#include<bits/stdc++.h>
using namespace std;
#define t first
#define w second
const int N=100, D=21;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch==‘-‘) f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int n, m, d, d1, ans;
vector<pair<int, int > > l[N];
bool f[N][1<<11][2];
int main(void){
	n=read(), m=read(), d=read(); d1=d>>1;
	int x, y, z;
	for(int i=1; i<=m; ++i){
		x=read(), y=read(), z=read();
		l[x].push_back(make_pair(y, z));
		l[y].push_back(make_pair(x, z));
	}
	f[1][1][0]=1;
	int ul, flag, f1;
	for(int i=2; i<1<<(d1+1); ++i){
		for(int j=d1; j; --j)
			if(i&(1<<j)) { ul=j; break; }
		flag=(i>>(ul-1))&1;
		f1=((i>>ul)<<(ul-1))|(i&((1<<(ul-1))-1));
		for(int u=1; u<=n; ++u) for(pair<int, bool > v : l[u])
			if(v.w==flag) f[u][i][0]|=f[v.t][f1][0];
	}
	for(int i=1; i<=n; ++i) f[i][1][1]=1;
	for(int i=2; i<1<<(d-d1+1); ++i){
		for(int j=d-d1; j; --j)
			if(i&(1<<j)) { ul=j; break; }
		flag=(i>>(ul-1))&1;
		f1=((i>>ul)<<(ul-1))|(i&((1<<(ul-1))-1));
		for(int u=1; u<=n; ++u) for(pair<int, bool > v : l[u])
			if(v.w==flag) f[u][i][1]|=f[v.t][f1][1];
	}
	for(int i=1<<d; i<1<<(d+1); ++i) for(int u=1; u<=n; ++u)
		if(f[u][i>>(d-d1)][0]&f[u][(i&((1<<(d-d1))-1))|(1<<(d-d1))][1]) { ans++; break; }
	printf("%d\n", ans);
	return 0;
}

C. z

由于正解还没有改出来,所以先咕掉了。。。

然而这题骗分可以骗到 \(65pts\) 。。。

首先 \(45pts\) 的做法是显然的。
然而还有一个限制条件 \(\forall i \in [1, n) |x_{i}|<|x_{i+1}|,x_{i}·x_{i+1}<0\) 的分貌似没几个人骗。。。实际上直接大力二分即可。。。

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch==‘-‘) f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int n, q;
int a[N], l, r, len, cnt;
long long ans, sum[N], b[N], c[N];
signed main(void){
	n=read(), q=read();
	for(int i=1; i<=n; ++i) a[i]=read();
	if(n<=1010){
		while(q--){
			ans=l=0, r=len=read();
			for(int i=1; i<=n; ++i){
				if(a[i]>=l&&a[i]<=r) continue;
				else if(a[i]>r) ans+=a[i]-r, r=a[i], l=r-len;
				else if(a[i]<l) ans+=l-a[i], l=a[i], r=l+len;
			}
			printf("%lld\n", ans);
		}
	}else{
		bool flag=0; ans=0;
		for(int i=1; i<n; ++i){
			if(abs(a[i])<abs(a[i+1])&&a[i]*a[i+1]<0) flag=1;
			else { flag=0; break; }
		}
		if(flag){
			int x, ul=0;
			if(a[1]>0) b[++cnt]=a[1], ul=1;
			for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+abs(a[i]-a[i-1]);
			for(int i=cnt+1; i<n; i+=2) b[++cnt]=a[i+1]-a[i], c[cnt]=0-a[i];
			while(q--){
				len=read(); ans=0;
				x=lower_bound(b+1, b+1+cnt,len)-b;
				ans+=c[x]; x=(x<<1)-1-ul;
				ans+=sum[n]-sum[x]; ans-=1ll*len*(n-x);
				printf("%lld\n", ans);
			}
		}else{
			while(q--){
				ans=l=0, r=len=read();
				if(a[1]<l) ans+=l-a[1], l=a[1], r=l+len;
				if(a[1]>r) ans+=a[1]-r, r=a[1], l=r-len;
				if(a[n]<l) ans+=l-a[n], l=a[n], r=l+len;
				if(a[n]>r) ans+=a[n]-r, r=a[n], l=r-len;
				printf("%lld\n", ans);
			}
		}
	}
	return 0;
}

恩欧挨批模拟试题-20

上一篇:noip模拟12 简单的区间 简单的玄学 简单的填数


下一篇:list.stream()