# 2019 牛客多校第一场

## Equivalent Prefixes

64bit IO Format: %lld

#### 题目描述

Two arrays u and v each with m distinct elements are called equivalent if and only if \mathrm{RMQ}(u, l, r) = \mathrm{RMQ}(v, l, r)RMQ(u,l,r)=RMQ(v,l,r) for all 1 \leq l \leq r \leq m1≤lrm
where \mathrm{RMQ}(w, l, r)RMQ(w,l,r) denotes the index of the minimum element among w_l, w_{l + 1}, \dots, w_{r}wl​,wl+1​,…,wr​.
Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number p \leq npn where \{a_1, a_2, \dots, a_p\}{a1​,a2​,…,ap​} and \{b_1, b_2, \dots, b_p\}{b1​,b2​,…,bp​} are equivalent.

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers a_1, a_2, \dots, a_na1​,a2​,…,an​.
The third line contains n integers b_1, b_2, \dots, b_nb1​,b2​,…,bn​.

* 1 \leq n \leq 10^51≤n≤105
* 1 \leq a_i, b_i \leq n1≤ai​,bi​≤n
* \{a_1, a_2, \dots, a_n\}{a1​,a2​,…,an​} are distinct.
* \{b_1, b_2, \dots, b_n\}{b1​,b2​,…,bn​} are distinct.
* The sum of n does not exceed 5 \times 10^55×105.

#### 输出描述:

For each test case, print an integer which denotes the result.

2
1 2
2 1
3
2 1 3
3 1 2
5
3 1 5 2 4
5 2 4 3 1

1
3
4

#### 树状数组乱搞一下，还挺简单的

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,a[maxn],b[maxn],c[2][maxn];
int id[2][maxn];
int lowbit(int x){return x & (-x);}
while(x<maxn){
x+=lowbit(x);
}
}
int getsum(int x,int op){
int ret=0;
while(x!=0){
ret=max(ret,c[op][x]);
x-=lowbit(x);
}
return ret;
}
void solve(){
rep(i,1,n) c[0][i]=c[1][i]=0;
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n) scanf("%d",&b[i]);
int ans=1;
modify(a[1],1,0);modify(b[1],1,1);
rep(i,2,n){
if(getsum(a[i]-1,0)==getsum(b[i]-1,1)){
modify(a[i],i,0);modify(b[i],i,1);
ans=i;
}
else break;
}
printf("%d\n",ans);
}
int main(){
while(~scanf("%d",&n)) solve();
}

## Integration

64bit IO Format: %lld

#### 题目描述

Bobo knows that \int_{0}^{\infty} \frac{1}{1 + x^2}\ \mathrm{d}x = \frac{\pi}{2}.∫0∞​1+x21​ dx=2π​.

Given n distinct positive integers a_1, a_2, \dots, a_na1​,a2​,…,an​, find the value of
\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x.π1​∫0∞​∏i=1n​(ai2​+x2)1​ dx.

It can be proved that the value is a rational number \frac{p}{q}qp​.
Print the result as (p \cdot q^{-1}) \bmod (10^9+7)(pq−1)mod(109+7).

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers a_1, a_2, \dots, a_na1​,a2​,…,an​.

* 1 \leq n \leq 10^31≤n≤103
* 1 \leq a_i \leq 10^91≤ai​≤109
* \{a_1, a_2, \dots, a_n\}{a1​,a2​,…,an​} are distinct.
* The sum of n^2n2 does not exceed 10^7107.

#### 输出描述:

For each test case, print an integer which denotes the result.

1
1
1
2
2
1 2

500000004
250000002
83333334

#### 数论题，队友写的，贴一下他的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll md=1e9+7;
ll qp(ll a,ll b=md-2){
ll ret=1;
while(b){
if(b&1) ret=(ret*a)%md;
a=(a*a)%md;
b>>=1;
}
return ret;
}
ll a[1050];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
ll ans=0;
for(int i=1;i<=n;i++){
//ll a;
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
ll cnt=a[i];
for(int j=1;j<=n;j++){
if(i==j) continue;
cnt=(cnt*(a[j]*a[j]%md-a[i]*a[i]%md+md)%md)%md;
}
ans=(ans+qp(cnt))%md;
}
printf("%lld\n",ans*qp(2)%md);
}

