牛客多校Round 5

Solved:3

rank:195

F. take

官方题解:小 A 在打开第 i 个箱子后会交换手中的钻石和第 i 个箱子中的钻石

当且仅当第 i个箱子的钻石是前 i 个箱子打开后出现的所有钻石里最大的。

那么要算概率的话，前面箱子中钻石大于等于它的打开后就不能有钻石
用树状数组维护一下

线段树(不会树状数组) 调了半天居然快速幂忘记写返回了

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <string.h>

using namespace std;

typedef long long ll;

const ll mod = ;

ll sum[];

int num[];

ll pow_mod(ll x, ll y)

{

    ll res = ;

    while(y)

    {

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

        y >>= ;

        x = x * x % mod;

    }

    return res;

}

struct node

{

    int p, d, id;

}E[];

bool cmp1(node A, node B)

{

    return A.d < B.d;

} 

bool cmp2(node A, node B)

{

    return A.id < B.id;

}

void pushup(int rt)

{

    sum[rt] = sum[rt << ] * sum[rt <<  | ] % mod;

}

void build(int l, int r, int rt)

{

    if(l == r)

    {

        sum[rt] = ;

        return;

    }

    int m = l + r >> ;

    build(l, m, rt << );

    build(m + , r , rt <<  | );

    pushup(rt);

}

void update(int k, ll v, int l, int r, int rt)

{

    if(l == r)

    {

        sum[rt] = v;

        return;

    }

    int m = l + r >> ;

    if(k <= m) update(k, v, l, m, rt << );

    else update(k, v, m + , r, rt <<  | );

    pushup(rt);

}

ll query(int ql, int qr, int l, int r, int rt)

{

    if(ql <= l && qr >= r) return sum[rt];

    ll res = ;

    int m = l + r >> ;

    if(ql <= m) res = res * query(ql, qr, l, m, rt << ) % mod;

    if(qr > m) res = res * query(ql, qr, m + , r, rt <<  | ) % mod;

    return res;

}

int main()

{

    int n;

    scanf("%d", &n);

    ll ny = pow_mod(, mod - );

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

    {

        scanf("%d%d", &E[i].p, &E[i].d);

        E[i].id = i;

        E[i].p =  - E[i].p;

    }

    sort(E + , E +  + n, cmp1);

    for(int i = ; i <= n; i++) num[E[i].id] = i;

    sort(E + , E +  + n, cmp2);

    build(, n, );

    ll ans = ;

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

    {

        int v = num[E[i].id];

        ans = (ans + query(v, n, , n, ) * ( - E[i].p) % mod * ny % mod) % mod;

        update(v, E[i].p * ny % mod, , n, );

    }

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

    return ;

}

H. subseq

题意:找一个字典序第k小的合法b数组使得以b数组的大小作为下标的a数组是严格上升的子序列

题解:用f(i)表示从第i个元素做为起始能组成的上升子序列个数

跃然纸上的转移 f(i) = 1 + ∑f(j) (i < j <= n && a(j) > a(i)) 这个用树状数组维护就好了

离散好以后从大到小的插入就可以

然后贪心的从1枚举在满足这个点a(i)大于上一个插入答案中的点的情况下

如果f(i) >= k就意味着这个点可以做为答案中的一位 k-- 就少了后面什么都不接的一种

如果f(i) < k 表示这个点显然不做为答案中的一位 k -= f[i] 把这些字典序比他小的答案全减去

还有个很坑的地方就是可能会爆ll 但是问的k只有1e18 所以判一下上界用我的写法用后缀和比较好

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll k;

struct node

{

    int val, id, v;

}a[];

ll c[];

ll f[];

int ans[];

bool cmp(node A, node B) {return A.val < B.val;}

bool cmp1(node A, node B) {return A.id < B.id;}

inline void add(int x, ll v)

{

    for( ; x > ; x -= x & -x)

    {

        c[x] += v;

        if(c[x] > 1e18) c[x] = 1e18;

    }

}

inline ll ask(int x)

