2058 笨拙的手指
二进制所有的可能保存进哈希表，三进制找出所有的可能判断哈希表中是否有数字。
注意一种情况就是修改完之后出现前导零。直接continue;
学到了，某些条件的限制不一定要在循环条件上，可以直接在循环体内。
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
//2058 笨拙的手指
unordered_set<int>hashh;
//某进制转化为十进制
int base(string s,int n )
{
int res=0;
for(int i=0;i<s.size();i++)
{
res=res*n+(s[i]-'0');
}
return res;
}
int main()
{
string s,u;
cin>>s;
cin>>u;
for(int i=0;i<s.size();i++)
{
string t=s;
t[i]^=1;
//把字符串某一位修改了之后
if(t.size()>1&&t[0]=='0')continue;
hashh.insert(base(t,2));
//cout<<base(t,2)<<endl;
}
for(int i=0;i<u.size();i++)
{
for(int j=0;j<3;j++)
{
string t=u;
if(t[i]==(j+'0'))continue;
t[i]=(j+'0');
if(t.size()>1&&t[0]=='0')continue;
//cout<<"3进制"<<base(t,3)<<endl;
if(hashh.count(base(t,3)))
cout<<base(t,3)<<endl;
}
}
}
//840. 模拟散列表
string类型的数据即使有一个字符也要 s=="n";这样比较。
//841字符串哈希
哈希不一定是把原来的东西放进哈希表，可以将其转化为数字，后序计算某个值的时候可以直接通过子串的位置得到。
在求某个区间的字符串的值的时候，注意边界。注意理解h数组存的值是以i为个位的字符串的哈希值。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
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-a+1];
}
int main()
{
int n,m;
cin>>n>>m;
scanf("%s",s+1);
h[0]=0;
p[0]=1;
for(int i=1;i<=n;i++)
{
p[i]=p[i-1]*131;
h[i]=h[i-1]*131+s[i];
}
int l1,r1,l2,r2;
for(int i=0;i<m;i++)
{
cin>>l1>>r1>>l2>>r2;
if(getnum(l1,r1)==getnum(l2,r2))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
}
830.单调栈
给出一个数组，要求求出每个数左边第一个小于其的数是谁。
指定是向前去找：所以想到有一种：如果一个数A左边存在一个大于他的数B。B这个数就没什么用了。也就是如果前面有一大串数，突然出现一个小数，前面的这些数都没用了。
所以每次给出一个数向前找的时候，就剪掉这些数。避免不必要的遍历。
这个过程是由一个idx实现的。每次循环都实时更新idx；
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef unsigned long long int ull;
//830 单调栈;
int a[N];
int main()
{
int n;
int t=0;//一开始的时候是没有数据的
cin>>n;
while(n--)
{
int num;
cin>>num;
while(t>0&&a[t]>=num)t--;//向前找合适的
if(t==0)
{
cout<<-1<<" ";
}
else
{
cout<<a[t]<<" ";
}
a[++t]=num;
}
}
//154 滑动窗口
和找离某个数左边最近的小于它的值的时候。每次新到一个数进来都会把左边所有大于它的数删掉。这里维持的是一个有序序列。
滑动窗口也是这样，维持一个有序的数组。每次只要新吞入一个数，它产生的作用就是把它前面所有大于它的数都淘汰掉，另外还有一个操作就是每次向右移动的时候。左边要删掉（但是为什么要判断一下队头呢，因为有可能从滑动窗口出来的点已经被删除了）
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
deque<int>q;
int n,k;
int a[N];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
while(!q.empty()&&q.back()>a[i])
q.pop_back();
if(i-k>=1&&q.front()==a[i-k])q.pop_front();
q.push_back(a[i]);
if(i>=k)cout<<q.front()<<" ";
}
cout<<endl;
deque<int>p;
for(int i=1;i<=n;i++)
{
while(!p.empty()&&p.back()<a[i])
p.pop_back();
p.push_back(a[i]);
if(i-k>=1&&p.front()==a[i-k])
{
p.pop_front();
//cout<<"*******************"<<endl;
//cout<<p.front()<<"此时有几个"<<p.size()<<endl;
}
if(i>=k)cout<<p.front()<<" ";
}
}