头像

leoma




离线:1个月前


最近来访(64)
用户头像
Meteor_7
用户头像
vvvvae
用户头像
小张同学
用户头像
lyktes
用户头像
你啦屎吔
用户头像
zeng9999jian
用户头像
wyyang
用户头像
封禁用户
用户头像
征途者
用户头像
凌乱之风
用户头像
SayonaraGzm
用户头像
HollowKnight
用户头像
爱吃企鹅的鱼
用户头像
饶了我吧
用户头像
Iris_随月浅唱
用户头像
番红柿要吃西茄
用户头像
yxc
用户头像
洞人老王
用户头像
zhangshuo2008
用户头像
坠落的余晖

活动打卡代码 AcWing 2768. 直播获奖

leoma
1个月前

```#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

priority_queue[HTML_REMOVED] l;
priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> r;

int main()
{
int n, w;
scanf(“%d%d”, &n, &w);

for (int i = 1; i <= n; i ++ )
{
    int x;
    scanf("%d", &x);

    if (r.empty() || x >= r.top()) r.push(x);
    else l.push(x);

    int k = max(1, (int)(i * w / 100.0));

    while (r.size() < k) r.push(l.top()), l.pop();
    while (r.size() > k) l.push(r.top()), r.pop();

    printf("%d ", r.top());
}

return 0;

}
```



活动打卡代码 AcWing 476. 对称二叉树

leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int w[N], l[N], r[N], s[N];
int ans;

int dfs1(int u )
{
    if (!u) return 0 ;
    s[u] = dfs1(l[u]) + dfs1(r[u]) + 1;
    return s[u];
}

bool check(int a, int b)
{
    if (!a && !b) return true;
    if (!a || !b) return false;
    if (w[a] != w[b]) return false;
    return check(l[a], r[b]) && check(r[a], l[b]);
}

void dfs2(int u)
{
    if (!u) return;
    if (s[l[u]] == s[r[u]])
        if (check(l[u], r[u]))
            ans = max(ans, s[u]);
    dfs2(l[u]);
    dfs2(r[u]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf ("%d", &w[i]);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &l[i], &r[i]);
        if (l[i] == -1) l[i] = 0;
        if (r[i] == -1) r[i] = 0;
    }

    dfs1(1);
    dfs2(1);

    printf("%d\n", ans); 

    return 0;
}


活动打卡代码 AcWing 2769. 表达式

leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 1000010;

int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
char c[N];
bool st[N];
int stk[N], top;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs1(int u){
    if (!c[u]) return w[u];
    if (c[u] == '!') w[u] = !dfs1(e[h[u]]);
    else
    {
        int a = e[h[u]], b = e[ne[h[u]]];
        if (c[u] == '&') w[u] = dfs1(a) & dfs1(b);
        else w[u] = dfs1(a) | dfs1(b);
    }
    return w[u];
}

void dfs2(int u)
{
    st[u] = true;
    if (!c[u]) return;
    if (c[u] == '!') dfs2(e[h[u]]);
    else
    {
        int a = e[h[u]], b = e[ne[h[u]]];
        if (c[u] == '&')
        {
            if (w[a]) dfs2(b);
            if (w[b]) dfs2(a);
        }
        else
        {
            if (!w[a]) dfs2(b);
            if (!w[b]) dfs2(a);
        }
    }
}

int main()
{
    string s;
    getline(cin, s);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    memset(h, -1, sizeof h);
    m = n;
    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] == ' ') continue;
        if (s[i] == 'x')
        {
            int j = i + 1, x = 0;
            while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++ ] - '0';
            stk[ ++ top] = x;
            i = j;
        }
        else if (s[i] == '!')
        {
            c[ ++ m] = s[i];
            add(m, stk[top -- ]);
            stk[ ++ top] = m;
        }
        else
        {
            c[ ++ m] = s[i];
            add(m, stk[top -- ]);
            add(m, stk[top -- ]);
            stk[ ++ top] = m;
        }
    }

    int res = dfs1(m);
    dfs2(m);

    int Q;
    cin >> Q;
    while (Q -- )
    {
        int x;
        cin >> x; 
        if (st[x]) cout << (res ^ 1) << endl;
        else cout << res << endl;
    }

    return 0;
}


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

leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, K, S, T;
int c[N], cg[N][N];
int g[N][N], d[N][N];
int ans = INF;
int path[N], top;

void dfs(int u, int dist)
{
    if (dist + d[S][u] >= ans) return; 
    if (u == S) ans = dist;
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (g[i][u] < INF)
            {
                bool flag = true;
                for (int j = 0; j < top; j ++ )
                    if (cg[path[j]][c[i]])
                    {
                        flag = false;
                        break;
                    }
                if (flag)
                {
                    path[top ++ ] = c[i];
                    dfs(i, dist + g[i][u]);
                    top -- ;  
                }
            }
    }
}

int main()
{ 
    cin >> n >> K >> m >> S >> T;
    for (int i = 1; i <= n; i ++ ) cin >> c[i];
    for (int i = 1; i <= K; i ++ )
        for (int j = 1; j <= K; j ++ )
            cin >> cg[i][j];
    for (int i = 1; i <= K; i ++ ) cg[i][i] = 1;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i ++ ) g[i][i] = 0;

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    memcpy(d, g, sizeof d);
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    path[top ++ ] = c[T]; 
    dfs(T, 0); 
    if (ans == INF) ans = -1;
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 452. 文化之旅

leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, K, S, T;
int c[N], cg[N][N];
int g[N][N], d[N][N];
int ans = INF;
int path[N], top;

