头像

acmsdut

SDUT




离线:22小时前


活动打卡代码 AcWing 244. 谜一样的牛

acmsdut
12天前
//                              _ooOoo_
//                             o8888888o
//                             88" . "88
//                             (| -_- |)
//                              O\ = /O
//                           ____/`---'\____
//                        .   ' \| |// `.
//                         / \||| : |||// \
//                        / _||||| -:- |||||- \
//                         | | \\ - /// | |
//                       | \_| ''\---/'' | |
//                        \ .-\__ `-` ___/-. /
//                    ___`. .' /--.--\ `. . __
//                  ."" '< `.___\_<|>_/___.' >'"".
//                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
//                    \ \ `-. \_ __\ /__ _/ .-` / /
//           ======`-.____`-.___\_____/___.-`____.-'======
//                              `=---='
//
//           .............................................
//                   佛祖保佑     一发AC     永无BUG
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int bit[maxn], a[maxn] ,biti[maxn];
int lowbit(int x) { return x & -x; }
int n, m;

int ask(int x) {
    int ans = 0;
    for (; x > 0; x -= lowbit(x)) {
        ans += bit[x];
    }
    return ans;
}

void updata(int x, int val) {
    for (; x <= n; x += lowbit(x)) {
        bit[x] += val;
    }
}
int ans[maxn];
int main(int argc, char const *argv[]) {
    cin >> n;
    updata(1,1);
    for(int i = 2; i <= n; i++) {
        cin  >> a[i];
        updata(i,1);
    }
    for(int i = n; i >= 1; i--) {
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(ask(mid) < a[i] + 1) {
                l = mid + 1;
            }else r = mid;
        }
        ans[i] = r;
        updata(r,-1);
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}




acmsdut
12天前
//                              _ooOoo_
//                             o8888888o
//                             88" . "88
//                             (| -_- |)
//                              O\ = /O
//                           ____/`---'\____
//                        .   ' \| |// `.
//                         / \||| : |||// \
//                        / _||||| -:- |||||- \
//                         | | \\ - /// | |
//                       | \_| ''\---/'' | |
//                        \ .-\__ `-` ___/-. /
//                    ___`. .' /--.--\ `. . __
//                  ."" '< `.___\_<|>_/___.' >'"".
//                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
//                    \ \ `-. \_ __\ /__ _/ .-` / /
//           ======`-.____`-.___\_____/___.-`____.-'======
//                              `=---='
//
//           .............................................
//                   佛祖保佑     一发AC     永无BUG
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
LL bit[maxn], a[maxn] ,biti[maxn];
LL lowbit(LL x) { return x & -x; }
LL n, m;

LL ask(LL bit[] , LL x) {
    LL ans = 0;
    for (; x > 0; x -= lowbit(x)) {
        ans += bit[x];
    }
    return ans;
}

void updata(LL bit[],LL x, LL val) {
    for (; x <= n; x += lowbit(x)) {
        bit[x] += val;
    }
}

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    LL x, y, e;
    for (int i = 1; i <= n; i++) updata(bit, i, a[i] - a[i - 1]), updata(biti, i, i * (a[i] - a[i-1]));
    while (m--) {
        char op[4];
        cin >> op;
        if (op[0] == 'Q') {
            cin >> x >> y;
            LL L = (x) * ask(bit,x-1) - ask(biti, x-1);
            LL R = (y+1) * ask(bit,y) - ask(biti, y);
            cout << R - L << endl;
        } else {
            cin >> x >> y >> e;
            updata(bit, x, e);
            updata(bit, y + 1, -e);
            updata(biti, x, x * e);
            updata(biti, y + 1, - (y + 1) * e);
        }
    }
    return 0;
}




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

using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int n, m;

int st[maxn], a[maxn];

int lowbit(int x) {return x & -x;}

void add(int pos, int x) {
    for(int i = pos; i <= n; i += lowbit(i)) st[i] += x;
}

LL sum(int x) {
    LL  ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += st[i];
    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]);
    while(m--) {
        char op[4];
        int l, r, d, x;
        scanf("%s",op);
        if(op[0] == 'Q') {
            cin >> x;
            cout << sum(x) << endl;
        }else {
            cin >> l >> r >> d;
            add(l,d);
            add(r+1,-d);
        }
    }
}


活动打卡代码 AcWing 241. 楼兰图腾

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

using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
int a[maxn], low[maxn], great[maxn], st[maxn];
int n;
int lowbit(int x) {return x & -x;}

void add(int root, int x) {
    for(int i = root; i <= n; i += lowbit(i)){
        st[i] += x;
    }
}

LL sum(int x) {
    LL ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += st[i];
    return ans;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1; i <= n; i++) {
        great[i] = sum(n) - sum(a[i]);
        low[i] = sum(a[i] - 1);
        add(a[i],1);
    }
    memset(st, 0, sizeof st);
    LL ans1 = 0, ans2 = 0;
    for(int i = n; i >= 1; i--) {
        ans1 += (sum(n) - sum(a[i])) * great[i];
        ans2 += sum(a[i]-1) * low[i];
        add(a[i],1);
    }
    cout << ans1 << ' ' << ans2;
}


