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

约定不等于承诺〃 2021-11-27 04:44 347阅读 0赞

## **Solutions** ##

--------------------

### **A：Equivalent Prefixes** ###

题意：

若$\\text\{RMQ(u,l,r)=RMQ(v,l,r)\}$ for all $1\{\\leq\}l\{\\leq\}r\{\\leq\}m$，则为$\\text\{equivalent\}$

其中$\\text\{RMQ(w,l,r)\}$的定义是$\{\[l,r\]\}$区间内最小数的下标

给两个数组，每组元素各不相同，求最大的$p\{\\leq\}n\\ where\\ \\\{a\_1,a\_2,\{\\ldots\}a\_p\\\} are\\ equivalent$

单调栈思路：

处理出每一位左边第一个比它小的下标，然后相同的话可取，不同不可取。

假如当前处理$a\_i$，(也就是$\\\{a\_1,a\_2,\{\\ldots\}a\_\{i-1\}\\\}$满足条件)，假设比它第一个小的是$last\[i\]$，那么$last\[i\]$右边的$RMQ$一定是$a\_i$，这样的话，$last\[i\]$左边的$RMQ$一定与新数无关，因为仅仅$last\[i\]$处就已经比$a\_i$小了。

可以利用单调栈求每一位左边第一个比它小的下标

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=1e5+10;
     4 
     5 int n,a[maxn],b[maxn],ida[maxn],idb[maxn];
     6 
     7 stack<pair<int,int> > s;
     8 
     9 int main() {
    10     while(~scanf("%d",&n)) {
    11         s.push(make_pair(-1,-1));
    12         for(int i=0;i<n;i++) {
    13             scanf("%d",&a[i]);
    14             while(!s.empty()&&s.top().first>a[i]) s.pop();
    15             ida[i]=s.top().second;
    16             s.push(make_pair(a[i],i));
    17         }
    18         while(!s.empty()) s.pop();
    19         s.push(make_pair(-1,-1));
    20         for(int i=0;i<n;i++) {
    21             scanf("%d",&b[i]);
    22             while(!s.empty()&&s.top().first>b[i]) s.pop();
    23             idb[i]=s.top().second;
    24             s.push(make_pair(b[i],i));
    25         }
    26         int cur=0;
    27         while(cur<n) {
    28             if(ida[cur]==idb[cur]) cur++;
    29             else break;
    30         }
    31         printf("%d\n",cur);
    32     }
    33     return 0;
    34 }

二分+分治+ST思路：

通过$ST$表预处理出$RMQ$，$p$具有单调性，可以二分判断是否满足条件，然后询问$1\{\\sim\}mid$最小值，再分治

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=100010;
     4 
     5 int dpa[maxn][20],dpb[maxn][20],a[maxn],b[maxn];
     6 int mm[maxn],n,ida[maxn],idb[maxn];
     7 
     8 void init() {
     9     mm[0]=-1;
    10     for(int i=1;i<=n;i++) {
    11         mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
    12         dpa[i][0]=a[i];
    13         dpb[i][0]=b[i];
    14     }
    15     for(int j=1;j<=mm[n];j++) {
    16         for(int i=1;i+(1<<j)-1<=n;i++) {
    17             dpa[i][j]=min(dpa[i][j-1],dpa[i+(1<<(j-1))][j-1]);
    18             dpb[i][j]=min(dpb[i][j-1],dpb[i+(1<<(j-1))][j-1]);
    19         }
    20     }
    21 }
    22 
    23 int rmqa(int x,int y) {
    24     int k=mm[y-x+1];
    25     return ida[min(dpa[x][k],dpa[y-(1<<k)+1][k])];
    26 }
    27 
    28 int rmqb(int x,int y) {
    29     int k=mm[y-x+1];
    30     return idb[min(dpb[x][k],dpb[y-(1<<k)+1][k])];
    31 }
    32 
    33 bool dfs(int l,int r) {
    34     if(l>=r) return true;
    35     int x=rmqa(l,r);
    36     int y=rmqb(l,r);
    37     if(x!=y) return false;
    38     else return dfs(1,x-1)&&dfs(y+1,r);
    39 }
    40 
    41 bool check(int mid) {
    42     return dfs(1,mid);
    43 }
    44 
    45 int main() {
    46     while(~scanf("%d",&n)) {
    47         for(int i=1;i<=n;i++) {
    48             scanf("%d",&a[i]);
    49             ida[a[i]]=i;
    50         }
    51         for(int i=1;i<=n;i++) {
    52             scanf("%d",&b[i]);
    53             idb[b[i]]=i;
    54         }
    55         init();
    56         int l=1,r=n,ans=1;
    57         while(l<=r) {
    58             int mid=(l+r)>>1;
    59             if(check(mid)) {
    60                 ans=mid;
    61                 l=mid+1;
    62             } else {
    63                 r=mid-1;
    64             }
    65         }
    66         printf("%d\n",ans);
    67     }
    68 }

