牛客多校第一场

A. Equivalent Prefixes

题意

两个序列相等的条件是RMQ(u,l,r) = RMQ(u,l,r)，($1\leq l \leq r\leq m$) ,RMQ(u,l,r)代表序列u，的任意区间(l,r）的最小值的序号，求一个最大的P，使得$\lbrace a_1, a_2,…a_p \rbrace$和$\lbrace b_1,b_2,…b_p \rbrace$相等

思路

我们假设$last_a[i]= max\lbrace j|j<i \&\& a_j<a_i\rbrace$ ,也就是$a_i$左边序号最大的小于$a_i$的数字的位置，

我们用单调栈去求这个last，求得以后

那么我们求序列[1,r]的RMQ，就是找到last[r],last[last[r]],last[last[last[r]],的值

如果两个序列的last数组相同，那么就证明$RMQ(a,l,r)=RMQ(b,l,r)$

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

int a[maxn], b[maxn];
int lasta[maxn], lastb[maxn];

stack<pis> sta;

int main() { 
    int n;
    while(~scanf("%d", &n)) {
        for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);
        while(!sta.empty()) sta.pop();
        sta.push(pis{0, 0});
        for (int i = 1; i <= n; i ++) {
            while(sta.top().first > a[i]) sta.pop();
            lasta[i] = sta.top().second;
            sta.push((pis{a[i], i})); 
        }
        while(!sta.empty()) sta.pop();
        sta.push(pis{0, 0});
        for (int i = 1; i <= n; i ++) {
            while(sta.top().first > b[i]) sta.pop();
            lastb[i] = sta.top().second;
            sta.push((pis{b[i], i})); 
        }
        int cnt = 0;
        for (int i = 1; i <= n; i ++) {
            if(lasta[i] == lastb[i]) cnt ++;
            else break;
        }
        cout << cnt << endl;
    }
    return 0;
}

B.Integration

题意

已知$\int_0^{\infty}\frac{1}{1+x^2}dx=\frac{\pi}{2}$

求：$\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod\limits_{i=1}^{n}(a_i^2+x^2)}dx$

思路

我们先算$\frac{1}{\prod\limits_{i=1}^{n}(a_i^2+x^2)}$
$=\frac{1}{a_1^2+x^2} \frac{1}{a_2^2+x^2}\frac{1}{\prod\limits_{i=3}^{n}a_i^2+x^2}\\
=\frac{1}{(a_2^2-a_1^2)}(\frac{1}{a_1^2+x^2}-\frac{1}{a_2^2+x^2})\frac{1}{\prod\limits_{i=3}^{n}a_i^2+x^2}\\
=\frac{1}{(a_2^2-a_1^2)}(\frac{1}{a_1^2+x^2}-\frac{1}{a_2^2+x^2})\frac{1}{a_3^2+x^2}\frac{1}{\prod\limits_{i=4}^{n}a_i^2+x^2}\\
=\frac{1}{(a_2^2-a_1^2)}(\frac{1}{a_1^2+x^2}\frac{1}{a_3^2+x^2}-\frac{1}{a_2^2+x^2}\frac{1}{a_3^2+x^2})\frac{1}{\prod\limits_{i=4}^{n}a_i^2+x^2}\\
=\frac{1}{(a_2^2-a_1^2)}(\frac{1}{(a_1^2-a_3^2)}(\frac{1}{a_3^2+x^2}-\frac{1}{a_1^2+x^2})-\frac{1}{(a_3^2-a_2^2)}(\frac{1}{a_2^2+x^2}-\frac{1}{a_3^2+x^2}))\frac{1}{\prod\limits_{i=4}^{n}a_i^2+x^2}\\
=(\frac{1}{a_2^2-a_1^2}\frac{1}{a_3^2-a_1^2})\frac{1}{a_1^2+x^2}+(\frac{1}{a_1^2-a_2^2}\frac{1}{a_3^2-a_2^2})\frac{1}{a_2^2+x^2}+(\frac{1}{a_1^2-a_3^2}\frac{1}{a_2^2-a_3^2})\frac{1}{a_3^2+x^2}\\
=…\\
=\sum\limits_{i=1}^{n}\frac{1}{\prod\limits_{j=1,j!=i}^{n}(a_j^2-a_i^2)}\frac{1}{a_i^2+x^2}$
我们设$c_i=\prod\limits_{j=1,j!=i}^{n}(a_j^2-a_i^2)$
$原式=\sum\limits_{i=1}^{n}\frac{1}{c_i}\frac{1}{a_i^2+x^2}$
那么
$\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod\limits_{i=1}^{n}(a_i^2+x^2)}dx\\
=\frac{1}{\pi}\int_0^{\infty}\sum\limits_{i=1}^{n}\frac{1}{c_i}\frac{1}{a_i^2+x^2}\\
=\frac{1}{\pi}\sum\limits_{i=1}^{n}\frac{1}{c_i}\int_0^{\infty}\frac{1}{a_i^2+x^2}\\
=\frac{1}{\pi}\sum\limits_{i=1}^{n}\frac{1}{c_i}\frac{\pi}{2a_i}\\
=\sum\limits_{i=1}^{n}\frac{1}{2c_ia_i}$

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

