头像

qsmy_41




离线:1个月前


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

qsmy_41
1个月前
#include <cstring>
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

string s;
stack<int> num;
stack<char> op;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval() {
    int res;
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    if (c == '*') res = a * b;
    if (c == '/') res = a / b;
    if (c == '+') res = a + b;
    if (c == '-') res = a - b;
    num.push(res);
}

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

    return 0;
}


活动打卡代码 AcWing 417. 不高兴的津津

qsmy_41
3个月前
#include <iostream>
using namespace std;
int main() {
    int a, b;
    int maxv=0, idx=0;
    for (int i=1; i<7; i++) {
        cin>>a>>b;
        int tmp=a+b;
        if (tmp>8 && tmp>maxv) maxv=tmp, idx=i;
    }
    cout<<idx;
    return 0;
}


活动打卡代码 AcWing 421. 陶陶摘苹果

qsmy_41
3个月前
#include <iostream>
using namespace std;
int n, a[10];

int main() {
    for (int i=0; i<10; i++) cin>>a[i];
    cin>>n;
    n+=30;
    int res=0;
    for (int i=0; i<10 ;i++) if (a[i]<=n) res++;
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 428. 数列

qsmy_41
3个月前
#include <iostream>
using namespace std;

int main() {
    int k, n;
    cin>>k>>n;
    int res=0, a=1;
    while (n) {
        if (n&1) res+=a;
        n>>=1;
        a*=k;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 875. 快速幂

qsmy_41
3个月前
#include <iostream>
using namespace std;
int a, b, p;

int main() {
    int T;
    cin>>T;
    while (T--) {
        cin>>a>>b>>p;
        int res=1%p;
        while (b) {
            if (b&1) res=res*1ll*a%p;
            b>>=1;
            a=a*1ll*a%p;
        }
        cout<<res<<'\n';
    }
    return 0;
}


活动打卡代码 AcWing 433. ISBN号码

qsmy_41
3个月前
#include <iostream>
using namespace std;

const int P=11;
char str[15];

int main() {
    cin>>str;
    int n=1, res=0;
    for (int i=0; i<11; i++) {
        if (str[i]=='-') continue;
        int x=str[i]-'0';
        res+=n*x;
        n++;
    }
    res%=P;
    if (res==10 && str[12]=='X' || res==str[12]-'0') cout<<"Right";
    else {
        for (int i=0; i<=11; i++) cout<<str[i];
        if (res==10) cout<<'X';
        else cout<<res;
    }
    return 0;
}


活动打卡代码 AcWing 89. a^b

qsmy_41
3个月前
#include <iostream>
using namespace std;

int main() {
    int a, b, p;
    cin>>a>>b>>p;
    int res=1%p;
    while (b) {
        if (b&1) res=res*a*1ll%p;
        a=a*1ll*a%p;
        b>>=1;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

qsmy_41
3个月前
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, m, e[N*2], ne[N*2], h[N], idx;
int d[N];
int q[N], hh, tt;

void add(int a, int b) {
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int bfs() {
    q[tt++]=1;
    d[1]=0;
    while (hh<tt) {
        auto cur=q[hh++];
        for (int i=h[cur]; i!=-1; i=ne[i]) {
            int j=e[i];
            if (d[j]==-1) {
                d[j]=d[cur]+1;
                if (j==n) return d[j];
                q[tt++]=j;
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(d, -1, sizeof d);
    memset(h, -1, sizeof h);
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        int a, b;
        cin>>a>>b;
        add(a, b);
    }
    cout<<bfs();
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

qsmy_41
3个月前
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n, h[N], e[N*2], ne[N*2], idx, ans=N;
bool st[N];

void add(int a, int b) {
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dfs(int x) {
    st[x]=true;
    int sum=1, res=0;
    for (int i=h[x]; i!=-1; i=ne[i]) {
        int j=e[i];
        if (!st[j]) {
            int s=dfs(j);
            res=max(res, s);
            sum+=s;
        }
    }
    res=max(res, n-sum);
    ans=min(ans, res);
    return sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(h, -1, sizeof h);
    cin>>n;
    for (int i=1; i<n; i++) {
        int a, b;
        cin>>a>>b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout<<ans;
    return 0;
}



qsmy_41
3个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N=210;
int T, n, m;
char g[N][N];
int cnt[N][N];
PII q[N*N], st, dest;
int hh, tt;
int dx[]={0,1,0,-1}, dy[]={-1,0,1,0};

int bfs() {
    q[tt++]=st;
    cnt[st.y][st.x]=0;
    while (hh<tt) {
        auto cur=q[hh++];
        for (int i=0; i<4; i++) {
            int x=cur.x+dx[i], y=cur.y+dy[i];
            if (x>=0 && x<m && y>=0 && y<n && cnt[y][x]==-1 && g[y][x]!='#') {
                q[tt++]={x, y};
                cnt[y][x]=cnt[cur.y][cur.x]+1;
                if (g[y][x]=='E') return cnt[y][x];
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>T;
    while (T--) {
        memset(cnt, -1, sizeof cnt);
        cin>>n>>m;
        hh=0, tt=0;
        for (int i=0; i<n; i++) {
            cin>>g[i];
            for (int j=0; j<m; j++) {
                if (g[i][j]=='S') st={j, i};
                if (g[i][j]=='E') dest={j, i};
            }
        }
        int res=bfs();
        if (res) cout<<res<<'\n';
        else cout<<"oop!\n";
    }
    return 0;
}