{

    ll res = ;

    for( ; x <= n; x += x & -x)

    {

        res += c[x];

        if(res > 1e18) res = 1e18;

    }

    return res;

}

int main()

{

    scanf("%d%lld", &n, &k);

    for(int i = ; i <= n; i++) scanf("%d", &a[i].val), a[i].v = a[i].val, a[i].id = i;

    sort(a + , a +  + n, cmp);

    a[].val = ;

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

    {

        if(a[i].val == a[i - ].v) a[i].val = a[i - ].val;

        else a[i].val = a[i - ].val + ;

    }

    sort(a + , a +  + n, cmp1);

    for(int i = n; i >= ; i--)

    {

        //f[i] = ask(n) - ask(a[i].val * 1LL) + 1LL;

        //这样写会wa 因为两个都很大的情况下 返回1e18 但是一减去就没了

        f[i] = ask(a[i].val + ) + ;

        add(a[i].val, f[i]);

    }

    int cnt = ;

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

    {

        if(!k) break;

        if(a[i].val > a[ans[cnt]].val)

        {

            if(f[i] >= k) ans[++cnt] = i, k--;

            else k -= f[i];

        }

    }

    if(k) puts("-1");

    else

    {

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

        for(int i = ; i < cnt; i++) printf("%d ", ans[i]);

        printf("%d\n", ans[cnt]);

    }

    return ;

}

I. vcd

题意:n个点定义一个集合是好的为对于这个集合的任意一个子集以右开口的矩形把他包起来不会包含这个子集的其他点

　　求有多少个好的集合

题解:考虑一个点的话显然都满足

考虑两个点的话显然纵坐标相同的不满足情况那么统计答案就减去纵坐标相同的

考虑三个点的话显然是满足像小于符号的点才行(好像不是很显然但是多画几种情况就看出来了)

统计答案就是对于每个点在比这个点横坐标大的情况下在他上面的点 x 在他下面的点且任意两个点横坐标不能相同

所以我们用树状数组维护y 再按x从大到小的插入对于相同的x 都统计完答案后再一起插入

考虑四个点的话是找不到答案的简单的证明一下对于一个像红对勾形状的三个点

假设再加入一个点要满足答案那么新加入的点和任意两个点都能组成小于号

对于右边两个点要组成小于号要在下面哪个点下面

对于左边两个点要组成小于号要在上面哪个点上面这显然是矛盾的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = ;

ll n;

struct node

{

    int x, y, pre;

}p[];

int b[];

ll vis[];

ll c[];

bool cmp1(node A, node B) {return A.y < B.y;}

bool cmp2(node A, node B) {return A.x < B.x;}

inline void add(int x) {for( ; x <= n; x += x & -x) c[x]++;}

inline ll ask(int x) {ll res = ; for( ; x > ; x -= x & -x) res += c[x], res %= mod; return res;}

int main()

{

    scanf("%lld", &n);

    for(int i = ; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y), p[i].pre = p[i].y;

    sort(p + , p +  + n, cmp1);

    p[].y = ; vis[]++; //这沙雕地方卡了一晚上 写昏了

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

    {

        if(p[i].y == p[i - ].pre) p[i].y = p[i - ].y;

        else p[i].y = p[i - ].y + ;

        vis[p[i].y]++;

    }

    sort(p + , p +  + n, cmp2);

    ll ans = ;

    ans += 1LL * n + n * (n - 1LL) / 2LL;

    for(int i = ; i <= n; i++) ans -= vis[i] * (vis[i] - ) / ;

    ans %= mod;

    int now = n;

    for(int i = n; i >= ; i--)

    {

        ll tmp1 = ask(n) - ask(p[i].y);

        ll tmp2 = ask(p[i].y - );

        ans += tmp1 * tmp2 % mod;

        ans %= mod;

        if(p[i].x != p[i - ].x)

        {

            for(int j = now; j >= i; j--) add(p[j].y);

            now = i - ;

        }

    }

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

    return ;

}

巴特西

牛客多校Round 5

最新文章

热门文章