07月25, 2018

7.25 杭电多校2题解及补题

比赛过程

上来秒掉签到D

Xander来了之后开始推J,

与wdh多次交流失败后,Xander转述解法,顺利签到J

感觉解题思路描述可以多加练习

然后全场卡线段树GG

赛后发现,不是出题人卡常数,也不是自己的线段树板子有问题,的确是思路上出现了一些小纰漏,导致了大量数据被过度的check

题解

D

题意

Alice 和Bob 开始玩你, Alice开始,轮流从1-n中删除x的所有因子,没有数删的失败,问alice先手胜还是败

题解

如果先手必败,那么拿1 否则拿x

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        puts("Yes");
    }
return 0;
}

G

题意

In a galaxy far, far away, there are two integer sequence a and b of length n. b is a static permutation of 1 to n. Initially a is filled with zeroes. There are two kind of operations:

  1. add l r: add one for al,al+1...ar
  2. query l r: query ∑ri=l⌊ai/bi⌋

    题解

    不难发现,修改是调和级数

那么我们可以维护是否Ci进行了变化,这可以用线段树维护最小值实现

注意不能维护区间余数最大值及bi最小值实现,这样有些结点其实不需要更新

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int flag[N << 2], c[N << 2], minflag[N << 2], b[N << 2], stamp;
void pushdown(int rt) {
    if (flag[rt]) {
        flag[rt << 1] += flag[rt];
        flag[rt << 1 | 1] += flag[rt];
        minflag[rt << 1] += flag[rt];
        minflag[rt << 1 | 1] += flag[rt];
        flag[rt] = 0;
    }
}

void pushup(int rt) {
    minflag[rt] = min(minflag[rt << 1], minflag[rt << 1 | 1]);
    c[rt] = c[rt << 1] + c[rt << 1 | 1];
}
void build(int l, int r, int rt) {
    if (l == r) {
        c[rt] = 0;
        minflag[rt] = b[l];
        flag[rt] = b[l];
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int l, int r, int rt, int L, int R, int v) {
    if (l > R || r < L) return;
    if (L <= l && r <= R && l == r && minflag[rt] == 1) {
        flag[rt] = b[l];
        minflag[rt] = flag[rt];
        c[rt]++;
        return;
    }
    if (L <= l && r <= R && minflag[rt] != 1) {
        minflag[rt] --;
        flag[rt] --;
        return;
    }
    pushdown(rt);
    int m = (l + r) >> 1;
    if (L <= m) update(l, m, rt << 1, L, R, v);
    if (m < R) update(m + 1, r, rt << 1 | 1, L, R, v);
    pushup(rt);
}
long long query(int l, int r, int rt, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R && l == r && minflag[rt] == 0) {
        flag[rt] = b[l];
        minflag[rt] = flag[rt];
        c[rt]++;
        return c[rt];
    }
    if (L <= l && r <= R && minflag[rt] != 0) {
        return c[rt];
    }
    pushdown(rt);
    long long ret = 0;
    int m = (l + r) >> 1;
    if (L <= m) ret += query(l, m, rt << 1, L, R);
    if (m < R) ret += query(m + 1, r, rt << 1 | 1, L, R);
    pushup(rt);
    return ret;
}
int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) == 2) {
        for (int i = 1; i <= n; i++) scanf("%lld", b + i);
        build(1, n, 1);
        memset(flag, 0, sizeof flag);
        for (int i = 0; i < k; i++) {
            int tmp1, tmp2;
            char op[100];
            scanf("%s", op);
            if (op[0] == 'a') {
                scanf("%d%d", &tmp1, &tmp2);
                update(1, n, 1, tmp1, tmp2, 1);
            } else {
                scanf("%d%d", &tmp1, &tmp2);
                printf("%lld", query(1, n, 1, tmp1, tmp2));
                puts("");
            }
        }
    }
    return 0;
}
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define max(x,y) ((x>y)?x:y)
#define min(x,y) ((x<y)?x:y)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll flag[N << 2], c[N << 2], b[N << 2], maxflag[N << 2];
inline void pushdown(int rt) {
    if (flag[rt]) {
        flag[rt << 1] += flag[rt];
        flag[rt << 1 | 1] += flag[rt];
        maxflag[rt << 1] += flag[rt];
        maxflag[rt << 1 | 1] += flag[rt];
        flag[rt] = 0;
    }
}
inline void pushup(int rt) {
    c[rt] = c[rt << 1] + c[rt << 1 | 1];
    maxflag[rt] = max(maxflag[rt << 1], maxflag[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    if (l == r) {
        flag[rt] = -b[l];
        c[rt] = 0;
        maxflag[rt] = -b[l];
        //minb[rt] = b[l];
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
   // minb[rt] = min(minb[rt << 1], minb[rt << 1 | 1]);
    maxflag[rt] = max(maxflag[rt << 1], maxflag[rt << 1 | 1]);
    c[rt] = c[rt << 1] + c[rt << 1 | 1];
}
bool fuck = 0;
void update(int l, int r, int rt, int L, int R, int v) {
    if (l > R || r < L) return;
    if (L <= l && r <= R && l == r && maxflag[rt] + 1 == 0) {
        flag[rt] = -b[l];
        c[rt]++;
        maxflag[rt] = -b[l];
        return;
    }
    if (L <= l && r <= R && (maxflag[rt] + 1 < 0)) {
        maxflag[rt]++;
        flag[rt]++;
        return;
    }

    int m = (l + r) >> 1;
    pushdown(rt);
    if (L <= m) update(l, m, rt << 1, L, R, v);
    if (m < R) update(m + 1, r, rt << 1 | 1, L, R, v);
    pushup(rt);
}
long long query(int l, int r, int rt, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R && l == r && maxflag[rt] == 0) {
        c[rt]++;
        flag[rt] = -b[l];
        maxflag[rt] = -b[l];
        return c[rt];
    }
    if (L <= l && r <= R && maxflag[rt] < 0) return c[rt];
    long long ret = 0;
    int m = (l + r) >> 1;
    pushdown(rt);
    if (L <= m) ret += query(l, m, rt << 1, L, R);
    if (m < R) ret += query(m + 1, r, rt << 1 | 1, L, R);
    pushup(rt);
    return ret;
}
int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) == 2) {
        for (int i = 1; i <= n; i++) scanf("%lld", b + i);
        build(1, n, 1);
        memset(flag, 0, sizeof flag);
        for (int i = 0; i < k; i++) {
            int tmp1, tmp2;
            char op[100];
            scanf("%s", op);
            if (op[0] == 'a') {
                scanf("%d%d", &tmp1, &tmp2);
                update(1, n, 1, tmp1, tmp2, 1);
            } else {
                scanf("%d%d", &tmp1, &tmp2);
                printf("%lld", query(1, n, 1, tmp1, tmp2));
                puts("");
            }
        }
    }
    return 0;
}

