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

Result

AC: 3/10, J A F
Rank: 359/890
Upsolved: 2/7, E B

J. Fraction Comparision

思路

直接交叉相乘会爆ll，比赛时__int128爆过去了
实际上，化成带分数比较就好了

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
int main()
{
  ll x,a,y,b;
  while (cin>>x>>a>>y>>b) {
    ll ans=0;
    if (x/a==y/b) {
      x=x%a,y=y%b;
      ans=x*b-y*a;
    } else {
      ans=x/a-y/b;
    }
  
    if (ans>0) {
      puts(">");
    } else if (ans==0) {
      puts("=");
    } else {
      puts("<");
    }
  }
  return 0;
}

A. Equivalent Prefixes

思路

单调栈处理出每个元素作为最小值的左端点

从左往右扫一遍，对应元素左端点不相同则跳出
可以证明，某个位置的右端点不同不影响结论

min(rightA[i], rightB[i])+1处的leftA和leftB一定不同

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
const int MAXN=(int)1e5+10;
int a[MAXN],b[MAXN];
int la[MAXN],lb[MAXN];
//
void init(int num[],int l[]int n);
//
int main()
{
  int n;
  while (cin>>n) {
    for (int i=1;i<=n;i++) {
      scanf("%d",a+i);
    }
    for (int i=1;i<=n;i++) {
      scanf("%d",b+i);
    }
    init(a,la,n);
    init(b,lb,n);

    int ans=1;
    for (int i=1;i<=n;i++) {
      if (la[i]!=lb[i]) {
        break;
      }
      ans=i;
    }
    printf("%d\n",ans);
  }
  return 0;
}

void init(int num[],int l[],int n)
{
  stack<int> s;
  for (int i=1;i<=n;i++) {
    while (!s.empty() && num[i]<num[s.top()]) {
      s.pop();
    }
    if (s.empty()) {
      l[i]=1;
    } else {
      l[i]=s.top()+1;
    }
    s.push(i);
  }
}

F. Random Point in Triangle

思路

显然是个多重积分，但是我不会求（摊手）

考虑到答案一定是个整数，蒙特卡洛跑一下找规律
发现答案是面积的22倍，玄学选手实锤
顺便学会了三角形面积计算公式

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
int main()
{
  ll x1,y1,x2,y2,x3,y3;
  while (cin>>x1>>y1>>x2>>y2>>x3>>y3) {
    ll ans=abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)*11;
    printf("%lld\n",ans);
  }
  return 0;
}

E. ABBA

思路

贪心一下，前n个A作为AB的A，答案是最优的

如果作为BA的A，显然可以从后面随便抓个A来匹配B

同样的，前m个B一定是BA的B

dp[i][j]表示用了i个A，j个B的方案数，枚举下一个位置放A或B

i<n，直接放A，dp[i+1][j]+=dp[i][j]
i>=n，确保A能匹配BA的B，即出现在所有B后面，给了的小于需要的，i-n<min(j,m)
j<m，直接放B，dp[i][j+1]+=dp[i][j]
j>=m，确保B能匹配AB的A，即出现在所有A后面，给了的小于需要的，j-m<min(i,n)

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
const ll mod=(ll)1e9+7;
const int MAXN=(int)2e3+10;
ll dp[MAXN][MAXN];
//
int main()
{
  int n,m;
  while (cin>>n>>m) {
    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=0;j<=n+m;j++) {
        if (i<n || i-n<min(j,m)) {
          dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
        }
        if (j<m || j-m<min(i,n)) {
          dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
        }
      }
    }

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

B. Integration

思路

根据裂项相消法，有 $\cfrac{1}{(x^2+a^2)(x^2+b^2)}=\cfrac{1}{(x^2+a^2)(b^2-a^2)}+\cfrac{1}{(x^2+b^2)(a^2-b^2)}$ ，可以用数学归纳法推广到任意有限项

所以 $\cfrac{1}{\coprod_{i=1}^n (a_i^2+x^2)}=\sum_{i=1}^{n}{\cfrac{c_i}{a_i^2+x^2}}$ ，其中 $c_i=\cfrac{1}{\coprod_{j\ne i}(a_j^2-a_i^2)}$

而 $\int_{0}^{\infty} \cfrac{c_i}{a_i^2+x^2}dx=\cfrac{c_i}{2a_i}\pi$

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define debug(x) cout<<#x<<' '<<x<<endl
//
const ll mod=(ll)1e9+7;
const int MAXN=(int)1e3+10;
ll a[MAXN];
//
ll qPow(ll a,ll n,ll m);
//
int main()
{
  int n;
  while (cin>>n) {
    for (int i=1;i<=n;i++) {
      scanf("%lld",a+i);
    }

    ll ans=0;
    for (int i=1;i<=n;i++) {
      ll c=1;
      for (int j=1;j<=n;j++) {
        if (j==i) {
          continue;
        }
        c=(a[j]*a[j]-a[i]*a[i])%mod*c%mod;
      }
      c=qPow(c,mod-2,mod);
      ans=(ans+c*qPow(a[i]*2%mod,mod-2,mod)%mod)%mod;
    }
    if (ans<0) {
      ans+=mod;
    }

    printf("%lld\n",ans);
  }
  return 0;
}

ll qPow(ll a,ll n,ll m)
{
  ll ans=1,res=a%m;
  while (n) {
    if (n&1) ans=ans*res%m;
    res=res*res%m;
    n>>=1;
  }
  return ans;
}