头像

藏锋守拙

盐城工学院




离线:16小时前


最近来访(34)
用户头像
小宋同学
用户头像
要好好学习鸭
用户头像
韵途琼梦
用户头像
wby0124
用户头像
itdef
用户头像
me一步到胃
用户头像
summeriver13
用户头像
Stitch_s
用户头像
_XY_
用户头像
acwing_4300
用户头像
世事难料
用户头像
j5zslhw
用户头像
captainDDL
用户头像
M_ming
用户头像
ZYYZ
用户头像
小约翰在鲜花社
用户头像
小糯米
用户头像
Monohydroxides
用户头像
whale77
用户头像
BPM37093

活动打卡代码 AcWing 3302. 表达式求值

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

stack<int> num;
stack<char> op;

unordered_map<char, int> h = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval()
{
    int a = num.top();
    num.pop();

    int b = num.top();
    num.pop();

    char c = op.top();
    op.pop();

    int x;
    if(c == '+')    x = b + a;
    if(c == '-')    x = b - a;
    if(c == '*')    x = b * a;
    if(c == '/')    x = b / a;

    num.push(x);
}

int main()
{
    string s;
    cin >> s;

    for(int i = 0; i < s.size(); i ++)
    {
        if(isdigit(s[i]))
        {
            int x = 0, j = i;
            while(isdigit(s[j]) && j < s.size())
            {
                x = x * 10 + s[j] - '0';
                j ++;
            }
            num.push(x);
            i = j - 1;
        }
        else if(s[i] == '(')
        {
            op.push('(');
        }
        else if(s[i] == ')')
        {
            while(op.top() != '(')
                eval();
            op.pop();
        }
        else
        {
            while(op.size() && h[op.top()] >= h[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while(op.size())    eval();
    cout << num.top() << endl;
    return 0;
}



#include <iostream>
#include <vector>
using namespace std;

vector<int> a;

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

    while(m --)
    {
        string op;
        int x;
        cin >> op;

        if(op == "push")
        {
            scanf("%d", &x);
            a.push_back(x);
        }
        else if(op == "pop")
        {
            a.pop_back();
        }
        else if(op == "empty")
        {
            if(a.size() == 0)
                printf("YES\n");
            else
                printf("NO\n");
        }
        else if(op == "query")
        {
            printf("%d\n", a.back());
        }
    }

    return 0;
}



啰嗦写法,但便于理解

#include <iostream>
using namespace std;

const int N = 100010;
int idx, e[N], l[N], r[N];

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void insertL(int x)
{
    r[idx] = r[0];
    l[idx] = 0;
    r[0] = idx;
    l[r[idx]] = idx;
    e[idx ++] = x;
}

void insertR(int x)
{
    r[idx] = 1;
    l[idx] = l[1];
    l[1] = idx;
    r[l[idx]] = idx;
    e[idx ++] = x;
}

void deleteK(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

void insertIL(int k, int x)
{
    l[idx] = l[k];
    r[idx] = k;
    r[l[k]] = idx;
    l[k] = idx;
    e[idx ++] = x;
}

void insertIR(int k, int x)
{
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    e[idx ++] = x;
}

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

    init();

    while(m --)
    {
        string op;
        int k, x;

        cin >> op;
        if(op == "L")
        {
            scanf("%d", &x);
            insertL(x);
        }
        else if(op == "R")
        {
            scanf("%d", &x);
            insertR(x);
        }
        else if(op == "D")
        {
            scanf("%d", &k);
            deleteK(k + 1);
        }
        else if(op == "IL")
        {
            scanf("%d%d", &k, &x);
            insertIL(k + 1, x);
        }
        else if(op == "IR")
        {
            scanf("%d%d", &k, &x);
            insertIR(k + 1, x);
        }
    }

    for(int i = r[0]; i != 1; i = r[i])
        printf("%d ", e[i]);
    return 0;
}



题目链接 双链表 827

错误的代码:

#include <iostream>
using namespace std;

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

void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;                        
}

void insertL(int x)
{
    r[idx] = r[0];
    l[idx] = 0;
    r[0] = idx;
    l[r[idx]] = idx;
    e[idx ++] = x;
}

void insertR(int x)
{
    l[idx] = l[1];
    r[idx] = 1;
    r[l[idx]] = idx;
    l[1] = idx;
    e[idx ++] = x;
}

void deleteK(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

void insertLK(int k, int x)
{
    r[idx] = k;
    l[idx] = l[k];
    r[l[idx]] = idx;
    l[k] = idx;
    e[idx ++] = x;
}

void insertRK(int k, int x)
{
    l[idx] = k;
    r[idx] = r[k];
    l[r[idx]] = idx;
    r[k] = idx;
    e[idx ++] = x;
}

int main()
{
    ios::sync_with_stdio(false);
    int m;
    scanf("%d", &m);

    init();

    while(m --)
    {
        int k, x;
        string op;
        cin >> op;

        if(op == "L")
        {
            scanf("%d", &x);
            insertL(x);
        }
        else if(op == "R")
        {
            scanf("%d", &x);
            insertR(x);
        }
        else if(op == "IL")
        {
            scanf("%d%d", &k, &x);
            insertLK(k + 1, x);
        }
        else if(op == "IR")
        {
            scanf("%d%d", &k, &x);
            insertRK(k + 1, x);
        }
        else if(op == "D")
        {
            scanf("%d", &k);
            deleteK(k + 1);
        }
    }

    for(int i = r[0]; i != 1; i = r[i])
        printf("%d ", e[i]);
    return 0;
}

没有输出。。。




题目链接 Acwing 826

#include <iostream>
using namespace std;

const int N = 100010;
int head, n[N], ne[N], idx;

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

void insert_head(int x)
{
    n[idx] = x;
    ne[idx] = head;
    head = idx ++;
}

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

void delete_node(int k)
{
    ne[k] = ne[ne[k]];
}

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

    init();

    while(m --)
    {
        char op;
        cin >> op;

        if(op == 'H')
        {
            int x;
            scanf("%d", &x);
            insert_head(x);
        }
        else if(op == 'D')
        {
            int k;
            scanf("%d", &k);
            if(!k)  head = ne[head];
            else    delete_node(k - 1);
        }
        else
        {
            int k, x;
            scanf("%d%d", &k, &x);
            insert_node(k - 1, x);
        }
    }

    for(int i = head; i != -1; i = ne[i])
        printf("%d", n[i]);
    return 0;
}

这个代码如果输入D 0,就是说删除头结点
如果说只有头结点那么只会删除头结点;
如果说头结点后面还有结点,那么这个算法删除头结点就不成立




题目链接 AcWing 799

代码:

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];

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

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

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

    printf("%d", res);
    return 0;
}