return 0;
}

## Euclidean Distance

64bit IO Format: %lld

#### 题目描述

Bobo has a point A in the n dimension real space \mathbb{R}^nRn, whose coodinate is (a_1 / m, a_2 / m, \dots, a_n / m)(a1​/m,a2​/m,…,an​/m) where a_iai​ and m are both integers. He wants to find another point P = (p_1, p_2, \dots, p_n)P=(p1​,p2​,…,pn​) meeting the following requirements.

* p_1, p_2, \dots, p_n \in \mathbb{R}p1​,p2​,…,pn​∈R. That is, they are real numbers.
* p_1, p_2, \dots, p_n \geq 0p1​,p2​,…,pn​≥0
* p_1 + p_2 + \dots + p_n = 1p1​+p2​+⋯+pn​=1
* The (squared) Euclidean distance between P and A, which is \|A - P\|_2^2 = \sum_{i = 1}^n (a_i / m - p_i)^2∥AP∥22​=∑i=1n​(ai​/mpi​)2, is minimized.

It can be proved the minimum is always a rational number. Print the squared distance in fraction. Note to print an integer n as n instead of n/1.

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers n and m.
The second line contains n integers a_1, a_2, \dots, a_na1​,a2​,…,an​.

* 1 \leq n \leq 10^41≤n≤104
* 1 \leq m \leq 10^31≤m≤103
* -m \leq a_i \leq m−mai​≤m
* The sum of n does not exceed 5 \times 10^55×105.

#### 输出描述:

For each test case, print a fraction which denotes the result.

1 1
0
2 3
1 2
3 10
1 -2 3

1
0
16/75

#### 还是数论题，还是队友写的，还是贴一下他的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10100];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int cmp(const ll& x,const ll& y){
return x>y;
}
ll pre[10100];
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1,cmp);
pre[1]=0;
int ub=n;
for(int i=2;i<=n;i++){
pre[i]=pre[i-1]+1ll*(i-1)*(a[i-1]-a[i]);
}
int lb=1;
int ans=1;
while(ub>=lb){
int md=(ub+lb)>>1;
if(pre[md]<=m){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
ll z=0;
for(int i=ans+1;i<=n;i++){
z+=a[i]*a[i];
}
ll dom=ans*ans;
z*=dom;
z+=(ans*a[ans]-(m-pre[ans]))*(ans*a[ans]-(m-pre[ans]))*ans;
if(z==0){
printf("0\n");
continue;
}
dom*=m*m;
ll g=gcd(dom,z);
dom/=g;
z/=g;
if(dom==1){
printf("%lld\n",z);
}
else{
printf("%lld/%lld\n",z,dom);
}
}
return 0;
}

## ABBA

64bit IO Format: %lld

#### 题目描述

Bobo has a string of length 2(n + m) which consists of characters A and B. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are AB while other m of them are BA.

Given n and m, find the number of possible strings modulo (10^9+7)(109+7).

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

Each test case contains two integers n and m.

* 0 \leq n, m \leq 10^30≤n,m≤103
* There are at most 2019 test cases, and at most 20 of them has \max\{n, m\} > 50max{n,m}>50.

#### 输出描述:

For each test case, print an integer which denotes the result.

1 2
1000 1000
0 0

13
436240410
1

#### 考虑判定给定串 S 是否能够由 n 个 AB 和 m 个 BA 构成贪心，A 肯定是先用 AB 的 A，再用 BA 的 A；B 同理DP 设 f(x, y) 是有 x 个 A，y 个 B 的前缀方案数转移枚举下一个字符是 A 还是 B• 通过 x, y, n, m 可以知道剩余的 AB，BA，B 和 A 的数量

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m;
ll dp[2010][2010];
void solve(){
rep(i,0,n+m) rep(j,0,n+m) dp[i][j]=0;
dp[0][0]=1;
rep(i,0,n+m) rep(j,0,n+m){
}
printf("%lld\n",dp[n+m][n+m]);
}
int main(){
while(~scanf("%d%d",&n,&m)) solve();
}

## Random Point in Triangle

64bit IO Format: %lld

#### 题目描述

