头像

sdsxdxl




离线:1天前


最近来访(42)
用户头像
日不落
用户头像
持灬成功
用户头像
我去2001年
用户头像
深海鱼
用户头像
我不是子龙
用户头像
皓月当空EX
用户头像
周赛坐牢选手
用户头像
77777777777
用户头像
Acwer
用户头像
记着别人的好
用户头像
pccc
用户头像
Jiejiege
用户头像
Summer01
用户头像
dugn2119
用户头像
Anum
用户头像
zzr0126
用户头像
Andrew1729
用户头像
210054070322
用户头像
YEEee
用户头像
-Acwing-

活动打卡代码 AcWing 1215. 小朋友排队

sdsxdxl
2个月前

归并排序

在合并过程中为左右两段的每一个元素求出包含它的逆序对的个数。注意一个细节,要以元素为基础,不能以下标为基础统计。因为归并过程中,下标对应的元素会不断变化。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e6 + 10;
PII q[N], tmp[N];
int cnt[N];
void merge_sort(int l, int r) {
    if(l >= r)  return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(q[i].first <= q[j].first) {
            cnt[q[i].second] += j - mid - 1;
            tmp[k++] = q[i++];
        }
        else {
            cnt[q[j].second] += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }
    while(i <= mid) {
        cnt[q[i].second] += r - mid;
        tmp[k++] = q[i++];
    }
    while(j <= r)   tmp[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++)     q[i] = tmp[j];
}
int main()
{
    int n, x;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        q[i] = {x, i};
    }
    merge_sort(0, n - 1);
    LL ans = 0;
    for(int i = 0; i < n; i++) {
        ans += (cnt[i] + 1) * (LL)cnt[i] / 2;
    }
    printf("%lld", ans);
    return 0;
}

树状数组

思路:统计每一个q[i]前面有多少元素(k1)比他大,后面有多少元素(k2)比他小。这个过程用两个反向的树状数组求即可。
最后包含元素q[i]的逆序对个数就是k1+k2。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int tr[N], q[N];
int cnt[N];
int lowbit(int x) {
    return x & -x;
}
void add(int x) {
    for(int i = x; i < N; i += lowbit(i))   tr[i]++;
}
int query(int x) {
    int s = 0;
    for(int i = x; i; i -= lowbit(i))   s += tr[i];
    return s;
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &q[i]);
        q[i]++;
    }
    for(int i = 1; i <= n; i++) {
        cnt[i] += (i - 1 - query(q[i]));
        add(q[i]);
    }
    memset(tr, 0, sizeof tr);
    for(int i = n; i >= 1; i--) {
        cnt[i] += query(q[i] - 1);
        add(q[i]);
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += (LL)cnt[i] * (cnt[i] + 1) / 2;
    }
    printf("%lld", ans);
    return 0;
}


活动打卡代码 AcWing 4484. 有限小数

sdsxdxl
2个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p, q, b;
LL gcd(LL a, LL b) {
    if(a % b == 0)  return b;
    return gcd(b, a % b);
}
bool solve() {
    while(q != 1) {
        LL d = gcd(q, b);
        if(d == 1) {
            return q == 1;
        }
        while(q % d == 0)   q /= d;
    }
    return true;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld", &p, &q, &b);
        LL d = gcd(p, q);
        p /= d, q /= d;
        p %= q;
        if(solve())     puts("YES");
        else    puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 4483. 格斗场

sdsxdxl
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int cnt[N], a[N];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }
    sort(a, a + n);
    int ans = 0;
    for(int i = 1; i < n; i++) {
        if(a[i] == a[i - 1])    continue;
        if(a[i] - a[i - 1] > k)     ans += cnt[a[i - 1]];
    }
    ans += cnt[a[n - 1]];
    printf("%d", ans);
    return 0;
}


活动打卡代码 AcWing 4482. 分组

sdsxdxl
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int cnt[N];
int main()
{
    int n, x;
    int ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        cnt[x]++;
        ans = max(ans, cnt[x]);
    }
    printf("%d", ans);
    return 0;
}



sdsxdxl
3个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL nums[N];
int stk[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &nums[i]);
        nums[i] -= 100;
        nums[i] += nums[i - 1];
    }
    int ans = 0, idx = 0;
    stk[idx++] = 0;
    for(int i = 1; i <= n; i++) {
        int l = 0, r = idx - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(nums[stk[mid]] >= nums[i])   l = mid + 1;
            else    r = mid;
        }
        if(nums[stk[l]] < nums[i])    ans = max(ans, i - stk[l]);
        if(nums[i] < nums[stk[idx - 1]])   stk[idx++] = i;
    }
    printf("%d", ans);
    return 0;
}


活动打卡代码 AcWing 4486. 数字操作