### B: Integration ###

题意：

给出$n$个数，$a\_1,a\_2,\\ldots,a\_n$，求$\\frac1\\pi\\int\_0^\{\\infty\}\\frac1\{\\prod\_\{i=0\}^n(a\_i^2+x^2)\}dx$

因为分母是连乘积，所以可以列项拆分。推几项可以得出规律

[具体参考这里][Link 1]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=1010;
     4 typedef long long ll;
     5 const int mod=1e9+7;
     6 
     7 ll a[maxn];
     8 int n;
     9 
    10 ll q_power(ll a,ll b) {
    11     ll ans=1,tmp=a%mod;
    12     while(b) {
    13         if(b&1) ans=ans*tmp%mod;
    14         tmp=tmp*tmp%mod;
    15         b>>=1;
    16     }
    17     return ans;
    18 }
    19 
    20 int main() {
    21     while(~scanf("%d",&n)) {
    22         for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    23         ll ans=0;
    24         for(int i=1;i<=n;i++) {
    25             ll tmp=1;
    26             for(int j=1;j<=n;j++) {
    27                 if(i==j) continue;
    28                 tmp=tmp*(((a[j]*a[j]%mod)-(a[i]*a[i]%mod)+mod)%mod)%mod;
    29             }
    30             tmp=tmp*2*a[i]%mod;
    31             ans=(ans+q_power(tmp,mod-2))%mod;
    32         }
    33         printf("%lld\n",ans);
    34     }
    35 }

### C：Euclidean Distance ###

题意：

给出$A$点的$n$维坐标$A=(a\_1/m,a\_2/m,\\ldots,a\_n/m)$，请找一点$P=(p\_1,p\_2,\\ldots,p\_n)$，满足一下条件

*  $p\_1,p\_2,\\ldots,p\_n\\ \\in\{\\mathbb\{R\}\}$
 *  $p\_1,p\_2,\\ldots,p\_n\{\\geq\}0$
 *  $p\_1+p\_2+\\ldots+p\_n=1$

使得$\\sum\_\{i=1\}^n(a\_i/m-p\_i)^2$最小。

思路：

[参考这里][Link 2]

首先，我们可以将$p$的坐标放大m倍,那么答案可以转化为：

$\\sum\_\{i=1\}^n(a\_i/m-p\_i)^2\\ =\\ \\sum\_\{i=1\}^n\[m(a\_i/m-p\_i)\]^2\\ \\Rightarrow\\ \\frac1\{m^2\}\\sum\_\{i=1\}^n(a\_i-mpi)^2$

考虑$a\_i$为每个矩形的高，减去的$m$相当于削减矩形的高度，首先将$a\_1,a\_2,\\ldots,a\_n$降序排列。证：

削减高度较大的收益会比削减高度较小的收益更大，（比如负数，减去数反而变大了）。

如图中的绿线，把矩形一点一点往下推，然后下一步一起推，道理同上。

若不能进一步往下推，就把整体减一点点。可以预处理出前缀和。然后判断够不够把$a\_i$前面的全部推平。

具体细节可以见上面大佬的博客。