ll a[maxn], b[maxn];
int n;

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if(!b) {
        x = 1; y = 0;
        return a;
    }
    ll d = ex_gcd(b, a % b, x, y);
    ll t = x;
    x = y; y = t - a / b * y;
    return d;
}

ll getInv(ll a, ll p) {
    ll x, y;
    ex_gcd(a, p, x, y);
    x = ((x % p) + p) % p;
    return x;
}

ll solve(ll x, int idx) {
    ll res = x;
    for (int i = 1; i <= n; i ++) {
        if(i == idx) continue;
        res *= (b[i] - b[idx] + mod) % mod;
        res %= mod;
    }
    return getInv(res, mod);
}

int main() { 
    while(~scanf("%d", &n)) {
        for (int i = 1; i <= n; i ++) {
            scanf("%lld", &a[i]);
            b[i] = a[i] * a[i] % mod;
        }
        ll ans = 0;
        for (int i = 1; i <= n; i ++)
            ans = (ans + solve(a[i], i)) % mod;
        printf("%lld\n", ans * getInv(2, mod) % mod);
    }
    return 0;
}

C:Euclidean Distance

题意

给你一些点$(\frac{a_1}{m},\frac{a_2}{m},…,\frac{a_n}{m})$,让你找一些$p_i$,使得$\sum\limits_{i=1}^{n}(p_i-a_i)^2$最小,$p_i$满足$\sum\limits_{i=1}^{n}p_i=1,p_i>=0$

思路

听说题解是用拉格朗日乘子法，但我也不会，
我看到有别人用的是贪心
因为所有的$a_i$都是除以m的，所以我们把$a_i$和$p_i$都乘以m，那么我们就变成了用m步使得面积最小（负数的面积不能变小只能变大）

那么贪心的做法就是把大的尽量的变小，因为是排过序的，所以前面的要比后面的大。
每次都试着把前i-1块变得跟第i块平齐，如果不能就把前(i-1)块全部减小$\frac{k}{i-1}$,保持前面的平齐

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

ll a[maxn];

bool cmp(ll a, ll b) {
    return a > b;
}

ll gcd(ll a, ll b) {
    return !b ? a : gcd(b, a % b);
}

int main() {
    ll n, m;
    while(~scanf("%lld %lld", &n, &m)) {
        for (int i = 1; i <= n; i ++) 
            scanf("%lld", &a[i]);
        sort(a + 1, a + n + 1, cmp);
        ll k = m;
        for (int i = 2; i <= n; i ++) {
            if(k > (a[i-1] - a[i]) * (i-1)) {
                k -= 1ll * (a[i-1] - a[i]) * (i-1);
            }else {
                for (int j = 1; j <= i-1; j ++) 
                    a[j] = 1ll* (i-1) * a[i-1] - k;
                for (int j = i; j <= n; j ++)
                    a[j] = 1ll * a[j] * (i-1);
                m = 1ll * m * (i-1);
                k = 0;
                break;
            }
        }
        if(k) {
            for (int i = 1; i <= n; i ++) 
                a[i] = 1ll * (a[n] * n) - k;
            m = 1ll * m * n;
        }
        ll ans = 0; 
        for (int i = 1; i <= n; i ++) 
            ans = (ans + 1ll * a[i] * a[i]);
        m = 1ll * m * m;
        ll k1 = gcd(ans, m);
        ans /= k1;
        m /= k1;
        if(m == 1) printf("%lld\n", ans);
        else printf("%lld/%lld\n", ans, m);
    }
    return 0;
}

E:ABBA

题意

