2019 牛客多校第一场

由 Edwiv 发布于  ｜  50,426次浏览

Equivalent Prefixes

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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≤l≤r≤m
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 np≤n 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.

示例1

输入

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);}
void modify(int x,int add,int op){
    while(x<maxn){
        c[op][x]=max(c[op][x],add);
        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

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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)(p⋅q−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
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

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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∥A−P∥22​=∑i=1n​(ai​/m−pi​)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−m≤ai​≤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 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

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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

输入

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 add(ll &x,ll y){x=(x+y)%mod;}
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){
		if((i<=n||i-j<=n)&&i) add(dp[i][j],dp[i-1][j]);
		if((j<=m||j-i<=m)&&j) add(dp[i][j],dp[i][j-1]);
	}
	printf("%lld\n",dp[n+m][n+m]);
}
int main(){
	while(~scanf("%d%d",&n,&m)) solve();
}

Random Point in Triangle

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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.

示例1

输入

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

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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 = PA∪B=P and A \cap B = \emptysetA∩B=∅. 
A partition (A, B) is valid if and only if there exists no i \in Ai∈A and j \in Bj∈B 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)(∑i∈A​ai​)+(∑j∈B​bj​) 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.

示例1

输入

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

一定存在一条 xy 单调不降的折线把点集划分为 AB 两个部分，不妨假设折线贴着集合 B

设 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

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
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

输入

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 评论
内联反馈
查看所有评论