![1445840-20190724093907345-1520460287.jpg][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 int n,m,a[10010],sum[10010];
     5 
     6 bool cmp(int a,int b) {
     7     return a>b;
     8 }
     9 
    10 int main() {
    11     while(~scanf("%d%d",&n,&m)) {
    12         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    13         sort(a+1,a+n+1,cmp);
    14         sum[0]=-m;
    15         for(int i=1;i<=n;i++) {
    16             sum[i]=sum[i-1]+a[i];
    17         }
    18         ll frac1,frac2;
    19         int now=n;
    20         for(int i=1;i<n;i++) {
    21             if(sum[i]>a[i+1]*i) {
    22                 now=i;
    23                 break;
    24             }
    25         }
    26         frac1=1ll*sum[now]*sum[now]*now;
    27         frac2=now*now;
    28         for(int i=now+1;i<=n;i++) {
    29             frac1+=1ll*a[i]*a[i]*frac2;
    30         }
    31         frac2=frac2*1ll*m*m;
    32         ll tmp=__gcd(frac1,frac2);
    33         if(frac2/tmp==1) printf("%lld\n",frac1/tmp);
    34         else if(!(frac1/tmp)) printf("0\n");
    35         else printf("%lld/%lld\n",frac1/tmp,frac2/tmp);
    36     }
    37 }

###  E：ABBA ###

题意：

给出$2(n+m)$个$A,B$构成序列，求可以划分为$n$个$AB$，$m$个$BA$的序列的个数。

思路：

首先贪心的想，前$n$个$A$是$AB$的$A$，前$m$个$B$是$BA$的$B$。

然后$dp\[i\]\[j\]$表示放了$i$个$A$，$j$个$B$的方案数。

若$i\{\\leq\}n$，$A$可以直接放

若$j\{\\leq\}m$，$B$可以直接放

若$i-n\{\\leq\}j$，即现在用于组合$BA$的$A$的数量小于$B$的数量，$A$可以放

若$j-m\{\\leq\}i$，即现在用于组合$AB$的$B$的数量小于$A$的数量，$B$可以放

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int mod=1e9+7;
     4 
     5 int dp[2010][2010];
     6 int n,m;
     7 
     8 int main() {
     9     while(~scanf("%d%d",&n,&m)) {
    10         for(int i=0;i<=n+m;i++) {
    11             for(int j=0;j<=n+m;j++)
    12                 dp[i][j]=0;
    13         }
    14         dp[0][0]=1;
    15         for(int i=0;i<=n+m;i++) {
    16             for(int j=0;j<=n+m;j++) {
    17                 if(i-n<j) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
    18                 if(j-m<i) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
    19             }
    20         }
    21         printf("%d\n",dp[n+m][n+m]);
    22     }
    23 }

### F：Random Point in Triangle ###

题意：

给出三角形三点坐标$A,B,C$，求

$$E=max\\\{S\_\{PAB\},S\_\{PBC\},S\_\{PCA\}\\\}$$

输出$36\{\\times\}E$

思路：

暂时只知道$ans=22\{\\times\}S\_\{ABC\}$，证明不会，记一下叉积求面积。$S\_\{ABC\}=\\frac12\\vec\{AB\}\{\\times\}\\vec\{AC\}$

1 #include<iostream>
     2 #include<cstdio>
     3 #define lowbit(x) (x&(-x))
     4 #include<cstring>
     5 using namespace std;
     6 typedef long long ll;
     7 
     8 int main() {
     9     ll x1,y1,x2,y2,x3,y3;
    10     while(~scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3)) {
    11         ll ans=abs(x2*y3-x2*y1-x1*y3-y2*x3+x1*y2+y1*x3);
    12         printf("%lld\n",22/2*ans);
    13     }
    14 }

### **J：Fraction Comparision** ###

题意：

判断$\\frac\{x\}a$与$\\frac\{y\}b$的大小关系

*  $0\{\\leq\}x,y\{\\leq\}10^\{18\}$
 *  $1\{\\leq\}a,b\{\\leq\}10^9$

思路：

*  不能用浮点数判断(精度不够？)
 *  把$\\frac\{x\}a$写成$\{\\lfloor\}\{\\frac\{x\}a\}\{\\rfloor\}+\{x\\%a\}$ 先比较整数部分，再交叉相乘比较分数

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 void out(ll x,ll y) {
     6     if(x==y)  puts("=");
     7     else if(x>y) puts(">");
     8     else puts("<");
     9 }
    10 
    11 
    12 int main() {
    13     ll x,a,y,b;
    14     while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b)) {
    15         ll A=x/a;
    16         ll B=y/b;
    17         x%=a;
    18         y%=b;
    19         if(A!=B) out(A,B);
    20         else out(x*b,y*a);
    21     }
    22     return 0;
    23 }

转载于:https://www.cnblogs.com/ACMerszl/p/11211445.html

[Link 1]: https://blog.csdn.net/ftx456789/article/details/96451366?tdsourcetag=s_pctim_aiomsg
[Link 2]: https://blog.nowcoder.net/n/1539da6d6d6e47a6998b5c6f5bba2167?tdsourcetag=s_pcqq_aiomsg
[1445840-20190724093907345-1520460287.jpg]: /images/20211126/58df2c4f640741eb9719acd8c21dcbc6.png