随缘补题中我好菜啊QAQ...

A-Equivalent Prefixes

题目链接：https://ac.nowcoder.com/acm/contest/881/A

题目大意：给出两个数组，分别包含n个数字。定义RMQ(u,l,r)=RMQ(v,l,r)是数组u和v在同样的[l,r]区间，最小值的位置是一样的。找到一个P满足所有的1<=l<=r<=P满足RMQ(u,l,r,)=RMQ(v,l,r)；

思路：对于每个数字，找到它在数组中的影响区间（在这个区间内他就是最小的），可用二分找到。然后从1开始，对于每个数字，判断是否能够被选中，要求所覆盖的区间重合，如果覆盖区间不重合，则右边取最小的那个（刷新上界）。直到到达上界位置。

注意些RMQ问题的时候不要用线段树，因为线段树查询longn，也是一笔不小的开支，用ST表就好了。我线段树的T掉了（当然大佬如果用更好的方法能过当我在瞎说）200ms+。

~~文少读题大喘气，给我说了三次题意，WA了6发，哭了。~~

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=998244353;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

class STtable{
	int STmax[MAXN][20],STmin[MAXN][20],mn[MAXN];
	
	public : void IntST(int n,int a[]){
		mn[0]=-1;
		for(int i=1;i<=n;++i){
			mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];
			STmax[i][0]=STmin[i][0]=a[i];
		}
		for(int j=1;j<=mn[n];++j){
			for(int i=1;i+(1<<j)-1<=n;++i){
				STmax[i][j]=max(STmax[i][j-1],STmax[i+(1<<(j-1))][j-1]);
				STmin[i][j]=min(STmin[i][j-1],STmin[i+(1<<(j-1))][j-1]);
			}
		}
	}
	public : int RMQMAX(int l,int r){
		int k=mn[r-l+1];
		return max(STmax[l][k],STmax[r-(1<<k)+1][k]);
	}
	public : int RMQMIN(int l,int r){
		int k=mn[r-l+1];
		return min(STmin[l][k],STmin[r-(1<<k)+1][k]);
	}
};
STtable STA,STB;
int A[MAXN],B[MAXN];
int InterA[MAXN][2],InterB[MAXN][2];
int n,m;

int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;++i) scanf("%d",&A[i]);
		for(int i=1;i<=n;++i) scanf("%d",&B[i]);
		STA.IntST(n,A);STB.IntST(n,B);
		for(int i=1;i<=n;++i){//找到每个点的有效区间 
			int l=1,r=i,mid;
			while(l<=r){//找到最左边的有效区间 
				mid=(l+r)>>1;
				if(STA.RMQMIN(mid,i)==A[i]) r=mid-1;
				else l=mid+1;
			}InterA[i][0]=l;
			l=i,r=n;
			while(l<=r){//找最右边的有效区间 
				mid=(l+r)>>1;
				if(STA.RMQMIN(i,mid)==A[i]) l=mid+1;
				else r=mid-1;
			}InterA[i][1]=r;
		}
		for(int i=1;i<=n;++i){//找到每个点的有效区间 
			int l=1,r=i,mid;
			while(l<=r){//找到最左边的有效区间 
				mid=(l+r)>>1;
				if(STB.RMQMIN(mid,i)==B[i]) r=mid-1;
				else l=mid+1;
			}InterB[i][0]=l;
			l=i,r=n;
			while(l<=r){//找最右边的有效区间 
				mid=(l+r)>>1;
				if(STB.RMQMIN(i,mid)==B[i]) l=mid+1;
				else r=mid-1;
			}InterB[i][1]=r;
		}
//		printf("A:");for(int i=1;i<=n;++i) printf("i=%d l=%d r=%d\n",i,InterA[i][0],InterA[i][1]);
//		printf("B:");for(int i=1;i<=n;++i) printf("i=%d l=%d r=%d\n",i,InterB[i][0],InterB[i][1]);
		int maxr=n,p=1;
		for(int i=1;i<=n;++i){
			if(InterA[i][0]==InterB[i][0]){
				int tempr;
				if(InterA[i][1]==InterB[i][1]){//符合区间 
					p=i;
				}
				else{
					tempr=min(InterA[i][1],InterB[i][1]);
					if(tempr>maxr) break;
					else maxr=tempr;
				}p=i;
			}
			else break;
		}printf("%d\n",p);
	}
}

B-Integration