void dfs(int u, int dist)
{
    if (dist + d[S][u] >= ans) return; 
    if (u == S) ans = dist;
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (g[i][u] < INF)
            {
                bool flag = true;
                for (int j = 0; j < top; j ++ )
                    if (cg[path[j]][c[i]])
                    {
                        flag = false;
                        break;
                    }
                if (flag)
                {
                    path[top ++ ] = c[i];
                    dfs(i, dist + g[i][u]);
                    top -- ;  
                }
            }
    }
}

int main()
{
    cin >> n >> K >> m >> S >> T;
    for (int i = 1; i <= n; i ++ ) cin >> c[i];
    for (int i = 1; i <= K; i ++ )
        for (int j = 1; j <= K; j ++ )
            cin >> cg[i][j];
    for (int i = 1; i <= K; i ++ ) cg[i][i] = 1;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i ++ ) g[i][i] = 0;

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    memcpy(d, g, sizeof d);
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    path[top ++ ] = c[T]; 
    dfs(T, 0); 
    if (ans == INF) ans = -1;
    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 460. 子矩阵

leoma
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m, r, c;
int w[N][N];
int f[N][N];
int rw[N][N], cw[N];
int q[N];

int get_count(int x)
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
        if (x >> i & 1)
            res ++ ;
    return res;
}

int main()
{
    cin >> n >> m >> r >> c;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> w[i][j];

    int res = 1e8;
    for (int i = 0; i < 1 << n; i ++ )
        if (get_count(i) == r)
        {
            for (int j = 0, k = 0; j < n; j ++ )
                if (i >> j & 1)
                    q[k ++ ] = j;
            for (int j = 0; j < m; j ++ )
            {
                cw[j] = 0;
                for (int k = 1; k < r; k ++ )
                    cw[j] += abs(w[q[k]][j] - w[q[k - 1]][j]);
            }
            for (int j = 0; j < m; j ++ )
                for (int k = j + 1; k < m; k ++ )
                {
                    rw[j][k] = 0;
                    for (int u = 0; u < r; u ++ )
                        rw[j][k] += abs(w[q[u]][j] - w[q[u]][k]);
                }

            memset(f, 0x3f, sizeof f);
            for (int j = 0; j < m; j ++ )
            {
                f[j][1] = cw[j];
                for (int k = 2; k <= c; k ++ )
                    for (int u = 0; u < j; u ++ )
                        f[j][k] = min(f[j][k], f[u][k - 1] + cw[j] + rw[u][j]);
                res = min(res, f[j][c]);
            }
        }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 416. 麦森数

leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 500;

void mul(int c[], int a[], int b[])
{
    static int tmp[N];
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (i + j < N)
                tmp[i + j] += a[i] * b[j];

    for (int i = 0, t = 0; i < N; i ++ )
    {
        t += tmp[i];
        c[i] = t % 10;
        t /= 10;
    }
}

void qmi(int k)
{
    int res[N] = {1};
    int a[N] = {2};

    while (k)
    {
        if (k & 1) mul(res, res, a);
        mul(a, a, a);
        k >>= 1;
    }

    res[0] -- ;
    for (int i = 0, k = N - 1; i < 10; i ++ )
    {
        for (int j = 0; j < 50; j ++, k -- )
            printf("%d", res[k]);
        puts("");
    }
}

int main()
{
    int p;
    cin >> p;
    cout << (int)(p * log10(2)) + 1 << endl;

    qmi(p);

    return 0;
} 


活动打卡代码 AcWing 415. 栈

leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 40;

int n;
LL C[N][N];

int main(){
    cin >> n;
    for (int i = 0 ; i <= n * 2 ; i ++ )
        for (int j = 0 ; j <= i ; j ++ )
            if (!j) C[i][j] = 1;
            else    C[i][j] = C[i-1][j] + C[i-1][j-1];

    cout << C[n*2][n] / (n+1) << endl;

    return 0;
}


活动打卡代码 AcWing 464. 推销员

leoma
1个月前
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII q[N];
int f[N], g[N], h[N];

int main(){
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++ ) scanf("%d", &q[i].y);
    for (int i = 1 ; i <= n ; i ++ ) scanf("%d", &q[i].x);
    sort(q+1, q+1+n, greater<PII>());

    for (int i = 1 ; i <= n ; i ++ ){
        f[i] = f[i-1] + q[i].x;
        g[i] = max(g[i-1], q[i].y);
    }

    for (int i = n ; i ; i -- ) h[i] = max(h[i+1], q[i].x + q[i].y * 2);

    for (int i = 1 ; i <= n ; i ++ )    printf("%d\n", max(f[i] + g[i] * 2, f[i-1] + h[i]));

    return 0;
}


活动打卡代码 AcWing 434. 排座椅

leoma
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int m, n, k, l, d;
int row[N], col[N];

void work(int a[], int n, int k)
{
    int id[N];
    for (int i = 0; i < n - 1; i ++ ) id[i] = i + 1;
    sort(id, id + n - 1, [&](int x, int y) {
        return a[x] > a[y];
    });
    sort(id, id + k);
    for (int i = 0; i < k; i ++ )
        cout << id[i] << ' ';
    puts("");
}

int main()
{
    cin >> m >> n >> k >> l >> d;
    while (d -- )
    {
        int x, y, p, q;
        cin >> x >> y >> p >> q;
        if (x > p) swap(x, p);
        if (y > q) swap(y, q);
        if (x == p) col[y] ++ ;
        else row[x] ++ ;
    }

    work(row, m, k);
    work(col, n, l);

    return 0;
}