首页 > 其他分享 >csp模拟 烦死!!!

csp模拟 烦死!!!

时间:2023-09-14 21:57:42浏览次数:33  
标签:const int 烦死 模拟 ull return csp dp mod

好久没有写博客了

csp模拟38

我是A题

真是服了,好好一个题怎么恶心的时间空间,自家oj的评测机真是欠修理。

考虑 \(z\) 从大到小时计算每层的剩下的值,割去的一定是一个阶梯状的图形,考虑到每一层,新增加的就是两条线割剩下的,且这两条线从上到下递增,维护前缀和计算就可以。

点击查看代码
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define max(x,y) (x)>(y)?(x):(y)
#define rg register 
using namespace std;
const int N = 3e7 + 1;
typedef unsigned long long ull;
int n, A, B, C;
struct asd{
	int x,y,z;
}a[N];
inline ull Rand (rg ull &k1, rg ull &k2) {
 	ull k3 = k1, k4 = k2;
 	k1 = k4;
 	k3 ^= (k3 << 23);
 	k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
 	return k2 + k4;
}

inline void print(__int128 x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
inline bool amp(const asd &a,const asd &b){
	return a.z>b.z;
}
inline int Mod(ull x,int p){
	return x<p?x:x%p;
}
void GetData () {
 	ull x, y;
 	scanf("%d%d%d%d%llu%llu",&n,&A,&B,&C,&x,&y);
 	for (int i = 1; i <= n; ++i) {
 		a[i].x = Mod(Rand(x, y) , A) + 1;
 		a[i].y = Mod(Rand(x, y) , B) + 1;
 		a[i].z = Mod(Rand(x, y) , C) + 1;
 		if (Rand(x, y) % 3 == 0) a[i].x = A;
 		if (Rand(x, y) % 3 == 0) a[i].y = B;
 		if ((a[i].x != A) && (a[i].y != B)) a[i].z = C;
 	}
}
int ma[N];
__int128 sma[N];
int mb[N];
__int128 smb[N];
int la[N],lb[N]; 
signed main(){
	GetData();
	__int128 r=1;//r*
	rg int h=a[1].z;
	rg int tp=0;
	for(rg int i=1;i<=n;++i){
		h=max(h,a[i].z); 
		if(a[i].x==A) lb[a[i].z]=max(lb[a[i].z],a[i].y);
		if(a[i].y==B) la[a[i].z]=max(la[a[i].z],a[i].x);
	} 
	for(int i=1;i<=n;i++){
		if(a[i].z==h){
			ma[a[i].x]=max(ma[a[i].x],a[i].y);
			mb[a[i].y]=max(mb[a[i].y],a[i].x);
		}
	}
	__int128 ans=0;
	__int128 sma1=0;
	for(rg int i=A;i;--i){
		ma[i]=max(ma[i],ma[i+1]);
		sma1=sma1+r*ma[i];
	}
	for(rg int i=B;i;--i){
		mb[i]=max(mb[i],mb[i+1]);
	}
	__int128 sma=0,smb=0;
	ans+=r*A*B-sma1;
	rg int sa=0,sb=0;
	for(rg int i=h-1;i;--i){
		if(sa<=la[i]){
			for(int j=sa+1;j<=la[i];j++){
				sma=sma+r*ma[j];
			}
			sa=la[i];
		}
		if(sb<=lb[i]){
			for(int j=sb+1;j<=lb[i];j++){
				smb=smb+r*mb[j];
			}
			sb=lb[i];
		}
		__int128 op;
		if(sb==0) op=1;
		else op=sb;
		if(mb[op]<sa){
			ans+=r*(A-sa)*(B-sb);
		}
		else{
			__int128 s1=r*A*sb-smb;//(smb[1]-smb[sb+1]);
			__int128 s2=r*B*sa-sma;//(sma[1]-sma[sa+1]);
			ans+=r*A*B-sma1-s1-s2; 
		}
	}
	__int128 uk=r*A*B*C-ans-r*A*B*(C-h);
	print(uk);
}
/* 
100 99 98 97 114514 1919810

2 10 10 10 114514 1919810

1000 43112 88371 27391 114514 1919810
104349748515623

9 7 10
7 10 3
*/

我是B题

考试只会状压。

设 \(dp[i][j]\) 表示到第 \(i\) 个机器时,目标物品排名为 \(j\) 的概率。

这里采用刷表法好写一点:

枚举质量为 \(rnk\) 的物品;

初始值 \(dp[1][rnk]=1\)

转移方程:

\(dp[i+1][j−1]+=dp[i][j]×(1−(1−p_i)^{j−1})\) //删除的是 \(j\) 前面的数,不可能让 \(j\) 前面的数全部逃掉

\(dp[i+1][j]+=dp[i][j]×(1−p_i)^j\) //删除的是 \(j\) 后面的数,\(j\) 及 \(j\) 前面的数必须全部逃掉

答案 \(\sum_{rnk=1}^{n} dp[n][1] \times rnk\)

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int mgml(int x,int p){
	x=(x+mod)%mod;
	int ans=1;
	while(p){
		if(p&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		p>>=1;
	}
	return ans;
}
int dp[305][305];
int p[305];
int n;
int work(int d){
	memset(dp,0,sizeof(dp));
	dp[0][d-1]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(dp[i][j]==0) continue;
			dp[i+1][j]+=dp[i][j]*mgml(1-p[i+1],j+1)%mod;
			dp[i+1][j]%=mod;
			if(j>0) dp[i+1][j-1]+=(dp[i][j]*(1-mgml(1-p[i+1],j)+mod)%mod)%mod;
			if(j>0) dp[i+1][j-1]%=mod;
		}
	}
	return dp[n-1][0];
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		scanf("%lld",&p[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int d=work(i);
		ans+=i*d%mod;
		ans%=mod;
	}
	printf("%lld",ans);
}

我是C题

首先一次找出所有出现次数较小的数字比较耗时,我们可以找到任意一个出现次数不满足要求的数字,并且从这个数字处把区间分成两半进行递归,并不会影响正确性,还大大降低了编程复杂度。

但是由于分治两边可能不均等,会导致时间复杂度退化成 \(O(n^2)\) ,维护 \(cnt_i\) 表示 \(i\) 出现的次数。所以选择只遍历小的区间。第一遍删去小区间的值,然后递归大区间,第二遍加上小区间的值递归小区间,不合法的区间以及合法的区间统计完后记得删去 \(cnt\)。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int cnt[N],d[N];
int ans=0;
void solve(int l,int r){
	if(r-l+1<b[r-l+1]){
		for(int i=l;i<=r;i++){
			cnt[a[i]]--;
		}
		return;
	}
	if(l==r){
		if(b[1]<=1) ans=max(ans,ans);
		cnt[a[l]]--;
		return;
	}
	int mid=(l+r)/2;
	int pos=-1,k=b[r-l+1];
	for(int i=l;i<=r;i++){
		if(cnt[a[i]]<k){
			pos=i;
			break;
		}
	}
	if(pos==-1){
		for(int i=l;i<=r;i++) cnt[a[i]]--;
		ans=max(ans,r-l+1);
		return;
	}
	if(pos<=mid){
		for(int i=l;i<=pos;i++) cnt[a[i]]--;
		solve(pos+1,r);
		for(int i=l;i<pos;i++) cnt[a[i]]++;
		solve(l,pos-1);
	}
	else{
		for(int i=pos;i<=r;i++) cnt[a[i]]--;
		solve(l,pos-1);
		for(int i=pos+1;i<=r;i++) cnt[a[i]]++;
		solve(pos+1,r);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	solve(1,n);
	cout<<ans<<endl;
} 

标签:const,int,烦死,模拟,ull,return,csp,dp,mod
From: https://www.cnblogs.com/jinjiaqioi/p/17703576.html

相关文章

  • CSP初赛错题集
    初赛错题集洛谷有题NOIP2018T9给定一个含N个不相同数字的数组,在最坏情况下,找出其中最大或最小的数,至少需要N-1次比较操作。则最坏情况下,在该数组中同时找最大与最小的数至少需要(A)次比较操作。(\(\lceil\rceil\)表示向上取整,\(\lfloor\rfloor\)表示向下取整)A.⌈3N/2⌉-2......
  • CSP-J 2022 游记
    10.8天气越来越冷了,已经开始穿两条秋裤了()。中午在宿舍,mca作为好心人去接电话,被叔叔一句“这是男生宿舍吗?”搞emo。随后415就成了动物园(mca:我还没夹呢)。常有高猿长啸,属引凄异。下午水了一会,写了DP。学习区间DP并放弃。换键盘时让sxx随便按一个键,结果sxx疯狂Ctrl......
  • 【考后总结】9 月 CSP-S 模拟赛 4
    9.14CSP模拟38T1我是A题每个点坐标都至少有一维卡上界。那么按照哪一维卡上界分成\((A,v,w),(u,B,w),(u,v,C)\)三类,对于点\((x,y,z)\),如果会被第一类点删去,那么第一维就不需要考虑了,只需要满足\(y\)不大于所有\(w\)大于等于\(z\)的第一类点中\(v\)的最大值。......
  • CSP 2023 游记
    有人已经开始催我写游记了???DAY-1凌乱……作业写完了,然后就开始再度刷复赛卷……明天的课只能咕了,相比OI,数学算什么!(doge,我今天数学考试还炸了阅读程序噩梦啊啊啊,完善程序要命啊啊啊,一整个疯狂的状态无可奈何啊,初赛前垂死挣扎一下吧QAQ晚上重刷CSP-J2019的卷子吧,不知结果会......
  • 模拟企业环境
               ......
  • 系统架构设计师 - 模拟题 - 案例题(二)
    试题二(25分)阅读以下关于软件系统建模的叙述,在答题纸上回答问题1至问题3。[说明]某软件公司计划开发一套教学管理系统,用于为高校提供教学管理服务。该教学管理系统基本的需求包括:(1)系统用户必须成功登录到系统后才能使用系统的各项功能服务。(2)管理员(Registrar)使用该系统管......
  • 2023年9月CSPM-3国标项目管理中级认证报名到这就对了
    CSPM-3中级项目管理专业人员评价,是中国标准化协会(全国项目管理标准化技术委员会秘书处),面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系,建立健全人才职业能力评价和激励机制的要求,培养我国项目管理领域复合型人才。  【证书含金量】 ·竞聘优先......
  • CSP 202109-2 非零段划分
    题目C++代码//202109-2非零段划分#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=500010;constintM=10010;inta[N],d[M];//d[i]为差分数组boolc[N];intn,ans,sum;intmain(){scanf(&q......
  • Android后台模拟点击探索(附源码)攻略
    ​本攻略将详细介绍如何在Android应用中使用后台模拟点击的技术。通过模拟点击,我们可以在后台执行一些用户交互操作,例如点击按钮、输入文本等。这对于自动化测试、批量操作等场景非常有用。步骤一:添加权限首先,在AndroidManifest.xml文件中添加以下权限:<uses-permissionandro......
  • 【气动学】基于龙格库塔法模拟单机无穷大系统功角稳定仿真matlab实现
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......