2019牛客暑期多校训练营（第一场）

A.Equivalent+Prefixes

思路：

二分答案，然后运用单调栈求出右边第一个比它小的数，若对于每一个二分答案左边的每一个数右边第一个比它小的数位置必须相同。

#include<bits/stdc++.h>
 
using namespace std;
 
const int N=200000;
int s[N],tot,a[N],b[N],f1[N],c[N],d[N],f2[N],n;
bool check(int x)
{
    for (int i=1; i<=x; i++)
    {
        if (f1[i]!=f2[i])
        {
            return 0;
        }
    }
    return 1;
}
 
void work(int a[],int f[],int d[],int n)
{
    tot=0;
    for (int i=n; i>=1; i--)
    {
        while (tot>0&&s[tot]>a[i])
        {
            tot--;
        }
        s[++tot]=a[i];
        if (tot>1)
        {
            f[i]=d[s[tot-1]];
        }
        else
        {
            f[i]=-1;
        }
    }
}
 
int main()
{
    while(~scanf("%d",&n))
    {
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            c[a[i]]=i;
        }
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&b[i]);
            d[b[i]]=i;
        }
        int l=1,r=n,ans=1;
        while (l<=r)
        {
            int mid=(l+r)>>1;
            work(a,f1,c,mid);
            work(b,f2,d,mid);
            if (check(mid))
            {
                l=mid+1;
                ans=mid;
            }
            else
            {
                r=mid-1;
            }
        }
        printf("%d
",ans);
    }
}

J.Fraction Comparision

不用说了，太简单了

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
ll x, y, a, b;
 
int main() {
    while(scanf("%lld%lld%lld%lld", &x, &y, &a ,&b) == 4) {
        __int128 tmp1 = 1, tmp2 = 1;
        tmp1 = tmp1 * x * b;
        tmp2 = tmp2 * y * a;
        if(tmp1 == tmp2) puts("=");
        else if(tmp1 < tmp2) puts("<");
        else puts(">");
    }
    return 0;
}

F.Random Point in Triangle