s[a[j 加加]] 减减 里面 加加,减减谁先执行的问题,有大佬解释一下么
我觉得这里面先执行加加,再执行减减,但是从程序效果来看却是相反的



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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> add;

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

    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        add.push_back({l, r});
    }

    sort(add.begin(), add.end());

    int res = 1;
    int l = add[0].first, r = add[0].second;
    for(auto item : add)
    {
        if(r < item.first)
        {
            res ++;
            l = item.first;
            r = item.second;
        }
        else 
        {
            r = max(r, item.second);
        }
        //cout << l << " " << r << endl;
    }
    printf("%d", res);
    return 0;
}


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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 300010;
int a[N], s[N];

typedef pair<int, int> PII;
vector<int> alls;
vector<PII> add, query;

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x)  r = mid;
        else    l = mid + 1;
    }
    return l;
}

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

    for(int i = 0; i < m; i ++)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &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 c = find(item.first);
        a[c] += item.second;
    }

    for(int i = 0; i < alls.size(); i ++)
    {
        s[i] = s[i - 1] + a[i];
    }

    for(auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}


活动打卡代码 AcWing 4615. 相遇问题

#include <iostream>
using namespace std;

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

    int x, y, a, b;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d%d%d", &x, &y, &a, &b);
        if((y - x) % (a +b) != 0)
            printf("-1\n");
        else
            printf("%d\n", (y - x) / (a + b));
    }

    return 0;
}


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

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int n, m;
    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]);

    for(int i = 0, j = 0; j < m; j ++)
    {
        if(a[i] == b[j])
        {
            i ++;
            //printf("%d\n", j);
        }
        if(i == n)
        {
            printf("Yes");
            return 0;
        }
    }
    printf("No");
    return 0;
}