首页 > 其他分享 >河南萌新联赛2024第(四)场

河南萌新联赛2024第(四)场

时间:2024-08-08 22:23:47浏览次数:12  
标签:prime 联赛 int 质数 cin 2024 l2 萌新 nums1

题目链接:河南萌新联赛2024第(四)场:河南理工大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

1.小雷的神奇电脑

同或概念:

• 如果两个输入位相同,则输出为1
• 如果两个输入位不同,则输出为0 

所以可以发现规律,最大同或一定出现在相邻两个数(二进制下位相同多),同时利用补位异或实现同或的功能

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int n, m;
	vector<int> nums1;
	cin >> n >> m;
	while (n--)
	{
		int num;
		cin >> num;
		nums1.push_back(num);
	}
	sort(nums1.begin(),nums1.end());
	int max1 = 0;
	for (int i = 0; i < nums1.size()-1; i++)
	{
		int ans = ~(nums1[i] ^ nums1[i+1]) & ((1 << m) - 1); // 计算同或值
		max1 = max(max1, ans);
	}
	cout << max1 << endl;

	return 0;
}
2.简单的素数
#include <iostream>
using namespace std;

bool is_prime(int n)
{
	if (n < 2) return false; // 0 和 1 不是质数
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0) return false; // 有因子,返回 false
	}
	return true; // 没有因子,返回 true
}

int main()
{
	int num,t;
	cin>>t;
	while(t--)
	{
		cin >> num;
		if (is_prime(num))
		{
			cout << "Yes" << endl; // 是质数
		}
		else
		{
			cout << "No" << endl; // 不是质数
		}
	}
	return 0;
}
3.AND 

1.发现子区间and和为0规律:大于2或者质数唯一则符合条件的子区间为0,质数大于2的等于sum-2
2.首先筛选法求出质数(减少时间复杂度),然后二分法查找质数个数(减少空间复杂度) 

#include <iostream>
#include <vector>
using namespace std;
bool sum[100000010];  // 存储是否被筛掉
vector<int> prime;    // 存储素数

void op(int n)
{
	sum[1] = 1;  // 1 不是素数
	for (int i = 2; i <= n; i++)
	{
		if (!sum[i]) prime.push_back(i);  // 如果 i 是素数,添加到 prime
		for (int j : prime)
		{
			if (j * i > n) break;  // 超过范围时停止
			sum[j * i] = 1;        // 筛掉倍数
			if (i % j == 0) break; // 如果 i 是 j 的倍数,停止
		}
	}
}
int main()
{
	op(100000000);  // 生成素数
	int t;
	cin >> t;  // 输入测试用例数量
	while (t--)
	{
		int x, y;
		cin >> x >> y;  // 输入范围 x 和 y
		int count = 0, l1 = 0, r1 = prime.size() - 1, l2 = 0, r2 = r1;
		// 二分查找 x 在 prime 中的位置
		while (l1 < r1)
		{
			int m = l1 + r1 >> 1;
			if (prime[m] < x) l1 = m + 1;
			else r1 = m;
		}
		// 二分查找 y 在 prime 中的位置
		while (l2 < r2)
		{
			int m = l2 + r2 >> 1;
			if (prime[m] < y) l2 = m + 1;
			else r2 = m;
		}

		if (prime[l2] > y) l2--;  // 确保 l2 在 y 的范围内
		count = l2 - l1 + 1;      // 计算在 [x, y] 范围内的质数个数

		// 输出结果
		cout << count << ' ';
		if (x > 2 || count == 1)
		{
			cout << 0 <<endl;  // 如果 x > 2 或者质数个数为 1
		}
		else if (count >= 2)
		{
			cout << count - 2 << endl;  // 质数个数大于等于 2
		}
	}
	return 0;
}
 4.小雷的算式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,temp;
vector<int>nums;
int sum=0,temp1;
int main()
{
	cin>>s;
	for(int i=0; i<s.size(); i++)
	{

		if(s[i]!='+')
		{
			temp+=s[i];
		}
		if (s[i]=='+'||i==s.size()-1)
		{
			temp1=stoi(temp);
			nums.push_back(temp1);
			sum+=temp1;
			temp.clear();
		}
	}
	sort(nums.begin(),nums.end(),greater<int>());//不要用string存储和排序(string排序逐字符比较,不看字符串长度)
	for(int i=0; i<nums.size()-1; i++)
	{
		cout<<nums[i]<<"+";
	}
	cout<<nums[nums.size()-1]<<endl<<sum<<endl;
	return 0;
}
 5.聪明且狡猾的恶魔

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin >> t; // 读取测试数据的数量
	while (t--)
	{
		int x, n;
		cin >> x >> n; // 读取金币数量和恶魔数量
		// 计算可以获得的最多金币
		int k = (n + 1) / 2 - 1; // 需要至少支持的恶魔数量
		int max1 = x - k; // 老大能够获得的金币数量
		cout << max1 << endl; // 输出结果
	}
	return 0;
}

