头像

ymh

郑州大学


访客:2043

离线:29分钟前


活动打卡代码 AcWing 1097. 池塘计数

ymh
17小时前

c++

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1010, M = N * N;
char g[N][N];
typedef pair<int, int>PII;
PII q[M];
int cnt, n, m;
bool st[N][N];

void bfs(int sx,int sy){
    int hh=0,tt=0;
    q[0]={sx,sy};
    st[sx][sy]=true;
    while(hh<=tt){
        PII t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++){
            for(int j=t.y-1;j<=t.y+1;j++){
                if(i==t.x&&j==t.y)continue;
                if(i<0||i>=n||j<0||j>=m)continue;
                if(g[i][j]=='.'||st[i][j])continue;
                st[i][j]=true;
                q[++tt]={i,j};
            }
        }
    }
}
int main(){
    scanf("%d%d",&n, &m);
    for(int i=0;i<n;i++)scanf("%s",g[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='W'&&!st[i][j]){
                bfs(i,j);
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}



活动打卡代码 AcWing 143. 最大异或对

ymh
1天前

c++

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=3100010;
int a[N];
int son[M][2];
int idx,n;

void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x){
    int p=0;
    int res=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(son[p][!u]){
            res+=1<<i;
            p=son[p][!u];
        }
        else{
            p=son[p][u];
        }
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int res=0;
    for(int i=0;i<n;i++){
        insert(a[i]);
        res=max(res,query(a[i]));
    }
    cout<<res<<endl;
    return 0;
}

python

n=int(input())
a=list(map(int,input().split()))
son=[[0]*2 for i in range(3100010)]
idx=0
def insert(x):
    global idx
    p=0
    for i in range(30,-1,-1):
        u=x>>i&1
        if not son[p][u]:
            idx+=1
            son[p][u]=idx
        p=son[p][u]
def query(x):
    p=0
    res=0
    for i in range(30,-1,-1):
        u=x>>i&1
        if(u):
            t=0
        else:
            t=1
        if son[p][t]:
            res+=(1<<i)
            p=son[p][t]
        else:
            p=son[p][u]
    return res
res=0
for i in range(n):
    insert(a[i])
    res=max(res,query(a[i]))
print(res)


新鲜事 原文

ymh
4天前
昨天睡得早,然后今天大概三天半就起来了,前几天在复习基础课,然后想着今天通过saber把第一章过一遍,完全是没有看之前的代码,竟然都成功了,但是但是但是但是遗憾的是,最后一个失败了,忘写了一个return ,哭了😂,啊哈哈哈哈哈
图片


活动打卡代码 AcWing 482. 合唱队形

ymh
5天前

求两次最长上升子序列

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N],f[N],g[N];
int n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(w[j]<w[i])f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=n;i>=1;i--){
        g[i]=1;
        for(int j=n;j>i;j--){
            if(w[j]<w[i])g[i]=max(g[i],g[j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[i]+g[i]-1);
    cout<<n-res<<endl;
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

ymh
7天前

c++

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int n,k;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)cin>>a[i];
    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&i-k+1>q[hh])hh++;
        while(hh<=tt&&a[q[tt]]>=a[i])tt--;
        q[++tt]=i;
        if(i+1>=k)cout<<a[q[hh]]<<' ';
    }
    puts("");
    hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&i-k+1>q[hh])hh++;
        while(hh<=tt&&a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i+1>=k)cout<<a[q[hh]]<<' ';
    }
    return 0;

}

python

n,k=map(int,input().split())
a=list(map(int,input().split()))
q=[0]*1000010
hh,tt=0,-1
for i in range(n):
    if hh<=tt and i-k+1>q[hh]:
        hh+=1
    while hh<=tt and a[q[tt]]>=a[i]:
        tt-=1
    tt+=1
    q[tt]=i
    if i+1>=k:
        print(a[q[hh]],end=" ")
print()
hh,tt=0,-1
for i in range(n):
    if hh<=tt and i-k+1>q[hh]:
        hh+=1
    while hh<=tt and a[q[tt]]<=a[i]:
        tt-=1
    tt+=1
    q[tt]=i
    if i+1>=k:
        print(a[q[hh]],end=" ")


活动打卡代码 AcWing 830. 单调栈

ymh
7天前

c++

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[N];
int n,x,tt;
int main(){
    scanf("%d",&n);
    while(n--){
        cin>>x;
        while(tt&&stk[tt]>=x)tt--;
        if(tt)cout<<stk[tt]<<' ';
        else cout<<-1<<' ';
        stk[++tt]=x;
    }
    return 0;
}

python

n=int(input())
stk=[0]*100010
tt=0
x=list(map(int,input().split()))
for i in range(n):
    while tt and stk[tt]>=x[i]:
        tt-=1
    if tt:
        print(stk[tt],end=" ")
    else:
        print(-1,end=" ")
    tt+=1
    stk[tt]=x[i]


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

ymh
8天前

python

hh=0
tt=-1
q=[0]*100010
n=int(input())
while n:
    n-=1
    op=input().split()
    if op[0]=="push":
        tt+=1
        q[tt]=int(op[1])
    elif op[0]=="pop":
        hh+=1
    elif op[0]=="empty":
        if hh<=tt:
            print("NO")
        else:
            print("YES")
    else:
        print(q[hh])

c++

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int q[N];
int hh,tt=-1;
int n;

int main(){
    cin>>n;
    while(n--){
        string op;
        int x;
        cin>>op;
        if(op=="push"){
            cin>>x;
            q[++tt]=x;
        }
        else if(op=="pop"){
            hh++;
        }
        else if(op=="query"){
            cout<<q[hh]<<endl;
        }
        else{
            if(hh<=tt)cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
    }
    return 0;
}


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

ymh
8天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
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"){
            if(tt>0)cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else{
            cout<<stk[tt-1]<<endl;
        }
    }
    return 0;
}



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

ymh
8天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int l[N],r[N],e[N],idx;
int m;
void init(){
    r[0]=1,l[1]=0;
    idx=2;
}
void add(int k,int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
void remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main(){
    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{
            cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<" ";
    return 0;
}


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

ymh
8天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int ne[N],e[N];
int head,idx;
int m;
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(int k,int x){
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}

int main(){
    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(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])cout<<e[i]<<" ";
    return 0;
}