活动打卡代码 AcWing 238. 银河英雄传说

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e4 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int fa[maxn], d[maxn], siz[maxn];//siz记录当前点下面有几个战舰,d记录当前点到最高父亲间有几个战舰
int f(int x) {
    if (fa[x] != x) {
        int root = f(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    for (int i = 0; i <= maxn; i++) fa[i] = i, siz[i] = 1;
    while (t--) {
        char op[4];
        int x, y;
        scanf("%s %d %d", op, &x, &y);
        int x1 = f(x), y1 = f(y);
        if (op[0] == 'M') {
            d[x1] = siz[y1];
            siz[y1] += siz[x1];
            fa[x1] = y1;
        } else {
            if (x1 != y1)
                puts("-1");
            else {
                printf("%d\n", max(0, abs(d[x] - d[y]) - 1));
            }
        }
    }
    return 0;
}



活动打卡代码 AcWing 239. 奇偶游戏

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
unordered_map<int, int> mp;
int n, m;
int fa[maxn], d[maxn];
int get_id(int x) {
    if (mp.count(x) == 0) mp[x] = ++n;
    return mp[x];
}

int f(int x) {
    if (x != fa[x]) {
        int root = f(fa[x]);
        d[x] ^= d[fa[x]];
        fa[x] = root;
    }
    return fa[x];//不能写x,递归返回时第一层x==fa[x],但是第二层的时候x!=fa[x]
}

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= maxn; i++) fa[i] = i;
    int res = m;
    n = 0;
    for (int i = 1; i <= m; i++) {
        int x, y;
        string s;
        cin >> x >> y >> s;
        x = get_id(x - 1), y = get_id(y);
        int pa = f(x), pb = f(y);
        int t = 0;
        if (s == "odd") t = 1;

        if (pa == pb) {
            if (d[x] ^ d[y] != t) {
                res = i - 1;
                break;
            }
        } else {
            fa[pa] = pb;
            d[pa] = d[x] ^ d[y] ^ t;
        }
    }
    cout << res << endl;
    return 0;
}




活动打卡代码 AcWing 237. 程序自动分析

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int fa[maxn];
struct node {
    int x, y, op;
} cao[maxn];
int Hash[maxn], cnt;
int f(int x) { return fa[x] == x ? x : fa[x] = f(fa[x]); }
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int m = 2 * n + 10;
        for (int i = 0; i <= m; i++) fa[i] = i;
        cnt = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &cao[i].x, &cao[i].y, &cao[i].op);
            Hash[cnt++] = cao[i].x;
            Hash[cnt++] = cao[i].y;
        }
        int flag = 1;
        sort(Hash, Hash + cnt);
        cnt = unique(Hash, Hash + cnt) - Hash;
        for (int i = 0; i < n; i++) {
            int x = f(lower_bound(Hash, Hash + cnt, cao[i].x) - Hash);
            int y = f(lower_bound(Hash, Hash + cnt, cao[i].y) - Hash);
            if (cao[i].op == 1) {
                fa[x] = y;
            }
        }
        for (int i = 0; i < n; i++) {
            int x = f(lower_bound(Hash, Hash + cnt, cao[i].x) - Hash);
            int y = f(lower_bound(Hash, Hash + cnt, cao[i].y) - Hash);
            if (cao[i].op == 0 && x == y) {
                flag = 0;
                break;
            }
        }
        if (flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}



活动打卡代码 AcWing 1252. 搭配购买

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e4+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int fa[maxn];
int dp[maxn];
int f(int x) {return fa[x] == x ? x  : fa[x] = f(fa[x]);}
int c[maxn], d[maxn];
vector<PII> good;
int main(int argc, char const *argv[]) {
    int n, m, w;
    cin >> n >> m >> w;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d",&c[i], &d[i]);
    }
    //并查集合并
    for(int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d",&x,&y);
        x = f(x), y = f(y);
        if(x == y) continue;//已经同一集合无需再次合并
        fa[x] = y;
        c[y] += c[x];
        d[y] += d[x];
    }
    //取出实际物品集合
    for(int i = 1; i <= n; i++) {
        if(fa[i] == i) {
            good.push_back({c[i], d[i]});
        }
    }
    //01背包
    for(int i = 0; i < good.size(); i++) {
        for(int j = w; j >= good[i].first; j--) {
            dp[j] = max(dp[j], dp[j-good[i].first] + good[i].second);
        }
    }
    cout << dp[w] << endl;
    return 0;
}




活动打卡代码 AcWing 1252. 搭配购买

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e4+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int fa[maxn];
int dp[maxn];
int f(int x) {return fa[x] == x ? x  : fa[x] = f(fa[x]);}
int c[maxn], d[maxn];
vector<PII> good;
int main(int argc, char const *argv[]) {
    int n, m, w;
    cin >> n >> m >> w;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d",&c[i], &d[i]);
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d",&x,&y);
        x = f(x), y = f(y);
        if(x == y) continue;
        fa[x] = y;
        c[y] += c[x];
        d[y] += d[x];
    }
    for(int i = 1; i <= n; i++) {
        if(fa[i] == i) {
            good.push_back({c[i], d[i]});
        }
    }
    for(int i = 0; i < good.size(); i++) {
        for(int j = w; j >= good[i].first; j--) {
            dp[j] = max(dp[j], dp[j-good[i].first] + good[i].second);
        }
    }
    cout << dp[w] << endl;
    return 0;
}



活动打卡代码 AcWing 1250. 格子游戏

acmsdut
1个月前
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int fa[maxn];

int f(int x) {return fa[x] == x ? x  : fa[x] = f(fa[x]);}

int main(int argc, char const *argv[]) {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= maxn; i++) fa[i] = i;
    int ans = 0, flag = 0;
    for(int i = 1; i <= m; i++) {
        int x, y;
        char op;
        scanf("%d %d %c",&x,&y,&op);
        if(flag) continue;
        int u = (x-1) * n + y;
        if(op == 'D') x++;
        else y++;
        int v = (x-1) * n + y;
        u = f(u), v = f(v);
        if(u == v) {
            ans = i;
            flag = 1;
        }
        fa[u] = v;
    }
    if(flag) cout << ans << endl;
    else 
    puts("draw");
    return 0;
}