2019牛客暑期多校第一场题解ABCEFHJ

A.Equivalent Prefixes

题意：给你两个数组，求从第一个元素开始到第p个元素满足任意区间值最小的元素下标相同的 p的最大值。

题解：我们可以从左往右记录到i为止每个区间的最小值有哪些，因为每个值都是不一样的，对于当前的 i 如果1~i中每个区间最小值数量相同那么下标肯定也会相同，否则记录的值的数量就会不同，我们可以用单调栈记录目前为止每个区间的“最小值”的下标，栈里面元素数量不同时肯定不满足条件。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5 + ;

int a[N],b[N],u[N],v[N];

int main() {

    int n;

    while(~scanf("%d",&n)) {

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

        for (int i = ; i <= n; i++) scanf("%d",&b[i]);

        int i,cnt1=,cnt2=;

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

            while (cnt1 && a[i] < a[u[cnt1]]) cnt1--;

            u[++cnt1] = i;

            while (cnt2 && b[i] < b[v[cnt2]]) cnt2--;

            v[++cnt2] = i;

            if (cnt1 != cnt2) break;

        }

        printf("%d\n", i-);

    }

    return ;

}

B.Integration

传送门

题意：已知求输出。

题解：

参考博客：　https://blog.csdn.net/mmk27_word/article/details/96450520

　　　　　　https://www.cnblogs.com/yanlifneg/p/11211455.html#commentform

代码：

#include <cstdio>

#include <cstring>

#define ll long long

using namespace std;

const int N =  + ;

const ll mod = 1e9 + ;

ll a[N],b[N];

ll qp(ll a,ll b) {

    ll ans = ;

    a%=mod;

    while(b) {

        if (b&) ans = ans * a % mod;

        a = a * a % mod;

        b >>= ;

    }

    return ans;

}

int main() {

    int n;

    while(~scanf("%d",&n)) {

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

            scanf("%lld",&a[i]);

        ll ans = ;

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

            b[i] =  * a[i] % mod;

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

                if (i != j) b[i] = b[i] * ((a[j]*a[j]-a[i]*a[i])%mod) %mod;

            b[i] = qp(b[i],mod-);

            ans = ((ans + b[i]) % mod + mod) % mod;

        }

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

    }

    return ;

}

C.Euclidean Distance

传送门

题意：在一个n维坐标系里面有个点A(a1/m,a2/m,...,an/m)，在坐标系中找到一个点P(p1,p2,...,pn)满足pi>0且∑ⁿ_i₌₁ pi =1，求满足条件的P到A的

最小欧几里得距离∑ⁿ_i₌₁ (ai/m−pi)^2

题解：为了方便计算我们可以先约去m最后再将结果除以m^2，就成了求∑ⁿ_i₌₁ (ai−pi)^2 /m^2，∑ⁿ_i₌₁ pi =m。显然我们减小数值大的ai的值比减小值小的ai更优。

我们先将ai排序，为了使得最大值更小，我们可以每次把最大值更新到与下一个值相同大小。我们初始化能更新到的数组长度num = n,可以用来减小ai的值have = m。

如果have的值能够将前i个元素更新为a[i+1]则更新；否则num更新为i，剩余的have平分到前num个元素上，此时前num个元素的值都是a[num]-have/num。剩下的n-num个元素值为ai。

此时∑ⁿ_i₌₁ (ai−pi)^2 /m^2 =(num*(a[num]-have/num)^2+∑ⁿ_i_=num+1a[i]^2)/m^2。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e4 + ;

const int M = ;

const ll mod = 1e9 + ;

int a[N];

int main() {

    int n,m;

    while(~scanf("%d%d",&n,&m)) {

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

            scanf("%d",&a[i]);

        }

        sort(a+,a+n+,greater<int>());

        int num = n,have = m;

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

            if (i* (a[i]-a[i+])<= have)

                have -= i*(a[i]-a[i+]);

            else {

                num = i;

                break;

            }

        }

        ll fm = 1ll * num * m * m;

        ll fz = (1ll*a[num]*num - have) * (1ll*a[num]*num - have) ;

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

            fz += 1ll*num*a[i]*a[i];

        ll tf = __gcd(fz,fm);

        fz/=tf;fm/=tf;

        if (fm ==  ) printf("%lld\n", fz);

        else printf("%lld/%lld\n", fz,fm);

    }

    return ;

}

E：ABBA

传送门

题意：有一个长度2(n+m)的字符串，它可以被分解成n个AB，m个BA，问有多少种符合条件的字符串，答案% 10^9+7

