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

A-Equivalent Prefixes

（单调栈，思维，笛卡尔树）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int ans1[maxn],ans2[maxn];
int val1[maxn],val2[maxn];
struct node
{
    int val,index;
};
  
int main()
{
    int n,i;
    stack<node> s;
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
        cin>>val1[i];
        for(i=1;i<=n;i++)
        cin>>val2[i];
        val1[0]=val2[0]=-1;
        for(i=n;i>=0;i--)
        {
            while(!s.empty()&&s.top().val>val1[i])
            {
                ans1[s.top().index]=i;
                s.pop();
            }
            s.push(node{val1[i],i});
        }
        for(i=n;i>=0;i--)
        {
            while(!s.empty()&&s.top().val>val2[i])
            {
                ans2[s.top().index]=i;
                s.pop();
            }
            s.push(node{val2[i],i});
        }
        for(i=1;i<=n;i++)
        {
             if(ans1[i]!=ans2[i])
             break;
        }
        cout<<i-1<<endl;  
    }
    return 0;
}

B-Integration

（数学积分推导，分式分解技巧，快速幂，逆元）

写这道题首先要知道部分分式分解这个技巧：

假定$p_1$,$p_2$,………$p_n$均为实数，且无重根，例如，考虑如下的变换式求其逆变换：

$F(s)=\frac{A(s)}{(s-p_1)(s-p_2)(s-p_3)}$

式子中分母多项式的阶次高于分子多项式的阶次。这时$F(s)$可以分解为以下形式：

$F(s)=\frac{K_1}{(s-p_1)}+\frac{K_2}{(s-p_2)}+\frac{K_3}{(s-p_3)}$

其中 $K_i=(s-p_i)F(s)|（s=p_i)$

知道这个结论后，开开始看原题的那个式子：$\frac{1}{\pi}\int1^\infty\frac{1}{\prod{i=1}^{n}(a^2_i+x^2)}dx$

先考虑$\frac{1}{\prod_{i=1}^{n}(a^2_i+x^2)}$，我们可以用上面的公式进行变换，得到：

$\sum{i=1}^n\frac{C_i}{(a^2_i+x^2)}$ 其中 $C_i=\frac{1}{\prod{i!=j}^{}(a^2_j-a^2_i)}$

因此原式：$\frac{1}{\pi}\int1^\infty\frac{1}{\prod{i=1}^{n}(a^2_i+x^2)}dx=\sum_1^n\frac{C_i}{2a_i}\pi$

所以暴力就完事了。

#include <iostream>
#include <algorithm>
 
#define int long long
 
using namespace std;
 
const int N = 1e3+5;
const int Mod = 1e9+7;
int a[N];
 
inline int qpow(int a,int b){
    a%=Mod;
    int res = 1;
    while(b){
        if(b&1) res = res*a%Mod;
        a = a*a%Mod;
        b>>=1;
    }
    return res;
}
 
inline int inv(int x){
    return qpow(x,Mod-2);
}
 
int32_t main() {
 
    ios_base::sync_with_stdio(false);cin.tie(0);
 
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            int p = 1;
            for(int j=0;j<n;j++){
                if(i==j) continue;
                p = p*((a[j]*a[j]-a[i]*a[i])%Mod)%Mod;
            }
            p = 2*a[i]*p%Mod;
            p = inv(p);
            ans = (ans+Mod+p)%Mod;
        }
 
        cout<<ans<<endl;
 
    }
 
    return 0;
}

C- Euclidean Distance

照着唯神的思路写的，没用分数类，导致最后细节太多还是没处理好。
放一个正解，没用标解中的拉格朗日乘数法。
在这里插入图片描述

