2019牛客多校第一场

A.Equivalent Prefixes

传送：https://ac.nowcoder.com/acm/contest/881/A

题意：定义$RMQ(u,l,r)=RMQ(v,l,r)$为，对于任意$1 le l le r le m$，总是存在区间内最小值的位置相同。

现在给定两个长度为$n$的数组$a,b$，求解最大的$p$，使得$RMQ(a,1,p)=RMQ(b,1,p)$。

数据范围：$1<=n<=1e5，1<=a_i,b_i<=n$，同时$a_i,b_i$不重复

$1 \leq n \leq 10^{5}$

考虑两个数组之间值的变化趋势，对于每增加进来一个$a_i$，去看在$1-a_i-1$内最大的位置，就是说，比$a_i$小的数的最大的位置是多少。然后去比较$a,b$两个数组每次查询的答案是否一致，一致就代表插入到当前位置时，最小值的位置一致。否则直接break就好。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=1e9;
 4 const int maxn=1e5+10;
 5 struct node{
 6     int l,r;
 7     int mx;
 8 }tree1[maxn<<2],tree2[maxn<<2];
 9 int a[maxn],b[maxn];
10 void pushup1(int root){
11     tree1[root].mx=max(tree1[root<<1].mx,tree1[root<<1|1].mx);
12 }
13 void build1(int root,int l,int r){
14     tree1[root].l=l; tree1[root].r=r;tree1[root].mx=0;
15     if (l==r){return ;} 
16     int mid=(l+r)>>1;
17     build1(root<<1,l,mid);
18     build1(root<<1|1,mid+1,r);
19     pushup1(root);
20 }
21 void pushup2(int root){
22     tree2[root].mx=max(tree2[root<<1].mx,tree2[root<<1|1].mx);
23 }
24 void build2(int root,int l,int r){
25     tree2[root].l=l; tree2[root].r=r;tree2[root].mx=0;
26     if (l==r){return ;} 
27     int mid=(l+r)>>1;
28     build2(root<<1,l,mid);
29     build2(root<<1|1,mid+1,r);
30     pushup2(root);
31 }
32 void update1(int root,int xx,int val){
33     if (tree1[root].l==tree1[root].r && tree1[root].l==xx){
34         tree1[root].mx=val;
35         return ;
36     }
37     int mid=(tree1[root].l+tree1[root].r)>>1;
38     if (xx<=mid) update1(root<<1,xx,val);
39     else update1(root<<1|1,xx,val);
40     pushup1(root);
41 }
42 void update2(int root,int xx,int val){
43     if (tree2[root].l==tree2[root].r && tree2[root].l==xx){
44         tree2[root].mx=val;
45         return ;
46     }
47     int mid=(tree2[root].l+tree2[root].r)>>1;
48     if (xx<=mid) update2(root<<1,xx,val);
49     else update2(root<<1|1,xx,val);
50     pushup2(root);
51 }
52 int query1(int root,int l,int r){
53     if (l<=tree1[root].l && tree1[root].r<=r){
54         return tree1[root].mx;
55     }
56     int mid=(tree1[root].l+tree1[root].r)>>1;
57     int res=0;
58     if (mid>=l) res=max(res,query1(root<<1,l,r));
59     if (mid<r) res=max(res,query1(root<<1|1,l,r));
60     return res; 
61 }
62 int query2(int root,int l,int r){
63     if (l<=tree2[root].l && tree2[root].r<=r){
64         return tree2[root].mx;
65     }
66     int mid=(tree2[root].l+tree2[root].r)>>1;
67     int res=0;
68     if (mid>=l) res=max(res,query2(root<<1,l,r));
69     if (mid<r) res=max(res,query2(root<<1|1,l,r));
70     return res; 
71 }
72 int main(){
73     int n;
74     while (~scanf("%d",&n)){
75         build1(1,0,n);
76         build2(1,0,n);
77         for (int i=1;i<=n;i++) scanf("%d",&a[i]);
78         for (int i=1;i<=n;i++) scanf("%d",&b[i]);
79         int ans;
80         for (int i=1;i<=n;i++){
81             int xx=query1(1,0,a[i]-1),yy=query2(1,0,b[i]-1);
82             if (xx==yy) ans=i;
83             else break;
84             update1(1,a[i],i);
85             update2(1,b[i],i);
86         }    
87         printf("%d
",ans);
88     }
89     return 0;
90 }

B.Integration

传送：https://ac.nowcoder.com/acm/contest/881/B

题意：已知公式$int_{0}^{infty}frac{1}{1+x^2}dx=frac{pi}{2}$ ，求解公式$frac{1}{pi}frac{1}{prod_{i=1}^{n}(a_i^2+x^2)}dx$。要求输出$(pcdot q^{-1})mod(1e9+7)$。

数据范围：$1<=n<=1000,1<=a_i<=10^9$。

分析：根据已知公式，推导出$int_{0}^{infty}frac{1}{a_i^2+x^2}dx=frac{pi}{2a_i}$。然后考虑将求解的式子裂项化解。

指路网友博客：https://blog.csdn.net/dillonh/article/details/96445321

（推了我一下午哭哭，，

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

E.ABBA

传送：https://ac.nowcoder.com/acm/contest/881/E

题意：构造一个长度为$2(n+m)$的只包含A和B的字符串，要求能够划分成$n$个$AB$串和$m$个$BA$串。

数据范围：$0<=n,m<=1000$。

分析：指路队友博客：https://blog.csdn.net/qq_43813163/article/details/96446287

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2007;
 4 const int mod=1e9+7;
 5 int dp[maxn][maxn];//dp[i][j] 有i个A和j个B
 6 int main(){
 7     int n,m;
 8     while (~scanf("%d%d",&n,&m)){
 9         for (int i=0;i<=n+m;i++)//memset超时
10             for (int j=0;j<=n+m;j++) dp[i][j]=0;
11         dp[0][0]=1;//0个A 0个B 只有一种方案
12         for (int i=0;i<=n+m;i++){
13             for (int j=0;j<=n+m;j++){
14                 //填一个A进去 从dp[i-1][j]转移来
15                 //要满足的条件是 此时填入的A小于n个 
16                 //或者 已经填入的A的个数减已经填入的B的个数不大于n 满足n个AB（不能超过n）
17                 if(i && (i<=n || i-j<=n)) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
18                 //类似同理
19                 if(j && (j<=m || j-i<=m)) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
20             }
21         }
22         printf("%d
",dp[n+m][n+m]);
23     }
24     return 0;
25 }

F.Random Point in Triangle

传送：https://ac.nowcoder.com/acm/contest/881/F

题意：给定一个三角形，在三角形内任取一个点，将三角形面积划分为三部分。取面积较大的一部分算入答案，即$E=max{S_(PAB),S_(PBC),S_(PCA)}$，问答案的期望是多少。输出$E36$。

数据范围：三角形点坐标的绝对值$<=10^8$。

分析：两个队友积分积了一下午，，tqllll。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int main()
 5 {
 6     ll x1,y1,x2,y2,x3,y3;
 7     while (~scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3))
 8     {
 9         ll S=abs(x1*y2+y1*x3+x2*y3-y2*x3-y3*x1-y1*x2);//没除2
10         // cout<<S<<endl;
11         printf("%lld
",(ll)S*11);
12     }
13     return 0;
14 }

H.XOR

题解传送：https://www.cnblogs.com/changer-qyz/p/11349296.html

J.Fraction Comparision

传送：https://ac.nowcoder.com/acm/contest/881/J

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

数据范围：$0<=x,y<=10^18$，$1<=a,b<=10^9$。

 1 import java.io.*;
 2 import java.util.*;
 3 import java.math.*;
 4 public class main {
 5 
 6     public static void main(String[] args) {
 7         Scanner cin=new Scanner(System.in);
 8         BigInteger x,y,a,b;
 9         while (cin.hasNext()) {
10             x=cin.nextBigInteger();y=cin.nextBigInteger();
11             a=cin.nextBigInteger();b=cin.nextBigInteger();
12             BigInteger tmp1,tmp2;
13             tmp1=x.multiply(b);tmp2=y.multiply(a);
14             int ans=tmp1.compareTo(tmp2);
15             if (ans==-1) System.out.println("<");
16             else if (ans==0) System.out.println("=");
17             else System.out.println(">");
18         }
19         
20     }
21 
22 }