首页 > 其他分享 >寒假集训Day1

寒假集训Day1

时间:2024-01-16 09:01:42浏览次数:27  
标签:int res 质数 Day1 寒假 哈希 字符串 isprime 集训

寒假集训Day1 主要了解到了两个比较有意义的东西,记录如下

质数筛法

埃氏筛

从二开始,二是一个质数,那么二的倍数就是合数,三同理,利用这样的思想可以把所有质数的倍数做上标记

欧拉筛

埃氏筛有一个问题,就是同一个合数可能被反复筛选,比如6既是2的倍数又是3的倍数,这样它就会被筛选两遍。现在利用欧拉筛进行一个简化操作
对于我们找到的一个数,我们只需要标记所有已经找到的质数和该数的乘积即可,这样的筛选一直到这个数可以被其中一个已找到的质数整除为止,这样进行的欧拉筛复杂度应该是O(n)
代码如下:

bool isprime[1000009]; 
int prime[1000009]; 
int cnt; 
void euler()
{
    memset(isprime, true, sizeof(isprime)); 
    isprime[1] = false; 
    for(int i = 2; i <= n; ++i) 
    {
        if(isprime[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        {
            isprime[i * prime[j]] = false;
            if(i % prime[j] == 0) break;
        }
    }
}

哈希

目前只学了最基础的哈希,哈希可以看作一个对字符串加密的过程,我们希望用一个数值代表出整个字符串,让不同字符串的数值尽量不同。
因此我们需要一种转换方法,我们按照如下方法构造一个哈希函数:
我们把字符串看作一个h进制的数,每一个字符就相当于这个数的一位上的数,我们用进制转换的方法对字符串进行一个类似的操作,获得一个字符串的哈希值

const int B = 233;
const int M = 1e9 + 7;
string s;
int n;
int a[10000001] = { };
int ans = 0;
int main () {
	scanf("%d" ,&n);
	for(int i = 1;i <= n; i++) {
		cin >> s;
		int len = s.size();
		int res = 0;
		for(int j = 0;j < len; j++) {
			res = (res * B + (s[j] - '0')) % M; //这里就比较像把B进制的数转化成10进制
		}
		a[i] = res;
	}

标签:int,res,质数,Day1,寒假,哈希,字符串,isprime,集训
From: https://www.cnblogs.com/Crazyman-W/p/17966774

相关文章

  • 南外集训 2024.1.15 T3
    纯粹技术性的题目。给定一个字符串的后缀数组以及对应的height数组的一部分(即一些height数组的位置是未知的,用\(-1\)表示),要求还原出一种可能的字符串。保证存在一种由\(26\)个小写英文字母构成的解。\(1\len\le10^6\)首先考虑没有\(-1\)的情况。注意到此时我们给......
  • STM32学习Day1
    一.所用型号二.STM32上所拥有的外设三.各个引脚的定义(查表)颜色引脚类型蓝色最小相关系统的引脚绿色I/O口和功能口的引脚红色电源相关的引脚类型:①S表示电源②I表示输入③O表示输出I/O口电平:I/O口能容忍的电压FT表示容忍5V,无FT则为3.3V主......
  • 寒假生活指导07
     今天学习了爬虫#导入所需库importurllib.requestfromlxmlimportetree#设置目标URL和请求头信息,模拟Chrome浏览器访问url='https://www.baidu.com/'headers={'User-Agent':'Mozilla/5.0(WindowsNT10.0;Win64;x64)AppleWebKit/537.36(KHTML,like......
  • 1.14寒假每日总结5
    小型物联网应用系统设计图(模拟器上截图)   (2)简述实现过程中的相关步骤及配置各设备配置如下:接入交换机:划分vlan,将终端连接接口划到相应vlan中,开启生成树,开启dhcpsnooping。核心交换机:划分vlan,将设备连接接口修改为trunk接口模式。无线路由器:接口配置ip地址、掩码和......
  • 南外集训 2024.1.12 T3/AGC022F Checkers 加强版
    第一步转化比较套路,DP设计需要很强的洞察力,最后的优化也很考验基本功。有\(n\)个\(n\)维空间中的点,第\(i\)个点\(x_i\)满足\(x_{i,i}=1,x_{i,j}=0(\foralli\neqj)\)。接下来进行\(n-1\)次操作,每次任选两个点,将第一个点关于第二个点对称,然后删掉第二个点。......
  • 寒假生活指导06
    实验报告题目:Spar机器学习库MLlib编程实践姓名 日期2024.1.14实验环境:操作系统:Ubuntu16.04JDK版本:1.7或以上版本Spark版本:2.1.0实验内容与完成情况:1.数据导入从文件中导入数据,并转化为DataFrame。代码:frompyspark.ml.featureimportPCA......
  • 开始学习Java - Day1
    学习Java目标掌握一门编程语言可以看懂代码,具备编程能力。WhyJava(vspython)相比较Python,更原生态,更灵活。(Python只是上手简单,仅此而已)Java封装好了,调用是一样的学完Java,再学习其他语言,会更快一些。如PHP,Python具体解决问题,底层更多的是看算法学习方法写代码......
  • 每日一练 | 华为认证真题练习Day164
    1、当两台BGP邻居协商的HOLDTime参数为0时,则不发送Keeplive报文。A.正确B.错误2、ospf路由协议中,bandwidth-reference命令的单位是mbps。A.正确B.错误3、在OSPF广播或者NBMA网络类型中,ROUTERPRIORITY大的设备不一定会成为DR。A.正确B.错误4、在广播或nbma网络上,并非所有的......
  • day1
    普通树的基本公式:结点数=总度数+1(天线)二叉树的基本公式:n0=n2+1(叶子=度为2的结点+1),,,,,这里有一道利用奇偶数解决的例题关于树的高度的问题自己推理就好了,不难的,不用记公式。。。。。。。。。。。。。。。。。。。顺序队列,一般front指首元素,rear指尾元素的后一个,通过模运算完成......
  • 寒假生活
    什么是Spark?   Spark是大数据的调度,监控和分配引擎。它是一个快速通用的集群计算平台.Spark扩展了流行的MapReduce模型.Spark提供的主要功能之一就是能够在内存中运行计算,但对于在磁盘上运行的复杂应用程序,系统也比MapReduce更有效2、Spark部署模式2.1、独立模式 在......