【历年CSP-S复赛第一题】暴力解法与正解合集（2019-2022）

news/2024/10/3 20:12:34 标签: c++
  1. P5657 [CSP-S2019] 格雷码
  2. P7076 [CSP-S2020] 动物园
  3. P7913 [CSP-S 2021] 廊桥分配
  4. P8817 [CSP-S 2022] 假期计划

P5657 [CSP-S2019] 格雷码

暴力50分

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
int n,k;
signed main()
{
	IOS;
	cin>>n>>k;
	vector<string> v;
	v.pb("0");
	v.pb("1");
	for(int j=1;j<=n-1;j++) 
	{
		vector<string> vt;
		for(int i=0;i<(int)v.size();i++)
		{
			vt.pb("0"+v[i]);
		}
		for(int i=(int)v.size()-1;i>=0;i--)
		{
			vt.pb("1"+v[i]);
		}
		v = vt;
	}
	cout<<v[k];
}

正解

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
unsigned long long n,k;
signed main()
{
	IOS;
	cin>>n>>k;
	__int128 sum = (__int128)pow(2,n);
	int pre = -1;
	while(1)
	{
		if(pre==-1)
		{
			if(k<=sum/2-1)
			{
				cout<<0;
				pre = -1;
			}
			else
			{
				cout<<1;
				pre = 1;
				k -= sum/2;
			}	
		}
		else
		{
			if(k<=sum/2-1)//k下标从1开始 
			{
				cout<<1;
				pre = -1;
			}
			else
			{
				cout<<0;
				pre = 1;
				k -= sum/2;
			}
		}
		sum /= 2;
		if(sum==1) break;
	}
}

P7076 [CSP-S2020] 动物园

暴力

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
int n,m,c,k;
int limit[N],va[N];
signed main()
{
	IOS;
	cin>>n>>m>>c>>k;
	for(int i=1;i<=n;i++) cin>>va[i];
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		limit[a] = b;//动物编号第a为1就必须有b号饲料 
	}
	set<int> s;
	for(int i=1;i<=n;i++)//由已有动物来倒推我有哪些饲料
	{
		for(int j=0;j<=k-1;j++)
		{
			if((va[i]>>j)&1)//动物编号的二进制第j位为1 
			{
				s.insert(limit[j]);//动物编号的二进制第j位为1,即需要limit[j]号饲料
			}
		}
	}
	int sum = 0;
	for(int i=0;i<=pow(2,k)-1;i++)
	{
		int suc = 1;
		for(int j=0;j<=k-1;j++)
		{
			if((i>>j)&1)
			{
				if(limit[j]==0) continue;
				if(s.count(limit[j])) continue;
				suc = 0;
			}
		}
		if(suc==1) sum++;
	}
	cout<<sum-n;
}

正解

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
int n,m,c,k;
int limit[N],va[N];
bool vis[N];
signed main()
{
	IOS;
	cin>>n>>m>>c>>k;
	for(int i=1;i<=n;i++) cin>>va[i];
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		limit[a] = b;//动物编号第a为1就必须有b号饲料 
	}
	for(int j=0;j<=k-1;j++)
	{
		if(limit[j]==0) vis[j] = 1;
		for(int i=1;i<=n;i++)
		{
			if((va[i]>>j)&1) vis[j] = 1;//由已有动物来倒推我哪些位置有哪些饲料
		}
	}
	int sum = 0;
	for(int i=0;i<=k-1;i++)
	{
		if(vis[i]==1) sum++;
	}
	if(sum==64)
	{
		if(n==0) cout<<"18446744073709551616";
		else cout<<(1ull<<(sum-1))-n+(1ull<<(sum-1));
	}
	else cout<<(1ull<<sum)-n;
}

P7913 [CSP-S 2021] 廊桥分配

暴力

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
int n,m1,m2;
struct node{
	int in;
	int out;
}va[N],vb[N];
bool cmp(node a,node b)
{
	return a.in<b.in;
}
int solve(int sum1,int sum2)
{
	int ans = 0;
	priority_queue <int,vector<int>,greater<int> > q1,q2;
	for(int i=1;i<=m1;i++) 
	{ 
		while(q1.size()&&q1.top()<=va[i].in) q1.pop();
		if(q1.size()<sum1)
		{
			ans++;
			q1.push(va[i].out);
		}
	}
	for(int i=1;i<=m2;i++) 
	{ 
		while(q2.size()&&q2.top()<=vb[i].in) q2.pop();
		if(q2.size()<sum2)
		{
			ans++;
			q2.push(vb[i].out);
		}
	}
	return ans;
}
signed main()
{
	IOS;
	cin>>n>>m1>>m2;
	int maxn = 0;
	for(int i=1;i<=m1;i++)
	{
		cin>>va[i].in>>va[i].out;
	}
	for(int i=1;i<=m2;i++)
	{
		cin>>vb[i].in>>vb[i].out;
	}
	sort(va+1,va+1+m1,cmp);
	sort(vb+1,vb+1+m2,cmp);
	for(int i=0;i<=n;i++)
	{
		maxn = max(maxn,solve(i,n-i));
	}
	cout<<maxn;
}

正解

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long

using namespace std;

const int N = 1e5+10;

int n,m1,m2;
PII va[N],vb[N];
int cnt1[N],cnt2[N];

priority_queue<PII,vector<PII>,greater<PII>> q1,q2;

