1145 Hashing - Average Search Time
目录
思路
样例解释
AC代码
思路
要做出这道题必须直到除留余数法和平方探测法的原理。
除此之外有两个注意点：
1. 在查找时，如果当前位置上不是要找的数会继续找下去(如果k没超过表长的话)，但是如果当前位置上是0，说明表里就是没有这个数，不必再往下找。
2. 在存储时，k的取值范围是[0,Tsize)而在查找时是[0,Tsize]，我认为后者也应该是左闭右开，但是要做出这道题就得按照它的规则。
样例解释
表长4不是一个素数，取大于4的第一个素数5作为表长。
有table[5] = {0,0,0,0,0}
对于10：10%5 == 0，table[0]是空的，可以插入，更新table[5] = {10,0,0,0,0}
对于6：6%5 == 1，table[1]是空的，可以插入，更新table[5] = {10,6,0,0,0}
对于4：4%5 == 4，table[4]是空的，可以插入，更新table[5] = {10,6,0,0,4}
对于15：15%5 == 0，table[0]非空，(15+1^2)%5 == 1，table[1]非空，(15+2^2)%5 == 4，table[4]非空，(15+3^2)%5 == 4，(15+4^2)%5 == 1，4已经是表长减一，所以插不进去了。
对于11：11%5 == 1，table[1]非空，(11+1^2)%5 == 2，table[2]是空的。更新table[5] = {10,6,11,0,4}。
最终的存储情况是 {10,6,11,0,4}。
下面开始查询
对于11：11%5 == 1 ，table[1]存储的是6，(11+1^2)%5 == 2，table[2]存储的是11，2次找到。
对于4：4%5 == 4，table[4]存储的是4，1次找到。
对于15：15%5 == 0，没找到，(15+1^2)%5 == 1，没找到，(15+2^2)%5 == 4，没找到，(15+3^2)%5 == 4，没找到，(15+4^2)%5 == 1，没找到，5次。
对于2：2%5 == 2，没找到，(2+1^2)%5 == 3，没找到，注意3号位存储的为空，不必再往下找了。2次。
共计11次。
AC代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>using namespace std;const int maxn = 1010;bool isPrime(int x){if(x==1)return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0)return false;}return true;
}int main(){ int Tsize,inN,outN;cin>>Tsize>>inN>>outN;if(isPrime(Tsize)==false){while(isPrime(Tsize)==false){Tsize ++;}}int Table[Tsize] = {0}; while(inN--){int x;cin>>x;int k;for(k=0;k<Tsize;k++){int idx = (x+k*k)%Tsize;if(Table[idx]==0){Table[idx] = x; break;}}if(k==Tsize)printf("%d cannot be inserted.\n",x);}int tt = 0;//total timefor(int i=0;i<outN;i++){int x;cin>>x;for(int k=0;k<=Tsize;k++){tt ++;int idx = (x+k*k)%Tsize;if(Table[idx]==x||Table[idx]==0)break; }}printf("%.1f",tt*1.0/outN);return 0;
}相关文章：
C#和Java的闭包－Jon谈《The Beauty of Closures》
第一段略。。。 大多数讲闭包的文章都是说函数式语言，因为它们往往对闭包的支持最完善。当你在使用函数式语言时，很可能已经清楚了解了什么是闭包，所以我想写一篇在经典OO语言出现的闭包有什么用处应该也是很合适的事情。这篇文章我准备讲一下…
谷歌浏览器输入框背景颜色变黄的解决方案
2019独角兽企业重金招聘Python工程师标准>>> input:-webkit-autofill, input:-webkit-autofill:hover, input:-webkit-autofill:focus { box-shadow:0 0 0 60px #eee inset; -webkit-text-fill-color: #878787; } 转载于:https://my.oschina.net/kitty0107/blog/296…
男人最不该做的7件事
1.没有目标 2.浪费时间 3.不独立 4.被动地活着 5.不规划自己的人生 6.不学习吸收信息 7.不接受爱情转载于:https://www.cnblogs.com/jiu0821/p/4315660.html
1085 Perfect Sequence
明确题目的核心是要找到 找到第一个满足 M > m*p 的M的下标。然后用该下标减去起点的下标即为序列元素个数。 二分区间应当是M所有可能的取值范围。起点是i1，终点是N而不是N-1，虽然A[N]上无元素。注意啊，原题要找的M是小于等于m*p的&…
[笔记]Go语言在Linux环境下输出彩色字符
Go语言要打印彩色字符与Linux终端输出彩色字符类似，以黑色背景高亮绿色字体为例： fmt.Printf("\n %c[1;40;32m%s%c[0m\n\n", 0x1B, "testPrintColor", 0x1B) 其中0x1B是标记，[开始定义颜色，1代表高亮…
javascript中this那些事
定义 this是函数执行的上下文。 调用方式 1. 作为函数调用，指向window（严格模式报undefined的错）。 var namehello; function a() { console.log(this.name) } a(); //hellovar c{ name:haha, d: function(){ a(); } } c.d(…
java序列化的作用-这个挺有用的，不妨学学
http://bbs.tech.ccidnet.com/read.php?tid249048 最近在阅读Core J2EE Patterns 的时候发现例子里用于在各个层次里进行传输的TO（Data Transfer Object）都实现了java.io.Serializable接口，看到这些偶突然感到茅塞顿开～困扰了很久…
二分法典例：木棒切割问题
Input : 输入木棒根数n，要得到的等长木棒数量K，以及n根木棒的长度。 Output : 等长木棒的最大长度。 用二分法求解这道题，首先要找到以得到的等长木棒数量为因变量、等长木棒长度为自变量函数。 int getK(int l){//随着l增大，返…
对Android 开发者有益的 40 条优化建议（转）
下面是开始Android编程的好方法： 找一些与你想做事情类似的代码 调整它，尝试让它做你像做的事情 经历问题 使用StackOverflow解决问题对每个你像添加的特征重复上述过程。这种方法能够激励你，因为你在保持不断迭代，不经意中你学到…
英语语法总结--连词
连词 连词是一种虚词， 它不能独立担任句子成分而只起连接词与词，短语与短语以及句与句的作用。连词主要可分为两类：并列连词和从属连词。并列连词用来连接平行的词、词组和分 句。如：and, but, or, nor, so, therefore, yet, howe…
开放平台鉴权以及OAuth2.0介绍
OAuth 2.0 协议 OAuth是一个开发标准，允许用户授权第三方网站或应用访问他们存储在另外的服务提供者上的信息，而不需要将用户名和密码提供给第三方网站或分享他们数据的内容。OAuth 2.0不兼容1.0。协议的参与者 RO (resource owner): 资源所有者…
1044 Shopping in Mars
这题我写了两个二分函数。 BS借用的模板是找到第一个大于等于总价的商品下标，然后返回的是钻石价值和减去商品总价，通过遍历来得到最小的差值，注意遍历的最后一个数字的时候可能会返回负值，所以只有当返回值大于等于0才可以用来竞…
nodeJS之eventproxy源码解读
1.源码缩影 !(function (name, definition) { var hasDefine typeof define function, //检查上下文环境是否为AMD或CMD hasExports typeof module ! undefined && module.exports; //检查上下文环境是否为Node if (hasDefine) { define(definition); //AMD环境或CM…
解决phpmyadmin3.4空密码登录被禁止登陆的方法
很多时候我们在本机测试时会将root用户密码设置为空。因为我把php升级到了5.3.1，以前的phpmyadmin版本不能用了，就升级到phpMyAdmin 3.2.4版的时候，会遇到无法以空密码登录root用户的情况。怎么解决呢? 请参照如下步骤： 1、打开程…
CentOS安装新版RabbitMQ解决Erlang 19.3版本依赖
2019独角兽企业重金招聘Python工程师标准>>> 通过yum等软件仓库都可以直接安装RabbitMQ，但版本一般都较为保守。 RabbitMQ官网提供了新版的rpm包（http://www.rabbitmq.com/download.html），但是安装的时候会提示需要erl…
1048 Find Coins(二分法解法)
非常基础的二分法-寻找序列中是否存在某一条件的元素 的应用 AC代码 #include<cstdio> #include<iostream> #include<set> #include<vector> #include<map> #include<algorithm>using namespace std;const int SUP 100000000; const in…
关于chrome等浏览器不支持showModalDialog的解决方案
目前，新版本的chrome和opera、Firefox等浏览器已经不支持showModalDialog方法。 如果是没有接收返回值的，可以直接将window.showModalDialog改为window.open。 需要接收返回值的情况： 父页面设置： var uIdName; function chooseus…
Flex Javascript 交互实现代码
关键字：ExternalInterface所用类库：SWFObject/*** Flex调用Javascript函数* params functionName:String Javascript函数名称* params ...params Javascript函数参数* return 返回Javascript函数的return内容**/ExternalInterface.call(functionName:Str…
C#反射使用时注意BindingFlags的用法（转载）
最近刚刚开始用反射做项目，遇到一个小的知识点，记录一下。 c#反射查找方法时，默认只能查到public方法。如果想要查找private方法，需要设定BindingFlags. 即： BindingFlags.Public|BindingFlags.Instance 默认…
1126 Eulerian Path
主要考英语或者数学基础。 一幅连通图的奇点个数为0或2时才能够被一笔画。 连通图的判断用DFS来计数。 连通图0个奇点：Eulerian 连通图2个奇点：semi-Eulerian 非连通图/连通图其他数量的奇点：non-Eulerian AC代码 #include<cstdio&…
各种小的 dp （精）
Q~ 抛一枚硬币 n 次，每次可能是正面或者反面向上，求没有连续超过 k 次硬币向上的方案数 A ： dp[ i ] 表示到 i 位置的方案数， 1 . 当 i < k 时， dp[i] dp[i-1]*2 2 . 当 i k 时， dp[i] dp[i-1]*2 - 1…
写给还在大学的兄弟姐妹
看到软件专业毕业生之一个月攻略 这篇文章之后，忽然想起了自己两个多月前找工作时的写的一篇文章，便拿出来与大家分享。这仅是个人的一些看法，不正确之处还请各位指出，有砖尽管拍。 基础很重要 许多企业招聘，要求大学…
grunt学习
1、http://javascript.ruanyifeng.com/tool/grunt.html Grunt：任务自动管理工具 2、转载于:https://www.cnblogs.com/king-bj/p/4322794.html
IP地址和MAC地址
MAC地址又称硬件地址，是MAC帧的头部，在数据链路层只能看见MAC地址。 IP地址是逻辑地址，是IP数据报的头部，路由器根据IP地址进行路由选择。 IP地址为4个字节32位，编制经历了3个历史阶段。 MAC地址为6个字节48位。
ie9下console不兼容的问题
最近在调整项目在ie9下的展示问题，发现在ie9下，js文件不执行，打开控制台才执行，原因是ie9不支持console，以下给出两种解决方案：1. 在webpack.prod.conf.js 中添加并修改js插件配置项（我用的是we…
[转载] linux、Solaris下xdmcp远程桌面服务
原文链接 http://youlvconglin.blog.163.com/blog/static/52320420106243857254/ 使用图形界面远程登录linux和Solaris，首先要在服务端开启xdmcp服务，windows下使用xmanager连接 Ubuntu下则使用下默认也安装了该客户端，一次打开[应用程序]-[…
3.2.4 控制图层显示的范围
为了是地图更加简洁 和 减小地图负载 ，达到分级显示某些图层的效果，应该为每一个图层设置 合理的 可见比例尺范围。1 begin2 3 aeMapMain.Layer[2].MaximumScale :500000;//最大可见比例尺 分母4 aeMapMain.Layer[2].MinimumScale :1000000;//最小可见比…
1103 Integer Factorization 需再做
本题是典型的DFS剪枝 我对DFS有了更深的认识：整个过程就是一片森林(根节点不唯一)的生长，到了界限就得到结果并返回或者得不到结果也返回，DFS的参数存放的是所有需要积累的变量。 提示： 1. 最外层的while或者for可以看成是一个…
POJ1001--Exponentiation（幂计算）翻译
Exponentiation幂计算Time Limit: 500MSMemory Limit: 10000KTotal Submissions: 141868Accepted: 34673 Description 描述 Problems involving the computation of exact values of very large magnitude and precision are common. 高精度、大数值的计算问题是很常见的&…
datatable无法设置横向滚动条(设置无效)
datatable设置横向滚动条无效 js如下： 页面如下： 设置 scrollx 属性为true时，还需在 table 添加 style"white-space: nowrap; "最终效果： 转载于:https://www.cnblogs.com/renzp/p/10069594.html