1028 模拟

本文主要是介绍1028 模拟，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

t1 - 回家 home

小 Z 是个路痴。有一天小 Z 迷路了，此时小 Z 到家有 \(N\) 个单位长度。小 Z 可以进行若干次行动，每次行动小Z有 \(\frac{1}{2}\) 的概率向家靠近一个单位长度，有 \(\frac{1}{2}\) 的概率向家远离一个单位长度。由于小Z的体力是有限的，他最多能行动 \(K\) 次。请你帮帮可怜的小Z算一算，他在体力耗尽之前到达家中的概率是多少。

\(1\leq N,K\leq 5\cdot 10^6\)

考虑概率计算，用方案数/总情况.

考虑枚举在 \(i\) 步之后走到终点 .

那么，可以直接计算出向左走的步数和向右走的步数 . 看作是 \(+1\) 和 \(-1\) .

考虑每次向右走一步，纵坐标 \(+1\) 走了 \(n+1\) 步，\(-1\) 走了 \(m\) 步 .

那么从 \((0,0)\) 走到 \((n+m+1,n+1-m)\) 的方案数，其中横坐标不能走到 \(0\) 以下 .

首先忽略第二个性质，方案数为 \(\dbinom{n+m}{n}\) ，因为最后一步一定要为 \(+1\) ，所以方案数就是在剩下 \(n+m\) 步中选出 \(n\) 步向上 . 但是，其中必定存在一些向下的边，考虑一旦接触到了 \(-1\) ，就把后面的步数翻转，一一对应到一种新的走法，最后走到的位置还是 \((n+m+1,n+2-m)\) . 从上可知方案数为 \(\dbinom{n+m}{n+1}\) .

因此，方案数就是 \(\dbinom{n+m}{n}-\dbinom{n+m}{n+1}\) .

枚举 \(i\) 步之后走到终点 . \(+1\) 走了 \(n+\frac{i-n}{2}\) 步，\(-1\) 走了 \(\frac{i-n}{2}\) 次 .

那么，最后的答案即为

只需要 \(O(n)\) 地预处理出阶乘，阶乘的逆元即可 .

时间复杂度 : \(O(n)\)

空间复杂度 : \(O(n)\)