sdsxdxl
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int cnt[N];
int divide(int n) {
    int k = 0;
    for(int i = 2; i <= n / i; i++) {
        if(n % i == 0) {
            int s = 0;
            while(n % i == 0) {
                n /= i;
                s++;
            }
            cnt[i] = s;
            k = max(k, s);
        }
    }
    if(n > 1) {
        cnt[n]++;
        k = max(k, cnt[n]);
    }
    return k;
}
int main()
{
    int n;
    cin >> n;
    int k = divide(n);
    int l = 0, r = 20;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(pow(2, mid) >= k)    r = mid;
        else    l = mid + 1;
    }
    k = pow(2, l);
    int ans = 1;
    bool flag = false;
    for(int i = 1; i < N; i++) {
        if(cnt[i]) {
            ans *= i;
            if(cnt[i] != k)     flag = true;
        }
    }
    cout << ans << ' ';
    cout << (flag ? l + 1 : l);
    return 0;
}


活动打卡代码 AcWing 4486. 数字操作

sdsxdxl
3个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL nums[N];
int stk[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &nums[i]);
        nums[i] -= 100;
        nums[i] += nums[i - 1];
    }
    int ans = 0, idx = 0;
    stk[idx++] = 0;
    for(int i = 1; i <= n; i++) {
        int l = 0, r = idx - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(nums[stk[mid]] >= nums[i])   l = mid + 1;
            else    r = mid;
        }
        if(nums[stk[l]] < nums[i])    ans = max(ans, i - stk[l]);
        if(nums[i] < nums[stk[idx - 1]])   stk[idx++] = i;
    }
    printf("%d", ans);
    return 0;
}


活动打卡代码 AcWing 4485. 比大小

sdsxdxl
3个月前
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, x;
    int s = 0;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x;
        s += x;
    }
    for(int i = 0; i < n; i++) {
        cin >> x;
        s -= x;
    }
    if(s >= 0)  puts("Yes");
    else    puts("No");
    return 0;
}


活动打卡代码 AcWing 4274. 后缀表达式

sdsxdxl
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
bool vis[N];
int l[N], r[N];
string s[N];
int n;
struct TreeNode {
    TreeNode(string v) {
        val = v;
        left = right = nullptr;
    }
    TreeNode* left;
    TreeNode* right;
    string val;
};
TreeNode* dfs(int u) {
    if(u == -1)         return nullptr;
    TreeNode* root = new TreeNode(s[u]);
    root -> left = dfs(l[u]);
    root -> right = dfs(r[u]);
    return root;
}
void dfs1(TreeNode* root) {
    if(!root)   return;
    cout << "(";
    if(root -> left) {
        dfs1(root -> left);
        dfs1(root -> right);
        cout << root -> val;
    } else {
        cout << root -> val;
        dfs1(root -> right);
    }
    cout << ")";
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> s[i] >> l[i] >> r[i];
        if(l[i] != -1)   vis[l[i]] = true;
        if(r[i] != -1)  vis[r[i]] = true;
    }
    int root = -1;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            root = i;
            break;
        }
    }
    TreeNode* rt = dfs(root);
    dfs1(rt);
    return 0;
}


活动打卡代码 AcWing 4273. 链表合并

sdsxdxl
3个月前

有bug,没做出来


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int tmp[N], addre[N], mp[N];
int addr = 0;
void add(int a, int b, int c) {
    if(!mp[a])  mp[a] = ++addr;
    int u = mp[a];
    w[u] = c;
    addre[u] = a;
    if(b == -1)     return;
    if(!mp[b])  mp[b] = ++addr;
    int v = mp[b];
    addre[v] = b;
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int main()
{
    memset(h, -1, sizeof h);
    int L1, L2, n;
    scanf("%d%d%d", &L1, &L2, &n);
    int address, data, nx;
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &address, &data, &nx);
        add(address, nx, data);
    }
    int u = 0, cur = mp[L2];
    //cout << mp[L1] << ' ' << mp[L2] << ' ' << cur << endl;
    cout << e[6] << endl;
    while(cur != -1) {
        tmp[u++] = e[cur];
        cout << addre[e[cur]] << ' ';
        cur = ne[cur];
    }
    reverse(tmp, tmp + addr);
    for(int i = h[mp[L1]], k = 1, j = h[mp[L2]]; ~i; i = ne[i], k++) {
        if(k == 2) {
            if(j == -1)     break;
            int t = ne[j];
            ne[j] = ne[i];
            ne[i] = j;
            j = t;
            k = 0;
        }
    }
    for(int i = h[mp[L1]]; ~i; i = ne[i]) {
        printf("%5d %d %5d\n", addre[i], w[i], addre[ne[i]]);
    }
    return 0;
}