J

题意

交换相邻数花费y 逆序数花费x 求最小花费

题解

判断x与y的大小

输出逆序数个数*min(x,y)

因为只需交换逆序数个数次就可以让逆序数个数为0

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define REP(i, x, n) for (int i = (x); i < (n); ++i)
#define PER(i, x, n) for (int i = (n) -1; i >= x; --i)
#define endl "\n"
#define DE puts("----------")
#define CASE(i, ans) cout << "Case #" << (i) << ": " << (ans) << "\n"
#define lowbit(x) ((x) & (-(x)))
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define PI acos(-1.0)
#define MOD 1000000007
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
__gnu_pbds::cc_hash_table<string, int> hash1;
__gnu_pbds::gp_hash_table<string, int> hash2;
__gnu_pbds::priority_queue<int> pq;
__gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag> rbtree;
typedef bitset<1005> Bitset;
const int maxn = 100050;
ll n, m, k;
const long long mod = 1000000007;
ll a[maxn],b[maxn];
ll merge_sort(int l, int r) {
    if (l == r) return 0;
    ll cnt = 0;
    int m = (l + r) >> 1;
    cnt = merge_sort(l, m) + merge_sort(m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++], cnt += (m - i + 1);
    }
    while (i <= m) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (i = l; i <= r; i++) a[i] = b[i];
    return cnt;
}
int main() {
    ios::sync_with_stdio(0);
    ll x,y;
    while(cin >> n >> x >> y){
        REP(i,1,n + 1){
            cin >> a[i];
        }
        ll sum = merge_sort(1,n);
        if (x >= y){
            cout << 1ll * sum * y << endl;
        }else{
            cout << 1ll * sum * x << endl;
        }
    }
}

本文链接:https://www.haolovej.com/post/hdumulti2.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。