给你n个AB和m个BA，问你能构造出多少个长度为(n+m)*2并且能组成n个AB和B个BA的串

思路

如果我们把A看做-1，B看成1，那么构成串的前缀和应该在[-n,m]，如果不在就是不合法的串
然后我们在用dp[i][j]来表示构成串的前i+j位中有i个A,j个B，那么我们考虑dp[i][j]—>(dp[i+1][j],dp[i][j+1])
转移是只需要判断(dp[i+1][j],dp[i][j+1])是否合法即可

AC代码

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const int maxn = 2e3 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
 
ll dp[maxn][maxn];
 
int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i <= n + m; i ++)
            for (int j = 0; j <= n + m; j ++)
                dp[i][j] = 0;
        dp[0][0] = 1;
        for (int i = 0; i <= n+m; i ++) {
            for (int j = max(0, i-n); j <= min(n+m, i+m); j ++) {
                if(i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
                if(j) dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod;
            }
        }
        printf("%lld\n", dp[n+m][n+m]);
    }
    return 0;
}

H:XOR

题意

给你一堆数，让你找他们子集xor和位0的的子集的大小之和

思路

明显的线性集问题,首先我们要知道一堆数字组成线性集，

可以范围线性集外的数字和线性集内的数字，线性集内的数字可以xor出线性集外的所有子集

因为是问子集大小的和，所以我们可以转化成求每个数字的贡献

分为两种：我们设数字总数为$n$,线性集大小为$r$

1.线性集外数字的贡献：

因为线性集内的数字能把线性集外的所有子集xor出来。

我们枚举线性集外的每一个数字$x$，那么如果线性集内的数字能把$x$xor出来那么，$x$对应的

线性集外的子集大小就为$2^{n-r-1}$,即这个数字的贡献就为$2^{n-r-1}$

2.线性集内的数字的贡献：

对剩下的n-1个数字做一次线性集，看是否能把$x$xor出来，能xor出来贡献就为$2^{n-r-1}$，不能就为0

AC代码

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;
 
ll a[maxn];
bool vis[maxn];
vector<int> vec;
 
struct LB{
    ll b[65], cnt = 0;
    bool flag;
 
    void init() {
        memset(b, 0, sizeof(b));
        flag = false;
        cnt = 0;
    }
 
    void ins(ll x) {
        for (int i = 62; i >= 0; i --)
            if(x >> i) {
                if(!b[i]) { b[i] = x; cnt ++; return ; }
                x ^= b[i];
            }
            flag = true;
    }
 
    bool Fin(ll x) {
        if(x == 0 && flag) return true;
        for (int i = 62; i >= 0; i --) {
            if(x >> i) {
                x ^= b[i];
            }
        }
        return x == 0;
    }
}A, B, C;
 
