CQUPT 训练题 2017/4/10

题解

题目链接：https://vjudge.net/contest/158057

B - Points in Segments

题目大意

存在长度为 n 的一个整型数组，求出在区间[a, b]中的整数个数

Input

先输入实例组数 T (≤ 5), 下一行再输入数组长度 n (1 ≤ n ≤ 105) 和询问次数 q (1 ≤ q ≤ 50000)，接下来的 q 行输入 a 和 b ，所有整数都在 [0, 10^8]区间内

Output

每一组开头输出 case 数和在区间[a, b]中的整数个数

Sample Input

1
5 3
1 4 6 8 10
0 5
6 10
7 100000

Sample Output

Case 1: 
2
3
2

解题思路

**二分查找**

代码

#include <cstdio>
#include <vector>
#include <algorithm>
#define N 100000
using namespace std;
int main()
{
    int i, T;
    scanf("%d", &T);
    for(i=1;i<=T;i++)
    {
        int n, q, j, a, b;
        scanf("%d %d", &n, &q);
        vector <int> num(n);
        for(j=0;j<n;j++)
        {
            scanf("%d", &num[j]);
        }
        sort(num.begin(), num.end());
        printf("Case %d:\n", i);
        for(j=0;j<q;j++)
        {
            vector <int> ::iterator a_pos, b_pos;
            scanf("%d %d", &a, &b);
            a_pos = lower_bound(num.begin(), num.end(), a);
            b_pos = upper_bound(num.begin(), num.end(), b);
            printf("%d\n", b_pos-a_pos);
        }
    }
    return 0;
}

该题收获

1. 了解到 STL 中的 lower_bound 和 upper_bound 可以用来进行二分查找并了解到其中的区别
2. 深刻领悟到 STL 确实很方便

C - Calm Down

题目大意

在一个半径为 R 的圆中内接 n 个小圆，求出小圆半径

Input

先输入 T (≤ 125), 再输入T组数据，每一行包含 R (0 < R < 1000)和 n (2 ≤ n ≤ 100)

Output

每一行输出 case 数和 r ，在10^-6之内的误差可被忽略

Sample Input

4
4.0 6
4.0 17
3.14 100
42 2

Sample Output

Case 1: 1.3333333333
Case 2: 0.6209067545
Case 3: 0.0956260953
Case 4: 21

解题思路

   按要求平分圆，得到扇形面积和内接圆半径的关系

代码

#include <cstdio>
#include <math.h>
#define pi 3.1415926536
using namespace std;
int main()
{
    int i, T;
    scanf("%d", &T);
    for(i=1;i<=T;i++)
    {
        double R, r;
        int n;
        scanf("%lf %d", &R, &n);
        r = R*sin(180.0/n/180.0*pi)/(1+sin(180.0/n/180.0*pi));
        if(r-(int)r<0.000001)
        {
            printf("Case %d: %d\n", i, (int)r);
        }
        else
        {
            printf("Case %d: %.10lf\n", i, r);
        }
    }
    return 0;
}

该题收获

1. 三角函数的使用要用弧度制,从<math.h>中直接使用
2. 一般来说 π 保留十位小数，即3.141592654便足以应付一般计算，但是这道题中需要在再上一位才能达到输出实例的结果
3. double类型只保留6位有效数字，但只要%.nlf即可以保留n位有效数字，这里的n可以大于6
4. 扇形的内接圆和扇形的关系： r=(Rsinα/2)/(1+sinα/2)