Bobo has a triangle ABC with A(x1,y1),B(x2,y2)A(x_1, y_1), B(x_2, y_2)A(x1​,y1​),B(x2​,y2​) and C(x3,y3)C(x_3, y_3)C(x3​,y3​). Picking a point P uniformly in triangle ABC, he wants to know the expectation value E=max⁡{SPAB,SPBC,SPCA}E = \max\{S_{PAB}, S_{PBC}, S_{PCA}\}E=max{SPAB​,SPBC​,SPCA​} where SXYZS_{XYZ}SXYZ​ denotes the area of triangle XYZ.

Print the value of 36×E36 \times E36×E. It can be proved that it is always an integer.

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

Each test case contains six integers x1,y1,x2,y2,x3,y3x_1, y_1, x_2, y_2, x_3, y_3x1​,y1​,x2​,y2​,x3​,y3​.

* ∣x1∣,∣y1∣,∣x2∣,∣y2∣,∣x3∣,∣y3∣≤108|x_1|, |y_1|, |x_2|, |y_2|, |x_3|, |y_3| \leq 10^8∣x1​∣,∣y1​∣,∣x2​∣,∣y2​∣,∣x3​∣,∣y3​∣≤108
* There are at most 10510^5105 test cases.

#### 输出描述:

For each test case, print an integer which denotes the result.

0 0 1 1 2 2
0 0 0 0 1 1
0 0 0 0 0 0

## 输出

0
0
0

#### 答案是 11/2 倍三角形 ABC 的面积

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll xx1,xx2,xx3,yy1,yy2,yy3;
int main(){
while(scanf("%lld%lld%lld%lld%lld%lld",&xx1,&yy1,&xx2,&yy2,&xx3,&yy3)!=EOF){
ll vx1=xx2-xx1,vx2=xx3-xx1,vy1=yy2-yy1,vy2=yy3-yy1;
ll s=abs(vx1*vy2-vx2*vy1);
printf("%lld\n",s*11);
}
return 0;
}

## Points Division

64bit IO Format: %lld

#### 题目描述

Bobo has a set P of n distinct points (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)(x1​,y1​),(x2​,y2​),…,(xn​,yn​).
The i-th point has two weights a_iai​ and b_ibi​.
He wants to partition the points into two sets A and B (That is, A \cup B = PAB=P and A \cap B = \emptysetAB=∅.
A partition (A, B) is valid if and only if there exists no i \in AiA and j \in BjB where x_i \geq x_jxi​≥xj​ and y_i \leq y_jyi​≤yj​.
Find the maximum of \left(\sum_{i \in A} a_i \right) + \left(\sum_{j \in B} b_j\right)(∑iAai​)+(∑jBbj​) among all valid partitions (A, B).

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test cases contains an integer n.
The i-th of the following n lines contains four integers x_i, y_i, a_i, b_ixi​,yi​,ai​,bi​.

* 1 \leq n \leq 10^51≤n≤105
* 1 \leq x_i, y_i, a_i, b_i \leq 10^91≤xi​,yi​,ai​,bi​≤109
* (x_i, y_i) \neq (x_j, y_j)(xi​,yi​)​=(xj​,yj​) for all i \neq ji​=j
* The sum of n does not exceed 5 \times 10^55×105.

#### 输出描述:

For each test case, print an integer which denotes the result.

2
1 2 1 9
2 1 9 1
1
1 1 2 3
4
1 1 1 5
1 2 2 6
2 1 3 7
2 2 4 8

10
3
26

#### 设 dp(i) 是点 i 在折线上的最大值，枚举上一个点 j对于所有 xj < xk < xi 且 yj > yk，都在折线下方• 线段树维护每个决策点 j 当前的代价 O(n log n)

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define lson rt<<1
#define rson rt<<1|1
#define delf int m=(l+r)>>1;
typedef long long ll;
const int maxn=(int)1e5+100;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;
struct node{
ll a,b,x,y;
}a[maxn];
ll h[maxn];
struct seg{
ll mx,lazy;
}tree[maxn<<2];
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
return a.y>b.y;
}
void build(int l,int r,int rt){
tree[rt].mx=0;
tree[rt].lazy=0;
if(l==r)return;
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
}
void pushdown(int rt){
if(tree[rt].lazy!=0){
tree[lson].mx+=tree[rt].lazy;
tree[lson].lazy+=tree[rt].lazy;
tree[rson].mx+=tree[rt].lazy;
tree[rson].lazy+=tree[rt].lazy;
tree[rt].lazy=0;
}
}
void pushup(int rt){
tree[rt].mx=max(tree[lson].mx,tree[rson].mx);
}
void update(int rt,int l,int r,int ql,int qr,ll v){
if(l>=ql&&r<=qr){
tree[rt].lazy+=v;
tree[rt].mx+=v;
return;
}
pushdown(rt); delf;
if(m>=ql)update(lson,l,m,ql,qr,v);
if(m<qr)update(rson,m+1,r,ql,qr,v);
pushup(rt);
}
void update2(int rt,int l,int r,int pos,ll v){
if(l==r){
tree[rt].mx=max(tree[rt].mx,v);
return;
}
pushdown(rt); delf;
if(pos<=m)update2(lson,l,m,pos,v);
else update2(rson,m+1,r,pos,v);
pushup(rt);
}
ll query(int rt,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){
return tree[rt].mx;
}
pushdown(rt);delf;
ll res=0;
if(ql<=m)res=max(res,query(lson,l,m,ql,qr));
if(qr>m)res=max(res,query(rson,m+1,r,ql,qr));
return res;
}
int main(){
while(~scanf("%d",&n)){
m=0;
h[++m]=-inf;
h[++m]=inf;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
h[++m]=a[i].y;
}
sort(a+1,a+n+1,cmp);
sort(h+1,h+m+1);
m=unique(h+1,h+m+1)-h-1;
for(int i=1;i<=n;i++) a[i].y=lower_bound(h+1,h+m+1,a[i].y)-h;
build(1,m,1);
for(int i=1;i<=n;i++){
ll g=query(1,1,m,1,a[i].y);
update2(1,1,m,a[i].y,g+a[i].b);
update(1,1,m,a[i].y+1,m,a[i].b);
update(1,1,m,1,a[i].y-1,a[i].a);
}
printf("%lld\n",tree[1].mx);
}
}

