头像

西柚-




离线:15小时前


活动打卡代码 AcWing 1341. 十三号星期五

西柚-
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  // 打表
int weekday[7];


int main()
{
    int n;
    cin >> n;

    int days = 0;
    for (int year = 1900; year < 1900 + n; year ++ )
    {
        for (int i = 1; i <= 12; i ++ )
        {
            weekday[(days + 12) % 7] ++ ;
            days += month[i];
            if (i == 2)
            {
                if (year % 100 && year % 4 == 0 || year % 400 == 0)
                    days ++ ;
            }
        }
    }

    for (int i = 5, j = 0; j < 7; i = (i + 1) % 7, j ++ )
        cout << weekday[i] << ' ';
    cout << endl;

    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

西柚-
1天前
#include <iostream>

using namespace std;

const int N=1e5+10,M=1e6+10;
int n,m;
char p[N],s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for(int i=2,j=0;i<=n;i++)               //处理p  
    {
        while(j&&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<=m;i++)
    {
        while(j&&s[i]!=p[j+1]) j=ne[j];  //跳回
        if(s[i]==p[j+1]) j++;             
        if(j==n)
        {
            printf("%d " ,i-n);
            j=ne[j];              //
        }
    }

    return 0;
}


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

西柚-
1天前
#include <iostream>

using namespace std;
const int N = 1e6+10;
int a[N],q[N];  //a用来存放值  q用来存放下标
int n,k;

int main()
{
    scanf("%d%d",&n,&k);

    for(int i = 0;i<n;i++) scanf("%d",&a[i]);

    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt &&q[hh]<i-k+1) hh++; //更新队头
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--; //如果队尾前的数大于插入数  删除
        q[++tt] = i;            

        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");

    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt &&q[hh]<i-k+1) hh++; //更新队头
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt] = i;

        if(i>=k-1) printf("%d ",a[q[hh]]); //从i=2开始输出
    }
    puts("");
}


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

西柚-
1天前
#include <iostream>
using namespace std;
const int N =1e6+10;
int stk[N] ,tt;
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=0;i<n;i++) 
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x) tt--;
        if(tt) cout<<stk[tt]<<" ";
        else cout<<"-1"<<" ";

        stk[++tt] = x;
    }
    return 0;
}


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

西柚-
2天前
#include<iostream>
using namespace std;
const int N = 1e6+10;
int que[N],hh,tt=-1;

int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        string op;
        int x;
        cin>>op;
        if(op=="push") cin>>x,que[++tt]=x;
        else if(op=="pop") hh++;
        else if(op=="empty") cout<<(tt>=hh?"NO":"YES")<<endl;
        else cout<<que[hh]<<endl;
    }
    return 0;
}


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

西柚-
2天前
#include<iostream>

using namespace std;

const int N = 1e6+10;
int stk[N],tt;

void push(int x)
{
    stk[++tt] = x;
}
void pop()
{
    if(tt>0) tt--;
}
void empty()
{
    cout<<(!tt?"YES":"NO")<<endl;
}
int query()
{
   return stk[tt]; 
}
int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        string op;
        int x;
        cin>>op;
        if(op=="push") cin>>x,push(x);
        else if (op=="pop") pop();
        else if(op=="empty") empty();
        else cout<<query()<<endl;
    }
    return 0;
}


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

西柚-
2天前
#include <iostream>

using namespace std;

const int N =100010;

int e[N],l[N],r[N],idx; //e[] l[] r[] 分别存放当前的值 左指针 右指针 

void init()
{
    r[0]=1,l[1]=0; // 0号点为左端点, 1号点为右端点 左右边界
    idx = 2;  //idx 从2开始分配
}

void add(int k ,int x)  //在k的右边添加新节点
{
    e[idx] = x;
    r[idx] = r[k];  //当前节点的右等于k的右
    l[idx] = k;
    l[r[k]] =idx;  
    r[k] =idx;     //与上一步的顺序不能改变
    idx++;
}

void removes(int k)
{
    r[l[k]] = r[k];  //当前节点的左指针的右指针等于它的右指针
    l[r[k]] = l[k];  //当前节点的右指针的左指针等于它的左指针
}

int main()
{
    ios::sync_with_stdio(false);
    int m;
    cin>>m;
    init();
    while(m--)
    {
        int x,k;
        string op;
        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;
            removes(k+1);
        }
        else if(op == "IR")
        {
            cin>>k>>x;
            add(k+1,x);
        }
        else 
        {
            cin>>k>>x;
            add(l[k+1],x);
        }
    }

    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
    cout<<endl;

    return 0;
}


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

西柚-
2天前
#include<iostream>

using namespace std;

const int N = 100010;

//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx 存储当前已经用到哪个点
int head,e[N],ne[N],idx;

void init()
{
    head = -1;
    idx = 0;
}

void add_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void removes(int k)
{
    if(k==-1) head = ne[head];
    ne[k]=ne[ne[k]];
}

void add(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

int main()
{
    ios::sync_with_stdio(false);
    int m;
    cin>>m;

    init();

    while(m--)
    {
        int k ,x;
        char op;
        cin>>op;
        if(op == 'H') cin>>x,add_head(x);
        else if(op == 'I') cin>>k>>x , add(k-1,x);
        else{
            cin>>k;
            removes(k-1); 
        }
    }

    for(int i = head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
    cout<<endl;

    return 0;
}


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

西柚-
2天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 300010;
typedef pair<int,int> PII;
int n,m;
int a[N],s[N];
vector<int> alls;      //
vector<PII> add,query; //

int find(int x)
{
    int l = 0 , r = alls.size()-1;
    while(l<r)
    {
        int mid = (r+l) / 2;
        if(alls[mid]>=x) r=mid;
        else l =mid+1;
    }
    return r+1; //从1开始 避免边界
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});

        alls.push_back(x);
    }
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});

        alls.push_back(l);
        alls.push_back(r);
    }

    //去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(auto item:add)
    {
        int x=find(item.first);
        a[x] += item.second;
    }
    //处理前缀和
    for(int i=1;i<=alls.size();i++) s[i]=a[i]+s[i-1];

    //查询
    for(auto item:query)
    {
        int l =find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

西柚-
3天前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100100;
int n ,m ;
int a[N],b[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);

    int i =0 ,j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j]) i++;
        j++;
    }
    if(i==n) printf("Yes");
    else printf("No");

    return 0;
}