BIT历年真是神人辈出，这些题目很有技巧性。 比如NH-02. 【选做题】Having a lunch

NH-02. 【选做题】Having a lunch

题目描述：

​ 聪明的你轻松的解开了门口的密码锁，打开了门锁，可是大门被一群饥饿的小朋友堵住的，善良的你并不想靠蛮力打开，于是打算去旁边的食品摊买点巧克力讨好小朋友。食品摊一共有六种巧克力，第一种巧克力只有一个，第二种巧克力有两个，第三种巧克力有三个，第四、五、六种巧克力均有无数个，但是你每次购买的数量必须有所限制：第四种巧克力每次购买的数量必须是1的倍数，第五种巧克力每次购买的数量必须是2的倍数，第六种巧克力每次购买的数量必须是3的倍数。你一共要买N块巧克力，你想知道你一共有多少种不同的购买方案。就算一个N也太简单了，你打算挑战一下一次性算两个。

**输入格式：**一行，两个整数，N1和N2，分别表示两个情况下的N。

**输出格式：**一行，两个用一个空格隔开的整数，分别表示当N=N1，和N=N2时候的答案。

**样例输入：**4 96

**样例输出：**34 18434

**样理解释：**对于N=4，记（a1,a2,a3,a4,a5,a6）表示六种巧克力的购买数量，可以知道，共有方案：

(0,0,0,0,4,0) (0,0,0,1,0,3) (0,0,0,2,2,0) (0,0,0,4,0,0) (0,0,1,0,0,3) (0,0,1,1,2,0) (0,0,1,3,0,0) (0,0,2,0,2,0) (0,0,2,2,0,0) (0,0,3,1,0,0) (0,1,0,0,0,3) (0,1,0,1,2,0) (0,1,0,3,0,0) (0,1,1,0,2,0) (0,1,1,2,0,0) (0,1,2,1,0,0) (0,1,3,0,0,0) (0,2,0,0,2,0) (0,2,0,2,0,0) (0,2,1,1,0,0) (0,2,2,0,0,0) (1,0,0,0,0,3) (1,0,0,1,2,0) (1,0,0,3,0,0) (1,0,1,0,2,0) (1,0,1,2,0,0) (1,0,2,1,0,0) (1,0,3,0,0,0) (1,1,0,0,2,0) (1,1,0,2,0,0) (1,1,1,1,0,0) (1,1,2,0,0,0) (1,2,0,1,0,0) (1,2,1,0,0,0)

**数据范围：**4≤N≤10^9

（买了当然自己也要吃，所以至少买四个！）

——by smzzl

这个题第一眼看上去想搜索，但仔细看看数据范围在1E9就知道这是个时间复杂度为常数的题目。 回看这个问题，第一第二第三种巧克力的数量是确定的，所以根据组合数的结论，我们可以直接计算出这几种情况。

接下来就需要讨论第四第五第六种巧克力，这三种巧克力的数量是无限的。实际上抽象模型就是求a+2b+3c=M的非负整数解个数。 其中a、b、c分别是第四第五第六中巧克力的选择次数。如此我们可以化简公式，求a+2b=M-3c，然后设K=M-3c， 用奇妙的数论方法（丢翻图方程）可以知道，对于任意的一元二次方程ax+by=c的非负整数解个数等于=⌊ c/ab/gcd(a,b) ⌋+1， 所以我们很容易知道对于a+2b=K有（K/2）向下取整+1个非负整数解，那么只需要遍历c，再求和就行。

经过计算，这个数列求和的结果是S=(m+3)^2 + 3 / 12，所以就有如下程序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include<stdio.h>  
#define int long long  
  
int coe[7] = {1,3,5,6,5,3,1};  
int cnt;  
  
int min(int a,int b){  
    return (a > b)? b : a ;  
}  
  
int calculate(int k){  
    return (k / 2) + 1;  
}  
  
int work(int n){  
    int cnt = 0;  
    for(int i = 0 ; i <= min(n , 6) ; ++i){  
        int m = n - i;  
int S =((m+3) *(m+3)+3)/12;;  
  
       cnt += S  * coe[i];  
          
    }  
    return cnt;  
}  
  
signed main(){  
    int n1,n2;  
    scanf("%lld %lld",&n1,&n2);  
    printf("%lld %lld\n",work(n1),work(n2));  
    return 0;  
}  

NH-3. 【选做题】Distribute

题目描述：

巧克力买来了肯定要分发呀，但是你的力气是有限的，你丢出去的糖果只能被距离你小于等于R的小朋友接到。因此你想知道，对于在某一个位置的小朋友，是否能接到你丢出去的糖果。

输入格式：

第一行一个整数T，表示数据组数

接下来T行，每行五个数，x,y,R,x0,y0，表示你的坐标(x,y)，你能丢出去的距离R，某一个小朋友的位置(x0,y0)

输出格式：

T行，每行为YES或NO，第i行表示的是对应第i组的答案。若第i组的小朋友能接到糖果，输出“YES”，否则输出“NO” （均不加引号）

样例输入：

2

0 0 1 1 1

0 0 2 1 0

样例输出：

NO

YES

数据范围：0<R<100000，|x|,|y|,|x0|,|y0|<100000 保证所有数的最多有四位小数

这个题需要注意的是精度问题，如何处理【四位小数】是重点。我们需要知道的是，在计算机中处理小数的难度是远大于整数的， 很容易精度丢失，因为浮点数的构造无法准确的表示很多小数。所以为了解决这个问题，我们先要把小数变成整数，然后在整数的基础上操作。

实际上我们并不真正关心二人的距离，只关心能不能到达，所以不用太在意最后距离的值正不正确。

最后要注意的是，小数乘1000为整数后，也会造成精度丢失，所以为了保持精确，我们一定要对其进行四舍五入，也就是round()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <stdio.h>
#include <math.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        double x, y, R, x0, y0;
        scanf("%lf%lf%lf%lf%lf", &x, &y, &R, &x0, &y0);
        
        // 将各值乘以10000并四舍五入转换为整数，保留四位小数精度
        long long x_int = (long long)round(x * 10000.0);
        long long y_int = (long long)round(y * 10000.0);
        long long R_int = (long long)round(R * 10000.0);
        long long x0_int = (long long)round(x0 * 10000.0);
        long long y0_int = (long long)round(y0 * 10000.0);
        
        // 计算dx和dy
        long long dx = x0_int - x_int;
        long long dy = y0_int - y_int;
        
        // 计算平方距离和R的平方
        long long dis_sq = dx * dx + dy * dy;
        long long R_sq = R_int * R_int;
        
        // 比较并输出结果
        printf(dis_sq <= R_sq ? "YES\n" : "NO\n");
    }
    return 0;
}