2019牛客多校 Round7

Solved:5

Rank:296

E Find the median (线段树)

题意:最开始一个空的数组 4e5次操作每次把Li，Ri中的每个数插入进来问当前的中位数

题解:把这n个区间离散化去重以后剩下m个点可以分成m-1个连续的区间

　　有个巧妙的方法是把所有的右端点+1后每两个点之间表示一个左闭右开的区间

　　然后线段树每个叶子节点就表示这个区间的信息每次操作就是先区间更新再查询了

　　用la表示这个区间被覆盖了多少次查询的时候类似整体二分其实还可以维护一个叶子节点表示的区间长度

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 4e5 + 5;

int n, cnt;

int a1, b1, c1, m1;

int a2, b2, c2, m2;

int x[MAXN], y[MAXN];

int p[MAXN << 1], L[MAXN], R[MAXN];

ll pre[MAXN << 1];

ll sum[MAXN << 5];

int la[MAXN << 5];

int lz[MAXN << 5];

void pushup(int rt) {

    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

}

void pushdown(int l, int r, int rt) {

    if(lz[rt]) {

        lz[rt << 1] += lz[rt];

        lz[rt << 1 | 1] += lz[rt];

        la[rt << 1] += lz[rt];

        la[rt << 1 | 1] += lz[rt];

        int mid = l + r >> 1;

        sum[rt << 1] += 1LL * lz[rt] * (pre[mid] - pre[l - 1]);

        sum[rt << 1 | 1] += 1LL * lz[rt] * (pre[r] - pre[mid]);

        lz[rt] = 0;

    }

}

void update(int ql, int qr, int l, int r, int rt) {

    if(ql <= l && qr >= r) {

        lz[rt]++; la[rt]++;

        sum[rt] += pre[r] - pre[l - 1];

        return;

    }

    pushdown(l, r, rt);

    int mid = l + r >> 1;

    if(ql <= mid) update(ql, qr, l, mid, rt << 1);

    if(qr > mid) update(ql, qr, mid + 1, r, rt << 1 | 1);

    pushup(rt);

}

int query(int l, int r, int rt, ll k) {

    if(l == r) return p[l] + (k - 1) / la[rt];

    pushdown(l, r, rt);

    int mid = l + r >> 1;

    if(sum[rt << 1] >= k) return query(l, mid, rt << 1, k);

    else return query(mid + 1, r, rt << 1 | 1, k - sum[rt << 1]);

}

int main() {

    cnt = 0;

    scanf("%d", &n);

    scanf("%d%d%d%d%d%d", &x[1], &x[2], &a1, &b1, &c1, &m1);

    scanf("%d%d%d%d%d%d", &y[1], &y[2], &a2, &b2, &c2, &m2);

    for(int i = 3; i <= n; i++) {

        x[i] = (1LL * a1 * x[i - 1] + 1LL * b1 * x[i - 2] + 1LL * c1) % m1;

        y[i] = (1LL * a2 * y[i - 1] + 1LL * b2 * y[i - 2] + 1LL * c2) % m2;

    }

    for(int i = 1; i <= n; i++) {

        L[i] = min(x[i], y[i]) + 1;

        R[i] = max(x[i], y[i]) + 2;

        p[++cnt] = L[i], p[++cnt] = R[i];

    }

    sort(p + 1, p + 1 + cnt);

    cnt = unique(p + 1, p + 1 + cnt) - p - 1;

    p[cnt + 1] = p[cnt];

    for(int i = 1; i <= cnt; i++) pre[i] = pre[i - 1] + 1LL * (p[i + 1] - p[i]);

    ll tot = 0;

    for(int i = 1; i <= n; i++) {

        int t1 = lower_bound(p + 1, p + 1 + cnt, L[i]) - p;

        int t2 = lower_bound(p + 1, p + 1 + cnt, R[i]) - p - 1;

        update(t1, t2, 1, cnt, 1);

        tot += 1LL * (R[i] - L[i]); //左闭右开

        printf("%d\n", query(1, cnt, 1, (tot + 1LL) / 2LL));

    }

    return 0;

}

E Find the median

F Energy Stones

题意:n个石头初始能量Ei 每秒能量增长Li 最多能量Ci

　　有m次收割操作每次选择一个时间点将区间L，R内的石头能量都吸收求最后一共吸收了多少能量