题目链接：https://ac.nowcoder.com/acm/contest/881/B

题目大意：给出一个公式，求另一个公式。

思路：由给出的公式求出单项的答案后，手写n=2,3,4化简找规律。

下面给出步骤：

得出单独的一项：

对于拆开。举特例：

当n=2时：

原式==（裂项相消）

前面的对后面的式子没有影响，忽略掉：

当n=3时：

原式==(裂项相消)

比较n=3和n=2容易发现通项公式：

带入上面得到的单项式子：

然后就是n^2跑答案了。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

ll A[MAXN];
int n;

ll Inv(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1) res=res*a%MOD;
		a=a*a%MOD;
		n>>=1;
	}return res;
}
int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;++i){
			scanf("%lld",&A[i]);
		}
		ll Ans=0;
		for(int i=1;i<=n;++i){
			ll Res=2*A[i];
			for(int j=1;j<=n;++j){
				if(j==i) continue;
				Res=Res*(A[j]*A[j]%MOD-A[i]*A[i]%MOD+MOD)%MOD;
			}
			Ans=(Ans+Inv(Res,MOD-2))%MOD;
		}
		printf("%lld\n",Ans);
	}
}

E-ABBA

题目链接：https://ac.nowcoder.com/acm/contest/881/E

题目大意：给出2(n+m)长度的字符串，问能有多少种方法构成n个AB和m个BA。

思路：前缀和+DP（文少牛逼）文少上来就A掉了这道题：https://blog.csdn.net/henu_1710252529/article/details/96467385

ACCode：文少的代码，在他博客里。

F-Random Point in Triangle

题目链接：https://ac.nowcoder.com/acm/contest/881/F

题目大意：给出三个点，找出三点组成三角形内一点p满足E的期望：36*E。

思路：可以猜出来的。但是既然写出了博客，那就证明出来吧：

由于求最大的三角形的面积。因为三角形在重心处三个面积相等。那么我们只考虑一个就好了。

首先直到一个概念：三角形的E(h)=重心。高的期望是重心所在的位置.

设三角形的高为h。

看图，三角形PBC在p在深绿***域内是满足最大面积的。所以P{P落在ADE范围内}:P{P落在ODE范围内}=3:1（易证）。

所以E(SPBC(DE上))=1/2BC(2/3h)；E(SPBC(DE下))=1/2BC(1\2h-1/2 *1/3 *1/3h)=1/2BC(4/9h)

所以：E(SPBC)=3/4 * 1/3BCh+1/4 * 2/9BCh=11/36BCh=11/36 * 2*SPBC.

因此直接输出11*（BC叉乘BA）即可。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=998244353;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

struct Point{
	ll x,y;
	Point(ll _x=0,ll _y=0){
		x=_x;y=_y;
	}
	friend Point operator + (Point a,Point b){
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator * (ll x,Point a){
		return Point(x*a.x,x*a.y);
	}
	friend ll operator ^ (Point a,Point b){
		return abs(a.x*b.y-a.y*b.x);
	}
	friend Point operator - (Point a,Point b){
		return Point(a.x-b.x,a.y-b.y);
	}
};

int main(){
	Point A,B,C;
	while(~scanf("%lld%lld%lld%lld%lld%lld",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y)){
		ll S=((B-A)^(C-A));
		if(S==0){
			printf("0\n");
			continue;
		}
		printf("%lld\n",S*11);
	}
}

J-Fraction Comparision

题目链接：https://ac.nowcoder.com/acm/contest/881/J

题目大意：给出四个数，比较他们的大小。

思路：Java大数牛逼！文少上去秒A。

ACCode：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in =new Scanner(System.in);
        String x1;
        while(in.hasNext()){
            x1=in.next();
            BigInteger x=new BigInteger(x1);
            x1=in.next();
            BigInteger a=new BigInteger(x1);
            x1=in.next();
            BigInteger y=new BigInteger(x1);
            x1=in.next();
            BigInteger b=new BigInteger(x1);
            x=x.multiply(b);
            y=y.multiply(a);
            if(x.compareTo(y)==0){
                System.out.println("=");
            }else if(x.compareTo(y)==1){
                System.out.println(">");
            }else if(x.compareTo(y)==-1){
                System.out.println("<");
            }
        }
    }
}

2019牛客多校第一场 A，B，E，F，J

A-Equivalent Prefixes

B-Integration

E-ABBA

F-Random Point in Triangle

J-Fraction Comparision