## Fraction Comparision

64bit IO Format: %lld

#### 题目描述

Bobo has two fractions \frac{x}{a}ax​ and \frac{y}{b}by​. He wants to compare them. Find the result.

#### 输入描述:

The input consists of several test cases and is terminated by end-of-file.

Each test case contains four integers x, a, y, b.

* 0 \leq x, y \leq 10^{18}0≤x,y≤1018
* 1 \leq a, b \leq 10^91≤a,b≤109
* There are at most 10^5105 test cases.

#### 输出描述:

For each test case, print = if \frac{x}{a} = \frac{y}{b}ax​=by​. Print < if \frac{x}{a} < \frac{y}{b}ax​<by​. Print > otherwise.

1 2 1 1
1 1 1 2
1 1 1 1

<
>
=

#### 签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
struct bign{
ll d[2000];
int len;
bign(){
memset(d,0,sizeof(d));
len=0;
}
};
bign change(char str[]){
bign a;
a.len=strlen(str);
for(int i=0;i<a.len;i++){
a.d[i]=str[a.len-i-1]-'0';
}
return a;
}
int compare(bign a,bign b){
if(a.len>b.len)return 1;//a大于b
else if(a.len<b.len)return -1;//a<b
else{
for(int i=a.len-1;i>=0;i--){
if(a.d[i]>b.d[i])return 1;
else if(a.d[i]<b.d[i])return -1;
}
return 0;//两个数相等
}
}
bign multi(bign a,ll b){
bign c;
ll carry=0;
for(int i=0;i<a.len;i++){
ll temp=a.d[i]*b+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
while(carry!=0){
c.d[c.len++]=carry%10;
carry/=10;
}
return c;
}
void print(bign a){
for(int i=a.len-1;i>=0;i--){
printf("%d",a.d[i]);
}
}
int main(){
char str1[1000],str2[1000];
ll aa,bb;
while(~scanf("%s%lld%s%lld",str1,&aa,str2,&bb)){
bign x=change(str1);
bign y=change(str2);
bign e=multi(x,bb);
bign f=multi(y,aa);
if(compare(e,f)==1) printf(">\n");
else if(compare(e,f)==-1) printf("<\n");
else printf("=\n");
}
return 0;
}

0 评论