code

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,k;
int fact[5000010],inv[5000010],inv2[5000010];
inline int ksm(int x,int k){
	if(k==0)return 1;
	int res=ksm(x,k>>1);
	res=1ll*res*res%mod;
	if(k&1)res=1ll*res*x%mod;
	return res;
}
inline int C(int a,int b){
	return 1ll*fact[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	fact[0]=1;
	for(int i=1;i<=k;i++)fact[i]=1ll*i*fact[i-1]%mod;
	inv[k]=ksm(fact[k],mod-2);
	for(int i=k-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	inv2[0]=1;inv2[1]=ksm(2,mod-2);
	for(int i=2;i<=k;i++)inv2[i]=1ll*inv2[i-1]*inv2[1]%mod;
	int ans=0;
	for(int i=n;i<=k;i+=2){
		int tmp=1ll*(C(i-1,n+(i-n)/2-1)-C(i-1,n+(i-n)/2)+mod)%mod*inv2[i]%mod;
		ans=(ans+tmp)%mod;
	}
	cout<<ans<<endl;
	return 0;
}
/*inline? ll or int? size? min max?*/

题目来源 : nflsoj 20034 #12514. 「NOIP2021模拟赛石室中学2」回家

t2 - 最小化 min

​ 小 F 有一个长度为 \(n\) 的正整数序列 \(A\) 。他的好朋友小 T 提出了这样的一个概念，对于一个序列 \(A\) ，它的 \(K\) 项差和为所有相邻 \(K\) 项的元素的差的绝对值的和。以序列 \(A\) 为例，它的 \(K\) 项差和为：

\[\sum\limits_{i=1}^{n-k}|A_i-A_{i+k}| \]

​ 现在小 F 想求序列 \(A\) 的 \(k\) 项差和，为了使序列 \(A\) 的 \(k\) 项差和尽可能地小，小 F 决定对序列 \(A\) 进行重新排序。

​ 现在，请你帮助小 F 求出对序列 \(A\) 进行任意重排后其 \(K\) 项差和的最小值。

\(1\leq n\leq 10^6,1\leq k\leq 5000,1\leq A_i\leq 10^9\)

对于 \(A_i\) ，只有 \(|A_i-A_{i-k}|\) 和 \(|A_i-A_{i+k}|\) 可能会对答案产生贡献 .

所以，对于 \(A_i\) 和 \(A_j\) ，如果 \(i\mod k\not= j\mod k\) 两个值不会互相影响 .

所以，把 \(i\mod k\) 相同的数都放在一起 .

考虑对于下标 \(1,1+k,1+2k,\cdots,1+ak\) 的值，怎样安排才能使产生的代价最小呢？

猜是 sort 一遍，从小到达填入 \(1,1+k,1+2k,\cdots ,1+ak\) 中 ，产生的代价是 \(|A_{1+ak}-A_{1}|\) .

考虑对于模 \(k\) 余 \(0,1,2,\cdots ,k-1\) 序列怎么分配 .

首先，把 \(A\) 从小到大排序，对于模 \(k\) 相同的序列选择的必须是连续的一段 .

对于模 \(k\) 余 \(0\) 到 \(k-1\) 的序列长度只有两种情况 ，\(l_1=\lfloor \frac{n}{k}\rfloor\) 和 \(l_2=\lfloor \frac{n}{k}\rfloor +1\) ，个数分别为 $s_1=n-k\lfloor \frac{n}{k}\rfloor $ 和 $s_2=k-n+k\lfloor \frac{n}{k}\rfloor $

此时可以考虑 \(dp\) .

用 \(f(i,j)\) 表示第一种长度的序列选了 \(i\) 个，第二种长度的序列选了 \(j\) 个的最小代价.

转移 \(dp\) 转移方程 .

\(f(i,j)\longrightarrow f(i+1,j)+|A_{(i+1)l_1+jl_2}-A_{il_1+jl_2+1}|\)

\(f(i,j)\longrightarrow f(i,j+1)+|A_{il_1+(j+1)l_2}-A_{il_1+jl_2+1}|\)

最小贡献即为 \(f(s_1,s_2)\) .

时间复杂度 : \(O(n\log n+m^2)\)

空间复杂度 : \(O(n+m)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res;
}
inline void print(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
const int inf=1e9+10;
int n,k;
int a[1000010];
int f[5010][5010];
inline void upd(int &x,int y){x=min(x,y);}
int main(){
	freopen("min.in","r",stdin);
	freopen("min.out","w",stdout); 
	n=read();k=read();
	for(int i=0;i<n;i++)a[i]=read();
	sort(a,a+n);
	for(int i=0;i<5010;i++)for(int j=0;j<5010;j++)f[i][j]=inf;
	int s1=n-n/k*k,s2=k-s1;
	f[0][0]=0;
	for(int i=0;i<=s1;i++)for(int j=0;j<=s2;j++){
		if(f[i][j]==inf)continue;
		upd(f[i+1][j],f[i][j]+a[(i+1)*(n/k+1)+j*(n/k)-1]-a[i*(n/k+1)+j*(n/k)]);
		upd(f[i][j+1],f[i][j]+a[i*(n/k+1)+(j+1)*(n/k)-1]-a[i*(n/k+1)+j*(n/k)]);
	}
	print(f[s1][s2]);
	return 0;
}
/*inline? ll or int? size? min max?*/
/*
6 3
4 3 4 3 2 5
*/

题目来源 : nflsoj 20034 #12515. 「NOIP2021模拟赛石室中学2」最小化

t3 - 集合 set

小 W 有一个可重正整数集合 \(S\)。集合 \(S\) 起初为空集。小 W 想对集合进行以下操作。

1．向集合中插入一个正整数 \(a\) 。

2．每次令集合中 \(c\) 个正整数减小 \(1\)，求最多进行的操作次数（该操作不改变集合中元素本身的值）。

现在，请您编写一个程序，帮助小W实现上述功能。

\(1\leq n\leq 10^6\)

时限 \(1s\) . 应该是道卡场题 .

正着考虑最多操作次数很难 . 考虑倒着想 . 因为可进行的最多操作次数具有单调性，考虑二分 .

二分当前最多操作次数是 \(mid\) . 那么，用到的个数是 \(c\times mid\) .

考虑 \(S\) 中的比 \(mid\) 小的数，必定可以被全部用掉，贡献是 \(\sum a_i\) 次 .

考虑比 \(mid\) 大的数 ，最多只会被用 \(mid\) 次 , 有 \(x\) 个，贡献就是 \(x\times mid\) .

\(x\times mid+\sum a_i\geq c\times mid\) .

需要维护 \(\sum a_i\) 和 \(x\) ，这两个东西都可以用 bit 来维护 .

但是加上二分 ，时间复杂度就是双 log ，要 t 飞了 .

此时考虑在 bit 上二分. 就解决了这个问题 .

时间复杂度 : \(O(n\log n)\)

空间复杂度 : \(O(n)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res;
} 
inline void print(long long res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[20],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
int q,n=0;
int type[1000010],a[1000010];
int b[2000010],m=0;
int bit1[2000010];
long long bit2[2000010];
inline void upd(int i){
	int val=b[i];
	while(i<=m){
		bit1[i]++;
		bit2[i]+=val;
		i+=i&-i;
	}
}
inline int sum1(int i){
	int res=0;
	while(i){
		res+=bit1[i];
		i-=i&-i;
	}
	return res;
}
inline long long sum2(int i){
	long long res=0;
	while(i){
		res+=bit2[i];
		i-=i&-i;
	}
	return res;
}
inline long long qry(int c){
	if(c>n)return 0;
	int i=0;
	int sum1=0;
	long long sum2=0;
	for(int k=19;k>=0;k--){
		if(i+(1<<k)>m)continue;
		if((sum2+bit2[i+(1<<k)])>=1ll*(c-(n-sum1-bit1[i+(1<<k)]))*b[i+(1<<k)]){
			sum2+=bit2[i+(1<<k)];
			sum1+=bit1[i+(1<<k)];
			i+=1<<k;
		}
	}		
	return 1ll*sum2/(c-(n-sum1));
}
int main(){
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	q=read();
	for(int i=0;i<q;i++){
		type[i]=read();
		a[i]=read();
		if(type[i]==1)b[++m]=a[i];
	}
	sort(b+1,b+m+1);
	m=unique(b+1,b+m+1)-b-1;
	for(int i=0;i<q;i++){
		if(type[i]==1){
			int id=lower_bound(b+1,b+m+1,a[i])-b;
			n++;
			upd(id);
		}else{
			print(qry(a[i]));
			putchar('\n');
		}
	}
	return 0;
}
/*inline? ll or int? size? min max?*/
/*
6
1 5
1 7
2 2
1 1
2 2
2 1
*/

题目来源 : nflsoj 20034 #12517. 「NOIP2021模拟赛石室中学2」王国

这篇关于1028 模拟的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！