题解：贪心，我们先用AB的A，再用BA的B，B同理。我们可以用dp[i][j]表示用了i个A和j个B组成合法序列的方案数，因为我们先用AB的A（AB有n个），再用BA的A，所以A的数量最多可以有B的数量+n个，当A的数量没这么多时可以在字符串中加个A，即 if (i-j<n) dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod; B同理。

代码：

#include <cstdio>

#include <cstring>

#define ll long long

using namespace std;

const int N =  + ;

const ll mod = 1e9 + ;

ll dp[N][N];

int main() {

    int n,m;

    while(~scanf("%d%d",&n,&m)) {

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

            for (int j = ; j <= n+m; j++) dp[i][j] = ;

        dp[][] = ;

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

            for (int j = ; j <= n+m; j++) {

                if (i-j<n) dp[i+][j] = (dp[i+][j]+dp[i][j])%mod;

                if (j-i<m) dp[i][j+] = (dp[i][j+]+dp[i][j])%mod;

            }

        printf("%lld\n",dp[n+m][n+m]);

    }

    return ;

}

F:Random Point in Triangle

传送门

题意：在△ABC中任选一个点P，P与A、B、C三点相连，求最大的面积的期望E = max{S△PBC，S△APC，S△ABP} * 36的结果。

题解：E= 11/36 * S△ABC => 36E = 11 S△ABC

证明参考：https://www.cnblogs.com/WAautomaton/p/11211864.html

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

    ll x1,x2,x3,y1,y2,y3;

    while(~scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3))

        printf("%lld\n", abs(*(x1*y2+x2*y3+x3*y1-x1*y3-x3*y2-x2*y1)));

    return ;

}

H.XOR

传送门

题意：给你一个有n个元素的集合a，问a的异或和为0的所有子集的元素数量和。

题解：我们可以转化为求每个数能异或为0的贡献。这里要用到线性基 <--- 推荐博客。

　　　我们先求集合a的线性基A，A中元素数量为r，对于线性基外n-r个元素，任选一个还剩n-r-1个，那么这n-r个元素每个的贡献为2^(n-r-1);

　然后我们考虑线性基内的元素x，我们对剩下n-1个数求线性基，避免超时我们先对线性基A外的n-r个元素求线性基B，然后在计算线性基A内各个元素x的贡献时，将B数组赋值给C再将A内其他元素加入C内，如果x加不进则求x的贡献。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5 + ;

const int M = ;

const ll mod = 1e9 + ;

ll a[N],b[N],A[M],B[M],C[M];

bool add(ll arr[],ll x) {

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

        if (x & (1ll<<i)) {

            if (arr[i]) x^=arr[i];

            else {

                arr[i] = x;

                return true;

            }

        }

    }

    return false;

}

ll qp(ll y){

    ll ans = ,x = ;

    while(y) {

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

        x = x * x % mod;

        y>>=;

    }

    return ans;

}

int main() {

    int n;

    while(~scanf("%d",&n)) {

        memset(A,,sizeof(A));

        memset(B,,sizeof(B));

        int r = ;

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

            scanf("%lld",&a[i]);

            if (add(A,a[i])) b[r++] = a[i];

            else add(B,a[i]);

        }

        if (r == n) {

            printf("0\n");

            continue;

        }

        ll ans = (n-r) * qp(n-r-) %mod;

        for (int i = ; i < r; i++) {

            for (int j = ; j <= ; j++) C[j] = B[j];

            for (int j = ; j < r; j++)

                if (i!=j) add(C,b[j]);

            if (!add(C,b[i])) ans = (ans + qp(n-r-)) % mod;

        }

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

    }

    return ;

}

J.Fraction Comparision

传送门

题意：比较x/a和y/b的大小关系。

题解：因为 0≤ x,y ≤10^18，所以我们可以先比较整数部分，当整数部分相同时再把余数交叉相乘比较大小。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N =  + ;

int main() {

    ll x,y,a,b;

    while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b)) {

        ll t1 = x/a, t2 = y/b;

        if (t1 < t2) printf("<\n");

        else if (t1 > t2) printf(">\n");

        else {

            t1 = x%a*b;

            t2 = y%b*a;

            if (t1 < t2) printf("<\n");

            else if (t1 > t2) printf(">\n");

            else if (t1 == t2) printf("=\n");

        }

    }

    return ;

}

巴特西

2019牛客暑期多校第一场题解ABCEFHJ

最新文章

热门文章