标签:prime,联赛,int,质数,cin,2024,l2,萌新,nums1
From: https://blog.csdn.net/2301_77869606/article/details/141037534

相关文章

  • 2024牛客多校第七场
    K贪心地先凑出前后端后,中间的部分是本质不同的子序列个数然后枚举可以重叠的部分,如果可以重叠肯定是回文后缀有不少细节,比如空串,重叠部分要求后面的能取到#include<cstdio>#include<iostream>#defineintlonglong#defineULLunsignedlonglongusingnamespacestd;......
  • 2024牛客多校第八场
    E观察到s(m)<=108,所以r是可以枚举的但是枚举完后再开根号,时间复杂度为O(T*r*sqrt(n))≈O(100*100*1e6)赛时还想了一种自认为更优的做法。考虑枚举i,枚举完i就能得到r,判断是否满足条件(当然,就像分解质因数那样,n/i也要判断)然后直接这么写会出点小问题,比如11=10*1+1,i=1时11%1=0在......
  • win7一键修复所有dll缺失详细方法,7个dll修复方法深度解析(2024)
    dll文件是一种包含函数和其他关键信息的文件,供Windows应用程序使用。虽然大多数普通用户对.dll文件的具体工作原理并不熟悉,但这些文件对于系统应用来说是至关重要的。通常情况下,人们在遇到因DLL文件缺失或损坏而导致的错误时,才会接触到它们。对于非专业用户来说,理解这些错......
  • 2024年最新免费AI大模型API汇总及国内大模型使用教程(附代码)
    免费大模型API一览大模型免费版本免费限制控制台(api_key等)API文档讯飞星火大模型spark-litetokens:总量无限;QPS:2;(每秒发送的请求数)有效期:不限访问链接访问链接百度千帆大模型平台ERNIE-Speed-8KRPM=300,TPM=300000(RPM是每分钟请求数(RequestsPerMinute),TPM是指每分......
  • 第二十天的学习(2024.8.8)Vue拓展
    昨天的笔记中,我们进行的项目已经可以在网页上显示查询到数据库中的数据,今天的笔记中将会完成在网页上进行增删改查的操作 1.删除表中数据现在网页上只能呈现出数据库中的数据,我们首先添加一个删除按钮,使其可以对数据库数据进行删除操作<template#default="scope"><e......
  • GMOJ 8101. 【2024年SD省队集训Day8】 正交向量
    效率时间复杂度:\(O(Tn\times3^9\times9)\)。没有任何卡常,能在\(1.08\)s内过hack.txt,而CHJ的代码在同样情况下跑了\(39\)s,LZY要用\(34\)s,PWX要用\(75\)s。但是在GMOJ上要用\(770\)ms,是目前比较劣的解。思路以下关于数字的第几位都是从\(0\)开始,从最低位到最......
  • 2024北京集训trick合集
    atcoderARC092F给定一张\(n\)个点\(m\)条边的有向图,判断每一条边反向后是否改变图中强连通分量的数量。数据范围:\(n\le1000\\\\m\le200000\)先跑一遍tarjan,然后问题转化为判断每个直接相连的两点在不经过其连边的情况下是否互通。对每个点dfs维护前缀和后缀能否回......
  • 2024睿抗机器人开发者大赛(RAICOM) CAIP编程技能赛 国一
    最后91分,国一。前几题都AK了,最后一题先是输出0,得了个1分。花了一个小时都没解决这题,难受ing,其实到最后差不多要改对了(降落那一部分没时间改),但是没时间了,hhhh。拿到国一,简直圆梦啦!!!本科拿的国三,差0.02秒就是国二,从此内心蒙上阴影。哭死ing研一终于拿了个编程比赛的国一,也算......
  • 2024年深圳市工业设计发展扶持计划申报时间
    为了进一步提升深圳市工业设计水平,加快工业设计与制造业的深度融合,2024年深圳市工业设计发展扶持计划现已全面启动。该计划旨在通过资金支持、政策优惠等多种方式,鼓励和支持工业设计企业及个人进行技术创新和产品开发,以增强深圳工业设计在全球市场的竞争力。对于符合条件的企业......
  • 2024年苏州市跨国公司地区总部和功能性机构申报临近截止时间
    苏州市跨国公司地区总部和功能性机构申报的截止时间已经迫在眉睫——8月12日。对于尚未提交申报材料的企业,现在是时候加快步伐,把握这最后的申报机会了。项目介绍苏州市一直致力于吸引和培育跨国公司地区总部及功能性机构,以推动外资总部经济的发展。截至目前,苏州已成功吸引了......