题解:因为他是问的最后一共吸收了多少能量不是问的每一次

　　所以我们可以考虑每一个石头对答案产生了多少贡献

　　对于每一个石头这m次收割只有部分收割到了它假设收割了k次

　　如果我们知道了这k个时间点除去第一个特判以外每两个时间点之间会产出一次贡献

　　贡献要么是Ci 要么是Li*区间长度

　　对于n个石头被收割的时间点有许多重复的所以我们用set维护收割的时间点

　　在枚举到到第L个石头的时候把时间点插入进set 在枚举到底R + 1个石头的时候删除这个时间点

　　然后一个树状数组维护长度为i的区间个数一个树状数组维护长度为i的区间长度和

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;

int n, m;

int E[MAXN], L[MAXN], C[MAXN];

ll a[MAXN << 1], b[MAXN << 1];

vector<int> g[MAXN];

set<int> st;

ll query1(int x) {

    ll res = 0;

    for(int i = x; i; i -= (i & -i)) res += a[i];

    return res;

}

ll query2(int x) {

    ll res = 0;

    for(int i = x; i; i -= (i & -i)) res += b[i];

    return res;

}

void add(int x, int val) {

    for(int i = x; i <= 200001; i += (i & -i)) {

        if(val > 0) a[i]++;

        else a[i]--;

        b[i] += 1LL * val;

    }

}

void inser(int x) {

    if(st.empty()) {

        st.insert(x);

        return;

    }

    auto pos = st.lower_bound(x);

    if(pos == st.begin()) {

        int t = (*pos) - x;

        add(t, 1LL * t);

    } else if(pos == st.end()) {

        int t = x - (*(prev(pos)));

        add(t, 1LL * t);

    } else {

        int t1 = x - (*(prev(pos)));

        int t2 = (*pos) - x;

        add(t1, 1LL * t1); add(t2, 1LL * t2);

        add(t1 + t2, 1LL * (-t1 - t2));

    }

    st.insert(x);

}

void del(int x) {

    auto pos = st.find(x);

    if(st.size() == 1) {

        st.erase(pos);

        return;

    }

    if(pos == st.begin()) {

        int t = (*(next(pos))) - x;

        add(t, 1LL * -t);

    } else if(pos == prev(st.end())) {

        int t = x - (*(prev(pos)));

        add(t, 1LL * -t);

    } else {

        int t1 = x - (*(prev(pos)));

        int t2 = (*(next(pos))) - x;

        add(t1, 1LL * -t1); add(t2, 1LL * -t2);

        add(t1 + t2, 1LL * (t1 + t2));

    }

    st.erase(pos);

}

int main() {

    int T;

    scanf("%d", &T);

    int cas = 0;

    while(T--) {

        st.clear();

        ll ans = 0;

        scanf("%d", &n);

        for(int i = 1; i <= n; i++) scanf("%d%d%d", &E[i], &L[i], &C[i]);

        for(int i = 1; i <= n + 1; i++) g[i].clear();

        memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));

        scanf("%d", &m);

        for(int i = 1; i <= m; i++) {

            int t, l, r; scanf("%d%d%d", &t, &l, &r);

            g[l].push_back(t);

            g[r + 1].push_back(-t);

        }

        for(int i = 1; i <= n; i++) {

            for(int j = 0; j < g[i].size(); j++) {

                if(g[i][j] > 0) inser(g[i][j]);

                else del(-g[i][j]);

            }

            if(st.empty()) continue;

            ans += min(1LL * C[i], 1LL * E[i] + 1LL * (*st.begin()) * L[i]);

            if(L[i] == 0) continue;

            int len = C[i] / L[i];

            ans += 1LL * query2(len) * L[i];

            ans += 1LL * C[i] * (st.size() - query1(len) - 1);

        }

        printf("Case #%d: %lld\n", ++cas, ans);

    }

    return 0;

}

F Energy stones

H pair

题意:给三个数a,b,c 求有多少对数满足 x & y > c || x ^ y < c x的范围在1-a y的范围在1-b；

题解:第一次写这种两个范围的数位DP.. 需要存的状态有

　　当前枚举到pos位 And=0表示x&y和c的大小不确定 1表示x&y已经大于c 2表示已经小于

　　 Xor同理然后存一下当前枚举两个数卡到的边界

　　因为数位dp是从0开始统计的还多统计了0^y(y<c) 和x^0(x<c) 的答案所以还要减去

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a, b, c;