#include<bits/stdc++.h>
using namespace std;
long long  ans,vecx1,vecx2,vecy1,vecy2,x1,x2,x3,yy,y2,y3;
int main()
{
    while (~scanf("%lld%lld%lld%lld%lld%lld",&x1,&yy,&x2,&y2,&x3,&y3))
    {
       vecx1=x2-x1;
       vecy1=y2-yy;
       vecx2=x3-x1;
       vecy2=y3-yy;
       ans=11*abs(vecx1*vecy2-vecy1*vecx2);
       cout<<ans<<endl;
    }
}

 B.Integration

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000;
const ll p=1e9+7;
ll pow1(ll a,ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

ll inv(ll x) {
    return pow1(x, p - 2);
}

ll k,n,a[N],c[N],ans,ret;
int main(){
    k=inv(2);
    while (~scanf("%lld",&n)){
        ans=0;
        for (int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        for (int i=1;i<=n;i++){
            ret=1;
            for (int j=1;j<=n;j++){
                if (i==j) continue;
                ret=ret*(a[j]*a[j]%p-a[i]*a[i]%p+p)%p;
            }
            c[i]=inv(ret);
        }
        for (int i=1;i<=n;i++){
            ans=(ans+c[i]*k%p*inv(a[i]))%p;
        }
        printf("%lld
",ans);
    }
}

 E.ABBA

 

 思路

思考这样一个问题：给你一个长为2*(n+m)的字符串，判断它是否能分解出n个’AB’和m个’BA‘。

贪心的思想，我们从前往后扫一遍，遇到A，如果还有’AB’没分到’A’，就把这个’A’分给’AB‘，否则看看’BA’种是否有分到了’B’但还没有分到’A’的，如果有，就把这个’A’分给他，如果没有，那么这个’A’就无法和任何东西配，这个字符串就不满足条件。
有了分配’A’和’B’的原则之后，我们就可以开始dp了。dp[i][j]表示放了i个’A’，j个’B’后依然有可能满足条件的方案数。
dp[i][j]的转移：
考虑放‘A’：
如果当前已经放的‘A’的个数比需要的’AB’个数少，可以直接放
如果当前已经放的’A’的个数大于等于n了，看看放了多少个‘B’，如果放的’B‘的个数小于多出来的’A’，可以直接放。
所以 dp[i+1][j] += dp[i][j] (i < n + j)
'B’同理。

这题的关键是要先想好怎么去分配A和B的归属，然后再去想dp。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2002;
const ll p=1e9+7;
ll n,m,f[N][N];
int main() {
    while (~scanf("%lld%lld", &n, &m)) {
        for (int i = 0; i <= n + m; i++) {
            for (int j = 0; j <= n + m; j++) {
                f[i][j] = 0;
            }
        }
        f[0][0] = 1;
        for (int i = 0; i <= n + m; i++) {
            for (int j = 0; j <= n + m; j++) {
                if (i < n + j) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % p;
                if (j < m + i) f[i][j + 1] = (f[i][j + 1] + f[i][j]) % p;
            }
        }
        printf("%lld
", f[n + m][n + m]);
    }
}

 c.Euclidean Distance

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10010;
ll n,m,a[N],now,sum[N],ansa,ansb;
int main() {
    while (~scanf("%lld%lld", &n, &m)) {
        now = n;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        sort(a + 1, a + n + 1, greater<int>());
        sum[0] = -m;
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = 1; i < n; i++) {
            if (sum[i] > a[i + 1] * i) {
                now = i;
                break;
            }
        }
        ansa = sum[now] * sum[now] * now;
        ansb = now * now;
        for (ll i = now + 1; i <= n; i++) {
            ansa += a[i] * a[i] * ansb;
        }
        ansb *= m * m;
        ll d = __gcd(ansa, ansb);
        ansa /= d;
        ansb /= d;
        if (ansb == 1 || ansa == 0) {
            printf("%lld
", ansa);
        } else {
            printf("%lld/%lld
", ansa, ansb);
        }
    }
}
 

 H.XOR

 I.Points Division

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL N = 100010;
const LL M = 999999999999999999LL;
 
LL n, num;
LL p[N];
map<LL, LL>m;
 
LL lazy[N << 2];
struct Node {
    LL l, r, v;
} t[N << 2];
 
struct Data {
    LL x, y, a, b;
} w[N];
 
inline bool cmp(Data a, Data b)
{
    if (a.x == b.x) return a.y > b.y;
    return a.x < b.x;
}
 
inline void pushdown(LL x)
{
    t[x << 1].v += lazy[x];
    t[x << 1 | 1].v += lazy[x];
    lazy[x << 1] += lazy[x];
    lazy[x << 1 | 1] += lazy[x];
    lazy[x] = 0;
}
 
void buildtree(LL x, LL l, LL r)
{
    t[x].l = l, t[x].r = r, t[x].v = -M, lazy[x] = 0;
    if (l == r) return;
    register int mid = (l + r) >> 1;
    buildtree(x << 1, l, mid), buildtree(x << 1 | 1, mid + 1, r);
}
 
void change(LL x, LL l, LL r, LL z)
{
    if (t[x].l == l && t[x].r == r) {
        t[x].v += z, lazy[x] += z;
        return;
    }
    if (lazy[x]) pushdown(x);
    register LL mid = (t[x].l + t[x].r) >> 1;
    if (r <= mid) change(x << 1, l, r, z);
    else if (l > mid) change(x << 1 | 1, l, r, z);
    else change(x << 1, l, mid, z), change(x << 1 | 1, mid + 1, r, z);
    t[x].v = max(t[x << 1].v, t[x << 1 | 1].v);
}
 
void change(LL x, LL pos, LL z)
{
    if (t[x].l == t[x].r) {
        t[x].v = max(t[x].v, z);
        return;
    }
    if (lazy[x]) pushdown(x);
    register LL mid = (t[x].l + t[x].r) >> 1;
    if (pos <= mid) change(x << 1, pos, z);
    else change(x << 1 | 1, pos, z);
    t[x].v = max(t[x << 1].v, t[x << 1 | 1].v);
}
 
LL query(LL x, LL l, LL r)
{
    if (t[x].l == l && t[x].r == r) return t[x].v;
    if (lazy[x]) pushdown(x);
    register LL mid = (t[x].l + t[x].r) >> 1;
    if (r <= mid) return query(x << 1, l, r);
    else if (l > mid) return query(x << 1 | 1, l, r);
    else return max(query(x << 1, l, mid), query(x << 1 | 1, mid + 1, r));
}
 
int main()
{
    while (scanf("%lld", &n) != EOF) {
        num = 0;
        for (register LL i = 1; i <= n; ++i) {
            scanf("%lld %lld %lld %lld", &w[i].x, &w[i].y, &w[i].a, &w[i].b);
            p[i] = w[i].y;
        }
        sort(p + 1, p + n + 1);
        for (register LL i = 1; i <= n; ++i) {
            if (p[i] != p[i - 1]) m[p[i]] = ++num;
        }
        for (register LL i = 1; i <= n; ++i) {
            w[i].y = m[w[i].y];
        }
        sort(w + 1, w + n + 1, cmp);
        buildtree(1, 0, num);
        change(1, 0, 0);
        register LL z;
        for (register LL i = 1; i <= n; ++i) {
            z = query(1, 0, w[i].y);
            change(1, w[i].y, z + w[i].b);
            if (w[i].y != num) change(1, w[i].y + 1, num, w[i].b);
            change(1, 0, w[i].y - 1, w[i].a);
        }
        printf("%lld
", t[1].v);
    }
    return 0;
}