(数学推导)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000;
int m,n;
struct frac
{
    ll p,q;
    frac(){}
    frac(ll _p,ll _q)
    {
        if(_p<0&&_q<0) _p=-_p,_q=-_q;
        else
            if(_q<0) _q=-_q,_p=-_p;
        //cout<<"ce "<<_p<< " "<<_q<<endl;
        p=_p/__gcd(abs(_p),abs(_q));
        q=_q/__gcd(abs(_p),abs(_q));
        //cout<<"ce "<<p<< " "<<q<<endl;
    }
    bool operator < (const frac &x) const
    {
        return p*x.q<q*x.p;
    }
    bool operator <= (const frac &x) const
    {
        return p*x.q<=q*x.p;
    }
    bool operator == (const frac &x) const
    {
        return p==x.p&&q==x.q;
    }
    frac operator + (const frac &x)
    {
        return frac(p*x.q+q*x.p,q*x.q);
    }
    frac operator * (const frac &x)
    {
        return frac(p*x.p,q*x.q);
    }
    frac operator / (const frac &x)
    {
        return frac(p*x.q,q*x.p);
    }
    frac operator - (const frac &x)
    {
        return frac(p*x.q-q*x.p,q*x.q);
    }
}a[maxn+5];
int main()
{
 
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;++i)
        {
            int x;
            scanf("%d",&x);
            a[i]=frac(x,m);
        }
        sort(a+1,a+n+1);
        //for(int i=1;i<=n;++i) cout<<a[i].p<<" "<<a[i].q<<endl;
        frac now(1,1);
        frac left(1,1);
        frac pos(0,0);
        for(int i=n-1;i>=1;--i)
            if((a[i+1]-a[i])*now<=left) left=left-(a[i+1]-a[i])*now,now.p+=1;
            else
            {
                pos=a[i+1]-left/now;
                break;
            }
       // cout<<"left : "<<left.p<<" "<<left.q<<endl;
        //cout<<now.p<<endl;
        if(pos.p==0&&pos.q==0)
        {
           // assert(now.p==n);
           //a[1]-left/now
            //cout<<"ok"<<endl;
            pos=a[1]-left/now;
            //cout<<pos.p<<" "<<pos.q<<endl;
        }
        frac ans(0,1);
        for(int i=1;i+now.p<=n;++i) ans=ans+a[i]*a[i];
        ans=ans+now*pos*pos;
        if(ans.p==0) printf("0\n");
        else if(ans.q==1) printf("%lld\n",ans.p);
        else printf("%lld/%lld\n",ans.p,ans.q);
    }
    return 0;
}

F-Random Point in Triangle

(数学推导，期望)

选三个中点，连接中线，利用中心的性质即可得出，具体推倒不算特别简单，还需要再画辅助线，代换等数学推导。

其实最简单的方法就是猜性质，我们画一个特例的等边三角形来算，这样节省了许多不必要的计算。

#include <iostream>
#include <algorithm>
 
#define int long long
using namespace std;
 
 
int32_t main() {
 
    ios_base::sync_with_stdio(false);cin.tie(0);
 
    int x1,x2,x3,y1,y2,y3;
    while(cin>>x1>>y1>>x2>>y2>>x3>>y3){
        int s = (x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)*11;
        cout<<abs(s)<<endl;
    }
 
    return 0;
}

J-Fraction Comparision

(签到题)

C++:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int x,a,y,b;
    while(scanf("%lld%lld%lld%lld",&x,&a,&y,&b)!=EOF){
        long long int i,o;
        i=x/a;
        o=y/b;
        if(i>o)printf(">\n");
        else if(i<o) printf("<\n");
        else {
            x=x%a*b;y=y%b*a;
            if(x>y)printf(">\n");
            else if(x<y) printf("<\n");
            else printf("=\n");
        }
    }
    return 0;
 }

python：

import sys
 
for line in sys.stdin:
    a,b,c,d = map(int,line.split(' '))
    if a*d>b*c:
        print('>')
    elif a*d==b*c:
        print('=')
    elif a*d<b*c:
        print('<')

ACM-牛客多校

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

ACM-树状数组基础上一篇

ACM-思维构造题（2019暑假集训）下一篇

2019牛客暑假多校训练（第一场）题解