祥云平台做网站好不好,企业网站优化推广方法,特色个人网站,注册网站给谁交钱2058 笨拙的手指
二进制所有的可能保存进哈希表#xff0c;三进制找出所有的可能判断哈希表中是否有数字。
注意一种情况就是修改完之后出现前导零。直接continue;
学到了#xff0c;某些条件的限制不一定要在循环条件上#xff0c;可以直接在循环体内。
#includebi…2058 笨拙的手指
二进制所有的可能保存进哈希表三进制找出所有的可能判断哈希表中是否有数字。
注意一种情况就是修改完之后出现前导零。直接continue;
学到了某些条件的限制不一定要在循环条件上可以直接在循环体内。
#includebits/stdc.h
using namespace std;
const int N50010;
//2058 笨拙的手指unordered_setinthashh;
//某进制转化为十进制
int base(string s,int n )
{int res0;for(int i0;is.size();i){resres*n(s[i]-0);}return res;
}
int main()
{string s,u;cins;cinu;for(int i0;is.size();i){string ts;t[i]^1;//把字符串某一位修改了之后if(t.size()1t[0]0)continue;hashh.insert(base(t,2));//coutbase(t,2)endl;}for(int i0;iu.size();i){for(int j0;j3;j){string tu;if(t[i](j0))continue;t[i](j0);if(t.size()1t[0]0)continue;//cout3进制base(t,3)endl;if(hashh.count(base(t,3)))coutbase(t,3)endl;}}
}//840. 模拟散列表
string类型的数据即使有一个字符也要 sn;这样比较。
//841字符串哈希
哈希不一定是把原来的东西放进哈希表可以将其转化为数字后序计算某个值的时候可以直接通过子串的位置得到。
在求某个区间的字符串的值的时候注意边界。注意理解h数组存的值是以i为个位的字符串的哈希值。
#includebits/stdc.h
using namespace std;
const int N100010;
typedef unsigned long long int ull;
//841 字符串哈希
char s[N];
ull h[N],p[N];
int getnum(int a,int b)
{return h[b]-h[a-1]*p[b-a1];
}int main()
{int n,m;cinnm;scanf(%s,s1);h[0]0;p[0]1;for(int i1;in;i){p[i]p[i-1]*131;h[i]h[i-1]*131s[i];}int l1,r1,l2,r2;for(int i0;im;i){cinl1r1l2r2;if(getnum(l1,r1)getnum(l2,r2)){coutYesendl;}else{coutNoendl;}}}830.单调栈
给出一个数组要求求出每个数左边第一个小于其的数是谁。
指定是向前去找所以想到有一种如果一个数A左边存在一个大于他的数B。B这个数就没什么用了。也就是如果前面有一大串数突然出现一个小数前面的这些数都没用了。
所以每次给出一个数向前找的时候就剪掉这些数。避免不必要的遍历。
这个过程是由一个idx实现的。每次循环都实时更新idx
#includebits/stdc.h
using namespace std;
const int N100010;
typedef unsigned long long int ull;
//830 单调栈;
int a[N];
int main()
{int n;int t0;//一开始的时候是没有数据的cinn;while(n--){int num;cinnum;while(t0a[t]num)t--;//向前找合适的if(t0){cout-1 ;}else{couta[t] ;}a[t]num;}}//154 滑动窗口
和找离某个数左边最近的小于它的值的时候。每次新到一个数进来都会把左边所有大于它的数删掉。这里维持的是一个有序序列。
滑动窗口也是这样维持一个有序的数组。每次只要新吞入一个数它产生的作用就是把它前面所有大于它的数都淘汰掉另外还有一个操作就是每次向右移动的时候。左边要删掉但是为什么要判断一下队头呢因为有可能从滑动窗口出来的点已经被删除了
#includebits/stdc.h
using namespace std;
const int N1000010;
dequeintq;
int n,k;
int a[N];
int main()
{cinnk;for(int i1;in;i){cina[i];}for(int i1;in;i){while(!q.empty()q.back()a[i])q.pop_back();if(i-k1q.front()a[i-k])q.pop_front();q.push_back(a[i]);if(ik)coutq.front() ;}coutendl;dequeintp;for(int i1;in;i){while(!p.empty()p.back()a[i])p.pop_back();p.push_back(a[i]);if(i-k1p.front()a[i-k]){p.pop_front();//cout*******************endl;//coutp.front()此时有几个p.size()endl;}if(ik)coutp.front() ;}
}
