AcWing 830. 单调栈
reflection
单调栈的本质,直接删除多余的,x右边的永远都不会被x左边且<x的更新
多余的东西不用写, 比如pair记录下标, save into ans[i]
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
stack<int > st;st.push(-1);
for(int i=1;i<=n;i++){
int x;cin>>x;
while(!st.empty() and st.top()>=x)st.pop();
cout<<st.top()<<' ';
st.push(x);
}
}
AcWing 154. 滑动窗口
reflection
题目简单时避免结构体麻烦。存下标,用a[i]来调用,
wr意识到以后没全改
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
deque<int> Q;
int n,k;cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
if(not Q.empty() and i-k+1>Q.front())Q.pop_front();
while(not Q.empty() and a[Q.back()]>a[i])Q.pop_back();
Q.push_back(i);
if(i>=k-1)cout<<a[Q.front()]<<' ';
}
cout<<endl;
while(not Q.empty())Q.pop_back();
for(int i=0;i<n;i++){
if(not Q.empty() and i-k+1>Q.front())Q.pop_front();
while(not Q.empty() and a[Q.back()]<a[i])Q.pop_back();
Q.push_back(i);
if(i>=k-1)cout<<a[Q.front()]<<' ';
}
}
AcWing 831. KMP字符串
reflection
kmp 为什么难理解
算法流程和ne的概念很抽象,
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
char s[maxn],p[maxn];
int ne[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>m>>p+1>>n>>s+1;
for(int i=2,j=0;i<=m;i++){
while(j and p[i]!=p[j+1])j=ne[j];
if(p[i]==p[j+1])j++;
ne[i]=j;
}
for(int i=1,j=0;i<=n;i++){
while(j and s[i]!=p[j+1])j=ne[j];
if(s[i]==p[j+1])j++;
if(j==m){
cout<<i-j<<' ';
}
}
}
AcWing 835. Trie字符串统计
1st 秒了
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)2e4+5;
int trie[maxn][256],idx=1,leaf[maxn];
void insert(string s){
int cur=0;
for(auto c:s){
if(trie[cur][c])cur=trie[cur][c];
else cur=trie[cur][c]=idx++;
}
leaf[cur]++;
return;
}
int find(string s){
int cur=0;
for(auto c:s){
cur=trie[cur][c];
if(cur==0)return 0;
}
return leaf[cur];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int q;cin>>q;while(q--){
char c;string s;cin>>c>>s;
if(c=='I'){
insert(s);
}else cout<<find(s)<<endl;
}
}
AcWing 143. 最大异或对
wr:
i 重用
爆ll ??不懂
reflection:
枚举一个,搜另一个。
#include<iostream>
using namespace std;
#define int long long
const int maxn=1e7+5;
int son[maxn][2],leaf[maxn],a[maxn],idx=1;
void insert(int x){
int cur=0;
for(int i=30;i>=0;i--){
int bit=(a[x]>>i)&1ll;
if(son[cur][bit]==0)son[cur][bit]=idx++;
cur=son[cur][bit];
}
leaf[cur]=x;
//cout<<cur<<' '<<idx<<' '<<x<<endl;
}
signed main(){
int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];insert(i);}
int ans=0;
for(int i=1;i<=n;i++){
int cur=0;
for(int j=30;j>=0;j--){
int bit=(a[i]>>j)&1ll;
if(son[cur][!bit])cur=son[cur][!bit];
else cur=son[cur][bit];
//cout<<cur<<' '<<bit<<' ';
}
ans=max(ans,a[i]^a[leaf[cur]]);
//cout<<endl;
}
cout<<ans<<endl;
}
AcWing 836. 合并集合
手写最多(短)的模板
秒了,更短了
以前不按size合并会爆栈,到底怎么办到的?大的连到小的上也没啥问题?
#include<iostream>
using namespace std;
int fa[100005];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
while(m--){
char c;cin>>c;
int x,y;cin>>x>>y;
if(c=='Q')cout<<(find(x)==find(y)?"Yes":"No")<<endl;
else merge(x,y);
}
}
AcWing 837. 连通块中点的数量
wr
两个点在同一个集合内的情况。
没有推严谨,所以难以debug
#include<iostream>
using namespace std;
const int maxn=100005;
int fa[100005],sz[maxn];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
if(find(y)==find(x))return;
sz[find(y)]+=sz[find(x)];
fa[find(x)]=find(y);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
while(m--){
string c;cin>>c;
if(c=="Q2"){int x;cin>>x;cout<<sz[find(x)]<<endl;continue;}
int x,y;cin>>x>>y;
if(c=="Q1")cout<<(find(x)==find(y)?"Yes":"No")<<endl;
else merge(x,y);
}
}
AcWing 240. 食物链???
wr
if else 不知道哪错,以后要加{}
合并时更新d[px]
D=x%3-y%3, (x-y)%3 判(D-1)%3时不同,?按照结果来说,会有等于1 or -2 的错误组合
1 2:-1 -1
1 3:1 -2
2 1:1 1
2 3:-1 -1
3 1:-1 2
3 2:-2 1
#include<iostream>
using namespace std;
const int maxn=100005;
int fa[maxn],d[maxn];
int find(int x){
if( x==fa[x])return x;
int tmp=fa[x];
fa[x]=find(fa[x]);
d[x]+=d[tmp];
return fa[x];
}
void merge(int x,int y,int D){
int px=find(x),py=find(y);
fa[px]=py;
d[px]=d[y]-d[x]+D;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i,d[i]=0;
int ans=0;
while(m--){
int op,x,y;cin>>op>>x>>y;
if(x>n or y> n){ans++;continue;}
if(find(x)==find(y)){
int D=(d[x]-d[y])%3;
//D%=3,D+=3,D%=3;
if(op==1&&D!=0)ans++;
if(op==2&&(D-1)%3!=0)ans++;
}else{
if(op==1){
merge(x,y,0);
}else merge(x,y,1);
}
}
cout<<ans<<endl;
}