int solve1()
{
	for(int i=1;i<=n;i++) q1.push({0,i});
	for(int i=1;i<=m1;i++)
	{
		int min_id = 1e9;
		vector<PII > v;
		while(q1.size()&&q1.top().fi<=va[i].fi)
		{
			v.push_back(q1.top());
			if(min_id>q1.top().se) min_id = q1.top().se;
			q1.pop();
		}
		for(auto t:v)
		{
			if(t.se==min_id) q1.push({va[i].se,t.se});
			else q1.push({0,t.se});
		}
		if(min_id!=1e9) cnt1[min_id]++;
	}
	for(int i=1;i<=n;i++) cnt1[i] = cnt1[i]+cnt1[i-1];
}

int solve2()
{
	for(int i=1;i<=n;i++) q2.push({0,i});
	for(int i=1;i<=m2;i++)
	{
		int min_id = 1e9;
		vector<PII > v;
		while(q2.size()&&q2.top().fi<=va[i].fi)
		{
			v.push_back(q2.top());
			if(min_id>q2.top().se) min_id = q2.top().se;
			q2.pop();
		}
		for(auto t:v)
		{
			if(t.se==min_id) q2.push({va[i].se,t.se});
			else q2.push({0,t.se});
		}
		if(min_id!=1e9) cnt2[min_id]++;
	}
	for(int i=1;i<=n;i++) cnt2[i] = cnt2[i]+cnt2[i-1];
}

signed main()
{
//	freopen("w.in","r",stdin);
//  freopen("ho.out","w",stdout);
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++) cin>>va[i].fi>>va[i].se;
	for(int i=1;i<=m2;i++) cin>>vb[i].fi>>vb[i].se;
	sort(va+1,va+1+m1);
	sort(vb+1,vb+1+m2);
	solve1();solve2();
	int anw = 0;
	for(int i=0;i<=n;i++) anw = max(anw,cnt1[i]+cnt2[n-i]);
	cout<<anw;
	return 0;
}

http://www.niftyadmin.cn/n/5688921.html

相关文章

FGPA实验——触摸按键

FGPA实验——触摸按键

本文系列都基于正点原子新起点开发板 FPGA系列 1&#xff0c;verlog基本语法&#xff08;随时更新&#xff09; 2&#xff0c;流水灯&#xff08;待定&#xff09; 3&#xff0c;FGPA实验——触摸按键 一、触摸操作原理实现 分类&#xff1a;电阻式&#xff08;不耐用&…
阅读更多...
基于香橙派AI PRO的千问大模型适配实战分享

基于香橙派AI PRO的千问大模型适配实战分享

文章目录 基于香橙派AI PRO的千问大模型适配实战分享1. 环境准备与基础设置2. 模型编译与适配3. ONNX 转 OM 模型4. 部署与推理5. 动态 shape 的性能优化6. 结束与总结 基于香橙派AI PRO的千问大模型适配实战分享 随着大模型技术的迅速发展&#xff0c;越来越多的开发者希望将…
阅读更多...
提升效率的秘密武器选择与使用指南

提升效率的秘密武器选择与使用指南

在忙碌且高速运转的工作环境中&#xff0c;每一个高效的编程工具都能被视作提高效率的秘密武器。它不仅仅是一款用于开发应用程序的机器或工具&#xff0c;而是一种能在各个层面上助力开发者的神器。本篇文章旨在分析那些能帮助开发者工作更加顺畅&#xff0c;提升编程效率和自…
阅读更多...
Overview of Transformer

Overview of Transformer

写在开头 在学习 Transformer 之前&#xff0c;需要对卷积神经网络和循环神经网络&#xff0c;以及 GRU 和 LSTM 有所了解。推荐吴恩达在 Coursera 平台的课程【深度学习专项】&#xff0c;B 站有搬运版 https://www.bilibili.com/video/BV12E411a7Xn/?spm_id_from333.337.sea…
阅读更多...
02SQLite

02SQLite

文章目录 索引创建索引删除索引索引优点及缺点&#xff1f;避免使用索引 视图创建视图删除视图 事务事务控制命令通过事务方式对数据库进行访问优势&#xff1a; 索引 创建索引 索引&#xff08;Index&#xff09;是一种特殊查找表&#xff0c;数据库搜索引擎用来加速数据检索…
阅读更多...
【重学 MySQL】五十一、更新和删除数据

【重学 MySQL】五十一、更新和删除数据

【重学 MySQL】五十一、更新和删除数据 更新数据删除数据注意事项 在MySQL中&#xff0c;更新和删除数据是数据库管理的基本操作。 更新数据 为了更新&#xff08;修改&#xff09;表中的数据&#xff0c;可使用UPDATE语句。UPDATE语句的基本语法如下&#xff1a; UPDATE ta…
阅读更多...
基于Springboot+Vue的小区停车场管理系统登录（含源码数据库）

基于Springboot+Vue的小区停车场管理系统登录（含源码数据库）

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: SpringBoot自带 apache tomcat 主要技术: Java,Springboot,mybatis,mysql,vue 2.视频演示地址 3.功能 在这个…
阅读更多...
MySQL高阶2010-职员招聘人数2

MySQL高阶2010-职员招聘人数2

目录 题目 准备数据 分析数据 总结 题目 一家公司想雇佣新员工。公司的工资预算是 $70000 。公司的招聘标准是&#xff1a; 继续雇佣薪水最低的高级职员&#xff0c;直到你不能再雇佣更多的高级职员。用剩下的预算雇佣薪水最低的初级职员。继续以最低的工资雇佣初级职员&…
阅读更多...
最新文章

Copyright @ 2022~2023