头像

well188




在线 


活动打卡代码 AcWing 829. 模拟队列

well188
1小时前

第2遍

本着中间思考,调整特例的策略
hh=0,tt=-1
push就++tt,
pop就++hh
hh>tt时为空,否则不空
查询就是qu[hh]

#include <iostream>
#include <string>
using namespace std;
const int N=1e5+10;
int qu[N];
int hh,tt=-1;
int main(){
    int m;
    cin>>m;
    while(m--){
        int x;
        string op;
        cin>>op;
        if(op=="push"){
            cin>>x;
            qu[++tt]=x;
        }
        else if(op=="pop") hh++;
        else if(op=="empty"){
            if(hh<=tt) cout<<"NO\n";
            else cout<<"YES\n";
        }
        else if(op=="query") cout<<qu[hh]<<endl;
    }
    return 0;
}

第1遍

#include <iostream>
#include <string>
using namespace std;
const int N=1e5+10;
int qu[N];
int front,tail;
int main(){
    int m;
    cin>>m;
    while(m--){
        string op;
        int x;
        cin>>op;
        if(op=="push"){
            cin>>x;
            qu[++tail]=x;
        }
        else if(op=="pop") front++;
        else if(op=="empty") cout<<(tail-front?"NO":"YES")<<endl;
        else if(op=="query") cout<<qu[front+1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 828. 模拟栈

well188
1小时前

第二遍

注意empty,问的是空吗?空为yes,不空为no

#include <iostream>
#include <string>
using namespace std;
const int N=1e5+10;
int stk[N],tt;
int main(){
    int m;
    cin>>m;
    while(m--){
        string op;
        int x;
        cin>>op;
        if(op=="push"){
            cin>>x;
            stk[++tt]=x;
        }
        else if(op=="pop") tt--;
        else if(op=="empty") cout<<(tt?"NO":"YES")<<endl;
        else if(op=="query") cout<<stk[tt]<<endl;
    }

    return 0;
}

第一遍

用数组装入数据,只在一头操作即可。

#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
int stack[N];
int tt;
void push(int x){
    stack[++tt]=x;
}
void pop(){
    tt--;
}
bool empty(){
    if(tt>0) return false;
    else return true;
}
int query(){
    return stack[tt];
}
int main(){
    int m;
    char op[10];
    scanf("%d",&m);
    while(m--){
        int x;
        scanf("%s",op);
        if(strcmp(op,"push")==0){
            scanf("%d",&x);
            push(x);
        }
        else if(strcmp(op,"pop")==0){
            pop();
        }
        else if(strcmp(op,"empty")==0){
            if(empty()) printf("YES\n");
            else printf("NO\n");
        }
        else if(strcmp(op,"query")==0){
            printf("%d\n",query());
        }
    }
    return 0;
}


活动打卡代码 AcWing 827. 双链表

well188
5小时前

第2遍

单链表中 (k - 1)是因为idx从0开始,双链表这里(k + 1)是不是因为idx从2开始的。

#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
    r[0]=1,l[1]=0,idx=2;
}
void add(int k,int x){
    e[idx]=x;
    l[idx]=k,r[idx]=r[k];
    l[r[k]]=idx,r[k]=idx++;
}
void remove(int k){
    l[r[k]]=l[k],r[l[k]]=r[k];
}
int main(){
    int m;
    init();
    scanf("%d",&m);
    while(m--){
        int k,x;
        char op[10];
        scanf("%s",op);
        if(strcmp(op,"L")==0){
            scanf("%d",&x);
            add(0,x);
        }
        else if(strcmp(op,"R")==0){
            scanf("%d",&x);
            add(l[1],x);
        }
        else if(strcmp(op,"D")==0){
            scanf("%d",&k);
            remove(k+1);
        }
        else if(strcmp(op,"IL")==0){
            scanf("%d%d",&k,&x);
            add(l[k+1],x);
        }
        else if(strcmp(op,"IR")==0){
            scanf("%d%d",&k,&x);
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]){
        printf("%d ",e[i]);
    }
    printf("\n");

    return 0;
}

第1遍

以0,1代表左,右端点,但不存储具体数据,idx从2开始,但遍历链表时,2不见得是第一个,第一个是r[0]

只需要添加一个add函数,一个remove函数,就可利用左右端点的特性表达这5种情况。

#include <iostream>
#include <string>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
    r[0]=1,l[1]=0,idx=2;
}
void add(int a,int x){
    e[idx]=x;
    r[idx]=r[a],l[idx]=a;
    l[r[a]]=idx,r[a]=idx++;
}
void remove(int a){
    l[r[a]]=l[a],r[l[a]]=r[a];
}
int main(){
    int m;
    cin>>m;
    init();
    while(m--){
        string op;
        int k,x;
        cin>>op;
        if(op=="L"){
            cin>>x;
            add(0,x);
        }
        else if(op=="R"){
            cin>>x;
            add(l[1],x);
        }
        else if(op=="D"){
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL"){
            cin>>k>>x;
            add(l[k+1],x);
        }
        else if(op=="IR"){
            cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]){
        cout<<e[i]<<' ';
    }
    cout<<endl;
    return 0;
}


活动打卡代码 AcWing 826. 单链表

well188
7小时前

第二遍

缩短了一些代码,功能函数remove的k和main的k意义不同,又忘了。

#include <iostream>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],head,idx;
void init(){
    head=-1,idx=0;
}
void add_head(int x){
    e[idx]=x,ne[idx]=head,head=idx++;
}
void remove(int k){
    ne[k]=ne[ne[k]];
}
void add_node(int k,int x){
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
int main(){
    int m;
    init();
    cin>>m;
    while(m--){
        int k,x;
        char op;
        cin>>op;
        if(op=='H'){
            cin>>x;
            add_head(x);
        }
        else if(op=='D'){
            cin>>k;
            if(!k) head=ne[head];
            else remove(k-1);
        }
        else{
            cin>>k>>x;
            add_node(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]){
        cout<<e[i]<<' ';
    }
    cout<<endl;
    return 0;
}

第一遍

用数组模拟链表,是因为链表的new操作生成新节点太慢,数组模拟的链表多用于竞赛中,图论的邻接表,不涉及大量删除操作。
无论添加还是删除都要对头结点特判
删除时,要对头结点特判
k从0开始数,所以第一个数时,k=0.那么题目中的第k个数,为实际代码的k-1.
功能函数写好尽量不动,在main函数中进行调整以适应外面的功能函数。

#include <iostream>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],head,idx;
void init(){
    head=-1;
    idx=0;
}
void add_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}
void remove(int k){
    ne[k]=ne[ne[k]];
}
void insert(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
int main(){
    int m;
    init();
    cin>>m;
    while(m--){
        int k,x;
        char op;
        cin>>op;
        if(op=='H'){
            cin>>x;
            add_head(x);
        }
        else if(op=='D'){
            cin>>k;
            if(!k) head=ne[head];
            else remove(k-1);
        }
        else{
            cin>>k>>x;
            insert(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]){
            cout<<e[i]<<' ';
    }
    cout<<endl;
    return 0;
}


活动打卡代码 AcWing 803. 区间合并

well188
23小时前

赞一个,第一章写完了

注意前置条件,每个动作,都会有一个暗含的前置条件。比如merge函数最后的
if(st!=-2e9) ans.push_back(make_pair(st,ed));
如果st==-2e9说明,ans为空啊,就不要放入了。

对pair类型排序,默认先以first为主,first相等则用second

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> v,ans;
int n;
void merge(){
    int st=-2e9,ed=-2e9;
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        if(ed<v[i].first){
            if(st!=-2e9) ans.push_back(make_pair(st,ed));
            st=v[i].first,ed=v[i].second;
        }
        else ed=max(ed,v[i].second);
    }
    if(st!=-2e9) ans.push_back(make_pair(st,ed));
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        v.push_back(make_pair(l,r));
    }
    merge();
    printf("%d\n",ans.size());
    return 0;
}


活动打卡代码 AcWing 802. 区间和

well188
1天前

第3遍

实现了find和unique函数
感悟:uni数组中包含所有位置,且每个位置都是唯一的一个。既不会拉下也不会多余!

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
PII a[N],b[N];
int uni[3*N],tj[3*N],s[3*N];
int n,m,k;
int find(int x){
    int l=1,r=k;
    while(l<r){
        int mid=l+r>>1;
        if(uni[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
int unique(int q[]){
    int j=0;
    for(int i=1;i<=k;i++){
        if(i==1 || q[i]!=q[i-1]){
            q[++j]=q[i];
        }
    }
    return j;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,c;
        scanf("%d%d",&x,&c);
        a[i]=make_pair(x,c);
        uni[++k]=x;
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        b[i]=make_pair(l,r);
        uni[++k]=l;
        uni[++k]=r;
    }
    sort(uni+1,uni+1+k);
    k=unique(uni);
    for(int i=1;i<=n;i++){
        int x=find(a[i].first);
        tj[x]+=a[i].second;
    }
    for(int i=1;i<=k;i++){
        s[i]=s[i-1]+tj[i];
    }
    for(int i=1;i<=m;i++){
        int l=find(b[i].first),r=find(b[i].second);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}

第2遍

区别:使用了unique函数

#include <cstdio> 
#include <utility> 
#include <algorithm> 
using namespace std; 
typedef pair<int,int> PII; 
const int N=1e5+10; 
PII a[N],b[2*N]; 
int uni[3*N],tj[3*N],s[3*N]; 
int n,m,k=0; 
int find(int x){ 
    return lower_bound(uni+1,uni+1+k,x)-uni; 
} 
int main(){ 
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++){ 
        int x,c; 
        scanf("%d%d",&x,&c); 
        a[i]=make_pair(x,c); 
        uni[++k]=x; 
    } 
    for(int i=1;i<=m;i++){ 
        int l,r; 
        scanf("%d%d",&l,&r); 
        b[i]=make_pair(l,r); 
        uni[++k]=l; 
        uni[++k]=r; 
    } 
    sort(uni+1,uni+1+k); 
    k=unique(uni+1,uni+1+k)-(uni+1); 
    for(int i=1;i<=n;i++){ 
        int x=find(a[i].first); 
        tj[x]+=a[i].second; 
    } 
    for(int i=1;i<=k;i++){ 
        s[i]=s[i-1]+tj[i]; 
    } 
    for(int i=1;i<=m;i++){ 
        int l=find(b[i].first),r=find(b[i].second); 
        printf("%d\n",s[r]-s[l-1]); 
    } 

    return 0; 
}

第1遍

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
PII a[N],b[N];//对应原始数据,插入位置,和查询的位置
int uni[3*N],t[3*N],s[3*N];//uni去重数组,t统计数组,s前缀和数组
int n,m,k=0;
int find(int x){
    return lower_bound(uni+1,uni+1+k,x)-uni;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=make_pair(x,y);
        uni[++k]=x;
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        b[i]=make_pair(l,r);
        uni[++k]=l;
        uni[++k]=r;
    }
    sort(uni+1,uni+1+k);
    int tmp=0;
    for(int i=1;i<=k;i++){
        if(i==1||uni[i]!=uni[i-1]){
            uni[++tmp]=uni[i];
        }
    }
    k=tmp;//k在find里用到
    for(int i=1;i<=n;i++){
        int x=find(a[i].first);
        t[x]+=a[i].second;
    }
    for(int i=1;i<=k;i++){
        s[i]=s[i-1]+t[i];
    }
    for(int i=1;i<=m;i++){
        int l=find(b[i].first),r=find(b[i].second);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}



well188
1天前
#include <cstdio>
using namespace std;
int lowbit(int x){
    return x&(-x);
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x,res=0;
        scanf("%d",&x);
        while(x) x-=lowbit(x),res++;
        printf("%d ",res);
    }

    return 0;
}



well188
1天前
#include <cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
    int n,m,x;
    scanf("%d%d%d",&n,&m,&x);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);

    for(int i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x) j--;
        if(j>=0&&a[i]+b[j]==x) {
            printf("%d %d\n",i,j);
            break;
        }
    }

    return 0;
}



well188
1天前

双指针可以把$O(n^2)$变成$O(n)$,靠的就是单调性。
单调性含义:随i的增加,j一直延一个方向变化,就是单调性。比如,随i的增加,j也一直增加,这叫单调递增,如随i的增加,j一直减小,这叫单调递减,总之随i的增加,j一会增,一会减就没有单调性了。

例题1:AcWing 799. 最长连续不重复子序列。
单调性:设[j,i]是目前的“最长不重复”,当i+1时,j也要增加。因为i增加后,如j减小了,那么组成[j-1,i+1]的新区间如果是“最长不重复”,那么上一个区间[j,i]属于[j-1,i+1],因此[j,i]就不是最长不重复,这和我们的设定有矛盾,故i增,j必增。

核心代码:

for(int i=0,j=0;i<n;i++){
    s[q[i]]++;
    while(s[q[i]]>1){
        s[q[j]]--;
        j++;
    }
    res=max(res,i-j+1);
}

例题2:AcWing 800. 数组元素的目标和
单调性:在A数组中i,在B数组中找到最靠左的j,使a[i]+b[j]>x成立,这时,当i增加的时候,j必然减小,因为,上一个j使得较小的i都大于x了,现在换成一个大一点的i,j必然要继续减小才能找到这样的值,符合条件。
核心代码:

    for(int i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x) j--;
        if(j>=0&&a[i]+b[j]==x) {
            printf("%d %d\n",i,j);
            break;
        }
    }



well188
1天前
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int q[N];
int d[N];
int n,ans;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    for(int i=0,j=0;i<n;i++){
        d[q[i]]++;
        while(d[q[i]]>1){
            d[q[j]]--;
            j++;
        }
        ans=max(ans,i-j+1);
    }
    printf("%d\n",ans);
    return 0;
}