ll dp[35][3][3][2][2];

ll dfs(int pos, int And, int Xor, int sj1, int sj2) {

    if(pos == -1) {

        if(And == 1 || Xor == 1) return 1;

        else return 0;

    }

    if(dp[pos][And][Xor][sj1][sj2] != -1) return dp[pos][And][Xor][sj1][sj2];

    ll res = 0;

    int up1 = sj1 ? (a >> pos & 1) : 1;

    int up2 = sj2 ? (b >> pos & 1) : 1;

    for(int i = 0; i <= up1; i++)

    for(int j = 0; j <= up2; j++) {

        int tand = And;

        int txor = Xor;

        if(tand == 0) {

            if((i & j) > (c >> pos & 1)) tand = 1;

            else if((i & j) < (c >> pos & 1)) tand = 2;

        }

        if(txor == 0) {

            if((i ^ j) < (c >> pos & 1)) txor = 1;

            else if((i ^ j) > (c >> pos & 1)) txor = 2;

        }

        res += dfs(pos - 1, tand, txor, sj1 && (i == up1), sj2 && (j == up2));

    }

    dp[pos][And][Xor][sj1][sj2] = res;

    return res;

}

int main() {

    memset(dp, -1, sizeof(dp));

    int T;

    scanf("%d", &T);

    while(T--) {

        memset(dp, -1, sizeof(dp));

        scanf("%d%d%d", &a, &b, &c);

        printf("%lld\n", dfs(31, 0, 0, 1, 1) - min(a, c - 1) - min(b, c - 1) - 1);

    }

    return 0;

}

H pair

I Chessbord

题意:给出n,m 问构造一个k*k的矩阵矩阵每个元素不小于m

　　且从每一行选一个数且这k个数的属于不同的列方案数

题解:枚举矩阵大小k 再枚举选出的k个元素的和j 为了计算方便这个j等于实际的和减去k*m 那么元素大小可为0

　　我们发现合法的方案一定长这个样子假定k为3

　　 a1+b1　　a2+b1　　a3+b1

　　 a1+b2　　a2+b2　　a3+b2

　　 a1+b3　　a2+b3　　a3+b3

　　这样我们随便选出的和一定都等于a1+a2+a3+b1+b2+b3 这就是我们枚举的和j

　　这个方案数就等于C(j+2*k-1，2*k-1) 因为元素可以为0 那么我们让这2k项每个都先+1 分配完了再-1

　　等价于从j+2*k-1个空位中插2*k-1个板子当然这样计算是有重复的

　　重复是因为假如让a1,a2,a3都加1 b1,b2,b3都减1 只要b都非负这个方案是一样的但是也计数了

　　所以我们就要减去b1,b2,b3都大于0的情况了那么就等于让k项都+1 分配完了再-1

　　综上所述一次枚举的方案数=C(j+2*k-1，2*k-1) - C(j+k-1，2*k-1)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;

ll jc[5005], ny[5005];

ll n, m;

ll pow_mod(ll x, ll y) {

    ll res = 1;

    while(y) {

        if(y & 1) res = res * x % mod;

        x = x * x % mod;

        y >>= 1;

    }

    return res;

}

ll C(ll x, ll y) {

    if(x < 0 || y < 0 || x < y) return 0;

    return jc[x] * ny[y] % mod * ny[x - y] % mod;

}

int main() {

    jc[0] = 1LL;

    for(ll i = 1; i <= 5000; i++) jc[i] = jc[i - 1] * i % mod;

    ny[5000] = pow_mod(jc[5000], mod - 2);

    for(ll i = 4999; i >= 0; i--) ny[i] = ny[i + 1] * (i + 1) % mod;

    int T;

    scanf("%d", &T);

    while(T--) {

        scanf("%lld%lld", &n, &m);

        ll ans = 0;

        for(ll i = 1; i <= n; i++) {

            if(i * m > n) break;

            for(ll j = 0; j <= n; j++) {

                if(i * m + j > n) break;

                ans += C(j + 2 * i - 1, 2 * i - 1) - C(j + i - 1, 2 * i - 1);

                ans %= mod;

            }

        }

        printf("%lld\n", (ans + mod) % mod);

    }

    return 0;

}

I Chessbord

巴特西

2019牛客多校 Round7

最新文章

热门文章