牛客练习赛46

题目描述

奕奕的几何很差，然而奕奕并不承认，所以华华扔给奕奕一道题目。如图：

已知大半圆的半径等于两个小半圆半径之和。若给出红色部分的面积，那么大圆的半径最小是多少呢？反正奕奕是不会的，所以现在请你回答。

输入描述:

输入一个正整数s表示红色部分的面积。 1<=s<=1e9

输出描述:

输出一个小数表示大圆的最小半径，保留三位小数

示例1

输入

复制

2

输出

复制

1.596

示例2

输入

复制

3

输出

复制

1.954

设大半圆半径为r,两个小半圆的半径为r1,r2。

则有：2*s=π*(r*r-r1*r1-r2*r2) ①

r=r1+r2 ②

两式联立得r=r1+s/(π*r1)

可以把r1看作自变量，r看作因变量，对r1求导，即可得r的最小值。

#include <iostream>
#include <cstdio>
#include <cmath>
#define pi 3.141592654
using namespace std ;

int main(){
  int s ;
  cin >> s ;
  double ans =sqrt((4.0*s)/pi ) ;
  printf("%.3f",ans);
  return 0 ;
}

链接：​​https://ac.nowcoder.com/acm/contest/894/B​​​ 来源：牛客网
 

题目描述

华华用数组a和数组b合成了矩阵c。其中a数组长度为n，b数组长度为m，c是n行m列的矩阵，且c[i][j]=a[i]*b[j]。定义矩阵的权值为矩阵中所有元素的和。然后他想把矩阵送给奕奕。然而他怕奕奕不喜欢。若矩阵的权值小于L,奕奕会讨厌它，因为奕奕不喜欢太小的数字。若矩阵的权值大于R，奕奕会生气因为奕奕不认识比R大的数字。所以奕奕只喜欢权值大于等于L并且小于等于R的矩阵。还好华华学过acm，他马上想到可以送奕奕一个子矩阵，并且他立马写程序从c矩阵中找出了所有奕奕喜欢的子矩阵。你只需要帮他算算这样的子矩阵有多少个即可。

输入描述:

第一行输入n,m,L,R。 第二行n个数表示a数组 第三行m个数表示b数组 1<=n,m<=1000,1<=L<=R<=1e18 1<=a[i],b[i]<=1e6

输出描述:

输出一个数表示子矩阵的个数

示例1

输入

复制

3 3 3 8 3 2 3 2 3 1

输出

复制

10

B:

设sum_a为a的前缀和，sum_b为b的前缀和。则以(x1,y1)为左上角，以(x2,y2)为右下角的矩阵的权值为(sum_a[x2]-sum_a[x1-1])*(sum_b[y2]-sum_b[y1-1])，其中要满足x1<=x2,y1<=y2。x1,x2的选择与y1,y2的选择相互独立。可以预处理所有y1,y2的组合，然后排序。接下来枚举x1,x2，对y二分即可。复杂度n^2*log(m^2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#pragma GCC optimize(2)
#include <cmath>
#define pi 3.141592654
using namespace std ;
const int MAX = 1005 ;
typedef long long LL ;
int n , m , len ;
int a[MAX]  ,b[MAX] ;
int c[MAX*MAX] ;
LL work(LL limit){
    LL id = 0 ;
    int l = 1 ,r =len ;
    while(l<=r){
        int mid = (l+r)/2 ;
        if(c[mid] <=limit) {
            id = mid ;
            l = mid + 1 ;
        }
        else
            r = mid -1 ;
    }
    return id ;
}
LL cal(LL limit){
    LL ans = 0 ;
    for(int i = 1 ; i<=n ; i++ ) {
        for(int j =1 ; j<=i ; j++ ) {
            LL x = a[i] - a[j-1] ;
        
            ans +=work(limit/x) ;
        }

    }
    return ans ;
}
int main()
{
    LL L ,R;
    scanf("%d%d%lld%lld",&n,&m,&L,&R);
    for(int i = 1 ; i<=n ; i++ ) {
        int x ;
        cin >>x ;
        a[i]=a[i-1]+x ;
    }
    for(int i = 1 ; i<=m ; i++){
        int x ;
        cin >>x ;
        b[i] = b[i-1]+x ;
        for(int j = 1 ;j<=i; j++ ) {
            c[++len] = b[i]-b[j-1] ;
        }
    }
    sort(c+1,c+1+len) ;
//  for(int i = 1 ; i<=len ; i++ )cout<<c[i]<<" " ;
//  cout<<endl;
//  cout<<cal(R) <<endl ;
//  cout<<cal(L-1) <<endl ;
    printf("%lld\n",cal(R)-cal(L-1)) ;
    return 0;
}