ll Ksm(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
int main() {
    int n;
    while(~scanf("%d", &n)) {
        A.init(); B.init(); vec.clear();
        for (int i = 1; i <= n; i ++) {
            scanf("%lld", &a[i]);
            if(!A.Fin(a[i])) {
                A.ins(a[i]);
                vec.push_back(i);
            }else B.ins(a[i]);
        }
        ll r = A.cnt;
        if(n == r) {
            cout << 0 << endl;
            continue;
        }
        ll base = Ksm(2, n-r-1);
        ll sum = base * (n-r) % mod;
        for (auto &it: vec) {
            ll x = a[it];
            for (int i = 0; i <= 62; i ++)
                C.b[i] = B.b[i];
            C.flag = B.flag;
            for (auto &it2: vec)
                if(it != it2) C.ins(a[it2]);
            if(C.Fin(x)) sum = (sum + base) % mod;
        }
        printf("%lld\n", sum);
    }
    return 0;
}

I:Points Division

题意

给你n个点，把点划分成A,B两部分，规定$i\in A$ and $j\in B$ and $x_j \leq x_i$ and $y_i\leq y_j$

求最后$\sum\limits_{i\in A}a_i+\sum\limits_{j\in B}b_j$ 的最大值

思路

我们发现$A$位于左上角，$B$位于右上角，$AB$边界时一条不下降的折线,所以我们可以沿着这条折线进行$dp$，

我们规定折线上的点全是$B$上的点。

首先我们先把纵坐标离散化，然后用$dp[i]$来表示当高度为i时最大值为多少

然后我们来求每一个点对结果的贡献，

对于一个点$i$,有两种情况:

​ 一：这个点不在折线上，那么大于$y_i$并且在折线上面的点$j$，$i$相当于位于$B$，那么$i$对于$j$的贡献就是$b_i$,对于那些小于$y_i$并且在折线上面的点$k$，$i$相当于位于$A$，那么$i$对$k$的贡献就是$a_i$,

​ 二：这个点在折线上，$dp[i]$就由从$1到i-1$的点的最大值+$b_i$ 也就是$dp[i] = \max\limits_{1\leq j < i} dp[j] + b_i$

大体思路就是这样，因为我们要对区间操作，所以要用一个线段树来维护一下

注意

因为我们默认折线上的点全是属于$B$的点，这就导致不会有$A=P$ and $B=\emptyset$的情况，但是我们在点中加入一个$(0,0)$的点，因为$1\leq x_i, y_i\leq 10^9$那么所有的点都位于$(0,0)$上面，对$(0,0)$的贡献就是$B=\emptyset$的值

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 5;

struct Node{
    ll x, y, a, b;

    bool friend operator < (Node a, Node b) {
        if(a.x == b.x) return a.y > b.y;
        return a.x < b.x;
    }

}node[maxn];
ll ty[maxn];

struct Seg{
    ll dp[maxn<<2], lazy[maxn<<2];

    void Build(int rt, int l, int r) {
        if (l == r) {
            dp[rt] = 0;
            lazy[rt] = 0;
            return ;
        }
        lazy[rt] = 0; dp[rt] = 0;
        int m = (l + r) >> 1;
        Build(rt<<1, l, m);
        Build(rt<<1|1, m+1, r);
    }

    void down(int rt) {
        lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt];
        dp[rt<<1] += lazy[rt]; dp[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }

    void Updata(int rt, int l, int r, int L, int R, ll v) { //区间更新
        if(l >= L && r <= R) {
            dp[rt] += v;
            lazy[rt] += v;
            return ;
        }
        if(lazy[rt]) down(rt);
        int m = (l + r) >> 1;
        if(L <= m) Updata(rt<<1, l, m, L, R, v);
        if(R > m) Updata(rt<<1|1, m+1, r, L, R, v);
        dp[rt] = max(dp[rt<<1], dp[rt<<1|1]);
    }

    void Updata(int rt, int l, int r, int w, ll v) { //单点更新
        if(l == r) {
            dp[rt] = max(dp[rt], v);
            return ;
        }
        if(lazy[rt]) down(rt);
        int m = (l + r) >> 1;
        if(w <= m) Updata(rt<<1, l, m, w, v);
        else Updata(rt<<1|1, m+1, r, w, v);
        dp[rt] = max(dp[rt<<1], dp[rt<<1|1]);
    }

    ll Query(int rt, int l, int r, int L, int R) {
        if(l >= L && r <= R) return dp[rt];
        ll Max = 0;
        int m = (l + r) >> 1;
        if(L <= m) Max = max(Max, Query(rt<<1, l, m, L, R));
        if(R > m) Max = max(Max, Query(rt<<1|1, m+1, r, L, R));
        return Max;
    }
}seg;


int main() {
    int n;
    while(~scanf("%d", &n)) {
        int cnt = 0;
        ty[cnt++] = 0;
        node[0] = Node{0, 0, 0, 0};
        for (int i = 1; i <= n; i ++) {
            scanf("%lld %lld %lld %lld", &node[i].x, &node[i].y, &node[i].a, &node[i].b);
            ty[cnt++] = node[i].y;
        }
        sort(ty, ty + cnt);
        cnt = unique(ty, ty+cnt) - ty;
        for (int i = 0; i <= n; i ++) 
            node[i].y = lower_bound(ty, ty + cnt, node[i].y) - ty + 1;
        sort(node, node + 1 + n);
        seg.Build(1, 1, cnt);
        for (int i = 0; i <= n; i ++) {
            if(node[i].y < cnt) seg.Updata(1, 1, cnt, node[i].y+1, cnt, node[i].b); //[node.y+1~cnt]+a
            seg.Updata(1, 1, cnt, node[i].y, seg.Query(1, 1, cnt, 1, node[i].y)+node[i].b);//dp[i] = max
            if(node[i].y > 1) seg.Updata(1, 1, cnt, 1, node[i].y-1, node[i].a);//[1~node.y] + b
        }
        printf("%lld\n", seg.dp[1]);
    }

    return 0;
}