头像

xybh

东华理工大学




离线:10天前


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

xybh
11天前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
int tt;
int st[N];
int main(){
    int n, x;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        while(tt && st[tt] >= x) tt--;
        if(tt) cout << st[tt] << " ";
        else cout << -1 << " ";
        st[++tt] = x;
    }
    return 0;
}


活动打卡代码 AcWing 868. 筛质数

xybh
12天前

埃氏筛

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
bool is[N];
void init(int n){
    memset(is, 1, sizeof is);
    is[0] = false; is[1] = false;
    for(int i = 2; i <= n; i++){
        if(is[i]){
            for(int j = 2 * i; j <= n; j += i){
                is[j] = false;
            }
        }
    }
}
int main(){
    int n, ans = 0;
    cin >> n;
    init(n);
    for(int i = 1; i <= n; i++){
        if(is[i]) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

线性筛

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
bool is[N];
int prime[N], cnt;
void init(int n){
    for(int i = 2; i <= n; i++){
        if(!is[i]) prime[cnt++] = i;
         for(int j = 0; prime[j] <= n / i; j++) {
            is[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int main(){
    int n;
    cin >> n;
    init(n);
    cout << cnt;
    return 0;
}



xybh
12天前

埃氏筛

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
bool is[N];
void init(int n){
    memset(is, 1, sizeof is);
    is[0] = false; is[1] = false;
    for(int i = 2; i <= n; i++){
        if(is[i]){
            for(int j = 2 * i; j <= n; j += i){
                is[j] = false;
            }
        }
    }
}
int main(){
    int n, ans = 0;
    cin >> n;
    init(n);
    for(int i = 1; i <= n; i++){
        if(is[i]) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

线性筛

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
bool is[N];
int prime[N], cnt;
void init(int n){
    for(int i = 2; i <= n; i++){
        if(!is[i]) prime[cnt++] = i;
         for(int j = 0; prime[j] <= n / i; j++) {
            is[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int main(){
    int n;
    cin >> n;
    init(n);
    cout << cnt;
    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

xybh
12天前

埃氏筛法

#include<bits/stdc++.h>
using namespace std;

void solve(int x){
    for(int i = 2; i <= x / i; i++){
        if(x % i == 0){
            int sum = 0;
            while(x % i == 0){
                sum++;
                x /= i;
            }
            cout << i << " " << sum << endl;
        }
    }
    if(x != 1) cout << x << " " << 1 << endl;
    puts("");
}
int main(){
    int t, x;
    cin >> t;
    while(t--){
        cin >> x;
        solve(x);
    }
    return 0;
}



xybh
12天前

埃氏筛法

#include<bits/stdc++.h>
using namespace std;

void solve(int x){
    for(int i = 2; i <= x / i; i++){
        if(x % i == 0){
            int sum = 0;
            while(x % i == 0){
                sum++;
                x /= i;
            }
            cout << i << " " << sum << endl;
        }
    }
    if(x != 1) cout << x << " " << 1 << endl;
    puts("");
}
int main(){
    int t, x;
    cin >> t;
    while(t--){
        cin >> x;
        solve(x);
    }
    return 0;
}



xybh
12天前
#include<bits/stdc++.h>
using namespace std;

bool check(int x){
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i++){
        if(x % i == 0){
            return false;
        }
    }
    return true;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        int x;
        cin >> x;
        cout << (check(x)?"Yes":"No") << endl;
    }

    return 0;
}


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

xybh
14天前

C++ STL

#include<bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;
    int t;
    cin >> t;
    while(t--){
        string op;
        cin >> op;
        if(op == "push"){
            int x;
            cin >> x;
            q.push(x);
        }
        if(op == "pop"){
            q.pop();
        }
        if(op == "query"){
           cout << q.front() << endl;
        }
        if(op == "empty"){
            cout <<  (q.empty()?"YES":"NO") << endl;
        }
    }
    return 0;
}



xybh
14天前

STL stack

#include<bits/stdc++.h>
using namespace std;

int main(){
    stack<int> s;
    int t; 
    string op;
    cin >> t;
    while(t--){
        cin >> op;
        if(op == "push"){
            int x;
            cin >> x;
            s.push(x);
        }
        if(op == "pop"){
            s.pop();
        }
        if(op == "query"){
            cout << s.top() << endl;
        }
        if(op == "empty"){
            if(!s.size()){
                cout << "YES" << endl;
            }else cout << "NO" << endl;
        }
    }
    return 0;
}

数组模拟栈

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
int e[N], top = -1;

void push(int x){
    e[++top] = x;
}

void pop(){
    top--;
}

bool isEmpty(){
    return top == -1;
}

int query(){
    return e[top];
}

int main(){
    int n;
    string op;
    cin >> n;
    while(n--){
        cin >> op;
        if(op == "query") cout << query() << endl;
        if(op == "push"){
            int x;
            cin >> x;
            push(x);
        }
        if(op == "pop") pop();
        if(op == "empty") cout << (isEmpty()?"YES":"NO") << endl;
    }

    return 0;
}


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

xybh
15天前

STL stack

#include<bits/stdc++.h>
using namespace std;

int main(){
    stack<int> s;
    int t; 
    string op;
    cin >> t;
    while(t--){
        cin >> op;
        if(op == "push"){
            int x;
            cin >> x;
            s.push(x);
        }
        if(op == "pop"){
            s.pop();
        }
        if(op == "query"){
            cout << s.top() << endl;
        }
        if(op == "empty"){
            if(!s.size()){
                cout << "YES" << endl;
            }else cout << "NO" << endl;
        }
    }
    return 0;
}

数组模拟栈

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
int e[N], top = -1;

void push(int x){
    e[++top] = x;
}

void pop(){
    top--;
}

bool isEmpty(){
    return top == -1;
}

int query(){
    return e[top];
}

int main(){
    int n;
    string op;
    cin >> n;
    while(n--){
        cin >> op;
        if(op == "query") cout << query() << endl;
        if(op == "push"){
            int x;
            cin >> x;
            push(x);
        }
        if(op == "pop") pop();
        if(op == "empty") cout << (isEmpty()?"YES":"NO") << endl;
    }

    return 0;
}


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

xybh
15天前
#include <iostream>

using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx=0;

void insertL(int x)
{
    l[idx]=0;//新节点->pre=head
    r[idx]=r[0];//新节点->next=head->next
    r[0]=idx;//head->next=新节点
    l[r[idx]]=idx;//新节点->next->pre=新节点
    e[idx++]=x;//add x
}

void insertR(int x)
{
    r[idx]=1;//新节点->next=tail
    l[idx]=l[1];//新节点->pre=tail->pre
    r[l[idx]]=idx;//新节点->pre->next=新节点
    l[1]=idx;//tail->pre=新节点
    e[idx++]=x;//add x
}

void deleteK(int k)
{
    r[l[k]]=r[k];//k->pre->next=k->next
    l[r[k]]=l[k];//k->next->pre=k->pre
}

void insertKL(int k,int x)                                  
{
    l[idx]=l[k];//新节点->pre=k->pre
    r[idx]=k;//新节点->next=k
    r[l[idx]]=idx;//新节点->pre->next=新节点
    l[k]=idx;//k->pre=新节点
    e[idx++]=x;//add x
}

void insertKR(int k,int x)
{
    r[idx]=r[k];//新节点->next=k->next
    l[idx]=k;//新节点->pre=k
    l[r[idx]]=idx;//新节点->next->pre=新节点
    r[k]=idx;//k->next=新节点
    e[idx++]=x;//add x
}   

void init()
{
    r[0]=1;//head->next=tail
    l[1]=0;//tail->pre=head
    idx=2;//add two nodes
}

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

    while(m-->0)
    {

        string command;
        int k,x;
        cin>>command;
        if(command=="L")
        {
            cin>>x;
            insertL(x);
        }
        else if(command=="R")
        {
            cin>>x;
            insertR(x);
        }
        else if (command=="D")
        {
            cin>>k;
            deleteK(k+1);//因为初始化加了两个节点,所以第k个数的下标为k+2-1
        }
        else if (command=="IL")
        {
            cin>>k>>x;
            insertKL(k+1,x);
        }
        else if(command=="IR")
        {
            cin>>k>>x;
            insertKR(k+1,x);
        }


    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';//从头开始,当i!=tail时输出
    cout<<endl;
    return 0;

}